컴퓨터 구조 lecture note #05

✍️ R-format

For the instructions that use only Register operands

 

명령들을 나타내는 방법에 대해 알아보자.

MIPS에서 명령들은 32Bit으로 Encoded 된다. 이는 ISA마다 다를 수 있다. MIPS는 32개의 레지스터를 가지고 있다.

레지스터들은 각각의 번호마다 쓰이는 역할이 다르다. (Green card 참조)

먼저 R-format 연산에 대해 살펴보자.

총 32bits

R-format은 위 그림과 같이 구성되어 있다.

• op(opcode) : 이 연산이 어떤 연산인지를 나타낸다. 만약 R-format의 연산이라면 추가적으로 funct비트를 확인
• rs : 첫번째 레지스터의 소스. 연산 후 rd에 저장
• rt : 두번째 레지스터의 소스. 연산 후 rd에 저장
• rd : destination 레지스터. 연산결과가 저장된다.
• shamt : shift 연산 시에 쓰인다.
• funct : op코드의 확장된 개념. 해당 연산이 어떤 연산인지를 나타낸다.

R-format의 연산에는 add, sub, and, or, slt 연산이 있다.

 

rs, rt, rd의 비트가 각각 5비트인 이유는 총 32개의 레지스터를 표현하기 위함이다.

 

위 예시를 통하여 연산이 어떻게 저장되는지 알아보자.

먼저 op코드가 0이므로 해당 연산은 R-format이므로 funct비트를 확인해야 한다.
funct비트가 32이므로 해당 연산은 add연산임을 알 수 있다.

또한 rs, rt, rd필드는 해당 레지스터의 number를 나타낸다. 레지스터의 number마다 사용하는 방법이 다르다.

이렇게 하여 결국 아래에 binary 형태로 나타난 코드가 실제 컴퓨터가 이해하는 코드이다.
위 연산을 HEX코드로 표현하면 0x02324020이다.

 

✍️I-format

For the instructions that use Immediate operands

다음은 I-format 연산에 대해 살펴보자.

 

I-format은 R-format과 달리 rd필드와 shamt필드가 없고 constant or adress를 저장하는 필드가 있다.

• op : op코드는 어떠한 연산이건 반드시 필요하며 사용되는 연산에 따라 형태가 다를 수 있다.
• rs : 첫번째 레지스터의 소스.
• rt : 두번째 레지스터의 소스.
• constant or address

마지막 constant or address필드에서는 주소를 저장하거나 immediate를 저장하여 상수 연산 및 lw, sw연산을 수행할 수 있다.

 

해당 포맷에서는 rt가 목적지 or 소스로 둘 다 사용되며, rs는 주소의 offset을 저장하고, 마지막 필드에서는 unsigned 2^16의 상수를 나타낼 수 있다.

 

R-format연산에는 lw, sw, beq, bne, slti, lui 등 자주 사용하는 연산들이 존재한다.

 

예를 들어 A [300]=h+A [300]이라는 C 코드를 MIPS코드로 컴파일하여 보자.

lw $t0, 1200($t1)
add $t0, $s2, $t0
sw $t0, 1200($t1)

과 같이 번역될 것이다. 각 연산들을 아래와 같이 나타낼 수 있다.

 

✍️CPU, registers, and memory

 

프로그램은 연산들의 집합이다. 프로그램은 메모리에 정되며 연산들은 메모리에 저장되어 실행된다.

프로그램이 실행되는 과정은 프로그램에 있는 연산들이 실행되는 것이며 결국 메모리에 있는 연산들을 이곳저곳 이동하는 과정이라고 생각할 수 있다.

같은 ISA를 사용하여 번역된 머신 코드는 다른 CPU에서도 사용이 가능하다.

 

• CU(control unit) : processor의 작동과 직접적으로 관련됨
• ALU(Arithmetic & Logic Unit) :계산함
• $0, ... , $31 : 계산에 사용되는 값들이 들어있음
• PC(Program Counter) : 실행되는instruction의 메모리 주소가 들어있음
• IR ( Instruction register) : 현재 명령어가 들어있음.

 

