2-1) CA1 정리

Chapter 2: Instructions - Language of the Computer

▶

중간고사 기출문제 풀이

▶

2019

1. What is the final value of $s

assembly

addi $s2, $0, 9
--> 9

assembly

addi $t0, $0, 3
sll $2, $t0, 3      # sll 3 == 2의 3승 배
--> 24

assembly

addi $t0, $0, 12   
addi $t1, $0, 9
xor $s2, $t0, $t1    # 1100 ^ 1001 == 0101  
--> 5

assembly

addi $t0, $0, -2
addi $t1, $0, -1
nor $s2, $t0, $t1    # 11111...111 nor 11111...110
--> 00000...000 == 0

assembly

addi $t0, $0, 3
addi $t1, $0, 3
slt $s2, $t0, $t1     # 같으므로(작지 않으므로) $s2에 0 저장 
bne $s2, $0, ELSE     # 0은 0과 같으므로 통과
nop
j DONE                # DONE으로 분기
nop
ELSE: addi $s2, $s2, 2
DONE: addi $s2, $s2, 1
--> 1

assembly

addi $t1, $0, 100
addi $s2, $0, 0
LO: slt $t2, $0, $t1     # 99부터 1까지 모두 더하기
	beq $t2, $0, DONE
	nop
	addi $t1, $t1, -1
	addi $s2, $s2, $t1
	j LO
	nop
	
DONE:
--> 4950

2. Translate MIPS assembly code from C code. Assume that f=$1, g=$2, h=$3, i=$4.

(a) f = g – h;

assembly

sub $1, $2, $3

(b) f = (g+h)-(f+i)

assembly

add $7, $2, $3
add $8, $1, $4
sub $1, $7, $8

assembly

addi $7, $0, 3
sll $1, $7, 4

(d) f = g*h-3

assembly

mul $5, $2, $3
addi $1, $5, -3

(e) if(i<5) i++; else i = -1;

assembly

slti $5, $4, 5    #if(i < 5)
beq $5, $0, XXX
nop
addi $4, $4, 1    #i++
j EXIT
nop

XXX: addi $4, $0, -1    #i = -1
EXIT:

(f) int f(int a, int b) {
return f(a-1,b) + f(a, b-1);
}

assembly

addi $sp, $sp, -16
sw $a0, 8($sp)
sw $a1, 4($sp)
sw $ra, 0($sp)
addi $a0, $a0, -1    # a-1
jal f
nop

sw $v0, 12($sp)
lw $a0, 8($sp)
lw $a1, 4($sp)
addi $a1, $a1, -1    #b-1
jal f
nop

lw $t0, 12($sp)
add $v0, $t0, $v0
lw $ra, 0($sp)
addi $sp, $sp, 16
jr $ra
nop

(g) int fib(int n) {
if(n < 3) return n;
else return fib(n-1) + fib(n-2);
}

assembly

fib: 
	addi $sp, $sp, -12     # 스택에 12 바이트 공간 할당 : n, fib(n-1), $ra 저장용
	sw $a0, 0($sp)         # 현재 n 값 스택에 저장
	sw $ra, 8($sp)         # 현재 복귀 주소 스택에 저장
	slti $t0, $a0, 3       # n<3 --> $t0 = 1 --> return n
	beq $t0, $0, EL        # n>=3 --> $t0 = 0 --> ELSE
	nop 
	
	add $a0, $0, $a0       #return n
	j R
	nop

EL:
	addi $a0, $a0, -1      # n-1
	jal fib                # fib(n-1) 재귀 호출
	nop

	sw $v0, 4($sp)         # fib(n-1)결과를 스택에 저장
	lw $a0, 0($sp)         # 원래 n 값 복원
	addi $a0, $a0, -2      # n-2
	jal fib                # fib(n-2) 재귀 호출
	nop

	lw $t0, 4($sp)         # 스택에서 fib(n-1) 결과 복원
	addi $v0, $t0, $v0     # fib(n-1) + fib(n-2) 계산후 $v0에 저장

R:
	lw $ra, 8($sp)         # 복귀 주소 복원
	addi $sp, $sp, 12      # 스택 포인터 원위치
	jr $ra                 # 호출자로 복귀
	nop

(h) int main() {
return fib(5); }

assembly

main:
	addi $sp, $sp, -4       # 스택에 4 바이트 공간 할당
	sw $ra, 0($sp)          # 메인 함수 복귀 주소 스택에 저장
	addi $a0, $0, 5      
	jal fib                 # 피보나치 함수 호출
	nop
	
	lw $ra, 0($sp)          # 스택에 저장된 복귀 주소 꺼내기
	addi $sp, $sp, 4        # 메인 함수 복귀 주소로 되돌리기
	jr $ra                  # 메인 함수 종료
	nop

(i) void numncpy(int* x, int* y, int n) {
for(int i = 0 ; y[i] ≠ 0, i++) {
}

assembly

_numncpy:                # int* x = $a0, * y = $a1, n = $a2, i = $t0
	addi $t0, $0, 0        # x[i] = $t4, y[i] = $t3
  
Loop: 
	add $t3, $a1, $t0      # y의 첫번째 칸에 접근
	lw $t1, 0($t3)         # y[i]의 값 불러오기
	beq $t1, $0, EXIT      # 불러온 값이 0이라면 탈출
	nop
	
	add $t4, $a0, $t0      # 
	sw $t1, 0($t4)
	addi $t0, $t0, 1
	j Loop
	nop
	
EXIT: 
	jr $ra
	nop

(j) int f(int a, int b, int c, int d) {
return g(g(a+b, c), d)); }

