Parallelism in sequential functional languages
Parallelism in sequential functional languages
复制标题
顺序函数语言中的并行性
DOI：
10.1145/224164.224210
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
John Greiner
中科院分区：
文献类型：
--
作者：
G. Blelloch;John Greiner
本文正式研究了一个问题，即在没有平行扩展的情况下，逐个价值的功能语言中可获得多少并行性（即ML或方案的功能子；特别是，我们有兴趣对各种问题的可用性有多少平行性。为此，我们基于逐个价值A-Calculus介绍了复杂性模型。该模型是根据分析语义的定义，并根据总工作和计算的平行深度来衡量复杂性。我们描述了在各种并行机器模型上的A-PAL（与算术操作扩展的PAL）的模拟，包括蝴蝶，HyperCube和Pram模型，并证明了模拟界限。特别是模拟离子是磨损的（机器上的处理器时间产品在a-pal上工作的恒定因素），对于p处理器，机器上的速度放缓（机器上的时间除以A-PAL上的深度）最多与O（log P）成正比。我们还证明了模拟A-PAL上的婴儿车的界限。基于模型，我们描述和分析了QuickSort和合并排序的基于树的版本。我们表明，对于大小为n的输入，这些算法在具有O（ri log n）工作和0（log2 n）深度的A-PAL模型上运行（QuickSort的预期情况）。
This paper formally studies the question of how much parallelism is available in cal-by-value functional languages with no parallel extensions (i. e., the functional sub;ets of ML or Scheme). In particular we are interested in placing bounds on how much parallelism is available for various problems. To do this we introduce a complexity model, the PAL, based on the call-by-value A-calculus. The model is defined in terms of a profiling semantics and measures complexity in terms of the total work and the parallel depth of a computation. We describe a simulation of the A-PAL (the PAL extended with arithmetic operations) on various parallel machine models, including the butterfly, hypercube, and PRAM models and prove simulation bounds. In particular the simulat ions are workeficient (the processor-time product on the machines is within a constant factor of the work on the A-PAL), and for p processors the slowdown (time on the machines divided by depth on the A-PAL) is proportional to at most O(log p). We also prove bounds for simulating the PRAM on the A-PAL. Based on the model, we describe and analyze tree-based versions of quicksort and merge sort. We show that for an input of size n these algorithms run on the A-PAL model with O(rI log n) work and 0(log2 n) depth (expected case for quicksort ).