✍️ Execution of the instruction

• Step 1 (fetch:가져옴) : CU 가 "PC에 들어있는 메모리 주소에 해당하는 명령어를 IR로 load하라." 고 말한다.
• Step 2(decode:해석) : CU가 "IR에 store된 명령어는 ADD $s0, $s1, $s2이다." 라고 말한다.
• Step 3 (execute :실행) : ALU가 $s1과 $s2에 있는 값을 가지고 더하기 연산을 수행한 후, 계산 결과를 $s0에 저장한다.

 

MIPS에는 NOT연산자가 없다. 대신에 R-type instruction인 NOR가 있다. 

a NOR b = (a OR b)에 NOT연산을 해준 것

NOR을 통해서 NOT연산을 해줄 수 있다.

ex. nor $t0, $t1, $zero

시프트 연산은 bit를 left, right로 원하는 값만큼 움직이는 연산이다.

예를 들어 $s0<<4라는 연산은 s0의 비트 값을 4만큼 왼쪽으로 밀어낸다. 예를 들어 1101 0011이라는 bit가 있다면 
0011 0000이 될 것이다. >>는 똑같은 논리를 오른쪽으로 적용시켜주면 된다.

아까 위에서 살펴본 R-format에서의 shamt필드가 이때에 사용된다.
shamt필드는 몇 개의 bit이 shift 되었는지를 기록하는 필드이다.

left shift를 i번 반복한다면 해당 값에 2^i의 값을 곱한 결과와 같다. right shift를 i번 반복한다면 해당 값에 2^i를 나눠준 값과 같다(unsigned 한정) 따라서 2^i의 연산을 수행한다면 시프트 연산을 사용하는 것이 실행 속도가 훨씬 빠르다.

 

 

Conditional branch instruction인 beq연산과 bne연산에 대해 알아보자.

beq rs, rt, L1연산은 rs와 rt가 같다면 L1로 분기(이동)하는 연산이다.
bne rs, rt, L1연산은 rs와 rt가 다르다면 L1로 분기(이동)하는 연산이다.

만약 조건을 만족하지 않는다면 계속하여 다음 명령을 수행하게 된다.

 

Unconditional branch instruction에는 j연산이 있다.

 

 

위 C 코드를 MIPS코드로 번역하여 보자.

beq $s3, $s4, IF
sub $s0, $s1, $s2
j Exit

IF: add $s0, $s1, $s2
Exit :...

와 같이 번역할 수 있다. 똑같은 논리로 bne를 이용하여도 번역이 가능하다. 이는 컴파일러가 결정한다.

반복문 역시 bne 혹은 beq를 이용하여 다음과 같이 번역할 수 있다.

크기비교를 해주는 blt(less than), bge(greater than or equal to)같은 branch instructions은 존재하지 않는다.

그 이유는

- 크기비교 연산은 =,!=연산보다 복잡하고 느리기 때문이다.

-  이러한 크기비교 연산을 branch로 하나의 명령어에 넣어주게 되면, 하드웨어가 더 복잡해지고 모든 명령어의 성능이 떨어질 것이다.

- beq와 bne는 common case 

 

대신에 MIPS에서 다른 conditional operations을 제공한다. slt, slti

 

그 외에 추가적인 Conditional 연산에는 대소 비교를 해주는 slt과 slti연산이 존재한다.

 

slt rd, rs, rt 연산은 rs <rt일 경우에 rd에 1을 저장하며 그렇지 않으면 0을 저장한다.
즉 True : 1, False : 0의 값을 저장하게 된다.

 

slt연산과 beq, bne연산을 이용하여 우리는 모든 비교 연산을 만들 수 있다.(==,!=,>=,<= 등)

 

slt $t0, $s1, $s2 
bne $t0, $zero, L

 

위 연산을 해석해보자. 먼저 s1과 s2의 크기를 비교하여 s1 <s2라면 t0에 1을 저장한다.
밑에 bne연산은 t0이 0이 아니라면, 즉 t0이 1이라면 L로 분기한다.

 

