A program’s run time is determined by the product of instructions per program, c
ID: 3763702 • Letter: A
Question
A program’s run time is determined by the product of instructions per program, cycles per instruction, and clock frequency. Assume the following instruction mix for a MIPS-like RISC instruction set:
a)15% stores, 39% loads, 15% branches, and 25% integer arithmetic, 5% integer shift, and 5% integer multiply. Given that stores require one cycle, load instructions require 3 cycles, branches require 4 cycles, integer ALU instructions require 1 cycle, and integer multiplies require 9 cycles, compute the overall CPI.
b) Given the parameters of Problem 3, consider a strength-reducing optimization that converts multiplies by a compile-time constant into a sequence of shifts and adds. For this instruction mix, 50% of the multiplies can be converted to shift-add sequences with an average length of three instructions. Assuming a fixed frequency, compute the change in instructions per program, cycles per instruction, and overall program speedup.
Explanation / Answer
a)
CPI can be calcualted by taking the average time/cycle to execute a instruction on the processor. We need to find the average for the cpi.
CPI = 15 * (time for one store) + 39 * (load inst. time) +15*(branch time) + 25 * (int alu inst.) + 5* (integer instruction time) + 5*(integer multiply instruction)/100
=15*1 + 39*3+15*4+25*1+5*1+5*9/100
=15+117+60+25+5+45/100
= 267/100 = 2.67
b)
in that case 2.5 * 9 for normal multiply
2.5*3 for add shift multiply
change in program will be 15% stores, 39% loads, 15% branches, and 25% integer arithmetic, 5% integer shift, 2.5% integer multiply and 2.5% shift-add sequene.
cpi will be
=15*1 + 39*3+15*4+25*1+5*1+2.5*(9+3)/100
= 252/100 = 2.52
Program speed will increase with thie change and it will take less time now.
speed will be 0.17/2.67 = 6.3%
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.