Efficient tree-traversals: reconciling parallelism and dense data representations
Efficient tree-traversals: reconciling parallelism and dense data representations
复制标题
高效的树遍历：协调并行性和密集数据表示
DOI：
10.1145/3473596
复制
发表时间：
2021
影响因子：
--
通讯作者：
Newton, Ryan R.
中科院分区：
文献类型：
--
作者：
Koparkar, Chaitanya;Rainey, Mike;Vollmer, Michael;Kulkarni, Milind;Newton, Ryan R.
最近的工作表明，编译函数程序以使用递归代数数据类型的密集、序列化内存表示可以为顺序程序带来显着的常数因子加速。但以最大密集格式序列化数据会导致数据处理的序列化，从而在密度和并行性之间产生紧张关系。本文表明，有纪律的、实际的妥协是可能的。我们推出了 Parallel Gibbon，这是一种具有密集数据格式和并行性优势的编译器。我们形式化了支撑这种新颖实现策略的并行位置演算的语义，并表明它是类型安全的。对于使用递归代数数据类型的纯函数程序，并行 Gibbon 超过了现有编译器的并行性能，尤其包括编译器中的抽象语法树遍历。
Recent work showed that compiling functional programs to use dense, serialized memory representations for recursive algebraic datatypes can yield significant constant-factor speedups for sequential programs. But serializing data in a maximally dense format consequently serializes the processing of that data, yielding a tension between density and parallelism. This paper shows that a disciplined, practical compromise is possible. We present Parallel Gibbon, a compiler that obtains the benefits of dense data formats and parallelism. We formalize the semantics of the parallel location calculus underpinning this novel implementation strategy, and show that it is type-safe. Parallel Gibbon exceeds the parallel performance of existing compilers for purely functional programs that use recursive algebraic datatypes, including, notably, abstract-syntax-tree traversals as in compilers.
登录
查看更多内容
压扁树木
DOI：
--
发表时间：
1998
期刊：
European Conference on Parallel Processing
影响因子：
--
作者：
G. Keller;M. Chakravarty
通讯作者：
M. Chakravarty
将并行性改造到 OCaml 上
DOI：
--
发表时间：
2020
期刊：
Proc. ACM Program. Lang.
影响因子：
--
作者：
K. Sivaramakrishnan;Stephen Dolan;Leo White;S. Jaffer;T. Kelly;Anmol Sahoo;S. Parimala;Atul Dhiman;Anil Madhavapeddy
通讯作者：
Anil Madhavapeddy
GPU 执行树遍历的一般转换
DOI：
--
发表时间：
2013
期刊：
2013 SC - International Conference for High Performance Computing, Networking, Storage and Analysis (SC)
影响因子：
--
作者：
Michael Goldfarb;Youngjoon Jo;Milind Kulkarni
通讯作者：
Milind Kulkarni
通过紧凑的范式进行高效的通信和收集
DOI：
--
发表时间：
2015
期刊：
ACM SIGPLAN International Conference on Functional Programming
影响因子：
--
作者：
Edward Z. Yang;Giovanni Campagna;Ömer S. Agacan;Ahmed El;Abhishek Kulkarni;Ryan Newton
通讯作者：
Ryan Newton
将效果处理程序改装到 OCaml 上
DOI：
--
发表时间：
2021
期刊：
ACM-SIGPLAN Symposium on Programming Language Design and Implementation
影响因子：
--
作者：
K. Sivaramakrishnan;Stephen Dolan;Leo White;T. Kelly;S. Jaffer;Anil Madhavapeddy
通讯作者：
Anil Madhavapeddy