2. MIPS : ALU and Data Transfer Instruction

ALU Instruction

ALU는 산술 연산과 논리 연산을 담당한다.

 

Register Arithmetic Instruction

Addressing mode는 instruction이 어떤 operand를 가질 수 있는지를 결정하는 것이다.

RISC의 ALU instruction은 레지스터 기반으로, register addressing mode와 R-format을 사용한다.

변수나 데이터는 레지스터에 저장되어, 레지스터로 사용된다.

 

모든 arithmetic operation은 3개의 operand를 가진다.

2개는 source이고, 1개는 destination이다.

예 : <pre>add a, b, c</pre>

 

register addressing mode

 

예시

C 코드에서 <pre>f = (g + h) - (i + j)</pre>라는 코드는 다음과 같이 MIPS code로 컴파일 된다.

<pre>

add  $t0, $s1, $s2

add  $t1, $s3, $s4

sub  $s0, $t0, $t1

</pre>

 

Immediate Arithmetic Instruction

Immeidate addressing mode와 I-format을 사용하는 ALU instruction이다.

 

Small constant와 register의 연산이 벤치마크에서 ALU instruction의 25%을 차지할 정도로 자주 사용된다.

예를 들어 <pre>A = A + 5</pre> 등이 있다.

자주 사용되는 것을 single instruction으로 처리하기 위해서 MIPS에서는 <pre>addi, andi</pre>와 같은 instruction이 존재한다.

 

Substract immediate instruction이 존재하지 않는다.

대신 negative constant를 addi 함으로써 대체할 수 있다.

예 : <pre>addi  $s2, $s1, -1</pre>

 

예시

<pre>addi $29, $29, 4</pre>

 

이는 <pre>$29 = $29 + 4</pre>을 수행하는 instruction이다.

16bit을 맞추기 위해 immediate operand를 sign extension 한다.

 

 

---

Logical Instruction

Logical instuction은 32bit 전체가 한번에 연산되는 것이 아니라 bit 단위로 연산되는 bitwise manipulation이다.

bit을 move하는 것과 강제로 1로 하는 것, 강제로 0으로 하는 것이 있다.

 

Shift Operation

R-format을 이용하고, opcode는 0이다. 또한 rs는 사용하지 않는다.

사용하는 opcode를 줄이고 funct를 이용해서 더 많은 instruction을 담기 위해서이다.

 

• <pre>sll</pre>
  • shift left logical 
  • bit를 왼쪽으로 i 만큼 이동한 것과 $2^i$을 곱한 것과 동일하다.
  • 곱셈보다 더 빠르기 때문에 컴파일러가 $2^i$의 곱을 sll로 대체하기도 한다.
• <pre>srl</pre>
  • shift right logical 
  • bit을 오른쪽으로 i 만큼 이동한 것과 $2^i$을 나눈 것과 동일하다.
  • 단 빈 bit을 0으로 채우기 때문에 unsigned에서만 동일하다.
• <pre>sra</pre>
  • shift right arithmetic
  • signed number을 division한 것과 같다.

 

<pre>sll  $t2, $s0, 4</pre>는 다음과 같은 machine code로 바뀐다.

 

옮길 비트 수가 변수에 담겨있다면 <pre>sllv, srlv, srav</pre>을 이용한다.

예를 들어 다음과 같다.

<pre>

sllv    $t0,  $t1,  $t2     // $t1을 $t2만큼 shift left하고 그 결과를 $t0에 담는다.

srlv   $t0,  $t1,  $t2

srav  $t0,  $t1,  $t2

</pre>

 

Bitwise AND, OR, NOR Operation

logical immeidate operation은 음수가 없다.

따라서 빈 곳은 모두 0으로 채운다.

 

• bitwise AND
  • 일부의 bit만 남기고 나머지는 0으로 만든다.
  • 원하는 bit을 0으로 할 수 있다.(없앨 수 있다.)
  • 예 : <pre>and $t0, $t2, $t1</pre>
  • immediate
    • andi을 통해서 logical immediate을 할 수 있다.
    • 예 : <pre>andi $t0, $t2, "1111" * 2^10</pre>

 

• bitwise OR
  • 일부를 1로 하고 나머지는 그대로 한다.
  • 원하는 bit을 1로 할 수 있다.(보존할 수 있다.)
  • 예 : <pre>or $t0, $t2, $t1</pre>
  • immediate
    • ori을 통해서 immediate을 할 수 있다.
    • 예 : <pre>ori  $t0, $t2, "1111" * 2^10</pre>

 

• bitwise NOR
  • MIPS는 NOT operation을 제공하지 않는다.
  • 대신 $zero와 NOR을 연산한다.
    • a NOR b = NOT( a OR b )
    • (0, 0) = 1, 나머지는 0으로 한다.
  • 예 : <pre>nor $t0, $t1, $zero</pre>

 

참고 : high-level language에서의 if-&&, ||, !

if문 안에서 &&, ||, !는 없어도 구현할 수 있기에 필수적인 것은 아니다.

그저 프로그래머의 편의를 위한 것이다.

 

 

---

Data Transfer Instruction

= Memory access instruction

 

메모리에서 데이터를 가져오고 저장하는 instruction이다.

RISC style은 Load와 Store을 이용해서 메모리에 접근한다.

 

Data transfer instruction은 base addressing mode을 사용한다.

 

• Load : memory's data → register
• Store : register's data → memory

 