assembly

▶

2022

1.
- (a)

javascript

if (i>=5) i++; else i=-1;

javascript

___ $5, $4, 5
___ $5, $0, XXX
nop
addi ___, ___, 1
j EXIT
nop
XXX: ___ ___, ___, ___
EXIT:

답

javascript

slti $5, $4, 5
bnq $5, $0, XXX
nop
addi $4, $0, 1
j EXIT
nop
XXX: addi $4, $0, -1
EXIT:

javascript

int f(int a, int b){
	return f(1,2) + f(b,a);}

javascript

f: addi $sp, $sp,   
sw $a0, 0($sp)
sw $a1,    
sw $ra,    
addi    , $0, 1
addi    , $0, 2
jal f
nop

    $v0,    
    $a0,    
    $a1,    
jal f

nop
    $t0,    
add    , $t0,    
lw $ra,    
addi $sp, $sp,    
jr $ra
nop

답

assembly

f: addi $sp, $sp, -16
sw $a0, 0($sp)    # a
sw $a1, 4($sp)    # b
sw $ra, 8($sp)
addi $a0, $0, 1
addi $a1, $0, 2
jal f              #return f(1,2)
nop

sw $v0, 12($sp)     
lw $a0, 4($sp)     # b
lw $a1, 0($sp)     # a 
jal f              #return f(b,a)
nop

lw $t0, 12($sp)
add $v0, $t0, $v0
lw $ra, 8($sp)
addi $sp, $sp, 16

피보나치 ㅇㅇ

javascript

void numncpy(int* x, int* y, int n){
	for(int i=0;i<n;i++)
		x[i] = y[i];
}

_numncpy: addi $t0, $0, 0
Loop: slt $t1, $t0, ___
			___ $t1, $0, ___
			nop
			sll $t5, $0, ___
			___ ___, ___, ___
			lw ___, 0($t3)
			___ ___, ___, ___
			sw $t2, 0($t4)
			addi $t0, $t0, ___
			j Loop
			nop
EXIT:

답

assembly

void numncpy(int* x, int* y, int n){
	for(int i=0;i<n;i++)
		x[i] = y[i];
}

_numncpy: addi $t0, $0, 0
Loop: slt $t1, $t0, $a2
			beq $t1, $0, EXIT
			nop
			sll $t5, $0, 2     #숫자는 x4 씩
			add $t3, $a1, $t5
			lw $t2, 0($t3)
			add $t4, $a0, $t5
			sw $t2, 0($t4)
			addi $t0, $t0, 1
			j Loop
			nop
EXIT:

3. c 코드 mips로 바꾸기

f(int a[10], int b[10]){
	a[2] = b[6];
}

답

assembly

f: 
	lw $t0, 24($a1)
	sw $t0, 8($a0)
	
	jr $ra 
	nop

4. (10pt) Compare the RISC and the CISC machine in terms of the number of instructions, the regularity of the instruction format, and the decoding logic for instructions. State which category MIPS, ARM, and x86 belong to, respective이거
5)
답
1. (1): beq (2): sw, (3): 16($sp), (4): 20
2. 스택을 그려라..?
  이거 박으면 되나
  문제 골때리네

▶

2024

2. f= $1, g=$2, h=$3, i=$4.

(d) if(i ≥ 5) i++; else i = -1;

assembly

slti $5, $4, 5
bne $5, $0, XXX
nop
addi $4, $4, 1
j EXIT
nop
XXX: addi $4, $0, -1
EXIT:

(e) int fib(int n) { if(n < 3) return 1; else return fib(n-1) + fib(n-2); }

assembly

fib:
	addi $sp, $sp, -12
	sw $s0, 0($sp)
	sw $s1, 4($sp)
	sw $ra, 8($sp)
	slti $t0, $a0, 3 
	beq $t0, $0, EL
	nop
	
	addi $v0, $0, 1       
	j R
	nop
	
EL: 
	addi $s0, $a0, 0
	addi $a0, $a0, -1
	jal fib
	nop
	
	addi $s1, $v0, 0
	addi $a0, $s0, -2
	jal fib
	nop
	
	add $v0, $s1, $v0
R: 
	lw $s0, 0($sp)
	lw $s1, 4($sp)
	lw $ra, 8($sp)
	addi $sp, $sp, 12
	jr $ra
	nop

f int main() { return fib(5); }

assembly

main:
	addi $sp, $sp, -4
	sw $ra, 0($sp)
	addi $a0, $0, 5
	jal fib
	nop
	
	lw $ra, 0($sp)
	addi $sp, $sp, 4
	jr $ra
	nop

assembly

_strcpy:
	addi $t0, $0, 0
Loop:	
	addi $t1, $a1, $t0       # t1 = &y[i]
	lb $t3, 0($t2)           # t3 = y[i]
	addi $t2, $a0, $t0       # t2 = &x[i]
	sb $t3, 0($t2)           # x[i] = t3
	beq $t3, $0, EXIT        # y[i] = 0이면 종료
	nop
	addi $t0, $t0, 1         # i++ 
	j Loop
