Title :
Good algorithm design style for multiprocessors
Author :
Deng, X. ; Gu, N.
Author_Institution :
Dept. of Comput. Sci., York Univ., North York, Ont., Canada
Abstract :
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 phases1 is constant, independent of the input size n. We show this is possible to achieve for several fundamental computational problems
Keywords :
communication complexity; computational complexity; parallel algorithms; algorithm design; computational problems; messages; multiprocessors; parallel algorithms; sequential time; Algorithm design and analysis; Application software; Computer science; Concurrent computing; Delay effects; Distributed computing; Parallel algorithms; Parallel machines; Phase change random access memory; Pipeline processing;
Conference_Titel :
Parallel and Distributed Processing, 1994. Proceedings. Sixth IEEE Symposium on
Conference_Location :
Dallas, TX
Print_ISBN :
0-8186-6427-4
DOI :
10.1109/SPDP.1994.346125
