Parallel block-delayed sequences
Parallel block-delayed sequences
复制标题
并行块延迟序列
DOI：
10.1145/3503221.3508434
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Blelloch, Guy E.
中科院分区：
文献类型：
--
作者：
Westrick, Sam;Rainey, Mike;Anderson, Daniel;Blelloch, Guy E.
在值集合上使用函数的编程语言，例如map、reduce、scan和filter，已经使用了50多年。这样的集合在并行性的上下文中被证明是特别有用的，因为这样的函数自然是并行的。但是，如果简单地实现它们，则会导致生成临时中间集合，这会显著增加内存使用和运行时间。为了避免这个缺陷，许多方法使用“融合”来组合联合收割机操作，避免临时结果。然而，大多数这些方法都涉及到编译器的重大变化，并限于一小部分功能，如地图和reduces.In本文中，我们提出了一个基于库的方法，融合广泛使用的操作，如扫描，过滤器，和过滤器。结合现有的技术，它涵盖了集合上的大多数常见操作。我们的方法是基于一种新的技术，并行块，每个块内的流。我们通过在两种语言中实现针对多核并行的库来演示这种方法：并行ML和C++，它们具有非常不同的语义和编译器。为了帮助用户理解何时使用该方法，我们定义了一个成本语义，指示何时发生融合以及它如何减少内存分配。我们提出了十几个基准测试的实验结果，证明在时间和空间上都有显着的减少。在大多数情况下，这种方法生成的代码对于它所运行的机器来说接近最优。
Programming languages using functions on collections of values, such as map, reduce, scan and filter, have been used for over fifty years. Such collections have proven to be particularly useful in the context of parallelism because such functions are naturally parallel. However, if implemented naively they lead to the generation of temporary intermediate collections that can significantly increase memory usage and runtime. To avoid this pitfall, many approaches use "fusion" to combine operations and avoid temporary results. However, most of these approaches involve significant changes to a compiler and are limited to a small set of functions, such as maps and reduces.In this paper we present a library-based approach that fuses widely used operations such as scans, filters, and flattens. In conjunction with existing techniques, this covers most of the common operations on collections. Our approach is based on a novel technique which parallelizes over blocks, with streams within each block. We demonstrate the approach by implementing libraries targeting multicore parallelism in two languages: Parallel ML and C++, which have very different semantics and compilers. To help users understand when to use the approach, we define a cost semantics that indicates when fusion occurs and how it reduces memory allocations. We present experimental results for a dozen benchmarks that demonstrate significant reductions in both time and space. In most cases the approach generates code that is near optimal for the machines it is running on.
登录
查看更多内容
优化纯函数式 GPU 程序
DOI：
10.1145/2500365.2500595
发表时间：
2013
期刊：
Proceedings of the 18th ACM SIGPLAN international conference on Functional programming
影响因子：
--
作者：
T. L. McDonell
通讯作者：
T. L. McDonell
扫描向量计算机的基元
DOI：
10.1109/superc.1990.130084
发表时间：
1990
期刊：
Proceedings SUPERCOMPUTING '90
影响因子：
--
作者：
S. Chatterjee;G. Blelloch;M. Zagha
通讯作者：
M. Zagha
Haskell 中的规则、形状多态、并行数组
DOI：
10.1145/1863543.1863582
发表时间：
2010
期刊：
Proceedings of the 18th ACM SIGPLAN international conference on Functional programming
影响因子：
--
作者：
G. Keller;M. Chakravarty;Roman Leshchinskiy;S. Jones;B. Lippmeier
通讯作者：
B. Lippmeier
影响因子：
22.7
作者：
G. Mainland;Roman Leshchinskiy;S. Jones
通讯作者：
S. Jones
DOI：
10.1145/800017.800539
发表时间：
1984
期刊：
Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages
影响因子：
--
作者：
J. Warren
通讯作者：
J. Warren