EXIT:

assembly

reverse:  # a0 는 문자열의 시작 포인터를 담고 있음 (0)
	addi $sp, $sp, -12      # 스택에 12바이트 공간 확보
	sw $ra, 8($sp)          # 복귀 주소 ra 저장
	sw $s0, 4($sp)          # s0 (앞 인덱스) 저장
	sw $s1, 0($sp)          # s1 (끝 인덱스) 저장
	addi $s0, $zero, 0      # s0 = 문자열 시작 주소
	addi $s1, $a0, $a1      # s1 = 문자열 끝 주소
	subi $s1, $s1, 1        # s1을 문자열 끝 (널 뒤) 바로 전 문자 위치로 설정
	loop:
		beq $s0, $s1, end       # 앞 뒤 포인터가 만나면 종료
		lb $t0, ($s0)           # 앞쪽 문자 가져오기
		lb $t1, ($s1)           # 뒤쪽 문자 가져오기
		sb $t1, ($s0)           # 뒤쪽 문자를 앞쪽에 대입
		sb $t0, ($s1)           # 앞쪽 문자를 뒤쪽에 대입
		addi $s0, $s0, 1        # 앞쪽 포인터 뒤로 이동
		subi $s1, $s1, 1        # 뒤쪽 포인터 앞으로 이동
		j loop          
		nop
	end:
		lw $s0, 4($sp)          # 레지스터 $s0 복원
		lw $s1, 0($sp)          # 레지스터 $s1 복원
		lw $ra, 8($sp)          # 복귀 주소 복원
		addi $sp, $sp, 12       # 스택 포인터 원위치 복구
		jr $ra
		nop

assembly

is_even:
	addi $sp, $sp, -4
	sw $ra, 0($sp)
	addi $t0, $a0, 0
	andi $t0, $t0, 1         
	addi $v0, $zero, 1       # 기본값 v0 = 1
	beq $t0, $zero, end      # t0 = 0이면 짝수
	addi $v0, $zero, 0       # 홀수면 0	
	end:
		lw $ra, 0($sp)           # 복귀 주소 복원
		addi $sp, $sp, 4         # 스택 포인터 복구
		jr $ra                   # 호출 복귀
		nop

5. (20pt) Consider two different implementations of the same instruction set architecture. The instructions can be divided into four classes according to their CPI (class A, B, C, and D). P1 with a clock rate of 2 GHz and CPIs of 1, 2, 3, and 4, and P2 with a clock rate of 3 GHz and CPIs of 2, 2, 2, and 2. Given a program with a dynamic instruction count of 10⁶ instructions divided into classes as follows: 10% class A, 20% class B, 50% class C, and 20% class D, which implementation is faster?
- a. What is the global CPI for each implementation?
- b. Find the clock cycles required in both cases.

▶

solution

CPI global = sum of (kclass * kCPI)
P1 = 0.1 * 1 + 0.2 * 2 + 0.5 * 3 + 0.2 * 4 = 2.8
P2 = 0.1 * 2 + 0.2 * 2 + 0.5 * 2 + 0.2 * 2 = 2.0
Clock Cycles = I * CPI global
P1 = 2.8 * 10^6 Cycles
P2 = 2.0 * 10^6 Cycles

P2 is faster because it has a lower global CPI, so it uses fewer cycles. Even with a higher clock rate, P2 completes the same instruction in less time.

6. (20 pt) Assume that the energy consumption of a processor core can be described by the equation Energy = 0.2 × s × V², where s is the execution time in seconds, and the operating voltage V is given by V = Frequency (in GHz). So at 1 GHz, V=1.0 V; if s=10 s then Energy=2 (=0.2×10×1²). If frequency=0 then V=0 and no energy is consumed. When program A runs at 1 GHz it takes 2 s.
- (1) If we run program A at 4 GHz, what voltage do we use and how much energy is consumed?
- (2) If V=0.5 V, what is the frequency and how much energy is consumed to finish program A?

▶

solution

문제에서 A는 1GHz에서 2초가 걸린다고 되어있다. 만약 4GHz를 가한다면 A에 전압 4V가 들어가게 되고, 실행시간은 0.5초로 줄어들게 된다. 따라서 E는 0.2 * 0.5 * 16 = 1.6이 된다.
0.5V로 작동시킨다면 실행시간은 4초가 걸린다. 따라서 E는 0.2 * 4 * 0.25 = 0.2가 필요하다.

▶

MIPS 레지스터 용도 정리

$t (temporary) — 임시값

$t0 ~ $t9 (10개)
함수 호출 시 보존 안 됨 (caller가 필요하면 직접 저장)
중간 계산, 조건 비교 등 짧게 쓸 때 사용

assembly

addi $t0, $0, 10    # 임시로 10 저장
slt  $t1, $t0, $0   # 비교 결과 임시 저장

$a (argument) — 함수 인자

$a0 ~ $a3 (4개)
함수 호출할 때 인자를 넘기는 용도
jal 전에 세팅

assembly

addi $a0, $0, 5     # fib(5) 호출 전 인자 세팅
jal  fib

$s (saved) — 보존값

$s0 ~ $s7 (8개)
함수 호출 시 보존됨 (callee가 스택에 저장 후 복원해야 함)
재귀나 함수 간에 값을 유지해야 할 때 사용

assembly

