[컴퓨터구조] Computer Organization and Design 5th Solution

본 게시글은 KUEE 정보공개 프로젝트에 포함된 글입니다.
https://blog.youhogeon.com/65

본 자료의 저작권은 모두 저에게 있으며
학업에 참고 자료로만 사용하시길 바랍니다.
부득이하게 인용해야 하는 경우 반드시 출처(KUEE 정보공개 프로젝트)와 링크를 남겨주시길 바랍니다.

단원명이 왜 뒤죽박죽인지 기억이 안나네요.

Computer Organization and Design 5th와

Computer Systems A Programmer's Perspective 두 권을 병행해서 수업하셨던 것 같긴 하네요.

 

 

2.txt

0.00MB

3.txt

0.00MB

4.txt

0.00MB

5.txt

0.00MB

6.txt

0.00MB

1.txt

0.00MB

==========================
컴퓨터 구조 Chapter 1 Exercises 과제

==========================

# 1.1 나머지 4개의 컴퓨터는 아래와 같다.
- Personal Computers : 가장 잘 알려진 형태ㅢ 컴퓨터
- Servers : 네트워크를 통해 연결되는 컴퓨터
- Supercomputers : 만개의 cpu와 TB단위의 메모리를 가진 컴퓨터
- Embedded computers : 가장 광범위하게 적용되는 컴퓨터

# 1.2 
a : Performance via Pipelining
b : Dependability via Redundancy
c : Performance via Prediction
d : Make the Common Case Fast
e : Hierarchy of Memories
f : Performance via Parallelism
g : Design for Moore’s Law
h : Use Abstraction to Simplify Design

# 1.3
Compiler 가 high-level language를 Assembly로 변환시킨 다음, Assembler가 Assembly를 기계어(Machine language)로 변환한다.

# 1.4
a : 3 * 1280 * 1024 = 3,932,160 bytes
b : 3932160 / (100000000 / 8) = 0.3146s

# 1.5.a
초당 명령 수행 횟수는 Clock rate를 CPI로 나눈 값이다.
1 : 2000000000
2 : 2500000000
3 : 1818181818
따라서 2번 프로세서가 가장 성능이 높다.

# 1.5.b
Number of Cycles Number of instructions
1 3 * 10^10 2 * 10^10
2 2.5 * 10^10 2.5 * 10^10
3 4 * 10^10 1.8182 * 10^10

# 1.5.c
Clock rate * (1 + 0.2) / (1 - 0.3) = 1.714 * Clock rate

# 1.6
총 Clock cycle 수
P1 10^6 * (0.1 * 1 + 0.2 * 2 + 0.5 * 3 + 0.2 * 3) = 2.6 * 10^6
P2 10^6 * 2 * 1 = 2 * 10^6

Instruction 수가 같으므로 CPI값이 작은 P2가 실행 속도가 빠르다.

# 1.7.a
A : (1.1s / 1ns) / 10^9 = 1.1
B : (1.5s / 1ns) / (1.2 * 10^9) = 1.25

# 1.7.b
execution time = instruction count * CPI / Clock rate

A's execution time : 1 * 10^9 * 1.1 / Clock rate
B's execution time : 1.2 * 10^9 * 1.25 / Clock rate
따라서 A의 코드가 더 빠르다

# 1.9.1
execution time = instruction count * CPI / Clock rate

- processor가 1개일때
= (1 * 2.56 * 10^9 + 12 * 1.28 * 10^9 + 5 * 2.56 * 10^8) / 2G

-processor가 n(>1)개일때
= ((1 * 2.56 * 10^9 / (0.7 * n)) + (12 * 1.28 * 10^9 / (0.7 * n)) + (5 * 2.56 * 10^8))/ 2G

processor 갯수 실행 시간 1 processor 대비 속도
1 9.6초 100%
2 7.0초 136%
4 3.8초 250%
8 2.2초 429%

# 1.9.2
- processor가 1개일때
= (2 * 2.56 * 10^9 + 12 * 1.28 * 10^9 + 5 * 2.56 * 10^8) / 2G

-processor가 n(>1)개일때
= ((2 * 2.56 * 10^9 / (0.7 * n)) + (12 * 1.28 * 10^9 / (0.7 * n)) + (5 * 2.56 * 10^8))/ 2G

processor 갯수 실행 시간
1 10.9초
2 8.0초
4 4.3초
8 2.5초

# 1.9.3
 (1 * 2.56 * 10^9 + x * 1.28 * 10^9 + 5 * 2.56 * 10^8) / 2G
