The Supra-Linear Condition for Parallel Computation
The problem: building efficient one-chip parallel machines (which means high performance/price ratio)
supposes supra-linear computational performances to compensate the supra-linear increasing of the price when the chip
The first starting point: Actual
performances for a parallel architecture could be defined only
application domain dependent.
The second starting point: an efficient
parallel system must correlate its granularity with the application domain.
The third starting point: Parallel computation can be done multiplying either big and powerful machines or multiplying small and simple
machines. In the first case, the area increases proportional with the number of machines, but the price will increase more. In the
a too small granurality will be sometimes unable to provide the expected performance. Consequently, for each application domain there is the best
granularity defined in the domain where the supra-linear condition applies.
The supra-linear condition establishes for a parallel machine the conditions for having the performance increasing more than the
area in order to compensate the price. That is:
(AP / Aa & l & dcd ) > (1 + ((q-1)/p))
The supra-linear condition is obtained comparing two parallel expansions: one of big & complex machines and another of
small & simple machines.
- AP is the area of a big machine able to perform any instruction (simple or complex) in one clock cycle
- Aa & l & dcd is the area of the logic circuits in each small machine limited to perform
only simple operations (more complex operations as multiplication, floating point operations, and the same are avoided)
- q is the number of clock cycles to perform a complex operation on a small machine
- p is associated to an application domain expressing how many times the total number of operations is
bigger than the number of complex operations (executed in q clock cycles):
p = total_number_of_operations / number_of_complex_operations
The main conclusion: it is possible for a specific application domain to tune a parallel machine to reach supra-linear
Results also that the basic rule governing large and intensive
computational systems is that their complexity must grow
slower than their size because intensive computation is rather simple than complex.
[Malita '04] Mihaela Malita, Gh. Stefan,:
"Granularity & Complexity in Parallel Systems" in Proceedings of Modelling and
Simulation - Marina del Rey, CA, 2004.