Parallel functional arrays
Parallel functional arrays
复制标题
并行函数数组
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
R. Harper
中科院分区：
文献类型：
--
作者：
Ananya Kumar;G. Blelloch;R. Harper
本文的目的是开发一种功能阵列（序列）的形式，这些功能阵列（序列）与命令式阵列一样有效，可以并行使用，并具有明确定义的成本范围。关键思想是考虑具有功能价值语义但非功能性成本语义的序列。由于值语义是功能性的，因此“更新”序列返回新序列。我们允许对“较旧”序列（称为内部序列）的操作比“最新”序列（称为叶序列）上的操作更昂贵。我们将序列嵌入了支持叉-Join并行性的语言中。由于平行性，可以非确定性地交织操作，并结合内部和叶片序列的不同成本，这可能会导致程序的非确定性成本。因此，程序成本可能很难分析。主要结果是推导确定性的成本动态，这使得分析成本更加容易。这些定理不是特定于序列的，可以应用于其他数据类型，其成本不同，以在内部和叶子版本上运行。我们提出了序列的候补同时实现，需要持续的工作来访问和更新叶片序列，以及用于访问和线性工作的对数工作，以更新内部序列。我们为序列实现绘制正确性证明。与当前方法相比，当前方法的关键优势在于，我们的实施不需要更改现有的编程语言，支持嵌套并行性，并且具有明确的成本语义。同时，它允许实现算法的功能实现，例如具有与命令性实现相同的渐近复杂性的深度优先搜索。
The goal of this paper is to develop a form of functional arrays (sequences) that are as efficient as imperative arrays, can be used in parallel, and have well defined cost-semantics. The key idea is to consider sequences with functional value semantics but non-functional cost semantics. Because the value semantics is functional, "updating" a sequence returns a new sequence. We allow operations on "older" sequences (called interior sequences) to be more expensive than operations on the "most recent" sequences (called leaf sequences). We embed sequences in a language supporting fork-join parallelism. Due to the parallelism, operations can be interleaved non-deterministically, and, in conjunction with the different cost for interior and leaf sequences, this can lead to non-deterministic costs for a program. Consequently the costs of programs can be difficult to analyze. The main result is the derivation of a deterministic cost dynamics which makes analyzing the costs easier. The theorems are not specific to sequences and can be applied to other data types with different costs for operating on interior and leaf versions. We present a wait-free concurrent implementation of sequences that requires constant work for accessing and updating leaf sequences, and logarithmic work for accessing and linear work for updating interior sequences. We sketch a proof of correctness for the sequence implementation. The key advantages of the present approach compared to current approaches is that our implementation requires no changes to existing programming languages, supports nested parallelism, and has well defined cost semantics. At the same time, it allows for functional implementations of algorithms such as depth-first search with the same asymptotic complexity as imperative implementations.