Consider the following execution scenario where four programs (each with single

Question

Consider the following execution scenario where four programs (each with single statement) running simultaneously on a quad-core processor. Assume that x and y are initially set to 0. Core 1: x = 2; Core 2: y = 3; Core 3: z = x - y; Core 4: w = x + yi What are the possible results of w. x, y, and z? You will need to consider all possible execution orders. As you can see, the execution order above is non-deterministic. Is there a way to make it more deterministic so that only one execution order is possible? Consider the following loop rest, and we would like to run it on two different machines, a MIMD machine and a SIMD machine. The above loop nest can be parallelized on both MIMD and SIMD without correctness issue. Why is that? lf the above loop is run on a quad-core MIMD machine, how would you partition the loop iterations into each core? Provide a pseudo code that shows your parallelization scheme. What is the potential speedup on this machine? Assuming the above loop is run on a SIMD machine with 128-bit vector registers, write a pseudo code using your own SIMD instruction to parallelize the above loop.

Explanation / Answer

Solution:

i)

For the given four cases 24 order is possible, which are mentioned below along with the output value.

1 2 3 4=> w= 5, x= 2, y=3, z= -1

1 2 4 3=> w= 5, x= 2, y=3, z= -1

1 3 4 2=> w= 2, x= 2, y=3, z= 2

1 3 2 4=> w= 5, x= 2, y=3, z= 2

1 4 3 2=> w= 2, x= 2, y=3, z= 2

1 4 2 3=> w= 2, x= 2, y=3, z= -1

2 1 3 4=> w= 5, x= 2, y=3, z= -1

2 1 4 3=> w= 5, x= 2, y=3, z= -1

2 3 4 1=> w= 3, x= 2, y=3, z= -3

2 3 1 4=> w= 5, x= 2, y=3, z= -3

2 4 3 1 => w= 3, x= 2, y=3, z= -3

2 4 1 3=> w= 3, x= 2, y=3, z= -1

3 2 1 4=> w= 5, x= 2, y=3, z= 0

3 2 4 1=> w= 3, x= 2, y=3, z= 0

3 1 4 2=> w= 2, x= 2, y=3, z= 0

3 1 2 4=> w= 5, x= 2, y=3, z= 0

3 4 1 2 => w= 0, x= 2, y=3, z= 0

3 4 2 1=> w= 0, x= 2, y=3, z= 0

4 2 3 1=> w= 0, x= 2, y=3, z= -3

4 2 1 3=> w= 0, x= 2, y=3, z= -1

4 3 1 2=> w= 0, x= 2, y=3, z= 0

4 3 2 1=> w= 0, x= 2, y=3, z= 0

4 1 3 2=> w= 0, x= 2, y=3, z= 2

4 1 2 3=> w= 0, x= 2, y=3, z= -1

ii)

If only one order is maintained throughout the execution then deterministic sequence is possible.

1-2-3-4 is the write sequence as the written values are executed in order.

I hope this helps. Don't forget to give a thumbs up if you like this.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.