Instructions: Language of the Computer Part.2 - Computer Architecture

Conditional Operations

• 만약 조건이 true라면, 표시된 instruction으로 향하게 하는 분기 ( branch )
• 그렇지 않으면 그대로 진행

• beq rs, rt, L1
• 만약 rs==rt라면 L1이라고 표시된 instruction으로 이동

• bne rs, rt, L1
• 만약 rs≠rt라면, L1이라고 표시된 instruction으로 이동

• j L1
• 무조건 L1이라고 표시된 instruction으로 이동

Compiling If Statements

• C code

if (i == j) f = g+h;
else f = g-h;

• Compiled MIPS code

		bne $s3, $s4, Else
		add $s0, $s1, $s2
		j Exit
Else: sub $s0, $s1, $s2
Exit: ... <- 어셈블러가 계산한 주소

Compiling Loop Statements

• C code

while (save[i] == k) i += 1;

• Compiled MIPS code

Loop: sll $t1, $s3, 2 (처음 주어질 i index 만큼의 주소를 위해 2^2 = 4를 곱해둠)
			add $t1, $t1, $s6 (offset(위에서 구해둔 i*4)에 시작 주소 더하면 save[i]의 주소)
			lw $t0, 0($t1)
			bne $t0, $s5, Exit
			addi $s3, $s3, 1
			j Loop
Exit: ...

Basic Blocks

• Basic block이란 instruction들의 순서대로 모인 집합이다.
• embedded branch(일체형 분기)는 없다. ( 끝 부분을 제외하고 끝에는 있을 수 있음 )
• branch target(분기 대상, labeled)은 없다 ( 처음 시작 부분을 제외하고, 처음에는 있을 수 있음)
• 즉, 중간에는 branch(분기)도 없고, labeled된 ( 점프할 곳으로 지정된 ) 곳도 없다. 분기가 없는 일련의 연속 작업 덩어리
• 컴파일러는 최적화를 위해 이러한 basic block들을 찾아낸다.
• 진보된 (고성능) 프로세서는 basic block들의 수행을 가속시킬 수 있다.

MIPS Control flow Instructions

• MIPS conditional branch instructions

bne $s0, $s1, Lbl # 만약 $s0 != $s1이라면 Lbl
beq $s0, $s1, Lbl # 만약 $s0 == $s1이라면 Lbl

• Instruction format (I format):

• 어떻게 branch destination address가 특정되는가?

Specifying Branch Destination

• 16-bit offset에 추가된 레지스터(lw 및 sw에서와 같이) 사용
• 어느 레지스터? Instruction Address Register (the PC)
• instruction에 의해 자동으로 implied됩니다
• PC는 fetch 사이클 동안 업데이트(PC+4)되어 주소 유지

• instruction 이후 branch instruction의 지점 거리는 -2^15 ~ 2^15-1 로 제한하지만, 보통 대부분의 지점은 local.

In Support of Branch Instructions

• beq, bne와 같은 branch 명령어가 있지만, 다른 종류의 branch는 어떤가? 그것을 위해선 slt라는 명령어가 필요하다.

• Set on less than instruction

slt $t0, $s0, $s1 # if $s0 < $s1 then
									# $t0 = 1      else
									# $t0 = 0 

• instruction format (R format)

• Alternate versions of slt

	slti $t0, $s0, 25 # if $s0 < 25 then $t0=1 ...
	sltu $t0, $s0, $s1 # if $s0 < $s1 then $t0=1 ...
	sltiu $t0, $s0, 25 # if $s0 < 25 then $t0=1 ...

More Branch Instructions

• slt, beq, bne, 그리고 $zero를 사용해서 다른 여러 컨디션을 만들 수 있음

• less than

slt $at, $s1, $s2 # $at set to 1 if
bne $at, $zero, Label # $s1 < s2

• less than or equal to (ble $s1, $s2, Label)

• greater than (bgt $s1, $s2, Label)

• great than or equal to (bge $s1, $s2, Label)

Branch Instruction Design

• 왜 blt, bge은 없는가?

• Hardware는 ≤, ≥ 가 =, ≠ 보다 느리다
• 모든 분기를 지원하면, 한 instruction마다 기존보다 더 많은 일을 수행하게 되고, 클럭 속도가 느려진다
• 모든 instruction 전체가 불이익을 받는다 (느려진 클럭 속도로 인해)

• beq와 bne가 더 일반적인 경우로 잦게 쓰인다

Signed vs Unsigned

• Signed comparison: slt, slti

• Unsigned comparison: sltu, sltiu

• Example
• $s0 = 1111 1111 1111 1111 1111 1111 1111 1111
• $s1 = 0000 0000 0000 0000 0000 0000 0000 0001
• slt　$t0, $s0, $s1
• -1 < 1 ??→YES→ $t0 = 1.
• sltu　$t0, $s0, $s1
• 4,294,967,295 < 1 ??→NO→ $t0 = 0.
 

Other Control Flow Instructions

