Using approximation algorithms to design parallel algorithms that may ignore processor allocation
Using approximation algorithms to design parallel algorithms that may ignore processor allocation
复制标题
使用近似算法设计可能忽略处理器分配的并行算法
DOI：
10.1109/sfcs.1991.185439
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
M. Goodrich
中科院分区：
文献类型：
--
作者：
M. Goodrich
提出了一种可忽略处理器分配的并行算法设计框架。提出了一些快速逼近算法，并展示了如何使用这些算法在随机化的CRCW PRAM上以保持工作的方式模拟任何符合该框架的算法。给出了该方法在并行计算几何中的几个应用。
A framework is presented for designing parallel algorithms that may ignore processor allocation. A number of fast approximation algorithms are developed, and it is shown how to use these algorithms to simulate any algorithm that fits this framework in a work-preserving fashion on a randomized CRCW PRAM. Several applications of the approach to parallel computational geometry are given.<<ETX>>