[컴퓨터구조#1-3] ISA(Instruction Set Architecture, 명령어 집합)의 원리 알아보기 - 컴파일러의 역할/MIPS 아키텍처

참고: Computer Architecture: A Quantitative Approach (5th edition) - Appendix A. Instruction Set Principles

ISA 원리 시리즈의 마지막으로, 이번 글에서는 지난 글에 이어 ISA에서의 컴파일러의 역할과 MIPS 아키텍처에 대해 알아볼 것이다.

2024.03.10 - [Computer Architecture] - [컴퓨터구조#2] ISA(Instruction Set Architecture, 명령어 집합 구조)의 원리 알아보기 (2) - 연산(Operations)/Control Flow/인코딩(Encoding)

목차

1. ISA 분류하기
2. Memory Addressing
3. 피연산자의 종류와 크기
4. Instruction Set에서의 연산(Operations)
5. Control Flow를 위한 명령어
6. 명령어 집합 인코딩
7. 컴파일러의 역할
8. MIPS 아키텍처

---

7. 컴파일러의 역할

이 챕터에서는 컴파일러 관점에서 명령어 집합의 주요 목표에 대해 이야기할 것이다. 

최신 컴파일러의 구조

최신 컴파일러는 다음과 같은 구조를 가진다. 더 최적화되어 있을수록 더 많은 pass를 가진다.

이 구조는 여러 최적화 단계를 거쳐 컴파일된 프로그램이 동일한 인풋에 대해 동일한 아웃풋을 산출해 낼 확률을 증가시킨다.

컴파일러 작성자의 주된 목표는 정확성과 컴파일된 코드의 속도이다. 다른 목표로는 빠른 컴파일 과정, 디버깅 지원, 여러 언어 간 상호 운용성 등이 있다. 컴파일러의 pass는 보통 높은 레벨(더 추상화된 표현)을 낮은 레벨의 표현으로 바꾸어, 결국 명령어 집합에까지 이르게 된다. 이러한 구조는 변환의 복잡성을 다루는 데 도움을 주고 버그가 없는 컴파일러를 더 쉽게 만들 수 있도록 한다.

현대 컴파일러에서 수행되는 최적화는 변환 스테일에 따라 다음과 같이 분류될 수 있다.

• 높은 레벨의 최적화High-level optimizations: 다음 최적화 pass에 전달되는 아웃풋의 소스에 수행됨
• 로컬 최적화Local optimizations: 일직선의 코드 조각(컴파일러 사람들은 basic block이라 부름)에 있는 코드만 최적화
• 전역 최적화Global optimizations: 로컬 최적화를 브랜치로 확장하고, 최적화 루프를 목표하는 변환 집합을 도입
• 레지스터 할당Register allocation: 피연산자 레지스터와 관련
• 프로세서-의존적 최적화Processor-dependent optimizations: 특정 아키텍처 지식의 이점을 활용

레지스터 할당

레지스터 할당은 그 역할 때문에 코드의 속도 향상과 최적화를 유용하게 하는 데 있어 가장 중요한 기법 중 하나이다. 오늘날의 레지스터 할당은 graph coloring 기술에 기반한다. 간단히 말하면 제한된 색깔 집합을 사용해서 dependency graph의 인접한 두 노드가 같은 색깔을 갖지 않도록 하는 것이다. 이 graph coloring은 정수형 변수를 위한 전역 할당이나 부동 소수점을 위한 추가 레지스터에 사용할 수 있는 일반 목적 레지스터general-purpose register가 최소 16개 이상 존재할 경우 가장 잘 작동한다.

성능 최적화 영향

다음 그래프는 두 개의 프로그램(mcf, lucas)을 실행하는 경우 다양한 최적화 기법의 효과를 보여준다. 이 경우 최적화된 프로그램은 그렇지 않은 프로그램 대비 25%에서 90% 적은 명령어로 실행된다. 즉, 설계자architect가 해결하고자 하는 문제점을 컴파일러가 완전히 없애버릴 수도 있으므로, 새로운 명령어 집합 특징을 제안하기 전에 최적화된 코드를 살펴보는 것의 중요성을 시사한다.

컴파일러 기술에 대한 설계자의 결정의 영향

컴파일러와 높은 레벨의 언어 간 상호작용은 프로그램이 ISA를 사용하는 방식에 큰 영향을 미친다. 이때 두 가지 중요한 질문이 있다: 변수들은 어떻게 할당되고 주소 붙여지는가? 변수를 적절하게 할당하려면 얼마나 많은 레지스터가 필요한가? 이 질문들에 답하기 위해, 현재의 높은 레벨 언어들이 데이터를 할당하는 3가지 분리된 영역에 대해 살펴보자.

• 스택stack: 로컬 변수를 할당하는 데 사용된다. procedure 콜에 따라 커지고, 리턴에 따라 줄어든다. 스택의 오브젝트들은 스택 포인터에 의해 상대적으로 주소가 붙여지며 보통 array가 아닌 스칼라(단일 변수)이다. 스택 영역은 expression을 평가하기 위함이 아니라 기록 활성화를 위해 사용되므로, 변수들은 스택에서 거의 push나 pop되지 않는다.
• 글로벌 데이터 영역global data area: 전역변수나 상수와 같이 정적으로 선언된 오브젝트를 할당하는 데 사용된다. 이 오브젝트의 대부분은 array나 다른 aggregate 데이터 구조이다.
• 힙heap: 스택 원리에 따르지 않는 동적 오브젝트 할당에 사용된다. 힙에 있는 오브젝트는 포인터로 접근되며 보통 스칼라가 아니다.

레지스터 할당은 스택에 할당된 오브젝트의 경우 전역 변수보다 훨씬 더 효과적이며, 포인터로 접근되는 힙 오브젝트에 대해서는 불가능하다. 전역 변수와 어떤 스택 변수는, 같은 이름으로 불리기 때문에aliased(한 변수의 주소를 나타내는 다양한 방법이 존재하기 때문에 이 레지스터에 넣는 것이 불가능하게 될 수 있다) 할당하는 것이 불가능하다. 

설계자가 컴파일러 작성자에게 도움을 줄 수 있는 방법

오늘날 컴파일러의 복잡성은 복잡한 명령어 때문이 아니라(대부분의 프로그램은 locally simple하다), 프로그램의 규모가 크고 상호작용 과정에서 globally complex하기 때문이다. 컴파일러 작성자들은 "frequent case는 빠르게, rare case는 정확하게"라는 원리 하에 일한다. 즉, 어떤 경우가 frequent하고 어떤 경우가 rare한지 알 수 있고 두 경우를 발생시키는 코드가 straightforward하다면, rare case에 대한 코드의 퀄리티가 크게 중요하지 않을 수 있다.

어떤 ISA의 특징은 컴파일러 작성자를 도울 수 있다. 이 특징들은 hard-and-fast 규칙으로 생각되어서는 안 되고, 컴파일러 작성자가 더 효율적이고 정확한 코드를 만들 수 있는 컴파일러를 더 쉽게 만들 수 있도록 하는 가이드라인으로 여겨져야 한다.

• regularity 제공: 명령어 집합의 3가지 주요 요소(연산, 데이터 타입, 주소 모드)가 orthogonal(=independent)이어야 함. 즉, 어떤 주소 모드가 적용될 수 있는 모든 연산에 대해서, 모든 주소 모드가 적용 가능하다면 연산과 주소 모드는 orthogonal이다. 이 특징은 코드 생성을 단순화하며 생성할 코드가 컴파일러에서 두 pass로 쪼개지는 경우 중요하다.
• 솔루션이 아닌 primitive 제공
• 여러 대안 간 trade-off를 단순화
• 컴파일 시간에 상수로 알 수 있는 quantity를 bind하는 명령어 제공

이번 섹션에서는 몇 가지 추천 사항에 대한 논의가 있었다. (1) graph coloring을 사용하는 레지스터 할당을 단순화하기 위해 적어도 16개의 일반 목적 레지스터를 갖는 ISA일 것 (2) orthogonality: 지원되는 모든 주소 모드는 데이터를 전달하는 모든 명령어에 적용될 것 (3) primitive 제공, trade-off 단순화, 런타임에 상수를 바인딩하지 않을 것 → 단순함의 측면에서 오류를 범하는 것이 나음.

---

8. MIPS 아키텍처

* MIPS: 64비트 load-store 아키텍처.

MIPS ISA와 RISC 특징들은 지금까지 살펴본 모든 관찰들에 기반하여 살펴볼 수 있다.

1. ISA 분류하기	load-store 아키텍처를 갖는 일반 목적 레지스터를 사용할 것
2. Memory Addressing	displacement(12-16비트의 주소 오프셋), immediate(8-16비트), register indirect의 주소 모드를 지원할 것
3. 피연산자의 종류와 크기	8-, 16-, 32-, 64- 비트의 정수와 64 비트 IEEE 754 부동 소수점을 지원할 것
4. Instruction Set에서의 연산(Operations)	실행되는 명령어의 대부분을 차지하는 load, store, add, subtract, move register-register, shift의 단순한 명령어를 포함할 것
5. Control Flow를 위한 명령어	compare equal(==), compare not equal(!=), compare less(<), branch(적어도 8비트의 PC-relative 주소), jump, call, return
6. 명령어 집합 인코딩	성능에 관심이 있다면 fixed instruction encoding을, 코드 크기에 관심이 있다면 variable instruction encoding을 사용
7. 컴파일러의 역할	적어도 16개의 일반 목적 레지스터, 모든 주소 모드가 모든 데이터 이동 명령어에 적용될 것, 최소한의 명령어 집합을 목표로 할 것

이 추천사항들을 MIPS가 어떻게 만족하는지 보여주면서 MIPS를 소개할 것이다. 대부분의 최신 컴퓨터와 같이, MIPS는 다음을 강조한다: 단순한 load-store 명령어 집합, fixed 명령어 집합 인코딩을 포함한 파이프라인 효율성을 위한 디자인, 컴파일러 타겟으로서의 효율성

MIPS는 인기 있는 프로세서 종류이며 이해하기 쉬윈 아키텍처이기 때문에 공부하기 좋은 아키텍처 모델이다. 1985년에 첫 MIPS 프로세서가 나온 이후 여러 버전이 있었다. 이 중 MIPS64라 불리는 버전을 사용할 것이며, 여기에선 편의상 MIPS로 줄여 이야기할 것이다.

MIPS 레지스터

MIPS64는 R0, ..., R31의 32개의 64비트 일반 목적 레지스터(GPR)을 가진다. GPR은 정수 레지스터로도 알려져 있다. 또한, 32개의 single-precision(32비트)나 32개의 double-precision(64비트) 값을 저장할 수 있는 32개의 부동 소수점 레지스터(floating-point register, FPR) F0, ... , F31을 가진다. single-precision이 사용되는 경우 FPR의 절반만 사용되며, MIPS는 두 개의 single-precision 피연산자가 하나의 64비트 FPR에서 작동하는 명령어 또한 포함하고 있다.

R0의 값은 항상 0이다. 몇 개의 특별한 레지스터는 GPR로/로부터 변환될 수 있다. FPR과 GPR 간 이동에 관한 명령어도 있다.

MIPS 데이터 타입

정수형: 8비트 바이트, 16비트 반워드, 32비트 워드, 64비트 더블워드

부동 소수점: 32비트 single precision, 64비트 double precision

MIPS64의 연산은 64비트 정수와 32- 혹은 64- 비트 부동소수점에 대해 이루어진다. 바이트, 반워드, 워드는 GPR에 로드된다. 이때 64비트의 GPR을 채우기 위해 0이나 sign bit로 채워진다. 일단 로드되면 64비트 정수 연산으로 이뤄진다.

MIPS 데이터 이동을 위한 주소 모드

데이터 주소 모드는 16비트 필드를 가지는 immediate와 displacement 뿐이다. Register indirect는 16비트 displacement 필드에 0을 둠으로써 이루어지며, 16비트 absolute addressing은 레지스터 0을 기본 레지스터로 사용함으로써 이루어진다. 

MIPS 메모리는 64비트 주소를 가지며 byte addressable하다. 소프트웨어가 Big Endian과 Little Endian 중 선택할 수 있는 모드 비트를 갖고 있다. MIPS가 load-store 아키텍처이기 때문에, 메모리와 GPR/FPR 간 모든 참조는 load 혹은 store을 통해서 이뤄진다. 위에서 언급된 데이터 타입을 지원하기 위해, GPR을 포함하는 메모리 접근은 바이트, 반워드, 워드, 더블워드가 될 수 있다. FPR은 single- 혹은 double-precision으로 load/store될 수 있다. 모든 메모리 접근은 align되어야 한다.

MIPS 명령어 포맷

MIPS가 두 개의 주소 모드만을 갖기 때문에, 이들은 opcode로 인코딩될 수 있다. 파이프라인과 디코딩을 쉽게 하기 위한 프로세서를 만들기 위해, 모든 명령어는 6비트의 opcode를 갖는 32 비트로 되어 있다. 

MIPS의 명령어 레이아웃.

이와 같은 포맷은 단순하면서도 displacement 주소 모드를 위한 16비트 필드, immediate constant,, PC-relative 브랜치 주소를 제공할 수 있다.

MIPS 연산

MIPS는 위에 설명된 이외에도 몇 가지 추가된 간단한 연산을 지원한다. 명령어 종류는 크게 4가지로 나눌 수 있다: load와 store / ALU 연산 / 브랜치와 점프 / 부동소수점 연산

모든 MIPS 명령어 (SP = single precision, DP = double precision)

load와 store

모든 GPR이나 FPR이 load나 store될 수 있다(아무 효과 없는 R0 로드 제외). 다음은 load와 store 명령어의 예시이다. single-precision 부동 소수점은 FPR의 절반을 차지한다. single과 double precision 간 변환은 명시적으로 일어나야 한다. 부동 소수점 포맷은 IEEE 754를 따른다. 

모두 단일 주소 모드를 사용하며, 메모리 혹은 값은 align되어야 한다. 모든 데이터 타입에 대해 load와 store가 가능하다.

• ←에 사용되는 첨자는 전달되는 자료의 길이가 명확하지 않을 수 있을 때 사용된다. 즉, ←_n 은 n비트의 양을 전달하겠다는 것이다. z가 x,y로 전달되어야 한다면 x, y ← z 와 같이 표현한다.
• 필드 내 비트 선택을 표시하기 위해 첨자를 사용한다. 비트는 0으로 시작하는 MSB에서부터 라벨링된다. 첨자는 single digit이거나(e.g. Regs[R4]_0은 R4의 sign bit를 뜻한다) subrange일 수도(e.g. Regs[R3]_{56..63}은 R3의 least significant 바이트를 의미한다) 있다.
• Mem 변수는 메인 메모리를 나타내는 array로 사용되는데, byte address로 인덱싱되며 어떤 수의 바이트라도 전달할 수 있다.
• 필드를 복제하기 위해서도 첨자가 사용된다. (e.g. 0^{48}은 48비트만큼 0으로 채워진 필드를 의미한다.)
• ## 은 두 개의 필드를 이어 붙이는 데 사용(concatenate)된다.

예를 들어, R8과 R10이 64비트 레지스터라고 해보자.

이 수식은 R8의 내용물로 주소가 지정된 메모리 위치의 바이트(Mem[Regs[R8]])가 부호 확장(^24)되어 R10의 하위 절반에 저장되는 32비트를 만들게 되는 것을 의미한다. R10의 상위 절반은 변경되지 않는다.

ALU 연산

모든 ALU 연산은 register-register 명령어이다. 다음은 산술/논리 명령어의 예시이다.

모든 명령어의 immediate 형태는 16비트 sign-extended immediate를 사용해서 제공된다. 위 예시에서, LUI는 레지스터 R1의 비트 32~47을 로드(42 이진수 변환 시 101010이지만, immediate 필드는 16비트이므로)하고 나머지는 0으로 설정한다. LUI는 두 개의 명령어로 32비트 상수를 만들거나, 하나의 추가 명령어로 상수 32비트 주소를 사용해 데이터를 전송할 수 있도록 한다.

R0은 인기 있는 연산을 합성하는 데 사용된다. 상수를 로드하는 것은 단순히 피연산자가 R0인 immediate add이고, register-register 이동은 source 중 하나가 R0인 덧셈이다.

MIPS Control Flow 연산(브랜치와 점프)

MIPS는 두 개의 레지스터를 비교하는 비교 연산을 제공한다. 만약 조건이 참이라면 이 명령어는 목적지 레지스터에 참을 나타내기 위해 1을 저장하고, 아니라면 0을 저장한다. 이러한 연산들이 레지스터를 "설정"하기 때문에, 이들은 set-equal, set-not-equal, set-less-than 등으로 불린다. 이 비교에도 immediate 형태가 있다.

컨트롤은 점프와 브랜치 연산들을 통해서 이루어진다. 다음은 일반적인 브랜치와 점프 명령어의 예시이다.

 4개의 점프 명령어는 목적지 지정 방식과 링크 여부에 따라 분류된다. 2개의 점프(J, JAL)는 2비트가 shift된 26비트의 오프셋을 사용하고, PC의 하위 28비트를 목적지 주소를 결정하는 데 사용한다. 나머지 2개의 점프(JALR, JR)는 목적지 주소를 포함함하는 레지스터를 명시한다. 즉, 점프는 plain jump와 jump and link로 구분된다. 후자는 procedure call에 사용되며, 리턴 주소(다음에 실행될 명령어의 주소)를 R31에 저장한다.

모든 브랜치는 conditional이다. 브랜치 조건은 명령어에 의해 지정된다.

MIPS 부동 소수점 연산

부동 소수점 연산은 FPR을 관리하고 연산이 single 혹은 double precision 중 무엇으로 진행될지 나타낸다. MOV.S는 single-precision FPR 복사를, MOV.D는 double precision FPR 복사를 나타낸다. MFC1, MTC1, DMFC1, DMTC1은 single 혹은 double의 FPR과 정수 레지스터 간에 데이터를 이동한다. 

덧셈, 뺄셈, 곱셈, 나눗셈 부동 소수점 연산은 suffix D와 S를 통해 double인지 single인지 나타낸다. (e.g. ADD.D, ADD.S) 부동 소수점 비교는 브랜치 쌍으로 테스트할 수 있는 특별한 floating-point status register의 비트를 설정한다: BC1T(branch floating point True), BC1F(branch floating point False)

그래픽 루틴의 성능을 높이기 위해 64비트 FPR의 각 절반에서 부동 소수점 연산을 수행하는 명령어도 존재한다. 이를 paired single 연산이라 하며 ADD.PS, SUB.PS, MUL.PS, DIV.PS가 있다.

---

본격적인 컴퓨터 아키텍처 내용에 들어가기 앞서, 여기까지 ISA에 대해 간단히 복습해 보았다. ISA가 가져야 할 특징에 대해 먼저 알아보고 이를 포함하는 MIPS에 대해 알아보는 순서로 진행되었다. 이후 글에서는 파이프라인과 메모리 위계에 대해 알아볼 예정이다.