What is Wrong with Parallelsim


Jerry Potter


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

Data Parallelism


Sequential   SISD        MISD


Parallel        SIMD      MIMD




Classification should be Based on

Instruction Stream Parallelism



Sequential     SISD     SIMD


Parallel         MIMD    MISD   



Speedup is Wrong


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.



Text Books are Wrong


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


ALU  operations reflect Data Parallelism complexity


IPU operations reflect Instruction Stream (control) Parallelism complexity




Amdahl's Law

Flynn's Taxonomy


Falkoff's Algorithm

Results in:

Least Complex                  Most Complex         Most Efficient                    Least Efficient

Data Parallel   <  Sequential < IS Parallel

      APs                   SISDs            MPs