Title :
Your favorite parallel algorithms might not be as fast as you think
Author :
Fisher, David C.
Author_Institution :
Dept. of Math., Harvey Mudd Coll., Claremont, CA, USA
fDate :
2/1/1988 12:00:00 AM
Abstract :
A problem that requires I inputs, K outputs and I computations is to be solved on a d-dimensional parallel processing machine (usually d⩽3). Finite transmission speed and other real-world conditions are assumed. It is proved that the time needed to solve the problem is t=Ω max (I1d/, K1d/, T1(d+1)/). This result is demonstrated for the standard algorithm for multiplying two n×n matrices
Keywords :
computational complexity; matrix algebra; parallel algorithms; computational complexity; finite transmission speed; matrix multiplications; parallel algorithms; real-world conditions; Circuits; Concrete; Concurrent computing; Mathematics; Parallel algorithms; Parallel processing; Very large scale integration; Wire;
Journal_Title :
Computers, IEEE Transactions on