= ((1 * 2.56 * 10^9 / (0.7 * 4)) + (12 * 1.28 * 10^9 / (0.7 * 4)) + (5 * 2.56 * 10^8))/ 2G

에서 x (new CPI of l/s instruction) = 3

# 1.12.1
실행시간 = CPI * Insturction 갯수 / Clock rate

P1 : 1.125s
P2 : 0.25s

따라서 Clock rate가 높다고 해서 성능이 좋은것은 아니다.

# 1.12.2
#1.12.2에서 P1의 실행시간을 5로 나누어주면(명령어 갯수가 1/5이므로)

P1_new = 0.225s

0.225s 동안 P2는
0.225 / 0.25 * 1.0 * 10^9 = 9 * 10^8 개의 명령어를 실행할 수 있다.

# 1.12.3
IPS = Clock rate / CPI 이고 MIPS = IPS / 10^6에 비례한다.

MIPS
P1 4444.4
P2 4000

따라서 MIPS가 높다고 processor의 성능이 높지는 않다. (P2의 성능이 더 높기때문)

# 1.12.4
Instruction 수행 속도가 40% 이므로 P1 = 2.8125s / P2 = 0.625

# 1.14 
program 실행시간을 구하면 아래와 같다.
106*(50*1 + 110*1 + 80*4 + 16*2) / 2000000000
= 0.000027136s

# 1.14.1
실행 시간이 절반(0.000013568s)이 되어야 하므로...
FP의 new CPI를 x라고 두면
106*(50*x + 110*1 + 80*4 + 16*2) / 2000000000 = 0.000013568
x = -4.12 이므로 불가능하다.

# 1.14.2
실행 시간이 절반(0.000013568s)이 되어야 하므로...
LS의 new CPI를 x라고 두면
106*(50*1 + 110*1 + 80*x + 16*2) / 2000000000 = 0.000013568
x = 0.8

# 1.14.3
CPI가 각각 0.6, 0.6, 2.8, 1.4 이므로 실행 시간을 계산하면 아래와 같다.
106*(50*0.6 + 110*0.6 + 80*2.8 + 16*1.4) / 2000000000
= 0.0000181472s

따라서 전체적인 실행속도 약 50% 증가한다.

 

==========================
컴퓨터 구조 Chapter 2 Exercises 과제

==========================

# 2.4
sll $t0, $s0, 2 # t0 = f * 4
add $t0, $s6, $t0 # t0 = &A[f]
sll $t1, $s1, 2 # t1 = g * 4
add $t1, $s7, $t1 # t1 = &B[g]
lw $s0, 0($t0) # f = A[f]
addi $t2, $t0, 4 # t2 = t0 + 4 // (t2 = &A[f+1] 과 동치)
lw $t0, 0($t2) # t0 = *t2 //(t0 = A[f+1] 과 동치)
add $t0, $t0, $s0 # t0 += s0 //(t0 = A[f] + A[f+1])
sw $t0, 0($t1) # B[g] = t0 //(B[g] = A[f] + A[f+1])

# 2.6.1
데이터들이 int (4byte) 크기를 가진다고 가정하였으나, "4"는 Address 38에 위치하므로, Address 40에 있는 "1"과 충돌한다. 따라서 Address 38이 28의 오타라고 가정하고 문제를 풀었다.

int t0 = Array[0];
int t1 = Array[1];
Array[0] = Array[4];
Array[4] = Array[3];
Array[3] = t1;
Array[1] = t0;

#2.6.2
lw $t0, 0($s6) #int t0 = Array[0];
lw $t1, 4($s6) #int t1 = Array[1];
lw $t2, 16($s6)
sw $t2, 0($s6) #Array[0] = Array[4];
lw $t2, 12($s6)
sw $t2, 16($s6) #Array[4] = Array[3];
sw $t1, 12($s6) #Array[3] = t1;
sw $t0, 4($s6) #Array[1] = t0;

# 2.9
sll $t0, $s3, 2
add $t0, $t0, $s6
lw $t0, 0($t0) # t0 = A[i];
sll $t1, $s4, 2
add $t1, $t1, $s6
lw $t1, 0($t1) # t1 = A[j];
add $t0, $t0, $t1 # t0 += t1;
sw $t0, 32($s7) # B[8] = t0;

# 2.15
sw는 I-type instruction 이고, opcode는 101011이다.
$t1과 $t2는 각각 01001, 01010의 값을 가진다.
$t1이 rt이고 $t2가 rs이고,
I-type은 opcode (6bit) + rs(5bit) + rt(5bit) + address(16bit) 의 구조를 가지므로
101011 01010 01001 0000000000100000 이다.