만약 t0에 1이 아닌 0이 저장되었다면 s1>=s2임을 알 수 있다.

 

slti연산은 I-foramt으로 상수 연산에 쓰인다.

 

또 slt에는 부호의 존재 유무에 따라 사용하는 연산이 다르다. signed의 경우 slt를 unsigned의 경우 sltu를 사용한다.

 

왜냐면 부호 비트를 사용하냐 안 하냐에 따라 값이 달라지게 되며, 해당 연산의 결과도 달라질 수 있기 때문이다.

 

 =,!=연산은 >, <= 연산 등에 비해 실행 속도가 빠르다. 따라서 blt, bqe연산 같은 것은 존재하지 않는다. slt와 beq연산의 조합으로 구현이 가능하기 때문이다.

 

1. caller는 input parameter와 return address를 callee에게 패스해 준다.

-> 메인 루틴에 $a0부터 $a3까지 argument register에 해당 파라미터를 가져다 놓음. 4개의 레지스터이므로 최대 4개까지의 파라미터를 보낼 수 있음.(callee가 이용할 수 있게)

 

2. caller는 callee에게 제어를 넘긴다.

-> caller루틴이 멈추고 callee가 실행된다는 말이다. 

callee가 실행되면 callee가 필요한 자원들을 받기 위해 메모리를 할당받는다.(보통 stack에 할당)

 

3. callee는 전달받은 input parameter를 가지고 자기 일을 수행

4. callee는 return 값을 caller에게 준다.

-> callee의 수행이 끝나면 callee의 수행결과(return value)를 caller가 접근 가능한 레지스터에 넘긴다.

($v0과 $v1을 이용하여 넘김)

 

5. callee는 권한을 caller에게 준다. (return address를 이용해서)

-> $ra 레지스터는 callee에게 제어를 넘기기 전까지 수행했던 단계를 저장해놓고 있으므로

$ra를 사용하여 해당 주소를 Program Counter로 복사해서 $ra의 명령어부터 다시 실행할 수 있도록 한다. 

 

6. caller는 저장된 내용을 restore

 

Q. input parameter, return address, return value들은 어떻게 pass해줄까?

register를 이용해서

서로 다른 procedure들이 같은 register을 공유할 수 있다. 즉, 레지스터 안의 값들이 덮어써질 수 있다는 것이다. MIPS는 적은 수의 register를 사용한다. 하지만 우리는 많은 arguments들을 pass해야 한다.

Q. 이러한 문제들은 누가 다룰까?

stack을 사용해서 각각의 procedure의 실행과 관련된 모든 정보들을 저장한다.

stack은 메모리에 보관된다.

- register $sp는 메모리 안에 있는 스택의 top을 가리킨다.

- stack은 낮은 주소로 증가

✍️ Procedure(Function)
  : 파라미터를 매개로 callee와 caller 간에 서로 필요한 task를 주고 리턴할 수 있도록 만들어진 subroutine

 

✍️ Procedure Calling

함수의 호출이 일어나는 과정을 연산의 관점에서 살펴보자.

 

✍️ Parameters(arguments)
   : interface 역할. caller와 callee 모두 접근 가능한 특정 저장공간에 담아두고 함수 호출&인자 전달

 

✍️과정 요약

   1. 파라미터를 callee도 접근 가능한 곳에 담아두고 함수 호출함.(제어권이 callee에게 넘어감)
   2. 인자를 이용해서 task를 수행함.
   3. 결과값을 caller도 접근 가능한 곳에 담아두고 리턴함.(돌아가기 위해 caller의 위치도 알고 있어야 함)
   -> 인자 : $a0~$a3 (four argument registers)
       반환 값 : $v0~$v1 (two value registers to return)
       돌아갈 곳 : $ra (one return address register)

 

✍️ jal (jump and link)
  : J-format instruction
   jal ProcedureAddress 주소(레이블)로 점프
   -> $ra <- pc + 4 
       링크 : 리턴 시 pc+4로 돌아올 수 있도록 $ra에 넣어둠. caller가 callee에게 제어권 넘김.
   -> pc <- jump target
       점프 : 제어권이 callee에게로 넘어감.

