# Computer Architecture 計算機結構
## 每週問答題
### Week2
#### Class Sheet (Group)
##### 問題一
Q : Why is the Instruction Count for a program determined by program, ISA and compiler ? Could you give an example ?

A :
Program - The algorithm that is adopted in the program might be different, and different algorithm leads to different instruction count.

ISA - An ISA may cover many arithmetic instructions like multiply or divide. Then it will make software developer easier to write shorter program by just using one instruction to reach the goal of multiply or divide something. However, if there isn't such instruction in ISA, it takes many addition and shift instructions to reach the goal of multiply.

Compiler - compiler optimizations like "gcc -O3" will do some work to remove unnecessary instructions and generate shorter program. Let's see an example below:

int main(){
    int a = 1, b = 5;
    a += b;
    return a;
}

It's a program that simply add variable a and variable b then return value of a. The assembly code generated by gcc without optimization will be like this:

main:
        addi    sp,sp,-32
        sw      ra,28(sp)
        sw      s0,24(sp)
        addi    s0,sp,32
        li      a5,1
        sw      a5,-20(s0)
        li      a5,5
        sw      a5,-24(s0)
        lw      a4,-20(s0)
        lw      a5,-24(s0)
        add     a5,a4,a5
        sw      a5,-20(s0)
        lw      a5,-20(s0)
        mv      a0,a5
        lw      ra,28(sp)
        lw      s0,24(sp)
        addi    sp,sp,32
        jr      ra

However, after triggering the optimization it turns out to be something below:

main:
        li      a0,6
        ret

##### 問題二
Q : There are two implementations of the processor, **Pipelined** or **Non-Pipelined** versions, and here are some of their design parameters:

| Parameter | Pipelined Version | Non-Pipelined Version|
|-----------|-------------------|----------------------|
| Clock Rate | 500MHz | 350MHz |
| CPI for ALU instructions | 1 | 1 |
| CPI for Control instructions | 2 | 1 |
| CPI for Memory instructions |2.7 | 1 |

(1) for a program with 20% ALU instructions, 10% control instructions
and 70% memory instructions, which design will be faster? Calculate
CPI for each case.
(2) for a program with 80% ALU instructions, 10% control instructions
and 10% memory instructions, which design will be faster? Calculate
CPI for each case.

A:

(1) Average CPI :
Pipelined : (0.2 × 1 + 0.1 × 2 + 0.7 × 2.7) = 2.29
Non-Pipelined : (0.2 × 1 + 0.1 × 1 + 0.7 × 1) = 1.0
Instruction time :
Pipelined : 2.29 / (500M) = 4.6 ns
Non-Pipelined : 1.0 / (350M) = 2.8 ns
Non-Pipelined version is the better choose.