• MIPS는 unconditional branch instruction인 jump instruction이 존재.

j label # go to label

• Instruction format (J format)

만약 분기 대상 주소가 멀다면?

• 만약 분기 대상(branch target)이 너무 멀어서 16-bit offset으로도 표현할 수 없다면, ( branch addressing은 현재 PC + 16bits의 offset으로 위아래를 표현하므로 ) 어셈블러는 코드를 다시 작성한다.

　　　beq　$s0, $s1, L1 가 아닌,
　　　　　　　↓
　　　bne　$s0, $s1, L2
　　　j　　　L1
　L2:　...
		으로 바꿈

프로시저(함수(function) 어떤 작업) 실행의 6가지 단계

1. 메인 routine[Caller]이 파라미터(매개값)를 프로시저[Callee]가 접근가능한 곳에 위치시킨다.
• $a0~$a3: 매개값을 위한 4개의 레지스터

2. Caller가 제어권(control)을 Callee에게 넘겨준다.

3. Callee는 필요한 storage(메모리)를 얻는다.

4. Callee는 요구되는 일(하기로 된 서브루틴 작업)을 수행한다.

5. Callee는 결과값을 Caller가 접근가능한 곳에 위치시킨다.
1. $v0~$v1: 결과값을 위한 2개의 레지스터

6. Callee는 제어권(control)을 Caller에게 반납한다.
1. $ra: 하드웨어가 사용하는, 반환 주소를 위한 레지스터. Caller에게 제어권을 주기 위한 주소.
 

Register Usage

Instructions for Procedure Call

• MIPS procedure call instruction:

• 프로시저 리턴

Leaf Procedure Example

• C code

int leaf_example(int g,h,i,j)
{
	int f;
	f = (g + h) - (i + j);
	return f;
}

• 매개변수들 g는 $a0, h는 $a1, i는 $a2, j는 $a3에

• f는 $s0에. (여기서부터는 이 루틴 안이므로, 스택으로서 $s0)

• 반환값은 $v0

• MIPS code

• 스택은 위에서 아래방향이기 때문에 음수방향

Non-Leaf Procedure

• 프로시저 내에서 다른 프로시저를 호출하는 형태

• nested한 호출이 있으므로, Caller는 스택에 다음 값들을 저장해야 한다.
• 반환될 주소. Leaf와 다르게 $ra 하나에 의존할 수 없기 때문
• 필요한 매개값이나 임시 값들

• call 이후에 (한 루틴이 끝나면) 스택에 저장해둔 값을 복귀시켜야 한다.

• C code

int fact(int n)
{
	if (n < 1) return 1;
	else return n * fact(n - 1);
}

• MIPS Code

Aside: Spilling Registers

• 만약 callee가 할당된 argument ($a0 ~ $a3) 나 return value ($v0 ~ $v1) 레지스터보다 더 많이 필요하면 어떻게 하는가?
• callee는 stack을 사용한다.

• 일반적인 레지스터중 하나인 $sp($29)는 보통 스택을 처리하는데 사용된다.
• 스택에 데이터를 넣을 때 - push
• $sp = $sp - 4
• 스택에 데이터를 뺄 때 - pop
• $sp = $sp + 4

Local Data on the Stack

• $sp는 스택의 top을 가리키고 (activation record의 끝 주소), $fp(frame pointer)는 이번 프로시저에 할당되기 직전 가리키고 있던 스택포인터를 가리킴(activation record의 시작 주소)

• procedure frame (activation record)
• $fp에서 $sp까지. 하나의 function을 실행할 때 할당되는 메모리 공간.
• 몇몇 컴파일러들은 스택 공간을 관리하기 위해 사용한다.

• local data는 callee에 의해 할당된다.
• e.g., C의 automatic variables
 

Aside: Allocating Space on the Heap

• Text: 프로그램 코드 (instruction 들)
• pc(program count)가 이 영역에서 움직이면서 현재 실행될 Instruction을 가리킨다.

• Static data: 전역 변수들
• e.g., C에서 static 변수, constant array나 string…
• $gp(global pointer)는 static data를 가리키기 쉽도록 Text의 끝과 Dynamic data의 시작의 중간에 위치하여, +- offset으로 데이터를 가리켜 준다.

• Dynamic data: heap 메모리에 할당
• e.g., C에서 malloc, Java나 C++에서 new, …

• Stack: 현재 영역에서 사용할 자료 및 복귀 주소 등
• activation record들이 쌓였다 복구됨.

Addressing Mode Summary

Synchronization

• 두 개 이상의 프로세서(멀티코어)가 메모리의 같은 영역을 공유
• P1이 쓴 후, P2가 읽음
• 만약 P1과 P2가 제대로 동기화하지 않으면 데이터는 race-condition에 놓인다.
• 접근 순서를 잘 조절해야 함.

