What is Wrong with Parallelsim

By

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.

But

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

CPU = ALU + IPU

ALU  operations reflect Data Parallelism complexity

 

IPU operations reflect Instruction Stream (control) Parallelism complexity

Conclusion

 

Resolving

Amdahl's Law

Flynn's Taxonomy

and

Falkoff's Algorithm

Results in:

Least Complex                  Most Complex         Most Efficient                    Least Efficient

Data Parallel   <  Sequential < IS Parallel

      APs                   SISDs            MPs