Efficient Parallelization of a Ubiquitous Sequential Computation

Code

• github.com/glassroom/heinsen_sequence
  OfficialIn paperpytorch★ 98

Abstract

We find a succinct expression for computing the sequence x_t = a_t x_t-1 + b_t in parallel with two prefix sums, given t = (1, 2, , n), a_t R^n, b_t R^n, and initial value x_0 R. On n parallel processors, the computation of n elements incurs O( n) time and O(n) space. Sequences of this form are ubiquitous in science and engineering, making efficient parallelization useful for a vast number of applications. We implement our expression in software, test it on parallel hardware, and verify that it executes faster than sequential computation by a factor of n n.

Reproductions