sw   $s0, 0($sp)    # 함수 시작 시 저장
# ... 사용 ...
lw   $s0, 0($sp)    # 함수 끝에 복원

$v (value) — 반환값

$v0 ~ $v1 (2개)
함수의 리턴값을 담는 용도
jr $ra 전에 세팅

assembly

addi $v0, $0, 1     # return 1
jr   $ra

요약

값을 넘길 때 → $a
값을 받을 때 → $v
잠깐 계산할 때 → $t
함수 걸쳐서 유지할 때 → $s

▶

2025 midterm

Note that 0x... denotes the hexadecimal number.

1. Value of `$s1`

(10pt) What is the value of $s1 after executing the following instruction sequences?

(a)

addi $s1, $0, 8
sll $s1, $s1, 2

답

rust

(b)

addi $t0, $0, 10
addi $t1, $0, 3
and $s1, $t0, $t1

답

rust

(c)

addi $t0, $0, -5
sub $s1, $0, $t0

답

rust

(d)

addi $t0, $0, 3
sll $s1, $t0, 2

답

rust

(e)

addi $t0, $0, 2
addi $s1, $0, 0
LOOP: slt $t2, $0, $t0
      beq $t2, $0, DONE
      addi $t0, $t0, -1
      addi $s1, $s1, $t0
      j LOOP
DONE:

답

rust

2. Translate MIPS assembly code from C code

Assume $1 = x, $2 = y, $3 = z, $4 = w.

(a) (3pt)

x = y + z;

답

rust

add $1, $2, $3

(b) (3pt)

x = (y + z) << 2;

답

rust

add $2, $2, $3
sll $1, $2, 2

(c) (4pt)

x = ~(y & z);

답

rust

and $5, $2, $3
nor $1, $5, $5

(d) (5pt)

if(w < 0) w = 0;

답

rust

slt $5, $4, $0
beq $5, $0, EXIT
nop
addi $4, $0, 0
EXIT:

(e) (17pt)

int fib(int n) {
  if(n < 3) return 1;
  else return fib(n-1) + fib(n-2);
}

assembly

fib: addi $sp,$sp,____
     sw $s0, ____
     sw $s1, ____
     sw $ra, ____
     slti $t0, $a0, ____
     ___ $t0, $0, EL
     addi ___,$0,1
     j R
EL:  addi $s0, $a0, 0
     addi ____, $a0, ____
     jal fibo
     addi $s1, ___, 0
     addi ____, $s0, ____
     jal fibo
     add $v0, ___, $v0
R:   lw $s0, ______
     lw $s1, ______
     lw $ra, ______
     addi $sp, $sp, _____
     jr $ra

답

rust

fib: addi $sp,$sp,-12
     sw $s0, 0($sp)
     sw $s1, 4($sp)
     sw $ra, 8($sp)
     slti $t0, $a0, 3
     beq $t0, $0, EL
     addi $v0,$0,1
     j R
EL:  addi $s0, $a0, 0
     addi $a0, $a0, -1
     jal fib
     addi $s1, $v0, 0
     addi $a0, $s0, -2
     jal fib
     add $v0, $s1, $v0
R:   lw $s0, 0($sp)
     lw $s1, 4($sp)
     lw $ra, 8($sp)
     addi $sp, $sp, 12
     jr $ra

(f) (7pt)

int main() {
  return fib(5);
}

assembly

main: addi $sp, $sp, -4
      sw ___, _____
      addi _____, $0, _____
      jal fib
      lw ____, _____
      addi $sp, $sp, _____
      jr $ra

답

rust

main: addi $sp, $sp, -4
      sw $ra, 0($sp)
      addi $a0, $0, 5
      jal fib
      lw $ra, 0($sp)
      addi $sp, $sp, 4
      jr $ra

(g) (6pt)

void strcpy(char* x, char* y) {
  int i=0;
  while((x[i] = y[i])!=0) I++;
}

_strcpy: addi $t0, $0, 0
Loop:    addi $t1, ____, $t0
         lb ____, 0($t1)
         addi $t2, ____, $t0
         sb $t3, _____
         b__ $t3, $0, EXIT
         addi $t0, $t0, _____
         j Loop
EXIT:

답

assembly

_strcpy:
    addi $t0, $0, 0         # i = 0 (인덱스)
Loop:
    addi $t1, $a1, $t0      # $t1 = src + i
    lb   $t3, 0($t1)        # $t3 = src[i]
    addi $t2, $a0, $t0      # $t2 = dst + i
    sb   $t3, 0($t2)        # dst[i] = src[i]
    beq  $t3, $0, EXIT      # src[i] == '\0' 이면 종료
    addi $t0, $t0, 1        # i++
    j    Loop
EXIT:

4. is_even(n)

(8pt) Write MIPS assembly code for a function is_even(n) that takes an integer n and returns 1 if n is even, or 0 otherwise.

is_even:
  addi $sp, $sp, ___
  sw $ra, ___($sp)
  addi $t0, $a0, ___
  andi $t0, $t0, ___
  addi $v0, $zero, ___
  beq $t0, $zero, end
  addi $v0, $zero, ___
end:
  lw $ra, ___($sp)
  addi $sp, $sp, ___
  jr $ra

답

rust

