Computer Architecture 2 - Instructions

 MIPS CPU의 instruction은 32bit 주소 값을 가지고 3가지 format으로 나누어진다. R-format, I-format, J-format 이 그것들이며, 이들에 대해 살펴보고 MIPS CPU의 instruction 구조에 대해서 알아보자.

 

Representing instruction : 우리가 보는 instruction도 binary machine code로 encode되어야 한다. MIPS instruction은 32 bit instruction word로 encoded된다. MIPS는 RISC이므로 instruction format이 적다.(R, I, J – format). 

MIPS는 32개의 레지스터를 가지고 있으며 이 이름을 모두 외우는 것이 힘드므로 그린 카드(책 앞의)에 이름과 번호를 매칭해놓은 표가 있다. 

R-format instruction(R = Registor) : 세개의 레지스터 연산일 경우. Instruction의 machine code는 총 6개의 부분으로 나누어진다.(6+5+5+5+5+6) 가장 맨 앞은 opcode = instruciton의 종류를 나타낸다.(R- format 등) 6비트이므로 64가지밖에 표현 못 하므로 마지막 6개도 사용하여 extends opcode로 나타낸다. (add 등) Rs, rt, rd는 각각 레지스터를 나타내며 (모두 5비트), rs와 rt의 값을 가지고 연산한 결과를 rd에 저장한다. 각 5비트는 레지스터 넘버를 나타내서 어떤 레지스터에 값이 저장되어 있는지 나타낸다. MIPS는 32개의 레지스터만 있으므로 5비트로 나타낼 수 있다.(2^5=32) Instruction을 최대한 간단하게 만들기 위해 레지스터 수를 더 늘리지 않았다. 만약에 레지스터가 더 늘어나면 instruction의 5비트가 각각 6비트 이상이 되어야 하므로 instruction이 더 복잡해지기 때문이다.

I-Format(I = immediate) : 여기서는 즉각적인 load/store instruction이 변환된다. 총 4부분으로 나누어지며(6+5+5+16) 앞서와 동일하게 맨 앞은 opcode, rs, rt(rt에/를 rs에서 offset만큼 옮긴 위치 값 가져오기 / 넣기)는 각각 source나 destination register number이다. 마지막 16비트는 -2^15 ~ 2^15-1까지의 const 값을 나타내는 곳이다. (메모리 주소)

비트연산(Logical operation) : logical shift(bitwise)의 MIPS instruction은 sll / srl로 나타낸다. 이 경우에는 옮기고 생기는 빈칸을 무조건 0으로 채운다. 이와 비슷하게 aristhmetic shift 연산도 있는데 이는 뒤의 l을 빼고 sl/sr로 나타낸다. 그런데 이 때는 MSB가 빈 경우에는 앞서 배운 것 처럼 sign extenstion이 유지되어야 한다.(부호 비트와 동일한 값으로 채움) 물론 *2가 될 때는 0을 채우면 된다.

Shift operation : R- format에서 세개의 레지스터 뒤의 5비트에는 쉬프트연산이 들어간다. 쉬프트 연산은 두 개의 레지스터만 필요하지만 R-format으로 분류된다. 따라서 rt와 rd만 사용하고 rs는 비워둔다. 물론 어떤 쉬프트연산인지는 rd 뒤의 5비트에 넣는다.(shamt = shift amount)
sll $t2, $s0, 4에서 (rd=$t2, rt = $s0). Sll = 2로 곱한 값. 컴퓨터는 곱셈 연산은 매우 느리므로 2의 제곱수로 곱할 때는 컴파일러가 자동으로 쉬프트 연산으로 바꿔준다. 

비슷하게 srl은 나누기 2가 된다.(unsigned only. 왜냐하면 logical shift에서 빈칸은 항상 0으로 채우므로. 당연하게도 나머지 1은 버림. ) 

그러나 srl은 arithmetic shift에서도 온전한 /2가 되진 않는다. 음수일 경우 나머지가 버려지지 않고, MSB가 버려지는 경우도 있으므로 오버플로가 일어날 수도 있다. 따라서 될 때도 있고 안될 때도 있다. 

따라서 사용할 때 매우 조심해야 한다. 변수의 범위를 확실하게 예측할 수 있는 경우에만 사용해야 한다.

마찬가지로 and, or도 bitwise 연산으로 존재한다. 그러나 NOT operation은 0과 nor 연산을 하면 되므로 해당 instruction은 존재하지 않는다. (instruction의 수를 최소로 하는 것이 MIPS)

