Good algorithm design style for multiprocessors
Xiaotie Deng, Nian Gu · 2002
We discuss a style of designing parallel algorithms with the following characteristics for a problem of the best known sequential time T(n): C1. Each processor spends O(T(n)/P) time in computing. C2. Each processor sends and/or receives O(n/P) messages of one-word-size. C3. The number of communication phases/sup 1/ is constant, independent of the input size n. We show this is possible to achieve for several fundamental computational problems.>