All over the 20th century computer architectures have advanced by multiple folds. The trend is continuing in the 21st century and will remain for a long time to come. Some of these trends in architecture follow Moore's Law. "Moore's law is the observation that, over the history of computing hardware, the number of transistors on integrated circuits doubles approximately every two years". Many devices in the computer industry are linked to Moore's law, whether they are DSPs, memory devices, or digital cameras. All the hardware advances would be of no use if there weren't any software advances. Algorithms and software applications grow in complexity, as more and more user interaction comes into play. An algorithm can be highly sequential or it may be parallelized, by using any parallel computing framework. Amdahl's Law is used to predict the speedup for an algorithm, which can be obtained given n threads. This speedup is dependent on the value of the amount of strictly serial or non-parallelizable code (B). The time T(n) an algorithm takes to finish when being executed on n thread(s) of execution corresponds to:
T(n) = T(1) (B + (1-B)/n)
Therefore the theoretical speedup which can be obtained for a given algorithm is given by :
Speedup(n) = 1/(B + (1-B)/n)
Amdahl's Law has a limitation, that it does not fully exploit the computing power that becomes available as the number of processing core increase.
Gustafson's Law takes into account the scaling of the platform by adding more processing elements in the platform. This law assumes that the total amount of work that can be done in parallel, varies linearly with the increase in number of processing elements. Let an algorithm be decomposed into (a+b). The variable a is the serial execution time and variable b is the parallel execution time. Then the corresponding speedup for P parallel elements is given by:
(a + P*b)
Speedup = (a + P*b) / (a + b)
Now defining α as a/(a+b), the sequential execution component, as follows, gives the speedup for P processing elements:
Speedup(P) = P – α *(P - 1)
Given a problem which can be solved using OpenCL, the same problem can also be solved on a different hardware with different capabilities. Gustafson's law suggests that with more number of computing units, the data set should also increase that is, "fixed work per processor". Whereas Amdahl's law suggests the speedup which can be obtained for the existing data set if more computing units are added, that is, "Fixed work for all processors". Let's take the following example:
Let the serial component and parallel component of execution be of one unit each.
In Amdahl's Law the strictly serial component of code is B (equals 0.5). For two processors, the speedup T(2) is given by:
T(2) = 1 / (0.5 + (1 – 0.5) / 2) = 1.33
Similarly for four and eight processors, the speedup is given by:
T(4) = 1.6 and T(8) = 1.77
Adding more processors, for example when n tends to infinity, the speedup obtained at max is only 2. On the other hand in Gustafson's law, Alpha = 1(1+1) = 0.5 (which is also the serial component of code). The speedup for two processors is given by:
Speedup(2) = 2 – 0.5(2 - 1) = 1.5
Similarly for four and eight processors, the speedup is given by:
Speedup(4) = 2.5 and Speedup(8) = 4.5
The following figure shows the work load scaling factor of Gustafson's law, when compared to Amdahl's law with a constant workload:
Comparison of Amdahl's and Gustafson's Law
OpenCL is all about parallel programming, and Gustafson's law very well fits into this book as we will be dealing with OpenCL for data parallel applications. Workloads which are data parallel in nature can easily increase the data set and take advantage of the scalable platforms by adding more compute units. For example, more pixels can be computed as more compute units are added.