Could someone explain what is the example a[f(i)] += b[i] want to explain for?
paluri
@sanchuah The compiler can't simply split up the loop that surrounds a[f(i)] += b[i] and divide the work among a bunch of threads running in parallel and independent of each other, without executing f(i). What if f(i) was dependent on b[i-1], for example? Or if there existed ix, iy such that f(ix) = f(iy)?
Edit: As a further note, in case it's still unclear, this is a problem with general programs, however because of the way Liszt constrains programs, it is able to perform dependency analysis (see next slide).
landuo
@sanchuah I think the example is saying that we cannot simply put a[f(i)] += b[i] into independent executions (for example, OpenMP parallel for). Because there may be dependency in the calculation of f(i) (maybe an iterative function like BFS)
Could someone explain what is the example a[f(i)] += b[i] want to explain for?
@sanchuah The compiler can't simply split up the loop that surrounds a[f(i)] += b[i] and divide the work among a bunch of threads running in parallel and independent of each other, without executing f(i). What if f(i) was dependent on b[i-1], for example? Or if there existed ix, iy such that f(ix) = f(iy)?
Edit: As a further note, in case it's still unclear, this is a problem with general programs, however because of the way Liszt constrains programs, it is able to perform dependency analysis (see next slide).
@sanchuah I think the example is saying that we cannot simply put a[f(i)] += b[i] into independent executions (for example, OpenMP parallel for). Because there may be dependency in the calculation of f(i) (maybe an iterative function like BFS)