GPGPU Programming for Games and Science

366 GPGPU Programming for Games and Science

S(0,0) S(1,1) S(2,2) S(3,3)

S(0,1)

S(0,2)

S(0,3)

S(2,3)

FIGURE 7.2: A DAG for computing partial sums of four numbers.

are many subproblems we could solve but we want to select a small set of

subproblems, memoize the results, and combine them to solve the original

problem. One such approach is illustrated as a directed acyclic graph (DAG)

when n = 4, shown in Figure 7.2. Each node in the graph has two arcs

pointing to the nodes whose values are summed. The inputs are S(i, i)=a

i

for 0 ≤ i ≤ 3. The first sums to compute are S(0, 1) = S(0, 0) + S(1, 1) and

S(2, 3) = S(2, 2) + S(3, 3). These may be computed simultaneously ...