5. 25 points] A program consisting of 1000 instructions is executed on a multi-c
ID: 3752847 • Letter: 5
Question
5. 25 points] A program consisting of 1000 instructions is executed on a multi-cycle machine. Each instruction type requires a different number of execution cycles. The instruction ratio for the program and CPl is shown in the table below: Type Add/Subtract Load/Store Multiply Percent of Program 45% 40% 15% CPI 10 a. How many clock cycles does it take to execute this program? EECE 459: Hardware Design Assignment 2 Due 09/24/2018 Fall 2018 b. Suppose you create a more efficient multiplier that takes half the time of the original to complete (i.e. 5 clock cycles). What is the overall speedup for the program? Using Amdahl's Law, what is the maximum speedup possible when improving each type of operation (Add/Subtract, Load/Store, Multiply)? c.Explanation / Answer
Answer a) Let's first calculate the CPI average
Formula of CPI average is : CPI1 * F1 + CPI2 * F2 .......... + CPIn * Fn
So, after calcuating values by putting values in formula we have :
Average CPI = 1.8 + 2.4 + 1.5 = 5.7
Next, we need to calculate Clock Cycles to execute the program :
Formula for Clock Cycles for the program is
Clock Cycles for a program = Average CPI * instructions Count -----------------------(i)
Value of instructions count provided in the question is = 1000 instructions
Now, putting values in equation (i) we get
Clock Cycles for a program = 5.7 * 1000
= 5700 Clock Cycles
-------------------------------------------------------------------------------------------------------------------------------------
Answer b) If we create more efficient multiplier that takes 5 clock cycles per instruction. Then to calculate overall speed up for the program, we need to follow following steps :
I am calculating the CPI average
using the Formula of CPI average is : CPI1 * F1 + CPI2 * F2 .......... + CPIn * Fn
new CPI of multiplier is 5, hence its respective value of CPI * F is 0.75
After putting values in CPI average formula we get :
CPI average : 1.8 + 2.4 + 0.75 = 4.95
Next, we need to calculate Clock Cycles to execute the program :
Formula for Clock Cycles for the program is
Clock Cycles for a program = Average CPI * instructions Count -----------------------(i)
Value of instructions count provided in the question is = 1000 instructions
Now, putting values in equation (i) we get
Clock Cycles for a program = 4.95 * 1000 = 4950 cycles
So, new architecture with efficient multiplier uses only 4950 Clock Cycles
i.e 750 less Clock cycles than previous architecture
5700(Clock cycles in less efficient architecture ) - 4950(Clock cycles in more efficient architecture ) = 750 less Clock Cycles in more efficient architecture
----------------------------------------------------------------------------------------------------------------------------------------------
Answer C) Using Amdahls's law, the maximun speedup possible when improving each type of instructions(Add/Subtract, Load/store, multiply) will be as explained below:
Amdahl’s law states that in parallelization, if P is the proportion of a system or program that can be made parallel, and 1-P is the proportion that remains serial, then the maximum speedup that can be achieved using N number of processors is 1/((1-P)+(P/N).
If N tends to infinity then the maximum speedup tends to 1/(1-P).
Speedup is limited by the total time needed for the sequential (serial) part of the program. For 10 hours of computing, if we can parallelize 9 hours of computing and 1 hour cannot be parallelized, then our maximum speedup is limited to 10x.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.