# Parallel Makespan Calculation for Flow Shop Scheduling Problem with Minimal and Maximal Idle Time
## 4 Parallel Prefix Sum  
This section briefly describes the concept of a prefix sum and the algorithm for its parallel computation. Prefix sums will be used both directly as part of the final algorithm as well as indirectly as a basis for the construction of a custom scan-like operation. It should be noted that all information in this section is well known in the literature. Let \(x=(x_{1},x_{2},\ldots,x_{n})\) be a sequence of \(n\) numbers. Then, the inclusive prefix sum of \(x\) is defined as sequence of \(n\) numbers \(y=(y_{1},y_{2},\ldots,y_{n})\) such that:  
\[y_{i}=\sum_{j=1}^{i}x_{i}. \tag{14}\]  
In other words, \(y_{i}\) holds the sum of all elements of \(x\) up to the \(i\)-th element and including it. Similarly, the exclusive prefix sum is defined as the sequence \(y^{\prime}=(y^{\prime}_{1},y^{\prime}_{2},\ldots,y^{\prime}_{n})\) such that:  
\[y^{\prime}_{1} =0, \tag{15}\] \[y^{\prime}_{i} =\sum_{j=1}^{i-1}x_{i}\quad i>1. \tag{16}\]  
Thus, \(y^{\prime}_{i}\) holds the sum of all elements up to the \(i\)-th but without including it. It should also be noted that transforming between \(y\) and \(y^{\prime}\) is easy as  
\[y_{i}=y^{\prime}_{i}+x_{i}, \tag{17}\]  
or alternatively:  
\[y_{i} =y^{\prime}_{i+1},\quad i<n \tag{18}\] \[y_{n} =y^{\prime}_{n}+x_{n}. \tag{19}\]  
The concept of prefix sums has many applications, as pointed out by [PERSON] [57]. Various authors have applied them to robotics [58], text pattern matching [59] and \(k\)-means clustering [60]--among other applications. Let us discuss the computation complexity of determining prefix sums \(y\) and \(y^{\prime}\) for a sequence \(x\) of \(n\) elements. On a single processor, computing either sum requires performing \(n\) additions for a total run time of \(O(n)\) using the simple recursive formula:  
\[y_{1} =x_{1}, \tag{20}\] \[y_{i} =y_{i-1}+x_{i}\quad i>1 \tag{21}\]  
For parallel algorithms, [PERSON] and [PERSON] [61] proposed an algorithm that runs on PRAM with \(n\) processors in time \(O(\log n)\). Unfortunately, this algorithm is not work-efficient as the total number of addition operations performed is \(O(n\log n)\). A work-efficient algorithm exists, as was shown by [PERSON] [57], and its pseudocode is presented in Algorithm 2. The algorithm works in-place and consists of two major phases: up-sweep and down-sweep. The phases are based on the leaves-to-root and root-to-leaves traversal of binary trees, respectively. The example of how the algorithm works at each step is shown in Figure 1 for \(n=8\). Black arrow pairs indicate addition, blue dashed arrows indicate copying and the dotted red arrow indicates the zeroing of the last element. ```
1 for\(s=1,2,\ldots,\log_{2}n\)do
2 for parallel processors\(p=1,2,\ldots,2^{(\log_{2}n)-s}\)do
3\(x[p2^{s}]\gets x[p2^{s}]+x[p2^{s}-2^{s-1}]\);
4\(x[n]\gets 0\);
5 for\(s=1,2,\ldots,\log_{2}n\)do
6 for parallel processors\(p=1,2,\ldots,2^{s-1}\)do
7\(t\gets x[p2^{(\log_{2}n)-s+1}]\);
8\(x[p2^{(\log_{2}n)-s+1}]\gets x[p2^{(\log_{2}n)-s+1}]+x[p2^{(\log_{2}n)-s +1}-2^{(\log_{2}n)-s}]\);
9\(x[p2^{(\log_{2}n)-s+1}-2^{(\log_{2}n)-s}]\gets t\);
```  
**Algorithm 2**Work-efficient exclusive parallel prefix sum computation  
Lines 1-3 correspond to the up-sweep phase. This phase has \(\log n\) steps. In each step, a number of processors compute partial sums. At the end of this phase, the element \(x[n]\) holds the sum of all elements. Then, in line 4, we zero that element and start the down-sweep phases which happen in lines 5-9. This phase is more complex. At each step, first the value of the \"right\" element is stored in the temporary variable \(t\) (which is a separate private variable for each processor). This corresponds to the start of the blue arrow. Then, a regular addition of the \"left\" and \"right\" element is performed and the result is stored in the \"right\" element. Finally, the blue copying operation is completed by putting the stored value \(t\) in the \"left\" element. The entire algorithm performs \(2(n-1)\) additions, \(n-1\) copy operations and one zeroing of an element.