2. Consider a program with 3 stages of execution. At first, we must execute 10%
ID: 3751620 • Letter: 2
Question
2. Consider a program with 3 stages of execution. At first, we must execute 10% of the code, which
is strictly sequential. Next, we can execute an additional 30% of the code, which can be split 2-way
equally and executed in parallel. Finally, we execute the remaining 60% of the code can be split 4-ways
equally and executed in parallel. Assume that the code takes 100 seconds to execute on a single core
and the code is uniform (e.g., executing X% of the code on a core takes X seconds). Using arguments
similar to the Amdahl’s law covered in the class, answer the following:
a) How long will the code take to run on a 2-core, 4-core and 6-core machine respectively?
b) Assume that the 30% 2-way code and the 60% 4-way code can run in parallel. How long would the
code take on 2, 4, and 6 core machines respectively?
Explanation / Answer
(a)
Total time taken by the code to execute on a single core = 100 seconds
Let the stage which is strictly sequential (10% of code) be stage A.
Let the stage which can be split 2-way (30% of code) be stage B.
Let the stage which can be split 4-way (60% of code) be stage C.
Therefore,
Time taken by stage A = 0.1*100 = 10 seconds
Time taken by stage B = 0.3*100 = 30 seconds
Time taken by stage C = 0.6*100 = 60 seconds
On a 2-core machine:
Time taken by stage A = 10 seconds (since it cannot be parallelized)
Time taken by stage B = 30/2 = 15 seconds (since it can be parallelized across only 2 available cores)
Time taken by stage C = 60/2 = 30 seconds (since it can be parallelized across only 2 available cores)
Therefore, total running time on 2-core machine = 10 + 15 + 30 = 55 seconds
On a 4-core machine:
Time taken by stage A = 10 seconds (since it cannot be parallelized)
Time taken by stage B = 30/2 = 15 seconds (since it can be parallelized across only 2 available cores)
Time taken by stage C = 60/4 = 15 seconds (since it can be parallelized across only 4 available cores)
Therefore, total running time on 4-core machine = 10 + 15 + 15 = 40 seconds
On a 6-core machine:
Time taken by stage A = 10 seconds (since it cannot be parallelized)
Time taken by stage B = 30/2 = 15 seconds (since it can be parallelized across only 2 available cores)
Time taken by stage C = 60/4 = 15 seconds (since it can be parallelized across only 4 available cores)
Therefore, total running time on 6-core machine = 10 + 15 + 15 = 40 seconds
(b) Here, the total number of cores available is divided between stage B and stage C, since they run in parallel.
On a 2-core machine:
Time taken by stage A = 10 seconds (since it cannot be parallelized)
Time taken by stage B = 30/1 = 30 seconds (since it can be parallelized across only 1 available core)
Time taken by stage C = 60/1 = 60 seconds (since it can be parallelized across only 1 available core)
Time taken for stage B and stage C to run in parallel = max(30, 60) = 60 seconds
Therefore, total running time on 2-core machine = 10 + 60 = 70 seconds
On a 4-core machine:
Time taken by stage A = 10 seconds (since it cannot be parallelized)
Time taken by stage B = 30/2 = 15 seconds (since it can be parallelized across only 2 available cores)
Time taken by stage C = 60/2 = 30 seconds (since it can be parallelized across only 2 available cores)
Time taken for stage B and stage C to run in parallel = max(15, 30) = 30 seconds
Therefore, total running time on 4-core machine = 10 + 30 = 40 seconds
On a 6-core machine:
Time taken by stage A = 10 seconds (since it cannot be parallelized)
Time taken by stage B = 30/2 = 15 seconds (since it can be parallelized across only 2 available cores)
Time taken by stage C = 60/4 = 15 seconds (since it can be parallelized across only 4 available cores)
Time taken for stage B and stage C to run in parallel = max(15, 15) = 15 seconds
Therefore, total running time on 6-core machine = 10 + 15 = 25 seconds
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.