✍️jr (jump register)
  : J-format instruction
   jr register 레지스터가 보관 중인 메모리 주소값으로 점프
   ex) jr $ra
       : $ra가 보관중인 주소로 점프. 즉, return (pc <- $ra)

- Arguments and Return Values

  -> caller와 callee가 같은 레지스터 사용함
  -> 아래 사진처럼 corruption 가능성 있음(문제 발생@_@!!)
  
- Register Corruption

  caller와 callee가 같은 레지스터를 사용해서 덮어쓰기 되는 것을 방지하기 위해
  '임시보관&복원하기'를 해야 함. -> save & restore (해결책ㅇ0ㅇ!!!)

 

- Stack
  : CPU가 갖고 있는 레지스터의 개수는 유한함(32개 in MIPS) -> 사용하는 모든 변수 수용 불가능
   -> 백업&복원 과정이 필요함
   Stack 은 temporarily save and restore data에 사용되는 메모리 공간임.

-> 레지스터에 있는 값을 메모리에 저장하고 다시 메모리에서 레지스터로 복원

- Spilling Registers
  Stack : last-in-first-out (LIFO) queue.
            -> stack grows from high address to low address in MIPS
  %sp ($29) : 일반 레지스터 中 stack의 top을 가리키는데 사용됨.

  push : add data onto the stack
           $sp = $sp-4
           store data on stack at new $sp
  pop : remove data from the stack
           restore data from stack at $sp
           $sp = $sp+4  

- Preserved and NonPreserved Registers
  : 앞의 예시에서 만약 caller가 $t0, $t1, $s0 를 callee 호출 후 사용하지 않는다면, save & restore 은 헛수고였음.
    그러한 경우를 방지하기 위해, MIPS는 레지스터를 두 개의 카테고리로 분류했음.
   Preserved : $s0~$s7 (saved)
                  -> 건드리면 callee책임. callee가 $s 쓸거면 save & restore 꼭 해야 함.
   Non-Preserved : $t0~$t9 (temporary)
                  -> 건드리면 caller책임. callee가 마음껏 overwrite 해도 됨.
                       caller가 $t 필요하다면 save & restore 해야 함.

 

✍️ Proceure Calling

- 어떤  register에 들어있는 값들은 call되었을 때 보존되야 한다.

- 이에 해당하는 register들에 저장된 값들은 call 또는 return이 완료된 후에도 복원될 수 있어야 한다.

• callee가 preserved register를 사용하는 경우 callee는...
  • call된 이후에 register안에 있는 값을 stack에 저장
  • return하기 전에 stack에 저장했던 값을 복원
• caller가 non-preserved register를 사용하는 경우 caller는...
  • call하기 전에 register안에 있는 값을 stack에 저장
  • return하기 전에 stack에 저장했던 값을 복원

✍️ jal PROCEDURE_LABEL

- 프러시저 콜은 jal함수를 통해 이루어진다.
- jal 은 jump-and-link로 먼저 다음 연산의 주소를 $ra에 저장하고, target의 주소로 이동하는 연산이다.

- PROCEDURE_LABEL = target address

 

✍️ jr $ra

- jr : jump register

- $ra에 저장된 주소로 jump

 

✍️ stack push

addi $sp, $sp, -4

sw $t0, 0($sp)

-> stack의 top에 $t0의 값을 push

 

✍️ stack pop

lw $t0, 0($sp)

addi $sp, $sp, 4

-> stack의 top에 있는 값을 pop해서 다시 t0에 넣어줌.

 

- Nested Procedure Calls
  leaf procedure : 다른 함수를 호출하지 않는 함수 (caller 역할 안 함)

  근데 어떤 함수가 caller이면서 callee라면 save & restore에 신경 써줘야 함.

ex) Recursive Procedure Call 

Recursive Call (3!)

 

 

Stack during Recursive Call (3!)

 

recursive example2