Parallel Recursion: Ladner-Fischer ParallelPrefix SumGreg PlaxtonTheory in Programming Practice, Spring 2005Department of Computer ScienceUniversity of Texas at AustinPrefix Sum• Fix an associative binary operator ⊕ defined over some domain– Let 0 denote a left identity element of ⊕, i.e., assume that 0 ⊕ x = xfor all x in the domain of ⊕• Throughout our discussion of parallel prefix, we consider only powerlistsfor which the elements are drawn from the domain of ⊕• The parallel prefix problem is to compute the function that maps anygiven powerlist p = hx0. . . xn−1i to the powerlisthx0(x0⊕ x1) (x0⊕ x1⊕ x2) . . . (x0⊕ . . . ⊕ xn−1)i• For the sake of brevity, we refer to this function as f in what followsTheory in Programming Practice, Plaxton, Spring 2005Ladner-Fischer Parallel Prefix Scheme• If n > 1, apply ⊕ to successive pairs of elements to obtain thelength-n/2 powerlistp0= h(x0⊕ x1) (x2⊕ x3) . . . (xn−2⊕ xn−1)i• Recursively compute the prefix sum of p0to obtain the length-n/2powerlistp00= h(x0⊕ x1) (x0⊕ x1⊕ x2⊕ x3) . . . (x0⊕ . . . ⊕ xn−1)i– The powerlist p00contains the odd-indexed elements of f(p)– To get the even-indexed elements of f(p), take the ⊕ of the powerlistobtained by shifting p00to the right one position (and introducing a0 in the first position) withhx0x2x4. . . xn−2iTheory in Programming Practice, Plaxton, Spring 2005A Powerlist Formulation of the LF Scheme: Overview• Definition of the ∗ operator• The LF scheme revisited• A powerlist specification of the prefix sum operation• Derivation of the LF schemeTheory in Programming Practice, Plaxton, Spring 2005Definition of the ∗ Operator• For any powerlist p = hx0. . . xn−1i, we define p∗as the powerlisth0 x0x1. . . xn−2i• Here is an inductive definition of p∗hxi∗= h0i(p ./ q)∗= q∗./ pTheory in Programming Practice, Plaxton, Spring 2005Remark: Some Properties of the ∗ Operator• Property 1: (p ⊕ q)∗= p∗⊕ q∗– This property may be proven by induction– The proof is left as an exercise• Property 2: (p ./ q)∗∗= p∗./ q∗– By the definition of ∗, (p ./ q)∗∗= (q∗./ p )∗– Applying the definition of ∗ a second time yields the desired equation• We will not need these particular properties in the proofs that followTheory in Programming Practice, Plaxton, Spring 2005The LF Scheme Revisited• Using the powerlist notation, we can write the LF scheme for computingthe parallel prefix function f as followsf(hxi) = hxif(p ./ q) = (t∗⊕ p) ./ t where t = f(p ⊕ q)• In what follows, we show how to derive the above equation from apowerlist-based specification of the prefix sum operationTheory in Programming Practice, Plaxton, Spring 2005Specification of Prefix Sum• Consider the equation q = q∗⊕p in the given powerlist p = hx0. . . xn−1iand the unknown powerlist q = hy0. . . yn−1i• This equation has a unique solution in q– Note that y0= 0 ⊕ x0= x0– Thus y1= y0⊕ x1= x0⊕ x1, so y2= y1⊕ x2= x0⊕ x1⊕ x2, etcetera– In general, yi= x0⊕ x1⊕ . . . ⊕ xi, 0 ≤ i < n– In other words, the unique solution (in q) to the equation q = q∗⊕ pis f(p)Theory in Programming Practice, Plaxton, Spring 2005Derivation of the LF Scheme• We wish to derive an equation for f(p ./ q), where p and q areequal-length powerlists• Since f(p ./ q) is a non-singleton powerlist, there is a unique way towrite it in the form r ./ t• Our plan is to solve for r and t in what follows• By the result of the previous slide, r ./ t = (r ./ t)∗⊕ (p ./ q)• By the definition of ∗, the latter expression is equal to (t∗./ r)⊕(p ./ q)• Since ⊕ is a pointwise operator, ⊕ and ./ commute and the previousexpression can be rewritten as (t∗⊕ p) ./ (r ⊕ q)Theory in Programming Practice, Plaxton, Spring 2005Derivation of the LF Scheme (continued)• Thus far we have established that r ./ t = (t∗⊕ p) ./ (r ⊕ q)– By unique deconstruction, r = t∗⊕ p and t = r ⊕ q– Hence t = (t∗⊕ p) ⊕ q = t∗⊕ (p ⊕ q)– Earlier we saw that the unique solution to this equation is t = f(p⊕q)• In summary, we have shown that f(p ./ q) is equal to (t∗⊕ p) ./ twhere t = f(p ⊕ q)– In effect we have derived the powerlist-based formulation of the LFscheme stated earlierTheory in Programming Practice, Plaxton, Spring 2005Sequential Complexity of the LF Scheme• Let T (n) denote the sequential running time of the LF scheme• We obtain the recurrence T (1) = O(1) and T (n) = T (n/2) + O(n)• This recurrence solves to give T (n) = O(n)Theory in Programming Practice, Plaxton, Spring 2005Parallel Complexity of the LF Scheme• Let T (n) denote the parallel running time of the LF scheme using nprocessors• We obtain the recurrence T (1) = O(1) and T (n) = T (n/2) + O(1)• This recurrence solves to give T (n) = O(log n)• In fact, the LF scheme can be used to compute prefix sum in O(log n)time using only n/ log n processors– The overhead at the top level of recursion is O(log n), but it dropsoff by a factor of two at each successive level– This parallel algorithm is considered to be “work-efficient” becauseits processor-time product is equal (to within a constant factor) tothe sequential time complexityTheory in Programming Practice, Plaxton, Spring