Data Parallel Programming for Irregular Tree Computations
Data Parallel Programming for Irregular Tree Computations
复制标题
不规则树计算的数据并行编程
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Wolfram Schulte
中科院分区：
文献类型：
--
作者：
Leo A. Meyerovich;Todd Mytkowicz;Wolfram Schulte
采用数据并行原始图以增加多核算利用率为积极的编译器优化提供了机会。我们尤其是通过树抽象数据类型（ADT）检查的计算。为了比扁平化的方法更好地利用，我们认为转型应该专门用于常见数据和计算规律性。例如，我们演示了一种新型模式，该模式将节点标记中的规律性作为Simd并行性机会，我们称为SimTask并行性。为了更好的适用性，我们主张更好地语言支持不规则性。例如，我们展示了如何使用未来原始的原始性来容忍原本关联的计算中的偶尔数据依赖性。我们在两个树计算上验证了我们的方法：repmin，在功能编程社区中流行，而内在宽度是原型Web浏览器中网页布局的阶段。我们分别显示了这些计算的传统版本的124倍和10倍。
The adoption of data parallel primitives to increase multicore utilization presents an opportunity for aggressive compiler optimization. We examine computations over the tree abstract datatype (ADT) in particular. For better utilization than approaches like flattening, we argue that transformations should specialize for common data and computation regularities. For example, we demonstrate a novel pattern that exploits regularity in node labeling as a SIMD parallelism opportunity, which we call SIMTask parallelism. For better applicability, we argue for better linguistic support of irregularity. For example, we show how the future primitive might be used to tolerate occasional data dependencies in an otherwise associative computation. We validate our approach on two tree computations: RepMin, popular in the functional programming community, and intrinsic widths, a stage of webpage layout in a prototype web browser. We show speedups over traditional versions of these computations of 124X and 10X, respectively.