Stored program computers : Instruction과 data는 모두 memory에 binary로 저장되므로 컴퓨터는 이들을 구별할 수 있다. running a program is moving in the memory. Memory 내부의 내 프로그램이 존재하고, 내 프로그램의 instruction을 하나씩 실행한다. 

그러나 function이나 if, else 문 등을 실행하면 instruction 사이를 jump 하여 이동하게 된다. 따라서 이런 움직임을 나타내는 instruction이 필요하다.
 

 

Decision instructions : conditional branch instructions(true 라면 jump 하고, 그렇지 않으면 계속 진행) -> beq rs, rt, L1 : rs, rt의 레지스터 저장 값이 같으면 레이블 1로 가라. (branch equal)

Bne rs, rt, L1 : rs, rt 레지스터 저장 값이 다르면 레이블 1로 가라. (branch not equal)
 

J L1 ->  jump instruction. 뒤의 레이블로 점프하라.
 

그리고 bne나 beq는 레지스터의 순서와 jump instruction의 순서를 조정하여 서로 상호교환 가능하다. 이는 컴파일러가 결정한다. 

SLT rd, rs, rt -> rs가 rt보다 작을 때 rd=1 아니면 0. (set on less then)
Slti rt, rs, constant -> rs가 constant보다 작을 경우에 위와 동일(rt=1, rt=0) Unsigned comparison은 sltu, sltui 가 된다. 앞서 배운 것처럼 메모리에 들어있는 비트는 동일하다.

하지만 해당 데이터를 어떻게 출력하거나 정의하느냐에 따라 signed, unsigned에 따라 값이 달라지므로 내 정의에 따라 서로 다른 instruction이 사용된다. 

예를 들어 ==는 beq로 가능하며, !=는 bne, >,<는 SLT(레지스터의 순서를 바꾸면 됨), <=,>=는 not을 사용하여 할 수 있다. (not > -> <=, not < -> >=, bne를 beq로 바꾸거나 순서를 바꾸는 등으로 가능) 

클락은 가장 느린 instruction에 맞춰서 느려진다. 또한 equality에 비해 비교 instruction은 속도가 느려서 사용하지 않고 beq, bne만 사용한다.

 

Procedure calling(function calling) :
 

PC(program counter) – register의 이름. 앞서 언급한 32개에 포함되지 않고 따로 존재하는 특별한 레지스터. 프로그램 실행 중에 현재(NOW!) cpu가 실행하고 있는 instruction의 주소가 저장되어 있다. instruction에서는 MIPS가 제공한 32개의 레지스터만 사용가능하므로 이런 특수한 레지스터는 접근할 수 없다.
 

$ra(return address) : 이 레지스터는 32개의 레지스터에 포함되는 것으로 return 값을 어디로 돌려줘야 하는지 주소를 기억하고 있는 레지스터.
 

Jal : procedurelabel(jump and link) - $ra에 PC+4의 주소를 저장하고 함수 부분으로 점프하는 instruction.
 

Jr $ra : procedure return. 다음 레지스터에 있는 주소로 jump 한다. 즉, function return의 instruction. 뒤의 레지스터는 반드시 $ra는 아니어도 가능하다. 해당 instruction의 기능은 PC=$ra로 하는 것이다.
 

모든 언어에서 function value는 단 한 개만 존재한다. 왜냐하면 result value를 저장하는 레지스터는 2번과 3번($v0, $v1) 뿐이므로. (32비트를 넘어가는 값을 넘길 때가 있을 수도 있으므로 레지스터를 두개 사용)

매개변수를 전달할 때 사용하는 레지스터는 $a0~$a3이다. (4번부터 7번까지의 레지스터) 4개 이상의 매개변수를 전달하면 메인 메모리에서 스택을 생성하여 4개씩 빼서 전달하여 사용한다. 즉, 메모리의 스택을 사용해야 하므로 매개변수가 5개 이상인 함수는 상대적으로 느릴 수 있다.

$t0~$t9(temporary) – caller calls the callee. 이들은 임시 레지스터이므로 callee에 의해 preserve 되지 않음. 

$s0~$s7(saved) – must be saved by callee. 즉, t resister들은 각 함수의 local variable이고, s resistor는 global 값이 된다. 따라서 s 레지스터를 서로 다른 함수에서 쓰더라도 original value는 저장되어야 하므로 callee(불러진 함수)가 이전의 값을 저장하고, 함수가 끝날 때 restore 해준다. 그러나 t register는 이런 것들을 신경쓰지 않는다.

