컴퓨터구조 (중간고사 필기정리)

이 필기는 학교에서 듣는 컴퓨터구조 수업 시험대비를 위한 필기입니다.

 

Metrics for computer performance (성능의 측정 기준)

Response Time (Execution Time) : 하나의 task를 수행하는데 걸리는 시간

Throughput : 단위 시간에 수행할 수 있는 일의 양

 

CPU Time : 프로세서가 task를 수행하는데 사용한 시간 ( I/O request 등 task와 관련 없는 시간 제외)

Performance = 1 / CPU time 으로 정의합니다. 

 

-User CPU Time : 프로그램의 코드를 실행하는데 든 CPU Time

-System CPU Time : 프로그램을 실행하기위해 OS에서 사용된 CPU Time

 

Clock Cycle : CPU Time의 기본 단위로, CPU가 기본연산(basic operation)을 수행하는 시간

-Clock Period : Clock Cycle의 길이 (duration)

-Clock Rate : 초당 Cycle의 수 (frequency) = 1 / Clock Period 

 

CPU Time = Clock Cycles(Instruction Count) * Clock Period

하지만 Instruction마다 걸리는 시간이 다르기 때문에 Instruction Count * Clock Period로 프로그램의 실행 시간을 계산할 수 없다.

CPI (Clock cycles per Instruction) : 각 instruction이 걸리는 clock cycle의 평균

 

Benchmark : 컴퓨터의 성능을 측정하는 도구로, instruction count를 실제 세계와 비슷하게 정함.

$$Performance\; of\; X\; relative\; to\; REF = \frac{1}{\sqrt[n]{\prod_{i = 1}^{n}\frac{Execution\;time_{X,i}}{Execution\;time_{REF,i}}}} $$

 

Amdahl's law : 성능 개선을 하면 모든 시간이 줄어드는게 아니라 성능이 개선된 부분의 Execution time 만 줄어들기 때문에, make common case faster 해야한다. 

 

ISA (Instruction Set Architecture)

ISA : 소프트웨어와 하드웨어 사이의 instruction을 정리해 둔 Layer (Abstraction)

 

MIPS ISA의 3가지 특징

 

1. Simplicity favors regularity

모든 MIPS instruction은 1개의 operation + 3개의 operands로 이루어집니다.

예) add, a, b, c ( a=b+c )

이 규칙으로 명령의 처리속도를 증가시킬 수 있습니다.

 

2. Smaller is faster

MIPS instruction의 operand는 적은 수의 레지스터 중에 하나여야 한다.

MIPS에는 32bit 레지스터가 32개 있고, 32개이기 때문에 레지스터의 위치를 5bit로 표현할 수 있습니다.

레지스터의 종류로는 임시 변수($t0~$t9), 저장된 변수($s0~$s7) 등이 있습니다.

 

메모리 접근 명령어

lw reg1 offset(reg2) : load a word from address [reg2+offset] to reg1

sw reg1 offset(reg2) : store a word from reg1 to address [reg2+offset]

 

MIPS에서 메모리를 관리할 때 Byte-addressing을 사용하지만, 데이터 교환에는 4byte 인 word를 사용합니다.

또, 데이터의 크기가 N이라면, 데이터는 N의 배수인 주소에 시작 주소를 가져야합니다.

 

Byte Ordering : MIPS는 Big endian 기법을 사용합니다.

Big endian : Most significant byte가 낮은(빠른) 주소번호에 옵니다.

Little endian : Most significant byte가 높은(늦은) 주소번호에 옵니다.

 

3. Make the common case fast

작은 상수를 더하는 연산을 자주 하기 때문에 이를 위해 16비트의 상수를 더하는 연산을 따로 제공합니다.

-> addi $t0, $t0, 4 : $t0에 4를 더함

또 값의 이동을 위해 $zero라는 상수 0만 저장하는 레지스터를 따로 둡니다.

-> add $t0, $t1, $zero : $t0 = $t1

 

Data representation