(2) Average CPI :
Pipelined : (0.8 × 1 + 0.1 × 2 + 0.1 × 2.7) = 1.27
Non-Pipelined : (0.8 × 1 + 0.1 × 1 + 0.1 × 1) = 1.0
Instruction time :
Pipelined : 1.27 / (500M) = 2.54 ns
Non-Pipelined : 1.0 / (350M) = 2.8 ns
Pipelined version is the better choose.
#### Class Sheet (Class)
##### 問題一
Q : Say we have three computers A, B and C, which vary in $T_{c'}$ (cycle time) and CPI (average cycles per instruction), with these values listed in the table below. The three computers are using the same ISA.
|Computer|$T_{c'}$(ps)|CPI|$T_{c'}$×CPI|Performance (relative to A)|
|:------:|:----------:|:-:|:----------:|:-------------------------:|
|A |250 |3.0|750 |1 |
|B |400 |2.0|800 |0.94 |
|C |600 |1.2|720 |1.05 |

Please answer the following questions

1. Calculate the performance of each computer relative to computer A
(round to 2nd decimal place).
2. Rank the performance of the computers from best to worst.

A :

(1) As the table forward.
(2) C > A > B
##### 問題二
Q : Please choose the correct answers.

(a) Response time and throughput use the same measuring unit.
(b) Instruction count and CPI both won't be affected by technology.
(c) By reducing the clock frequency of a processor from 2.5 GHz to 2
GHz, and also reducing its supply voltage from 1.2 Volt to 0.9
Volt,the dynamic power consumption will be reduced by 50%
theoretically.
(d) Using more CPUs in a computer system may not help in reducing the
response time.

A : (b), (d)

(a) Response time : How long it takes to do a task (second)
Throughput : Total work is done per unit time (per second)
(c) Power = Capacitive load * Voltage^2 * Frequency
1 - (2/2.5) * (0.9/1.2)^2 = 55%
##### 問題三
Q : What is the full name of CPI? Suppose I have a computer with a performance A, and I want it to be 2A. What can I do without modifying the program, ISA and compiler?
Hint:

A : The full name of **CPI** is **Clock Per Instruction**. To boost performace A to 2A, We can improve CPI or clock cycle time, that is, to use advanced technology or efficient organization.
##### 問題四
Q : Please fill out the below table and give some brief explanations about your answers. (Put a tick by the item you think which will affect the below performance factors)
| |Instruction Count |CPI |Clock Rate|
|:-------------------:|:----------------:|:----------------:|:--------:|
|Program |:heavy_check_mark:|:heavy_check_mark:| |
|Compiler |:heavy_check_mark:|:heavy_check_mark:| |
|Instruction Set |:heavy_check_mark:|:heavy_check_mark:|:heavy_check_mark:|
|Organization/Hardware| |:heavy_check_mark:|:heavy_check_mark:|
|Technology | | |:heavy_check_mark:|
##### 問題五
|Program |Girlfriend Simulator 6900™|GPA Forecast v2.1|
|:----------------:|:------------------------:|:---------------:|
|Instruction Class |A |B |
|Instruction Counts|6 |4 |

|Computer |MadBook Pro|Microhard Surface|
|:--------------------------------:|:---------:|:---------------:|
|Clock Frequency |3GHz |2.6GHz |
|Instruction Set Architecture (ISA)|ARMPIT |x886 |
|Compiler |gcc |g++ |
|CPI for Class A Instructions |1.5 |2.5 |
|CPI for Class B Instructions |3 |0.8 |

Q : If I were to execute both the Girlfriend Simulator 6900™ and the GPA Forecast v2.1, which computer requires less execution time?

A :
CPU time of MadBook Pro : $6 * \frac{1.5}{3} + 4 * \frac{3}{3}$ = 7
CPU time of Microhard Surface : $6 * \frac{2.5}{2.6} + 4 * \frac{0.8}{2.6}$ = 7
The two computers are the same.
##### 問題六
Q : Consider two different implementations, M1 and M2, of the same instruction set. There are three classes of instructions (A, B, and C) in the instruction set. M1 has a clock rate of 80MHz and M2 has a clock rate of 100MHz. The average number of cycles for each instruction class and their frequencies (for a typical program) are shown as the table below. Which of the following statements are correct? (Note: MIPS stands for Million Instructions per second in this problem.)
|Instruction class|Machine M1 cycles/instuction class|Machine M2 cycles/instruction class|Frequencies in the program|
|:---------------:|:--------------------------------:|:------------------------------------------:|:------------------------:|
|A |1 |2 |60% |
|B |2 |3 |30% |
|C |4 |4 |10% |

(a) The average CPI for M1 is 1.6
(b) The average CPI for M2 is 2.5
(c) M2 has higher MIPS rating than M1
(d) If we change CPI of A for M2 to 1, M2 has higher MIPS rating than
M1.
(e) If we increase the clock rate of M1 to 100MHz without affecting
the CPI of A, B, and C. The speedup of M1 is 0.8.

A : (a), (b), (d)

(a) CPI for M1 : 1 * 0.6 + 2 * 0.3 + 4 * 0.1 = 1.6
(b) CPI for M2 : 2 * 0.6 + 3 * 0.3 + 4 * 0.1 = 2.5
(c) MIPS rating of M1 : 80MHz / 1.6 = 50
MIPS rating of M2 : 100MHz / 2.5 = 40
M1 has higher MIPS rating than M2
(d) CPI = 1 * 0.6 + 3 * 0.3 + 4 * 0.1 = 1.9
MIPS rating = 100 / 1.9 = 52.5 > 50 = MIPS rating of M1
(e) 100MHz / 1.6 = 62.5
62.5 / 50 = 1.25
##### 問題七
是非題：

a. Program execution time decreases when the clock rate increases.
b. Program execution time increases when the CPI increases.
c. Program execution time increases when the Instruction count
increases.
d. A speedup of 50 times on 40% of the program will result in an
overall speedup of at least 2 times.

A:

a.X
b.O
c.O
d.X