ALL 7 CHAPTERS & Appendix A, B & C. COVERED
Solutions to Case Studies and Exercises
, Appendix A Solutions
A.1 The exercise statement gives CPI information in terms of five major instruction
categories, with two subcategories for conditional branches. The five main cate-
gories are ALU, loads, stores, conditional branches, and jumps. ALU instructions
are any that take operands from the set of registers and return a result to that set of
registers. Load and store instructions access memory. Conditional branches
instructions must be able to set the program counter to a new value based on
a condition, while jump instructions always set the program counter to a
new value.
Instruction Clock cycles
All ALU operations 1.0
Loads 5.0
Stores 3.0
Conditional branches
Taken 5.0
Not taken 3.0
Jumps 3.0
For astar and gcc, the average instruction frequencies are shown in Figure S.1.
The effective CPI for programs in Figure A.29 is computed by combining instruction
category frequencies with their corresponding average CPI measurements.
X
Effective CPI ¼ Instruction category frequency Clock cycles for category
¼ ð0:41Þð1:0Þ + ð0:225Þð5:0Þ + ð0:145Þð3:0Þ
+ ð0:19Þ½ð0:6Þð5:0Þ + ð1 0:6Þð3:0Þ + ð0:03Þð3:0Þ
¼ 2:86
Instruction category astar gcc Average of astar and gcc
ALU operations 46% 36% 41%
Loads 28% 17% 22.5%
Stores 6% 23% 14.5%
Branches 18% 20% 19%
Jumps 2% 4% 3%
Figure S.1 RISC-V dynamic instruction mix average for astar and gcc programs.
,A-2 ■ Solutions to Case Studies and Exercises
Average of bzip
Instruction category bzip hmmer and hmmer
ALU operations 54% 46% 50%
Loads 20% 28% 24%
Stores 7% 9% 8%
Branches 11% 17% 14%
Jumps 1% 0% 0.5%
Other 7% 0% 3.5%
Figure S.2 RISC-V dynamic instruction mix average for bzip and hmmer programs.
A.2 For bzip and hmmer, the average instruction frequencies are shown in Figure S.2.
The effective CPI for programs in Figure A.29 is computed by combining instruc-
tion category frequencies with their corresponding average CPI measurements.
Note that the total instruction frequency of bzip adds up to 93%, so an additional
category is considered to account for the remaining 7% of instructions, each requir-
ing 3.0 clock cycles.
X
Effective CPI ¼ Instruction category frequency Clock cycles for category
¼ ð0:5Þð1:0Þ + ð0:24Þð5:0Þ + ð0:08Þð3:0Þ + ð0:14Þ½ð0:6Þð5:0Þ + ð1 0:6Þð3:0Þ
+ ð0:005Þð3:0Þ + ð0:035Þð3:0Þ
¼ 2:65
A.3 For gobmk and mcf, the average instruction frequencies are shown in Figure S.3.
The effective CPI for programs in Figure A.29 is computed by combining instruc-
tion category frequencies with their corresponding average CPI measurements.
Note that the total instruction frequency of gobmk adds up to 99%, so an additional
category is considered to account for the remaining 1% of instructions, each requir-
ing 3.0 clock cycles.
Average of gobmk
Instruction category gobmk mcf and mcf
ALU operations 50% 29% 39.5%
Loads 21% 35% 28%
Stores 12% 11% 16.5%
Branches 14% 24% 19%
Jumps 2% 1% 1.5%
Other 1% 0% 0.5%
Figure S.3 RISC-V dynamic instruction mix average for gobmk and mcf programs.
, Appendix A Solutions ■ A-3
X
Effective CPI ¼ Instruction category frequency Clock cycles for category
¼ ð0:395Þð1:0Þ + ð0:28Þð3:5Þ + ð0:165Þð2:8Þ
+ ð0:19Þ½ð0:6Þð4:0Þ + ð1 0:6Þð2:0Þ + ð0:015Þð2:4Þ + ð0:005Þð3:0Þ
¼ 2:5
A.4 For perlbench and sjeng, the average instruction frequencies are shown in
Figure S.4.
The effective CPI for programs in Figure A.29 is computed by combining instruc-
tion category frequencies with their corresponding average CPI measurements.
X
Effective CPI ¼ Instruction category frequency Clock cycles for category
¼ ð0:475Þð1:0Þ + ð0:22Þð3:5Þ
+ ð0:105Þð2:8Þ + ð0:15Þ½ð0:6Þð4:0Þ + ð1 0:6Þð2:0Þ + ð0:05Þð2:4Þ
¼ 2:14
A.5 Take the code sequence one statement at a time.
A ¼ B + C; The operands here are given, not computed by the code,
so copy propagation will not transform this statement.
B ¼ A + C; A is a computed operand, so transform the code by
¼ B + C + C; substituting A ¼ B + C.
The work has increased by one addition operation.
D ¼ A – B; Both operands are computed, so transform the code by
substituting for A and B.
¼ (B + C) – (B + C + C); The work has increased by three addition operations, but
expression can be simplified algebraically.
¼ –C; The work has been reduced from a subtraction to a negation.
The copy propagation technique presents several challenges for compiler optimi-
zations. Compilers need to consider how many levels of propagations are sufficient
in order to gain benefit from this technique. Note that copy propagation might
increase the computational work of some statements. Selecting the group of state-
ments for which to apply copy propagation is another challenge. The above
Average of
Instruction category perlbench sjeng perlbench and sjeng
ALU operations 39% 56% 47.5%
Loads 25% 19% 22%
Stores 14% 7% 10.5%
Branches 15% 15% 15%
Jumps 7% 3% 5%
Figure S.4 RISC-V dynamic instruction mix average for perlbench and sjeng
programs.
Solutions to Case Studies and Exercises
, Appendix A Solutions
A.1 The exercise statement gives CPI information in terms of five major instruction
categories, with two subcategories for conditional branches. The five main cate-
gories are ALU, loads, stores, conditional branches, and jumps. ALU instructions
are any that take operands from the set of registers and return a result to that set of
registers. Load and store instructions access memory. Conditional branches
instructions must be able to set the program counter to a new value based on
a condition, while jump instructions always set the program counter to a
new value.
Instruction Clock cycles
All ALU operations 1.0
Loads 5.0
Stores 3.0
Conditional branches
Taken 5.0
Not taken 3.0
Jumps 3.0
For astar and gcc, the average instruction frequencies are shown in Figure S.1.
The effective CPI for programs in Figure A.29 is computed by combining instruction
category frequencies with their corresponding average CPI measurements.
X
Effective CPI ¼ Instruction category frequency Clock cycles for category
¼ ð0:41Þð1:0Þ + ð0:225Þð5:0Þ + ð0:145Þð3:0Þ
+ ð0:19Þ½ð0:6Þð5:0Þ + ð1 0:6Þð3:0Þ + ð0:03Þð3:0Þ
¼ 2:86
Instruction category astar gcc Average of astar and gcc
ALU operations 46% 36% 41%
Loads 28% 17% 22.5%
Stores 6% 23% 14.5%
Branches 18% 20% 19%
Jumps 2% 4% 3%
Figure S.1 RISC-V dynamic instruction mix average for astar and gcc programs.
,A-2 ■ Solutions to Case Studies and Exercises
Average of bzip
Instruction category bzip hmmer and hmmer
ALU operations 54% 46% 50%
Loads 20% 28% 24%
Stores 7% 9% 8%
Branches 11% 17% 14%
Jumps 1% 0% 0.5%
Other 7% 0% 3.5%
Figure S.2 RISC-V dynamic instruction mix average for bzip and hmmer programs.
A.2 For bzip and hmmer, the average instruction frequencies are shown in Figure S.2.
The effective CPI for programs in Figure A.29 is computed by combining instruc-
tion category frequencies with their corresponding average CPI measurements.
Note that the total instruction frequency of bzip adds up to 93%, so an additional
category is considered to account for the remaining 7% of instructions, each requir-
ing 3.0 clock cycles.
X
Effective CPI ¼ Instruction category frequency Clock cycles for category
¼ ð0:5Þð1:0Þ + ð0:24Þð5:0Þ + ð0:08Þð3:0Þ + ð0:14Þ½ð0:6Þð5:0Þ + ð1 0:6Þð3:0Þ
+ ð0:005Þð3:0Þ + ð0:035Þð3:0Þ
¼ 2:65
A.3 For gobmk and mcf, the average instruction frequencies are shown in Figure S.3.
The effective CPI for programs in Figure A.29 is computed by combining instruc-
tion category frequencies with their corresponding average CPI measurements.
Note that the total instruction frequency of gobmk adds up to 99%, so an additional
category is considered to account for the remaining 1% of instructions, each requir-
ing 3.0 clock cycles.
Average of gobmk
Instruction category gobmk mcf and mcf
ALU operations 50% 29% 39.5%
Loads 21% 35% 28%
Stores 12% 11% 16.5%
Branches 14% 24% 19%
Jumps 2% 1% 1.5%
Other 1% 0% 0.5%
Figure S.3 RISC-V dynamic instruction mix average for gobmk and mcf programs.
, Appendix A Solutions ■ A-3
X
Effective CPI ¼ Instruction category frequency Clock cycles for category
¼ ð0:395Þð1:0Þ + ð0:28Þð3:5Þ + ð0:165Þð2:8Þ
+ ð0:19Þ½ð0:6Þð4:0Þ + ð1 0:6Þð2:0Þ + ð0:015Þð2:4Þ + ð0:005Þð3:0Þ
¼ 2:5
A.4 For perlbench and sjeng, the average instruction frequencies are shown in
Figure S.4.
The effective CPI for programs in Figure A.29 is computed by combining instruc-
tion category frequencies with their corresponding average CPI measurements.
X
Effective CPI ¼ Instruction category frequency Clock cycles for category
¼ ð0:475Þð1:0Þ + ð0:22Þð3:5Þ
+ ð0:105Þð2:8Þ + ð0:15Þ½ð0:6Þð4:0Þ + ð1 0:6Þð2:0Þ + ð0:05Þð2:4Þ
¼ 2:14
A.5 Take the code sequence one statement at a time.
A ¼ B + C; The operands here are given, not computed by the code,
so copy propagation will not transform this statement.
B ¼ A + C; A is a computed operand, so transform the code by
¼ B + C + C; substituting A ¼ B + C.
The work has increased by one addition operation.
D ¼ A – B; Both operands are computed, so transform the code by
substituting for A and B.
¼ (B + C) – (B + C + C); The work has increased by three addition operations, but
expression can be simplified algebraically.
¼ –C; The work has been reduced from a subtraction to a negation.
The copy propagation technique presents several challenges for compiler optimi-
zations. Compilers need to consider how many levels of propagations are sufficient
in order to gain benefit from this technique. Note that copy propagation might
increase the computational work of some statements. Selecting the group of state-
ments for which to apply copy propagation is another challenge. The above
Average of
Instruction category perlbench sjeng perlbench and sjeng
ALU operations 39% 56% 47.5%
Loads 25% 19% 22%
Stores 14% 7% 10.5%
Branches 15% 15% 15%
Jumps 7% 3% 5%
Figure S.4 RISC-V dynamic instruction mix average for perlbench and sjeng
programs.