Stack : data structure for spilling registers.
$sp(stack pointer) : stack에 가장 최근 저장된 주소를 저장하는 레지스터.
Stack grows down : high memory addres 에서 low memory address로 간다.

 

재귀적인 함수를 실행하면 메모리를 매우 많이 잡아먹는다. 이는 recursive의 작동방식을 살펴보면 된다. Function call은 레지스터의 값들을 저장하고 불러오는 과정이 필요하므로 속도가 매우 느리고, 메모리를 많이 잡아먹는다. 그렇기에 메모리 적인 측면에서 볼 때 for이나 while 문을 돌리는 것이 훨씬 효율적이다. 

Memory layout : text, static, heap, stack과 reserved로 구성된다. 이 중 reserved는 컴퓨터의 다른 특정 작업을 수행하기 위해 예약된다. 실제로 이 주소의 메모리가 사용되지는 않지만 마치 사용되는 것 처럼 주소를 선점한다.(마우스, 키보드 등등)

Const, global var 등으로 컴파일러가 데이터 크기를 정확하게 알 수 있으면 이는 static data 부분에 저장된다. Malloc, free, new, gc, 등등으로 dynamic memory allocation을 할 때는 얼마나 크기가 필요할 지 모르므로 이들은 heap에 저장된다. Stack 역시도 크기를 모르는 것들을 저장한다.

Static data와 text, reserved는 모두 결정된 크기를 가지므로 dynamic한 두 값 중 stack은 top to bottom으로 자라고, dynamic data는 아래에서 위로 자란다.(메모리 주소가 큰 것부터 작은 것으로 가면 stack, 그 반대는 allocation). 이들이 만날 경우에는 crash가 발생한다. 물론 현대 컴퓨터는 자동으로 메모리 보호가 작동하여 해당 프로그램만 종료될 수 있다.

Byte & halfword operation : 1 word = 4byte, 따라서 halfword = 2byte, byte = 1byte operation들. 앞서 Load word / store word랑 작용은 같지만 1, 2 byte만큼만 하는 것이 다른 점.  1 혹은 2 바이트를 제외한 나머지 바이트는 sign / unsigned version에 따라 sign extend / zero extend를 한다. Lb=(byte signed), lhu(unsigned halfword) register의 값과 16bit constant를 더해서 메모리 주소를 계산하고, 해당 주소로 접근함(Base addressing)
마찬가지로 주어진 예제에서 이전에는 배열의 크기를 4byte라고 생각했지만, 여기서는 1, 2 byte이다. (예시에서는 char이므로 1바이트)

이제까지 살펴본 instruction들은 모두 i-format instruction으로 대부분의 constant가 작았기 때문에 16비트로 충분했다. 그러나 32bit 이상의 constant가 필요할 때는 lui rt, constant, 형식으로 앞부분의 절반(upper part)을 레지스터에 저장하고, 나머지는 ori rt, rt, constant로 해당 레지스터의 뒷 부분에 나누어서 저장하는 방법이 필요하다. (load upper immediate – 여전히 i-format이긴 함). 이렇게 나누는 이유는 앞서 32bit 레지스터의 address 주소(constant)는 16bit이고, 나머지는 명령어를 저장하는 공간이었기 때문이다. 

Branch addressing : 32bit 주소는 4GB 크기의 메모리를 제공하는데, 주소값이 16bit인 레지스터로는 메모리 공간 전부에 접근할 수 없다.(주솟값의 절반이 잘리므로) 따라서 이를 해결하기 위해 MIPS 디자이너들은 PC-relative addressing이라는 방법을 생각해냈다. 이는 Target address(원하는 위치) = PC(현재 instruction pointer의 위치) + Offset * 4(instruction word가 4byte이므로) 로 나타낼 수 있다. 이 때, offset에는 레지스터의 16bit constant가 들어간다. 해당 아이디어의 근간은, 대부분의 branch target은 branch 주위에 있다는 가정에서 시작한다.

 

 예를 들어 c코드에서 if – else문, for, while, switch문 등은 서로 가깝게(약 100~200 줄. 그 이상 넘어가면 좋은 코드가 아님) 위치한다. 따라서 offset인 constant를 적절히 변화시키면 내가 현재 위치한 instruction의 위치에서 앞뒤로 적절한 위치를 움직일 수 있다. Constant는 16bit이므로 +-2^15 instruction = 2^17byte(1word = 4byte) 만큼 branch할 수 있다.