모든 수는 2진수로 저장되며, signed 숫자들은 첫 비트를 부호로 하기위해 이진수의 2의 보수(2's complement)로 저장됩니다.

2의 보수 : 모든 비트를 reverse하고, 1을 더합니다.

2의 보수를 사용하면 부호가 있는 덧셈, 뻴셈 연산을 쉽게 할 수 있습니다.

16bit 숫자를 32bit로 늘릴 때는 가장 앞 비트를 왼쪽에 복제하면됩니다.

예) 0000 1010 -> 0000 0000 0000 1010, 1010 1111 -> 1111 1111 1010 1111

 

Instruction representation

R-format : 레지스터 피연산자만 사용하는 instruction의 포맷

op (6 bits)	rs (5 bits)	rt (5 bits)	rd (5 bits)	shamt (5 bits)	funct (6 bits)
basic operation	destination register	source register1	source register2	shift amount	operation variant

 

I-format : 상수와의 연산에 사용하는 instruction의 포맷

op 6bit / rs 5bit / rt 5bit / constant or address 16bit

 

MIPS 기본 명령어

Operation	C언어 표현	MIPS Assembly	Example + 설명
Add	t0 = t1+t2	add(R) / addi(I)	add $t0, $t1, $t2
Subtract	t0 = t1-t2	sub(R)	sub $t0, $t1, $t2 subi 대신 addi를 활용한다.
Bitwise AND	t0 = t1 & t2	and(R) / andi(I)	and $t0, $t1, $t2
Bitwise OR	t0 = t1 | t2	or(R) / or(I)	or $t0, $t1, $t2
Bitwise NOR	t0 = ~(t1 | t2)	nor(R)	nor $t0, $t1, $t2 not 대신 nor $t0,$t1,$zero를 활용한다.
Shift	t0 = t1 << t2	sll(R) : shift left srl(R) : shift right	sll $t0, $t1, $t2 sll $t0, $t1, 5 source register 중 rs를 사용하지 않으며, 마지막 값은 shamt에 저장한다.
Conditional branch	if ($t0 == $t1) goto LABEL if ($t0 != $t1) goto LABEL	beq(I) bne(I)	beq $t0, $t1, LABEL bne $t0, $t1, LABEL destination register, shamt, funct 자리를 묶어 LABEL의 offset을 저장한다.
Unconditional branch	goto LABEL	j (J-format)	j LABEL op를 제외한 다른 비트들을 모두 합쳐 LABEL의 주소를 저장한다.
Set on less than	if ($t1 < $t2) $t0 = 1 else  $t0 = 0	slt(R), slti(I), sltu(R), slti(R)	slt $t0, $t1, $t2

 

Procedures (functions)

프로시져를 Call/Return 할 때 parameter, return value, return address 등을 관리해야하는데, 이들을 위한 레지스터가 준비돼있습니다.

레즈서트들은 Preserved/Non-preserved 레지스터로 나뉘는데, 기능상의 차이는 없고 의미상의 차이만 있는 것 같습니다.

Preserved register은 callee가 유지시켜줘야하고, non-preserved register은 그럴 의무가 없는 것 같습니다.

Preserved Registers : $v0~1 (Return values), $a0~3 (Arguments), $t0~9 (Temporary variables)

Non-preserved Registers : $s0~7 (Saved variables), $sp (stack pointer), $ra (return address), $gp, $fp

호출받는 callee가 perserved register를 이용하기 전에 stack에 저장을 해야하며, return 전에 복구시켜놔야 합니다.

호출하는 caller가 non-preserved register를 저장하고싶으면 호출 전에 stack에 저장해야하며, return 후 복구시킵니다.

 

관련 명령어

jal LABEL : 다음 명령의 주소를 $ra에 넣고 LABEL로 jump

jr $ra : $ra에 저장된 명령의 위치로 jump

addi $sp, $sp, -4 / sw $t0, 0($sp) : 스택에 데이터 push (스택의 주소값은 감소함)

lw $t0, 0($sp) / addi $sp, $sp, 4 : 스택의 데이터 pop

 

$sp : 스택의 top을 가리키는 포인터

$fp : 어떤 프로시져가 사용하는 local variable 등이 담긴 스택 공간(activation record, frame)의 시작점

 

 

