What is Wrong with Parallelsim
Copyright J. Potter, 2000
Dr.Amdahl was Wrong
"A fairly obvious conclusion which can be drawn at this point is that the effort expended on achieving high parallel processing rates is wasted unless it is accompanied by achievements in sequential processing rates of nearly the same magnitude." - Amdahl, G. M., "Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities" in THE PROCEEDINGS OF THE AFIPS SPRING JOINT COMPUTER CONFERENCE, 1967, pp. 483-485.
Amdahl's Law assumes that parallelism achieves ever increasing thruput rates.
This is not true for Multi-processors. Interprocessor communication introduces Instruction Stream components which become worse not better when more processors are added.
Dr. Flynn was Wrong
Flynn's Taxonomy is Based on
Parallel SIMD MIMD
Classification should be Based on
Instruction Stream Parallelism
Sequential SISD SIMD
Speedup is often defined as the ratio of the fastest sequential algorithm and the fastest parallel algorithm.
Superlinear speedup (worst case) is impossible because any parallel algorithm can be implemented on a sequential machine. So that the above ratio is a function of the number of processors in the parallel implementation.
Falkoff's maximum value algorithm is O(1) on a Data Parallel Associative Processor (AP), but O(logw n) on a sequential machine.
The contradiction is because super-
linear speedup is based on Instruction Stream (control) parallelism, Falkoff's algorithm is data parallel.
Data parallel problems are used to teach Instruction Stream (control) parallelism (The Manhattan telephone book problem).
This trivializes Instruction Stream (control) parallelism analysis.
Dynamic real time scheduling problems, such as Air Traffic Control, are intractable using Instruction Stream (control) parallelism.
Complexity Analysis is Wrong
CPU operations do not distinguish between Data Parallelism and Instruction Stream (control) Parallelism
CPU = ALU + IPU
ALU operations reflect Data Parallelism complexity
IPU operations reflect Instruction Stream (control) Parallelism complexity
Least Complex Most Complex Most Efficient Least Efficient
Data Parallel < Sequential < IS Parallel
APs SISDs MPs