단, 이 때 주의할 점은 내가 해당 instruction을 실행할 때는(next instruction) 이미 PC의 위치가 다음 instruction으로 넘어가 있는 상태이므로 엄연히 말하면 target address = (PC+4) + offset * 4가 된다. 따라서 실제 beq, bne를 통해 branching하는 실제 주소는 위와 같이 된다. (PC-relative address)

Jump addressing : j or jal의 target은 text segment(내 code)의 어디에도 존재할 수 있다. 바꿔 말하면, 해당 jump instruction을 통해 내 코드의 어디든 접근할 수 있어야 한다. 즉, 현재 위치인 PC로부터 먼 곳일 수 있다. 따라서 여기서는 constant의 크기를 약간 늘려서 26bit로 주솟값을 받아오는 새로운 J-format을 사용한다. J-format의 instruction은 = OP code(what operation to do at address = 6 bit) + address(26bit)로 구성된다. 맨 앞에 op를 보고 해당 instruction이 J-format이라는 것을 알 수 있다. 

해당 방식은 Pseudo direct jump addressing이라고 하는데, 수도인 이유는 온전히 32비트가 아니기 때문. Target address = address(26bit) * 4(1word = 4 byte) 의 방식으로 jump를 할 수 있는데, 이 때 점프 가능 범위는 2^26 word = 2^28 byte가 된다. 이는 PC와 상관없이 계산되는 절대주소이다. 

전체 메모리 주소는 2^32이므로 남는 부분(Top 4 bits)는 PC의 top 4 bits를 가져와서 사용하고, 나머지는 동일하게 더하는 식으로 접근한다. 즉, target address = PC31~28(top 4 bits of PC) : address * 4(concate) 가 된다. 이 때 계산되는 주소는 PC의 top 4 bits + address(26bit) + 2bit(by *4)의 형태이다. 필기한 내용처럼, Jump addressing은 PC 주위 256MB의 range를 커버할 수 있다. 

Jump register jr : 레지스터의 전체 32bit가 모두 메모리의 주소이고 operation은 하지 않음. 그냥 그 주소로 바로 점프. (R-format) J-format을 사용하더라도 매우 먼거리(PC가 있는 256MB region 이상의 거리)는 갈 수 없다. 따라서 이런 주소에 접근할 때는 해당 jump register를 사용하여 주소를 지정해준다.

Branching Far away : branch target이 16bit offset으로는 접근할 수 없을 만큼 먼 경우(+-2^15 word보다 먼 경우)에는 assembler가 자체적으로 접근할 수 있도록 코드를 바꿔준다. (beq를 bne와 j로 나누는 등)

Addressing mode : Immediate addressing(I-format), Register Addressing(R-format), Base addressing, PC-relative addressing, Pseudodirect addressing(J-format) 이들의 차이점 알기

Decoding machine language : MIPS machine instruction에 대해 assembly language statement를 추론하는 것. 앞서 말한 것 처럼 모든 기계어는 그냥 이진수의 나열이다. 이에 어떤 의미를 줄 것인지는 프로그래머가 결정하는 것이다. 

 

ex) 

0x00af8020 = 0000 0000 1010 1111 1000 0000 0010 0000 (2). 

 

맨 처음 6bit는 op code로 (000000) -> green card를 통해 찾을 수 있다. Green card는 3자씩 끊어 읽는데, 맨 처음 3자는 세로줄(맨 왼쪽 줄)에서, 그 다음 3자는 가로줄(맨 윗줄)에서 찾아 교차점의 값을 읽는다. 

따라서 000000은 R-format instruction이라는 것을 알 수 있다. R-format은 rs, rt, rd 3개의 레지스터를 가지고 있으므로 각각 5비트씩 끊어 읽으면 된다. Rs(00101) = 5, rt(01111) = 15, rd(10000) = 16번 레지스터라는 것을 알 수 있다. 

이후 해당 번호의 레지스터에 저장된 값들 역시 green card에서 유추할 수 있다. 5번은 arguments($a1)이고, 15번은 temporaries($t7), 16번은 saved($s0)라는 것을 알 수 있다. R-format instruction에서 다음에 오는 5bit는 shift값은 사용하지 않으므로 무시하고 마지막 6 bit를 보면(100000) 이는 function code이다. 

Function code 역시 green card에서 찾을 수 있다. (R-format일 때만 마지막 6비트가 function field이다. 다른 포맷이면 또 달라짐). 앞서 format을 찾는 것과 동일한 방법으로 표에서 함수를 찾으면 해당 binary는 add instruction이라는 것을 알 수 있다. 

따라서 주어진 예시 instruction 0x00af8020은 add $s0, $a1, $t7이 된다.