is_even:
  addi $sp, $sp, -4
  sw $ra, 0($sp)
  addi $t0, $a0, 0
  andi $t0, $t0, 1
  addi $v0, $zero, 1
  beq $t0, $zero, end
  addi $v0, $zero, 0
end:
  lw $ra, 0($sp)
  addi $sp, $sp, 4
  jr $ra

5. Processor comparison

(15pt) Two processors execute the same instruction set.

P1: 2.5GHz clock, CPIs = 1 (A), 3 (B), 2 (C), 5 (D)
P2: 2GHz clock, CPIs = 2 (A), 2 (B), 2 (C), 2 (D)

Dynamic instruction count: 2 × 10^6

20% A
30% B
30% C
20% D

Questions:

(a) What is the global CPI for each processor?
(b) How many clock cycles are needed?
(c) Which processor is faster?

답

💡

(a)

(b)

(c)

6. Dynamic energy consumption

(20pt) The dynamic energy consumption of a processor is given by:

Energy = 0.5 × s × V^2

where s is time (seconds), and voltage is:

V = 0.5 + 0.5 × Frequency

with frequency in GHz.

Given: program B takes 3 seconds at 1GHz.

(a) How much energy is consumed at 1GHz?

(b) If we run program B at 3GHz, how much voltage must be supplied, and how much energy will be consumed?

답

💡

(a)

(b)

7. RISC vs CISC

(10pt) Compare the RISC and the CISC machine in terms of:

the number of instructions
the regularity of the instruction format
the decoding logic for instructions

Also state which category the following belong to:

MIPS
ARM
x86

답

💡

RISC has fewer instructions, more regular instruction formats, and simpler decoding logic. CISC has more instructions, less regular instruction formats, and more complex decoding logic. MIPS and ARM are RISC, while x86 is CISC.

▶

2024 midterm

Note that 0x... denotes the hexadecimal number.
Use the following operations:
- add, addi, sub, mul, div, slt, slti, and, or, nor, xor, sll, srl, sra, andi, ori, nori, xori, nop, lw, sw, beq, bne, j, jr, jal
Use the following registers:
- $a0, $a1, $a2, $a3, $v0, $v1, $ra, $sp, $pc, ...
- $0, $1, ..., $31
Put nop after beq, bne, j, jal, and jr instructions.

1. Final value of `$s2`

Represent $s2 in hexadecimal or decimal format.

(a)

addi $s2, $0, 2

답

rust

(b)

addi $t0, $0, 7
sll $s2, $t0, 1

답

rust

(c)

addi $t0, $0, 5
addi $t1, $0, 6
xor $s2, $t0, $t1

답

rust

(d)

addi $t0, $0, -9
nor $t1, $t0, $t0
addi $s2, $t1, 1

답

rust

(e)

addi $t0, $0, 4
addi $t1, $0, 3
slt $s2, $t0, $t1
bne $s2, $0, ELSE
nop
j DONE
nop
ELSE: addi $s2, $s2, 2
DONE: addi $s2, $s2, 1

답

rust

(f)

addi $t1, $0, 4
addi $s2, $0, 0
LO: slt $t2, $0, $t1
beq $t2, $0, DONE
nop
addi $t1, $t1, -1
addi $s2, $s2, $t1
j LO
nop
DONE:

답

rust

2. Translate MIPS assembly code from C code

Assume that f = $1, g = $2, h = $3, i = $4.

(a)

f = g + h;

___ $1, $2, $3

답

rust

add $1, $2, $3

(b)

f = (g+h) - (f+i);

add $5, _____, _____
add $6, _____, _____
sub ____, _____, _____

답

rust

add $5, $2, $3
add $6, $1, $4
sub $1, $5, $6

(c)

f = 1 << 3;

addi $5, $0, _____
____ $1, ____, ___

답

rust

addi $5, $0, 1
sll $1, $5, 3

(d)

if( i>=5 ) i++; else i = -1;

___ $5 , $4 , 5
___ $5, $0, XXX
nop
addi ____, _____, 1
j EXIT
nop
XXX: ___ ____, _____, _____
EXIT:

답

rust

slti $5, $4, 5
bne $5, $0, XXX
nop
addi $4, $4, 1
j EXIT
nop
XXX: addi $4, $0, -1
EXIT:

(e)

int fib(int n) {
  if(n < 3) return 1;
  else return fib(n-1) + fib(n-2);
}

fib: addi $sp,$sp,____
     sw $s0, ____
     sw $s1, ____
     sw $ra, ____
     slti $t0, $a0, ____
     ___ $t0, $0, EL
     nop
     addi ___,$0,1
     j R
     nop
EL:  addi $s0, $a0, 0
     addi ____, $a0, ____
     jal fibo
     nop
     addi $s1, ___, 0
     addi ____, $s0, ____
     jal fibo
     nop
     add $v0, ___, $v0
R:   lw $s0, ______
     lw $s1, ______
     lw $ra, ______
     addi $sp, $sp, _____
     jr $ra
     nop

답

rust

fib: addi $sp,$sp, -12
     sw $s0, 0($sp)
     sw $s1, 4($sp)
     sw $ra, 8($sp)
     slti $t0, $a0, 3
     beq $t0, $0, EL
     nop
     addi $v0, $0, 1
     j R
     nop
EL:  addi $s0, $a0, 0
     addi $a0, $a0, -1
     jal fib
     nop
     addi $s1, $v0, 0
     addi $a0, $s0, -2
     jal fib
     nop
     add $v0, $s1, $v0
