Practical PRAM Programming - Errata

• p. 44, first line after Definition 2.9: SUrel(p,n) <= SUabs(p,n) should read vice versa: SUrel(p,n) >= SUabs(p,n)

• p. 55, lower half: The calls to the recursive prefix function should read

  prefix_rec(x,n,d)

  and

  prefix_rec(a,m,1)

  respectively.

• p. 137, Table 4.8: The init command is missing.
  init F V : Initialize SB-PRAM with F physical and V virtual processors and reset program counter to program start.

• p. 154, middle: Some comment on "sequential consistency":

  Actually the PRAM model (and also the SB-PRAM machine) assume an even stronger consistency model, namely strict consistency, which means that consistency is maintained at every clock cycle (assuming existence of a global time axis) and a fixed, determinisitic order of memory accesses is determined by the programmer (at least for Weak, Common, Priority, and Combining Concurrent Write PRAMs). The SB-PRAM is the only strictly consistent MIMD machine in the world, achieved by central clocking, uniform memory access, and instruction-level synchronous execution.

  In contrast, sequential consistency requires consistency only for the memory accesses in that it implies some linear order of all memory accesses by all processors such that the effect of a write access, once applied to the memory, becomes visible to all processors immediately. Sequential consistency thus does not need a global time axis. An imaginary global observer of a sequentially consistent system may see that pending reads could return the old value after the write was committed to the memory, but in that case the read was "overtaken" by the write and thus comes before the write in the linear order of memory accesses. Hence, sequential consistency is nondeterministic and not programmable. This, by the way, is also the consistency model adopted in the Asynchronous PRAM model.

  Hence, "strict consistency" would be the more precise term here (although "sequential consistency" is not wrong - every strictly consistent parallel computation is also sequentially consistent). However, the term "strict consistency" is not widely used in the literature (probably because there is no other MIMD machine supporting it). This is why we used the more common term "sequential consistency" plus a verbose description of the stronger PRAM features in this book.

  For further information on strict versus sequential consistency, see e.g. the survey of consistency models (ps slides) in a recent course.

• p. 292 middle: The parallel prefix algorithm described here and explained in Figure 7.10(b) and 7.11 is not identical to the Ladner/Fischer algorithm. Indeed this easy-to-implement EREW version uses the minimum possible (on an EREW PRAM) number of time steps, but it is not work-optimal (as stated at the bottom of that page). In contrast, the Ladner/Fischer algorithm (CREW) performs only linear work.

• p.305 Equation (7.12) does not give the most general formulation of the execution time of the sequential generic divide_conquer function (it implicitly assumes that only one subproblem of size n/k is solved, as in the algorithm in Section 7.3.5). Rather, a factor c denoting the number of subproblems generated should precede the term t_{seq_divide_conquer...} (n/k), which results in a different closed formula for the execution time, such as O(n^log_kc log n) for the case where the time for the divide and the combine step is bounded by O(n^log_kc) according to Case 2 of the Master Theorem, see Cormen et al. [CLR90]. Hence, in this more general case the term O(log_k(n/n₀)) that is given in the following paragraph denotes the recursion depth, not the work performed by the sequential algorithm.
  Note that in the parallel case (Equation 7.13) such a factor c is not needed because all recursive calls will be executed in parallel.

• p. 473 Fig. 9.10: create_scanline must be create_ilist