int, sum

Consider first the int, sum case which computes the sum of an array of integers.

Question: Extract the dependencies of this problem. What is the width? the critical path? the work?

Question: Noticing that the different loop iterations could execute in any order. Introduce a mutual

exclusion clause on the dependency graph. Does that help?

Question: Assuming you have P processors, rewrite the code to introduce one local variable per processor

to store partial computation. Extract the dependencies now. What is the width, critical path and work ?

Question: What does a schedule look like on P processors?

2.2 Variants

Question: Would these two parallel versions (with mutual exclusion and with local variable) be correct for int, max ? Why?

Question: Would these two parallel versions (with mutual exclusion and with local variable) be correct for string, concat ? Why?

Question: Would these two parallel versions (with mutual exclusion and with local variable) be correct for float, sum ? Why?

Question: Would these two parallel versions (with mutual exclusion and with local variable) be correct for float, max ? Why?