R:   lw $s0, 0($sp)
     lw $s1, 4($sp)
     lw $ra, 8($sp)
     addi $sp, $sp, 12
     jr $ra
     nop

(f)

int main() {
  return fib(5);
}

main: addi $sp, $sp, -4
      sw ___, _____
      addi _____, $0, _____
      jal fib
      nop
      lw ____, _____
      addi $sp, $sp, _____
      jr $ra
      nop

답

rust

main: addi $sp, $sp, -4
      sw $ra, 0($sp)
      addi $a0, $0, 5
      jal fib
      nop
      lw $ra, 0($sp)
      addi $sp, $sp, 4
      jr $ra
      nop

(g)

void strcpy(char* x, char* y) {
  int i=0;
  while((x[i] = y[i])!=0)
    i++;
}

_strcpy: addi $t0, $0, 0
Loop:    addi $t1, ____, $t0
         lb ____, 0($t1)
         addi $t2, ____, $t0
         sb $t3, _____
         b__ $t3, $0, EXIT
         nop
         addi $t0, $t0, _____
         j Loop
         nop
EXIT:

답

rust

_strcpy: addi $t0, $0, 0
Loop:    addi $t1, $a1, $t0
         lb $t3, 0($t1)
         addi $t2, $a0, $t0
         sb $t3, 0($t2)
         beq $t3, $0, EXIT
         nop
         addi $t0, $t0, 1
         j Loop
         nop
EXIT:

3. reverse(str)

Write MIPS assembly code for a function reverse(str) that takes a string str and reverses its contents in place.

reverse:
  addi $sp, $sp, ___
  sw $ra, ___($sp)
  sw $s0, ___($sp)
  sw $s1, ___($sp)
  addi $s0, $zero, ___
  addi $s1, $a0, ___
  subi $s1, $s1, 1
loop:
  beq $s0, $s1, end
  lb $t0, ($s0)
  lb $t1, ($s1)
  sb $t1, ($s0)
  sb $t0, ($s1)
  addi $s0, $s0, ___
  subi $s1, $s1, ___
  j loop
  nop
end:
  lw $s0, ___($sp)
  lw $s1, ___($sp)
  lw $ra, ___($sp)
  addi $sp, $sp, ___
  jr $ra
  nop

답

rust

reverse:
  addi $sp, $sp, -12
  sw $ra, 8($sp)
  sw $s0, 4($sp)
  sw $s1, 0($sp)
  addi $s0, $zero, 0
  addi $s1, $a0, $a1
  subi $s1, $s1, 1
loop:
  beq $s0, $s1, end
  lb $t0, ($s0)
  lb $t1, ($s1)
  sb $t1, ($s0)
  sb $t0, ($s1)
  addi $s0, $s0, 1
  subi $s1, $s1, 1
  j loop
  nop
end:
  lw $s0, 4($sp)
  lw $s1, 0($sp)
  lw $ra, 8($sp)
  addi $sp, $sp, 12
  jr $ra
  nop

4. is_even(n)

Write MIPS assembly code for a function is_even(n) that takes an integer n and returns 1 if n is even, or 0 otherwise.

is_even:
  addi $sp, $sp, ___
  sw $ra, ___($sp)
  addi $t0, $a0, ___
  andi $t0, $t0, ___
  addi $v0, $zero, ___
  beq $t0, $zero, end
  addi $v0, $zero, ___
end:
  lw $ra, ___($sp)
  addi $sp, $sp, ___
  jr $ra
  nop

답

rust

is_even:
  addi $sp, $sp, -4
  sw $ra, 0($sp)
  addi $t0, $a0, 0
  andi $t0, $t0, 1
  addi $v0, $zero, 1
  beq $t0, $zero, end
  addi $v0, $zero, 0
end:
  lw $ra, 0($sp)
  addi $sp, $sp, 4
  jr $ra
  nop

5. Processor implementation comparison

(20pt) Consider two different implementations of the same instruction set architecture.

P1: clock rate 2 GHz, CPIs = 1, 2, 3, 4
P2: clock rate 3 GHz, CPIs = 2, 2, 2, 2

A program has a dynamic instruction count of 10^6 instructions divided as follows:

10% class A
20% class B
50% class C
20% class D

Questions:

(a) What is the global CPI for each implementation?
답
💡
P1
10% * 1 + 20% * 2 + 50% * 3 + 20% * 4 = 0.1 + 0.4 + 1.5 + 0.8 = 2.8 P2
2
(b) Find the clock cycles required in both cases.
답
💡
Instruction Count = 10^6
P1
Clock Cycles = 10^6 * 2.8
P2
Clock Cycles = 10^6 * 2
(c) Which implementation is faster?
답
💡
P2

6. Energy consumption

(20pt) Assume that the energy consumption of a processor core can be described by:

Energy = 0.2 * s * V^2

where s indicates the execution time in second, and the operation voltage is:

V = Frequency

with frequency measured in GHz.

Given that program A takes 2 second at 1 GHz:

If we want to run program A on 4GHz, then what voltage do we provide, and how much energy does the processor consume?
답
💡
V = 4
1GHz에 2초이므로 4GHz 에서는 0.5초
E = 0.2 * 0.5 * 4^2 = 1.6
If the voltage is 0.5, then what is the frequency and how much energy does the processor consume to finish program A?
답
💡
Frequency = 0.5GHz
Time = 4초
E = 0.2 * 4 * 0.25
= 0.2