global variable은 activation record에 저장될 수 없으므로 fixed address에 statically allocated 됩니다.

메모리 구조: 코드가 가장 낮은 메모리, 그 위에 global variable, 그 위에 위로 자라는 힙이 있고, 맨 위부터 아래로 자라는 스택이 있습니다.

 

Addressing Mode

Immediate addressing (immediate operands) : data is in instructions

Register addressing (register operands) : data is in registers

Base addressing (data transfer instruction) : data is in memory (base address(in 32bit register) + offset(16bit))

PC-relative addressing (branch instruction) : Target branch address = LABEL의 branch offset*4 + PC address

Pseudo direct jump addressing (unconditional branch instruction) : PC의 앞 4자리와 LABEL의 offset*4를 concat

 

 

32비트 상수가 필요할 경우

lui reg, i : 레지스터의 상위 16bit를 설정

ori reg, reg, i : 레지스터와 i를 or연산 (상위 16비트와 하위 16비트를 합치는 방법)

 

Arithmetic Instructions

Addition/Subtraction

carry 비트를 추가적으로 활용해 덧셈을 수행하며, 뺄셈은 2의 보수를 취해서 더하면 되기 때문에 if_subtract 비트와 두번째 숫자의 각비트를 xor연산 후 add하면 됩니다. 또 첫 자리 덧셈에 carry로 if_subtract비트를 입력해줍니다.

 

Overflow : 결과가 out of range될 경우 발생합니다. 이는 첫 비트가 양수끼리 더했는데 1일 때, 양수-음수인데 1일 때, 음수-양수인데 0일 때 입니다.

addu, addui, subu (unsigned version)를 사용하면 overflow에 예외가 발생하지 않고 무시됩니다.

 

Multipliation

m자리 수 * n자리 수는 m+n자리 수(최대)가 되기때문에 결과를 저장할 때 64비트를 사용해야합니다.

A*B에서 B는 결과값을 저장하는 공간에 같이 저장됩니다. B는 64비트의 오른쪽에 저장되며,

가장 마지막 자리 수 * A의 결과를 결과 저장 레지스터 중 왼쪽 32비트에 더합니다. 그리고 그 공간 전체를 오른쪽으로 1칸 쉬프트 합니다. 이 과정을 32번 반복하면 곱셈이 완료됩니다.

부호 있는 곱셈을 위해 양수로 변환 후 연산 후 마지막에 추가해줄 수도 있고, Booth's Algorithm을 사용할 수도 있습니다.

 

곱셈 명령어 mult rs, rt / multu rs, rt 를 사용하면 결과값이 특별한 레지스터 HI / LO에 저장되고,

mfhi rd / mflo rd 명령어를 이용해 각 값을 load할 수 있습니다.

 

Division

m자리수 / n자리수의 몫은 m-n+1, 나머지는 n자리입니다(최대).

A/B에서 A와 몫과 나머지가 64비트 레지스터를 공유합니다.

A가 64비트의 오른쪽에 저장되며, 나누는 수 B를 결과 레지스터의 왼쪽 부분에서 뺍니다. 결과가 음수일 경우 뻴셈을 취소하고 결과 레지스터를 왼쪽으로 1 쉬프트합니다. 결과가 양수였다면 뻴셈을 취소하지 않고 레지스터를 왼쪽으로 1 쉬프트 후 맨 오른쪽 비트를 1로 설정합니다. 이 과정을 33번 반복하고 마지막에 왼쪽부분을 오른쪽으로 1 쉬프트하면 왼쪽 32비트엔 나머지가, 오른쪽 32비트엔 몫이 저장됩니다.

부호가 있는 나눗셈은 양수로 변환 후 마지막에 추가해줍니다.

 

곱셈과 마찬가지로 명령어 div rs, rt / divu rs, rt 를 사용하면 나머지와 몫이 HI/LO에 저장됩니다.

mfhi rd / mflo rd 명령어를 이용해 각 값을 load할 수 있습니다.

오버플로우나 divide by 0 는 따로 체크해줘야 합니다.