Load vs Store

Load와 store는 작동하는 방식이 다름에 주의해야 한다.

어셈블리 : <pre>opcode  rt  rs</pre>

Load : rt ← rs

Store : rt → rs 

 

Base addressing mode

예를 들어 <pre>A[8]</pre>의 데이터는 <pre>32($s3)</pre>와 같이 나타낸다.

Array A의 시작주소인 A[0]에서 index 8까지는 8*4byte가 차이난다.

 

다음과 같은 I-type format으로 구성된다.

Opcode는 주로 6bit을 사용하기 때문에 offset으로는 16bit가 가능하다.

만약 offset이 매우 크다면 lui와 ori을 이용한다.

 

예시

C에서 <pre>A[12] = h + A[8]</pre>과 같은 코드는 다음과 같은 MIPS code로 컴파일된다.

 

<pre>

lw    $t0, 32($s3)    // load $t0 <- A[8]

add  $t0, $s2, $t0  // A[8] = h + A[8]

sw   $t0, 48($s3)   // store A[12] <- A[8]

</pre>

 

Base addressing mode을 사용하는 이유? : Direct mode를 사용하지 않는 이유?

Base register와 offset을 같이 제공한다.

메모리 주소를 직접 사용하지 않고 offset을 이용해서 나타낸다.

메모리 주소를 직접 사용하게 되면 instruction의 길이가 32bit을 넘게 되고 그렇게 되면 fetch를 2번 해야 한다.

즉, 메모리에 2번 갔다와야 하기 때문에 성능이 저하된다.

 

---

Large Constants

Immediate operand가 너무 큰 수여서 16bit로 표현하기 힘든 경우 addi 대신 register을 이용한다.

이 때는 총 3개의 machine instruction이 수행된다.

 

이 때 special operation을 사용한다.

• <pre>lui  rt, constant</pre>
  • load upper immediate
  • 굉장히 큰 32bit constant에 대해 사용된다.
  • constant를 rt의 왼쪽 16개 bit에 복사한다.
  • 오른쪽 16개 bit는 0으로 초기화한다.

 

예시 1

<pre>a = b + (8 * 2^16 + 128);</pre>의 연산은 다음과 같이 수행된다.

 

<pre>

lui  $s0, 8               // $s0의 상단 16개 bit에 8을 넣는다.

ori  $s0, $s0, 128   // $s0의 하단 16개 bit에 128을 넣는다.

</pre>

 

예시 2

<pre>addi  $t1, $t2, 2^21</pre>은 immediate operand가 너무 커서 수행할 수 없다.

따라서 아래와 같은 instruction으로 대체한다.

 

<pre>

lui    $t0, upper 16 bits

ori    $t0, $t0, lower 16bits

add  $t1, $t2, $t0

</pre>

 

예시 3

Load/Store에서 immeidate operand가 너무 큰 경우도 lui와 ori을 이용한다.

 

<pre>lw  $t1, 2^21($s2)</pre>은 다음과 같이 수행된다.

 

<pre>

lui     $t0, upper 16bits

ori     $t0, $t0, lower 16bits

add   $t0, $t0, $s2

lw     $t1, 0($t0)

</pre>

 

---

예제

C 에서의 코드를 machine code로 바꿔보자

 

In C Code

아래 코드는 array v에서 v[k]와 v[k+1]을 swap하는 함수이다.

swap(int v[], int k) {
	int temp;
    temp = v[k];
    v[k] = v[k+1];
    v[k+1] = temp;
}

 

In Machine Code

muli	$2, $5, 4	// $5 : k -> $2 : index * 4 byte
add		$2, $4, $2	// $4 : v[0] -> $2 : v[k]의 주소
lw		$15, 0($s2)	// $15 <- v[k]
lw		$16, 4($s2)	// $16 <- v[k+1]
sw		$16, 0($s2)	// v[k+1] <- v[k]
sw		$15, 4($s2)	// v[k] <- v[k+1]
jr		$31			// return

 

---

Operand Type : Byte, Half word

word 단위의 operation 수행 뿐만 아니라 half word(=2byte), byte 단위의 operand도 지원해야 한다.

 

가장 자주 사용되는 데이터 타입은 character이다.

기존의 ASCII에서의 character는 1byte이었지만, 현재는 UTF-8, UTF-16의 8bit(byte), 16bit(half word)가 주로 사용된다.

또한 요즘에는 multimedia data가 많이 사용되는데 여기에서도 byte와 half word가 많다.

 

따라서 byte와 half word 단위의 데이터를 operand로 사용할 수 있도록 해야한다.

 

Load

레지스터는 32bit이므로 부족한 부분은 sign extension한다.

<pre>lh, lb</pre>을 통해서 이를 지원한다.

 

그런데 character 같은 경우에는 unsigned 데이터이므로 이 또한 operand로써 지원해야 한다.

이는 <pre>lhu, lbu</pre>을 통해 가능하다.

 

 

이렇듯 load의 종류만해도 5가지가 넘기 때문에 opcode가 부족하다.

R-format에서는 이를 위해 funct를 활용한다.

 

Store

store 을 할 때에는 이미 완성된 data에서 가장 오른쪽부터의 byte나 halfword을 저장하기만 하면 된다.

오히려 주변의 다른 데이터를 건드리면 crash가 발생할 수 있다.

따라서 extension 할 필요 없이 그저 <pre>sb, sh</pre>을 통해 저장하면 된다.