2021. 9. 30. 20:22ㆍ배움엔 끝이없다/학교공부
이 필기는 학교에서 듣는 컴퓨터구조 수업 시험대비를 위한 필기입니다.
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 는 따로 체크해줘야 합니다.
'배움엔 끝이없다 > 학교공부' 카테고리의 다른 글
프로그래밍언어론 (중간고사 필기정리) (0) | 2021.10.04 |
---|---|
선형대수학 ~Linear System (중간고사 필기정리) (0) | 2021.09.29 |