In General, software development adapts existing code to the new destination. This can be referred to as optimizing the existing algorithms. This can enable a new execution model for search solutions.
Software developers can reuse previous program code to take advantage of parallel execution. Developers will get maximum results because developers have unlimited freedom to design algorithms and implementation, to enlarge the advantage of using parallel execution.
If developers require re-use most of the implementations of the algorithm, then the developer can still have a chance. In some ways, the developer work easier, because the correct results are determined by the results of serial algorithms.
Pemfaktoran is the process of transforming the internal structure of the software without changing the functional behavior of the eksternalnya. This technique can be used by developers to express its purpose becomes clearer and remove reliance serial process contained in the implementation of the sequential algorithm.
| T1 = F1 (A + B) T2 = F2 (C * D) |
Figure 1
In Figure 1, the series is the first semantic sum A + B, apply the function F1, and store the result in T1. Then multiplying C * D, apply the function F2, and save the result in T2. Assumed to be F1 and F2 is a pure function, mathematically the same semantiknya If T2 is calculated first, then T1.
The second writing semantic above can create a constraint. If the declared limitation task parallel semantics, for example, as shown in Figure 2, then the programmer can use the same technique in the source code, so that the dependence on data not to worry about in order to produce a parallel execution that is true.
| parallel {task {T1 F1 = (A + B)} task {T2 = F2 (C * D)}} |
Figure 2
| for (int i = 0; i ++; n < i) A [i] = B [i] + C [i] |
Figure 3
Figure 3 shows the same situation. This loop is shorthand for writing the array variable i is in the range 0: N-1. The result of this loop is each element A contains the summation of elements B and C matching. In this series the loop, execution is too restricted by the index variable i is calculated through induction i = i + 1. If the declared task constraints as shown in Figure 4, all iterations of the loop are executed in parallel on as a separate task-task, in other words the value of i is computed simultaneously when each task was created.
| parallel {for (int i = 0; i ++; n < i) task {A [i] = B [i] + C [i]}} |
Figure 4
Re-Pemfaktoran to identify the sequential execution is generally implemented through fork-join parallelism. Programmers download the fork when the programmer wants to reduce the constraint of serial execution, and men-join when programmers want to apply the constraint of serial execution (using the barrier).
On the fork-join parallelism, computer programs are executed in series or in parallel. From Amdahl's law, the programmer knows that the potential speedup is limited by the percentage of time a computer program is executed in series. Therefore, the transition from parallel to serial can reduce the performance of parallel computing.
To resolve the above issue, programmers can think in hierarchical. This trick is used to repeat the serial algorithm on the deepest level, and creates multiple task at the outermost level each task work independently. QuickSort algorithm is a good example for it, as shown in Figure 5.
| void QuickSort (Value [], int L, int H) {if (H-L < TooSmallLimit) {SerialSort (A, L, H); return;} Pivot value = A [L + (H-L)/2]; int L1 = L; int H1 = H; While (L1 < H1) {if (A [L1] < Pivot) + + L1; else if (A [H1] > = Pivot)-H1; else Swap (A [L1], [H1]);} parallel {task {QuickSort (A, L, L1-1);} task {QuickSort (A, L1, H);}}} |
Figure 5
The algorithm above has a series of phases (sort of an array of smaller, choose a pivot, and partition the array) and a parallel phase (sort of two part of the array is partitioned). The hierarchy that can be used is a recursive QuickSort function calls.
Introducing parallelism through re-pemfaktoran the main task is to identify the location of the serial semantics are too restricted to be completed by the programmer. Design of parallel program through the pemfaktoran birthday is the main key in order for the execution of the series just became trivial in the execution of parallel programs.