# 2.19.1
shift연산을 44칸 하면 $t2는 0x00000000이 된다.
여기서 $t1과 or연산을 하면 $t2는 $t1값을 가지게 되므로
$t2 : 0x12345678

# 2.19.2
shift연산을 4칸 하면 $t2는 0xAAAAAAA0이 된다.
-1은 0xFFFFFFFF 이므로 and연산을 하면 $t2의 값을 바뀌지 않는다.
$t2 : 0xAAAAAAA0

# 2.19.3
shift연산을 우측으로 3칸 하면 $t2는 0x15555555가 된다.
이 때 0XFFEF와 and연산을 하면 다음과 같다.
0x15555555 = 0001 0101 0101 0101 0101 0101 0101 0101
0x0000FFEF = 0000 0000 0000 0000 1111 1111 1110 1111
0x15555555&0xFFEF = 0000 0000 0000 0000 0101 0101 0100 0101
= 0x00005545

# 2.23
0은 $t0보다 작기 때문에 slt 연산을 하면 $t2에 값 1이 들어간다.
$t2 (= 1)과 $0이 다르기 때문에 j 명령어를 건너뛰고 ELSE label로 넘어간다.
따라서 addi $t2, $t2, 2 명령이 실행되게 되고, $t2값에 2가 더해지므로
$t2 에는 값 3이 들어가게 된다.

# 2.31
fib:
addi $sp, $sp,  -8
sw $ra, 4($sp)
sw $a0, 0($sp)

beq $a0, $zero, R0

addi $t0, $zero, 1
beq $a0, $t0, R1

addi $a0, $a0, -1
jal fib

lw $a0, 0($sp)
sw $v0, 0($sp)
addi $a0, $a0, -2
jal fib

lw $t0, 0($sp)
add $v0, $v0, $t0
lw $ra, 4($sp)
j END

R0:
addi $v0, $zero, 0
j END

R1:
addi $v0, $zero, 1

END:
addi $sp, $s8, 8
jr $ra


fib(0) : 8개의 명령이 필요하다.
fib(1) : 9개의 명령이 필요하다.
fib(2) :  18개의 명령 + fib(0) + fib(1)개의 명령이 필요하다. 즉 35개의 명령이 필요하다.
fib(n) : 18개의 명령 + fib(n-1) + fib(n-2)개의 명령이 필요하다.

# 2.32
C코드를 주어준다고 하였으나, 문제에 C 코드가 없는 관계로 2.31의 코드를 이용해 n=5일때 필요한 instruction 갯수를 구했습니다.
fib(3) = 18 + fib(2) + fib(1) = 18 + 35 + 9 = 62
fib(4) = 18 + fib(3) + fib(2) = 18 + 62 + 35 = 115
fib(5) = 18 + fib(4) + fib(3) = 195
따라서 n=5일 때 195개의 instruciton 이 실행된다.

 

 

==========================
컴퓨터 구조 Chapter 2 Exercises 과제

==========================



# 7.6

Symbol Entry Type Where Section
---------------------------------------------------------------------
buf Y extern main.o .data
bufp0 Y global swap.o .data
bufp1 Y local swap.o .bss
swap Y global swap.o .text
temp N stack
incr Y local swap.o .text
count Y local swap.o .data



# 7.7

변수 선언시 static을 붙여서 충돌을 해결해 주면 된다.

double x;
--> static double x;

* 참고 자료 : https://koyo.kr/post/csapp-linking-1/



# 7.8.A
(a) REF(main.1) --> DEF(main.1)
strong 심볼인 main 함수가 우선이다.
(b) REF(main.2) --> DEF(main.2)
static인 main 변수가 우선이다.

# 7.8.B
(a) UNKNOWN
(b) UNKNOWN
a, b 모두 week symbol 두 개가 충돌하므로, UNKNOWN

# 7.8.C
(a), (b) ERROR
a, b 모두 strong symbol 두 개가 충돌하므로, ERROR




# 7.10

(A) gcc p.o libx.a
(B) gcc p.o libx.a liby.a libx.a
(C) gcc p.o libx.a liby.a libx.a libz.a

* 참고 자료 : Example 7.1





# 7.13

x, xp가 .data section에서 relocation 되고, p2, p3가 .text section에서 reloaction 된다.
(추가적인 공부가 필요할 것 같습니다)

 

 

 

 

