A parallel-design distributed-implementation (PDDI) general-purpose computer

A scheme of an efficient general-purpose parallel computer is introduced. Its design space (i. e. , the model for which parallel programs are written), is a permissive parallel RAM model of computation. The implementation space is presented as a scheme of a synchronous distributed machine which is not more involved than a sorting network followed by a merging network. An efficient translation from the design space into the implementation space is given. Suppose for some t and x there is a parallel algorithm in the design space which has depth (i. e. , parallel time) O( t p ) using p processors for all p⩽x. This translates to an algorithm in the implementation space with depth O( t s ) for all s⩽ t l where l depends on the choice of the sorting and merging networks, s is the number of ‘powerful’ processors used (processors not in the sorting or merging networks) and ƒ(s, m) auxiliary processors, where m is the size of the common memory in the design space. For a specific choice, l = log 2 s + log m and ƒ(s, m) = O(s log2 s + m log m), comparing favorably with alternative known solutions. Since many parallel algorithms are designed for a wide range of processors our solution pays the fine for implementation where it hurts least.

Authors

• Uzi Vishkin

Keywords

No keywords are indexed for this paper.