▶

2023 midterm

2023 Spring

Note that 0x... denotes the hexadecimal number.
Put nop after beq, bne, j, jal, and jr instructions.

1. sum(n)

(10pt) Write MIPS assembly code for a function sum(n) that takes an integer n and returns the sum of all integers from 1 to n.

assembly

sum:
  addi $sp, $sp, ___   # Adjust stack pointer
  sw $ra, ___($sp)     # Save return address
  addi $t0, $zero, ___ # Initialize $t0
  addi $t1, $zero, ___ # Initialize $t1
loop:
  ___ $t1, $t1, ___    # Update $t1
  addi $t0, $t0, ___   # Update $t0
  slt $t2, $t0, $a0    # Compare $t0 and $a0
  bne $t2, $zero, loop # Branch if not equal
  ___
  lw $ra, ___($sp)     # Restore return address
  addi $sp, $sp, ___   # Adjust stack pointer
  jr $ra
  nop

답

assembly

sum:
  addi $sp, $sp, -4   # Adjust stack pointer
  sw $ra, 0($sp)     # Save return address
  addi $t0, $zero, 0 # Initialize $t0
  addi $t1, $zero, 1 # Initialize $t1
loop:
  add $t1, $t1, t0     # Update $t1
  addi $t0, $t0, 1   # Update $t0
  slt $t2, $t0, $a0    # Compare $t0 and $a0
  bne $t2, $zero, loop # Branch if not equal
  nop
  lw $ra, 0($sp)     # Restore return address
  addi $sp, $sp, 4   # Adjust stack pointer
  jr $ra
  nop

2. max(a, b)

(10pt) Write MIPS assembly code for a function max(a, b) that takes two integers a and b and returns the larger value.

max:
  addi $sp, $sp, ___   # Adjust stack pointer
  sw $ra, ___($sp)     # Save return address
  sw $s0, ___($sp)     # Save $s0
  slt $t0, $a0, $a1    # Compare a0 and a1
  beq $t0, $zero, else # Branch if a0 >= a1
  add $s0, $a1, $zero
  j exit
  nop
else:
  add $s0, $a0, $zero
exit:
  lw $ra, ___($sp)     # Restore return address
  lw $s0, ___($sp)     # Restore $s0
  addi $sp, $sp, ___   # Adjust stack pointer
  jr $ra
  nop

답

assembly

max:
  addi $sp, $sp, -4   # Adjust stack pointer
  sw $ra, 0($sp)     # Save return address
  sw $s0, 4($sp)     # Save $s0
  slt $t0, $a0, $a1    # Compare a0 and a1
  beq $t0, $zero, else # Branch if a0 >= a1
  add $s0, $a1, $zero
  j exit
  nop
else:
  add $s0, $a0, $zero
exit:
  lw $ra, 4($sp)     # Restore return address
  lw $s0, 0($sp)     # Restore $s0
  addi $sp, $sp, 4   # Adjust stack pointer
  jr $ra
  nop

3. strlen(s)

(10pt) Write MIPS assembly code for a function strlen(s) that takes a string s and returns its length.

strlen:
  addi $sp, $sp, ___   # Adjust stack pointer
  sw $ra, ___($sp)     # Save return address
  sw $s0, ___($sp)     # Save $s0
  add $s0, $a0, $zero  # Copy s to $s0
loop:
  ___ $t0, 0($s0)      # Load byte from memory
  beq $t0, ___, exit   # Exit loop if byte is null
  ___ $s0, $s0, ___    # Increment pointer
  j loop               # Jump back to loop
  nop
exit:
  sub $v0, $s0, $a0    # Calculate length of string
  lw $ra, ___($sp)     # Restore return address
  lw $s0, ___($sp)     # Restore $s0
  addi $sp, $sp, ___   # Adjust stack pointer
  jr $ra               # Return
  nop

답

assembly

strlen:
  addi $sp, $sp, ___   # Adjust stack pointer
  sw $ra, ___($sp)     # Save return address
  sw $s0, ___($sp)     # Save $s0
  add $s0, $a0, $zero  # Copy s to $s0
loop:
  ___ $t0, 0($s0)      # Load byte from memory
  beq $t0, ___, exit   # Exit loop if byte is null
  ___ $s0, $s0, ___    # Increment pointer
  j loop               # Jump back to loop
  nop
exit:
  sub $v0, $s0, $a0    # Calculate length of string
  lw $ra, ___($sp)     # Restore return address
  lw $s0, ___($sp)     # Restore $s0
  addi $sp, $sp, ___   # Adjust stack pointer
  jr $ra               # Return
  nop

4. is_even(n)

(10pt) Write MIPS assembly code for a function is_even(n) that takes an integer n and returns 1 if n is even, or 0 otherwise.

is_even:
  addi $sp, $sp, ___   # Adjust stack pointer
  sw $ra, ___($sp)     # Save return address
  sw $s0, ___($sp)     # Save $s0
  andi $t0, $a0, ___   # Bitwise AND with 1
  beq $t0, ___, even   # Check if n is even
  nop
  addi $v0, $zero, ___ # n is odd, return 0
  j exit
  nop
even:
  addi $v0, $zero, ___ # n is even, return 1