==========================
컴퓨터 구조 Chapter 4 Exercises 과제

==========================



# 3.9 > Assume 151 and 214 are signed 8-bit decimal integers stored in
two’s complement format. Calculate 151  + 214 using saturating arithmetic. Th e
result should be written in decimal. Show your work.

151 : 1001 0111
214 : 1101 0110
151+214 : 1 0110 1101

overflow를 제거하면 0110 1101이므로 답은 109


# 3.14 > Calculate the time necessary to perform a multiply using the
approach given in Figures 3.3 and 3.4 if an integer is 8 bits wide and each step
of the operation takes 4 time units. Assume that in step 1a an addition is always
performed—either the multiplicand will be added, or a zero will be. Also assume
that the registers have already been initialized (you are just counting how long it
takes to do the multiplication loop itself). If this is being done in hardware, the
shift s of the multiplicand and multiplier can be done simultaneously. If this is being
done in soft ware, they will have to be done one aft er the other. Solve for each case.

SW : 한 반복당 add 1회, shift 2회 일어나고, 총 8번 반복이 일어나므로, 3 * 8 * 4 = 96
HW : 한 반복당 add 1회, shift 1회 일어나고, 총 8번 반복이 일어나므로, 2 * 8 * 4 = 64



# 3.17 > As discussed in the text, one possible performance enhancement
is to do a shift and add instead of an actual multiplication. Since 9 x 6, for example,
can be written (2 x 2 x 2 + 1) x 6, we can calculate 9 x 6 by shift ing 6 to the left 3
times and then adding 6 to that result. Show the best way to calculate  33 x 55
using shift s and adds/subtracts. Assume both inputs are 8-bit unsigned integers.

* 문제에서 0 x 33 x 0 x 55 라고 표시된 것을 33 x 55로 수정하여 풀었습니다.

33 = 2^5 + 2^4 + 2 + 1 이므로
(55를 5번 left shift 시킨 값) + (55를 4번 left shift 시킨 값) + (55를 1번 left shift 시킨 값) + 55
를 통해 33 x 55를 구할 수 있다.

55를 5번 left shift 시킨 값 : 1010 1010 0000
55를 4번 left shift 시킨 값 : 0101 0101 0000
55를 1번 left shift 시킨 값 : 0000 1010 1010
55를 0번 left shift 시킨 값 : 0000 0101 0101

SUM : 1 0000 1110 1111 = 4335



# 3.23 > Write down the binary representation of the decimal number
63.25 assuming the IEEE 754 single precision format.

63.25 = 111111(2) + 1/4 이므로
63.25 = 111111.01(2)

sign은 0이고, Mantissa는 1.1111101이며, exponent는 5(bias : 132)로 Normalize 할 수 있다.

따라서 IEEE754 포맷으로 나타내면
0 / 1000 0100 / 111 1101 0000 0000 0000 0000



# 3.41 > Using the IEEE 754 fl oating point format, write down the bit
pattern that would represent 1/4. Can you represent 1/4 exactly?

-1/4는  sign이 1이고, mantissa가 0이고, exponent가 -2인(bias : 125) 값이다.

따라서 IEEE 754 포맷으로 나타내면 아래와 같다.
1 / 0111 1101 / 000 0000 0000 0000 0000 0000

* 참고자료 : https://www.h-schmidt.net/FloatConverter/IEEE754.html

IEEE-754 Floating Point Converter

 

 

==========================
컴퓨터 구조 Chapter 5 Exercises 과제

==========================



# 4.4.1
ADD를 거치는 경로는 70ps가 소요되고
I-Mem을 거치는 경로는 200ps가 소요되므로
총 소요시간은 200ps

# 4.4.2
명령어가 unconditional PC-relative branch일 경우
cycle은 상단 mux를 통과하는 가장 긴 경로를 의미한다.
따라서 Instruction memory, Sign-extend, shift left 2, Add, Mux를 통과하는 경로의 시간은
(200+15+10+70+20)ps = 315ps이다.

# 4.4.3
명령어가 conditional PC-relative branch가 되면
ALU까지 가는 과정이 추가된다.
따라서 총 cycle time은 420ps이다.

# 4.4.4
unconditional branch

# 4.4.5
conditional branch

# 4.4.6
add instruction와 conditional banch의 critical path가 다르기 때문에 add instruction에 의해 latency가 증가한다.

# 4.8.1
파이프라인이 없다면 각 단계의 latency를 더한 1250ps가 걸리고
파이프라인이 있다면 각 단계 중 가장 높은 latency인 350ps가 걸린다.

