Getting rid of data dependency

Question

I have this code:

for(i=0; i<size; i++)
{
    d[i] = d[i-1] + v[i];
}

When I do parallel processing for this loop, I have data dependency and the initiation interval becomes 2 Meaning I have:

initiation interval:2

|load v[i-1]|load d[i-2]|    add    |store d[i-1]|
|           |           |  load v[i]|load d[i-1] |     add    | store d[i] |

I do not want to stall in between.

initiation interval:1

|load v[i-1]|load d[i-2]|    add    |store d[i-1]|
|           |load v[i]  |load d[i-1]|     add    | store d[i] |

This is not possible since d[i-1] is not stored yet.

How do we make initiation interval to 1 by changing the code?

what language? It's quite hard to understand exactly what you are asking. — Alastair Pitts, Apr 18 '13 at 00:32
I'm asking how can I change the code to make the program not to stall. No specific language — user1382007, Apr 18 '13 at 00:37

score 1 · Answer 1 · edited May 23 '17 at 12:04

1

You cannot reduce that gap.

Also this (loop unrolling) is not the most efficient way of parallel processing for this kind of loop. Your loop looks like a prefix-sum operation. There are fast parallel algorithms and implementations available for prefix-sum. For example, this question

edited May 23 '17 at 12:04

Community

1
1

answered Apr 18 '13 at 00:50

shawn

336
1
3

Getting rid of data dependency

1 Answers1