liveBook · Manning

Data dependency

As explained in Grokking GPU Programming

A data dependency occurs when one computation requires a value produced or modified by another computation.

A data dependency occurs when one task needs a value produced by another before it can start. Independent tasks can run in parallel; dependent tasks limit how much work can happen at once. section 1.5

A dependency can limit parallelism without ruling it out:

  • In straightforward Fibonacci calculation, each number needs the two before it, so the sequence proceeds step by step. section 1.5
  • In tournament-style summation, each round depends on the previous one, but additions within a round can happen at once. section 1.5

A common mistake is updating an array in place while threads read neighboring elements. A thread may see an old or newly written value, making results inconsistent or wrong. Read from one array and write to another to avoid that collision. section 4.14

A[idx] = A[idx-1] + A[idx];    #A

This in-place neighbor update can make one thread read a value another thread is overwriting. section 4.14

if (idx > 0) B[idx] = A[idx-1] + A[idx];    #A

Reading from A and writing to B avoids the read-write collision; the index guard also prevents reading before the array. section 4.14

How Grokking GPU Programming covers it

How deep it goes
Defines data dependencies, distinguishes control dependencies, and illustrates their effects without detailing hardware internals.
Examples
Uses Fibonacci, tournament summation, and an in-place neighbor update to illustrate sequential chains, partial parallelism, and race conditions.
What it assumes
Defines a task as a piece of work, requiring no prior formal definition of parallel tasks.
What you can do after
Evaluate parallelizability by checking whether a task needs another task’s result before starting.
How it connects
Connects dependencies to Map, reduction, scan, and stencil patterns.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Grokking GPU Programming. The section links point to the parts of the book it draws on.