---
# System prepended metadata

title: Computer Organization HWI
tags: [Computer Organization]

---

---
title : Computer Organization HWI
---

# Problem 1
## Topic:
You are going to enhance a computer, and there are two possible improvements: either make multiply instructions run **four times faster** than before, or make memory access instructions run **two times faster** than before. You repeatedly run a program that takes 100 seconds to execute.  Of this time,20% is used for multiplication, 50% for memory access instructions, and 30% for other tasks. Calculate the speedup  (答案請四捨五入到小數點第二位)  
 
(1)  Speedup if we improve only multiplication (6 pt.)
(2)  Speedup if we only improve memory access (6 pt.)
(3)  Speedup if both improvements are made (6 pt.) 

## Solution:
$Speedup=Time_{old}/Time_{new}$
(1)
$Time_{new}=Time_{old}*(0.8+0.2/4)$
$=0.85Time_{old}$
$Speedup=1/0.85=1.18$
(2)
$Time_{new}=Time_{old}*(0.5+0.5/2)$
$=0.75Time_{old}$
$Speedup=1/0.75=1.33$
(3)
$Time_{new}=Time_{old}*(0.3+0.2/4+0.5/2)$
$=0.6Time_{old}$
$Speedup=1/0.6=1.67$


# Problem2
## Topic:
Machine X has a clock rate of 4180MHZ and machine Y has a clock rate of 400 MHZ. The following is the CPI(clock cycle per instruction) and the percentage of instruction in gcc program. 

|    Instruction     | CPI of X | CPI of Y | Percentage of gcc |
|:------------------:|:--------:|:--------:|:-----------------:|
|     Arithmetic     |    2     |    2     |        48%        |
|   Data transfer    |    3     |    2     |        33%        |
| Conditional branch |    3     |    4     |        17%        |
|        Jump        |    5     |    4     |        2%         |

(1) Compute the CPI for gcc of machine X and Y. (6 pt.)
(2) Compute the MIPS (million instructions per second) for gce in Machine X and Y. (6 pt.)
(3) Which machine shall be chosen to run gcc in terms of execution time? (6 pt.)

## Solution:
(1)
$CPI_X=2*0.48+3*0.33+3*0.17+5*0.2$
$=2.56$
$CPI_Y=2*0.48+2*0.33+4*0.17+4*0.02$
$=2.38$
(2)
$MIPS_X=\dfrac{4180*10^6}{2.56*10^6}$
$=1632.81$
$MIPS_Y=\dfrac{400*10^6}{2.38*10^6}$
$=168.07$
(3)
Because $MIPS_X>MIPS_T$,
$X\ machine$ shall be chosen.

# Problem3
## Topic:
A certain machine with a 10ns(10 ∗ 10−9𝑠)clock period can perform jumps(1 cycle), branches (3 cycles), arithmetic instructions (2 cycles), multiply instructions (5 cycles), and memory instructions (4 cycles), A certain program has 10% jumps, 10% branches, 50% 
arithmetic, 10% multiply, and 20% memory instructions. Answer the following question. Show your derivation in sufficient detail. 
 
(1)  What is the CPI of this program on this machine ? (6 pt.) (2)  If the program executes 109 instructions, what is its execution time ? (6 pt.)
(3)  A 5-cycle multiply-add instruction is implemented that **combines an arithmetic and a multiply instruction. (1 arithmetic + 1 multiply = 1 new instruction)** 50% of the multiplies can be turned into multiply-adds.  What is the new CPI? (*注意指令比例加總不為 1)  (6 pt.)
(4) Following (3) above, if the clock period remains the same, what is the program's new execution time. (6 pt.) 

## Solution:
(1)
$CPI=1*0.1+3*0.1+2*0.5+5*0.1+4*0.2$
$=2.7$
(2)
$Execution\ time = 10^9*2.7*10*10^{-9}$
$=27(s)$
(3)
$CPI_{new}=1*\dfrac{10}{95}+3*\dfrac{10}{95}+2*\dfrac{45}{95}+5*\dfrac{5}{95}+4*\dfrac{20}{95}+5*\dfrac{5}{95}$
$=2.74$
(4)
$Execution\ time_{new}=10^9*2.74*10*10^{-9}$
$=27.4(s)$

# Problem4
## Topic:
Translate the following assembly codes into corresponding MIPS machine codes (in binary notation). 
 
(1) add $t0, $t1, $t2    (6 pt.)
(2) addi $s3, $s6, -26   (6 pt.)
(3) lw $t0, 1000($t1)   (6 pt.)
(4) sw $t5, 1200($t6)   (6 pt.)   

## Solution:
(1)000000 01001 01010 01000 00000 100000
(2)001000 10110 10011 1111111111100110
(3)100011 01001 01000 0000001111101000
(4)101011 01110 01101 0000010010110000

# Problem5
## Topic:
For the pseudo instruction “bge $t5, $t3, Loop” (branch on greater than or equal), please use a minimal sequence of MIPS instructions (beq/bne/slt) to accomplish it. You may use $t1 if necessary. (10 pt.) 

## Solution:
slt $t1, $t5, $t3
beg $t1, $zero, Loop

# Problem6
## Topic:
Please write MIPS instructions to load the following 32 bits constant into a register $s0 (6 pt.) 
> 0000 0000 0011 1101 0000 1001 0000 0000 

## Solution:
lui $s0, 0000 0000 0011 1101(0x003D)
ori $s0, $s0, 0000 1001 0000 0000(0x0900)

###### tags: `Computer Organization`