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 area increases.

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 second case, 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: (A_P / A_{a & l & dcd}) > (1 + ((q-1)/p)) where:

A_P is the area of a big machine able to perform any instruction (simple or complex) in one clock cycle
A_{a & 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 supra-linear condition is obtained comparing two parallel expansions: one of big & complex machines and another of small & simple machines.

The main conclusion: it is possible for a specific application domain to tune a parallel machine to reach supra-linear performances.

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.

References

[Malita '04] Mihaela Malita, Gh. Stefan,: "Granularity & Complexity in Parallel Systems" in Proceedings of Modelling and Simulation - Marina del Rey, CA, 2004.