• 하드웨어가 지원해야 사용이 가능하다.
• Atomic read/write memory operation(하드웨어가 이러한 기능을 사용 가능해야 함)
• 한 번 실행하면 쉬지 않고 종료까지 달리는. 실행되었거나/실행되지 않았거나
• spin lock이라는 메커니즘을 구현할 때에도 사용됨
• 읽고 쓰는 중에는 이 메모리에 다른 접근이 허용될 수 없다.

• Atomic read/write memory operation을 지원하는 single instruction(단일 명령문)이 있음
• e.g., 레지스터↔ 메모리의 atomic swap
• 또는 instruction들의 atomic pair

Atomic Exchange Support

• atomic exchange(atomic swap) - 레지스터의 값을 atomic하게 메모리의 값으로 교환
• uninterrupable instruction.

• Load linked: ll rt, offset(rs)
• 가리키는 주소에 있는 값을 rt에 적재

• Store Conditional (조건적인 저장): sc rt, offset(rs)
• ll 이후로 해당 주소 위치의 값이 변하지 않았다면 ( 여전히 $r1에 둔 값과 같다면 ), 해당 주소 위치의 값을 rt로 (store O), 그리고 rt의 값을 1로, 그렇지 않다면 건드리지 않고 (store X), rt는 0으로
• 성공하면 ( ll 이후로 가리키는 주소 위치의 값이 변하지 않았다면 )
• rt에 1을 반환한다 (넣는다)
• 실패하면 ( ll 이후로 가리키는 주소 위치의 값이 변해있다면, 즉 그 사이에 다른 누군가 건드렸겠지 )
• rt에 0을 반환한다 (넣는다)
 

Example

try:  add $t0, $zero, $s4 # $t0에 $s4의 값을 MOV ( 저장 )
			ll $t1, 0($s1)      # load linked. $s1이 가리키는 주소 위치의 값을 가져와둠
			sc $t0, 0($s1)      # store conditional
													# $s1이 가리키는 주소 위치의 값이 그대로면($t1과 같다면),
													# $s1이 가리키는 주소 위치에 $t0의 값($s4에서 가져온)을 넣어주고 동시에 $t0에 1
													# 다르면 건드리지 않고 $t0에 0
			beq $t0, $zero, try # 저장에 실패했다면 반복
			add $s4, $zero, $t1 # $t1에 load된 값을 $s4에 MOV(저장)
													# 즉, $s4의 값과 $s1이 가리키는 주소의 위치의 값이 교환되는 결과를 atomic하게 수행

Assembler Pseudoinstructions

• 대부분의 어셈블러 Instruction들은 기계 instruction들을 1:1대응으로 표현한다.

• 실제 MIPS instruction에는 없지만, 어셈블러에서 사용할 수 있는 가짜 명령어

• 어셈블러가 이 명령어들을 실제 MIPS instruction들로 바꿔줌.

• psuedoinstructions: 어셈블러의 상상으로 꾸며낸 것들.

move $t0, $t1 -> add $t0, $zero, $t1
blt $t1, L -> slt $at, $t0, $t1
							bne $at, $zero, L

Translation and Stratup

Linking Object Modules

• 하나의 실행가능한 이미지를 생성한다.
1. 조각들(segments)을 병합(merge)한다.
2. label을 결정한다. (label의 주소를 정한다.) 서로 다른 label을 사용했던 레퍼런스들을 해결함
3. 경로 의존적인 것들을 해결하고, 외부 참조들(external refs)을 처리한다. (patch 과정)

• relocating loader에 의해 조절되는 경로 의존성(location dependencies)은 그냥 둔다
• 하지만 가상 메모리 환경(현재 컴퓨터들이 주로 사용하는 형태)에서는, 그럴 필요가 없다(버려도 된다.)
• 가상 메모리 환경은, 모든 프로그램들이 같은 메모리 영역을 사용한다. 그러므로 경로 의존 정보는 없어진다.
• 즉, 프로그램은 가상 메모리 공간의 절대 경로로 로드될 수 있다. 절대 주소를 사용한다.

Loading a Program

• 디스크로부터 이미지 파일을 메모리에 Load(적재)
1. segment size들을 결정하기 위해 header를 읽어들인다.
2. 가상 메모리 공간을 만든다.
3. 텍스트와 초기 데이터를 메모리에 복사한다.
1. 혹은 이것만으로 문제가 발생할 수 있다면, page table 전체를 세팅하기도 한다.
4. 스택에 매개값들(arguments)을 세팅한다.
5. 레지스터들을 초기화한다. ($sp, $fp, $gp 포함..)
6. startup(시동) 루틴으로 점프한다.
1. 매개값들(arguments)을 $a0~에 복사하고, main을 호출한다.
2. main이 return되면, exit syscall을 수행한다.

Compiler Benefits

• 버블 정렬을 통해 본 성능 비교
• 100,000개의 데이터(word, 무작위 값들로 초기화된 배열)를 정렬하는 작업을 Pentium 4(3.06 GHz clock rate, 533MHz system bus), 2GB DDR SDRAM, Linux 2.4.20 환경에서 테스트.