exit:
  lw $ra, ___($sp)     # Restore return address
  lw $s0, ___($sp)     # Restore $s0
  addi $sp, $sp, ___   # Adjust stack pointer
  jr $ra               # Return
  nop

5. Final value of `$s2`

Represent $s2 in hexadecimal or decimal format.

(a) (2pt)

addi $s2, $0, 7

(b) (2pt)

addi $t0, $0, 5
sll $s2, $t0, 2

(c) (2pt)

addi $t0, $0, 7
addi $t1, $0, 3
xor $s2, $t0, $t1

(d) (2pt)

addi $t0, $0, -1
addi $t1, $0, -3
nor $s2, $t0, $t1

(e) (6pt)

addi $t0, $0, 1
addi $t1, $0, 4
slt $s2, $t0, $t1
bne $s2, $0, ELSE
nop
j DONE
nop
ELSE: addi $s2, $s2, 4
DONE: addi $s2, $s2, 1

(f) (6pt)

addi $t1, $0, 5
addi $s2, $0, 0
LO: slt $t2, $0, $t1
beq $t2, $0, DONE
nop
addi $t1, $t1, -1
addi $s2, $s2, $t1
j LO
nop
DONE:

6. C to MIPS translation

(a) (10pt)

Fill the blanks.

int fib(int n) {
  if(n==0) return 0;
  else if (n==1) return 1;
  else return fib(n-1) + fib(n-2);
}

fib: addi $sp,$sp,____(1)______
     sw $s0, 0($sp)
     sw $s1, 4($sp)
     sw _(2)__, ___(3)_____
     b_(4)_ $a0, $0, E1
     addi _(5)__,$0,0
     j R
     nop
E1: addi $t0, $a0, -1
    b_(6)_ $t0, $0, E2
    addi _(7)__,$0,1
    j R
    nop
E2: add $s0, $a0,$0
    addi $a0,$s0,-1
    _(8)__ fib
    add $s1, $v0, $0
    addi $a0,$s0,__(9)__
    _(10)__ fib
    add _(11)_, $s1,$v0
R:  lw _(12)__, 0($sp)
    lw _(13)__, 4($sp)
    lw _(14)__, 8($sp)
    addi $sp, $sp, _(15)____
    jr $ra
    nop

(b) (5pt)

Consider the following main function. Fill the blanks.

int main() {
  return fib(3);
}

main: addi $sp, $sp, -4
      sw _(1)_, 0($sp)
      addi _(2)__, $0, _(3)__
      jal fib
      nop
      lw _(4)__, 0($sp)
      addi $sp, $sp, _(5)___
      jr $ra
      nop

(c) (10pt)

Suppose that the addresses of labels main and fib in questions 7 and 8 are 0x1000 and 0x2000, respectively. Assume that jalstores $ra by $PC+8.

Draw the stack change when function fib is called and returned. Initially $sp is 0x8000.

7. Processor comparison

(10pt) Consider three different processors P1, P2, and P3 executing the same instruction set with the clock rates and CPIs given in the following table.

Processor	Clock rate	CPI
P1	3GHz	3
P2	1GHz	4
P3	4GHz	2

(a) Which processor has the highest performance?

(b) If each processor executes a program in 10 seconds, find the number of cycles and the number of instructions.

8. Energy consumption

(10pt) Assume that the energy consumption of a processor core can be described by:

Energy = 0.2 * s * V^2

where s indicates the execution time in second, and the operation voltage of the processor is described by:

V = Frequency

with the frequency measured in GHz.

At 1 GHz, the voltage is 1.0V.
If s = 10 seconds, then Energy = 2 (= 0.2 * 10 * 1 * 1).
If the frequency is 0, then no energy consumption is required since V = 0.
When program A is running on 1 GHz, it takes 2 second.

(a) If we are running program A on 2GHz, then how much energy does the processor consume?

(b) If the voltage is 0.5, then what is the minimum frequency and how much energy does the processor consume to finish program A?

2-1) CA1 정리

중간고사 기출문제 풀이

2019

2022

2024

solution

solution

MIPS 레지스터 용도 정리

2025 midterm

1. Value of $s1

(a)

(b)

(c)

(d)

(e)

2. Translate MIPS assembly code from C code

(a) (3pt)

(b) (3pt)

(c) (4pt)

(d) (5pt)

(e) (17pt)

(f) (7pt)

(g) (6pt)

4. is_even(n)

5. Processor comparison

6. Dynamic energy consumption

7. RISC vs CISC

2024 midterm

1. Final value of $s2

(a)

(b)

(c)

(d)

(e)

(f)

2. Translate MIPS assembly code from C code

(a)

(b)

(c)

(d)

(e)

(f)

(g)

3. reverse(str)

4. is_even(n)

5. Processor implementation comparison

6. Energy consumption

2023 midterm

2023 Spring

1. sum(n)

2. max(a, b)

3. strlen(s)

4. is_even(n)

5. Final value of $s2

(a) (2pt)

(b) (2pt)

(c) (2pt)

(d) (2pt)

(e) (6pt)

(f) (6pt)

6. C to MIPS translation

(a) (10pt)

(b) (5pt)

(c) (10pt)

7. Processor comparison

8. Energy consumption

1. Value of `$s1`

1. Final value of `$s2`

5. Final value of `$s2`