# 4.8.2
lw 명령어는 다섯 단계를 모두 거치므로 #4.8.1과 동일하다.

# 4.8.3
ID stage를 split하면 ID stage의 latency가 175ps가 되므로, 파이프라인을 가정했을 때, 총 latency는 300ps가 된다.(MEM의 latency)

# 4.8.4
데이터 메모리는 lw명령어와 sw명령어만이 이용하므로, utilization = 35%

# 4.8.5
alu, lw만 이용하므로 utilization = 65%

# 4.8.6
#4.8.1에서 확인한 바와 같이 execution times는 1250ps에서 350ps가 되고, 3.57배 증가한다.

# 4.10.1
sw 와 lw 명령어로 인해 add 명령어의 수행이 지연된다.
총 2 cycle동안 stalling이 발생하므로
기존 9 cycle에 2 cycle을 더한 11cycle이 소요된다.
따라서 총 소요시간은 11 * 200ps = 2200ps

# 4.10.2
stalling이 발생하지 않으면 소요시간은 9 * 200ps = 1800ps

# 4.10.3
branch 명령어가 하나이므로 한 사이클만큼 차이난다.

# 4.10.4
EX stage와 MEM stage가 합쳐지면 210ps의 latency를 갖는다,(190+20)
따라서 총 소요시간은 8 * 210 = 1680ps
# 4.10.2와 비교하면 1.07배 증가한다.

# 4.10.5
ID stage와 EX stage의 latency의 값이 바뀌어도, 가장 큰 latency는 200ps로 동일하므로
속도는 같다.

# 4.10.6
한 사이클이 추가되고, 최대 latency는 같으므로 총 소요시간은 12 * 200ps = 2400ps

# 4.12.1
stalling으로 인하여 CPI가 (1.05 + 1.2 + 1.1) * 2 + (1.1 + 1.05) = 1.85가 된다.

# 4.12.2
마찬가지로 CPI가 1.2로 증가한다.

# 4.12.3
(1.2 + 1.05 + 1.1 + 1.1) = 1.45
이고 두 번째 경우는
(1.05 + 1.2 + 1.1) = 1.35 이다.

# 4.12.4
speedup을 CPI 비율로 정의한다면
1.85 / 1.2 = 1.54이다.

# 4.12.5
clock cycle은 250ps이지만 full forwarding인 경우 180ps로 감소한다.
(0.72배)

# 4.15.1
3 * 0.55 * 0.25 = 0.4125

# 4.15.2
3 * 0.45 * 0.25 = 0.3375

# 4.15.3
3 * 0.15 * 0.25 = 0.1125

# 4.15.4
3 * 0.15 * 0.125 = 0.05625
1.1125 / 1.05625 = 1.05

# 4.15.5
1.1125 / (0.125 + 0.05625) = 0.94

# 4.16.1
T가 5개 중 3개이므로 0.6
NT가 5개중 2개이므로 0.4

# 4.16.2
T와 NT로 이루어진 쌍은 4쌍이므로 0.25

# 4.16.5
존재할 수 없다.

 

 

 

==========================
컴퓨터 구조 Chapter 6 Exercises 과제

==========================

# 5.2.1
cache의 크기가 16word 이므로 16word마다 index가 중복된다
그러나 한 블럭당 크기가 1word이므로 모든 데이터가 miss

# 5.2.2
cache의 크기가 8word이므로 8word마다 idnex가 중복된다.
더불어, 한 블럭당 크기가 2word이므로
예를들어 주소가 0000 .... 0000 0011 이면 index가 001, offset이 1이 된다.

따라서 2, 190, 181이 hit

# 5.2.3
C1은 hit가 일어나지 않으므로
AMAT = 2 + 25 * 1 = 27

C2는 hit가 한 개 일어나므로, AMAT = 3 + 25 * 11/12 = 25.9

C3은 hit가 두 개 일어나므로, AMAT = 5 + 25 * 10/12 = 25.8

# 5.2.4
tag는 17bit, index는 12bit, offset은 3 bit을 가진다.
하나의 블록은 64bit의 데이터, 17bit의 태그, 1bit의 valid bit을 가지므로, 335872bit이 필요하다.

# 5.3.1
8 words (32/(5-1))

# 5.3.2
index가 5bit이므로 32개

# 5.3.3
한 데이터 엔트리는 22bit의 태그, 256bit의 데이터, 1bit의 valid bit 을 가지므로
256/279 = 0.918

# 5.3.4
4번

# 5.3.5
1/3