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 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(log_{w} 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

**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