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

AbstractA 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(tp) using p processors for all p⩽x. This translates to an algorithm in the implementation space with depth O(ts) for all s⩽tl 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 = log2 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