A provable time and space efficient implementation of NESL
A provable time and space efficient implementation of NESL
复制标题
NESL 的可证明时间和空间高效的实现
DOI：
10.1145/232627.232650
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
John Greiner
中科院分区：
文献类型：
--
作者：
G. Blelloch;John Greiner
在本文中，我们证明了在各种并行机器模型上实现编程语言NESL的时间和空间范围。 NESL是一个带有一组阵列原始图的加糖典型λ-calculus，并且在阵列上有明确的并行图。我们的结果通过考虑空间和包括数组来扩展了对功能语言可证明的实施界限的先前工作。为了建模NESL的成本，我们增加了标准的逐项呼叫操作语义，以返回两种成本度量：一个代表连续依赖性的DAG，以及顺序实现对空间的度量。我们表明，可以使用O（w/p + w/p + + crcw pram（w/p +），可以在P Processor Butterfly网络，HyperCube或CRCW Pram上实现具有W工作的NESL程序（DAG中的节点），D深度（DAG中的级别）和S顺序空间d log p）时间和o（s + dp log p）可到达空间。1对于具有足够并行性的程序，这些界限是最佳的，因为它们给出线性加速并在恒定因素的范围内使用空间顺序空间。
In this paper we prove time and space bounds for the implementation of the programming language NESL on various parallel machine models. NESL is a sugared typed λ-calculus with a set of array primitives and an explicit parallel map over arrays. Our results extend previous work on provable implementation bounds for functional languages by considering space and by including arrays. For modeling the cost of NESL we augment a standard call-by-value operational semantics to return two cost measures: a DAG representing the sequential dependence in the computation, and a measure of the space taken by a sequential implementation. We show that a NESL program with w work (nodes in the DAG), d depth (levels in the DAG), and s sequential space can be implemented on a p processor butterfly network, hypercube, or CRCW PRAM using O(w/p + d log p) time and O(s + dp log p) reachable space.1 For programs with sufficient parallelism these bounds are optimal in that they give linear speedup and use space within a constant factor of the sequential space.