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

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

이번 글에서는 지난 글에 이어 명령어 집합에서의 연산과 control flow, 그리고 인코딩에 대해서 다룰 것이다.

2024.03.10 - [Computer Architecture] - [컴퓨터구조#1] ISA(Instruction Set Architecture, 명령어 집합 구조)의 원리 알아보기 (1) - ISA 분류/Memory Addressing/피연산자의 종류와 크기

목차

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

---

4. Instruction Set에서의 연산

대부분의 ISA에서 지원되는 연산자들은 다음과 같이 분류될 수 있다. 

연산 종류	예시
산술, 논리	정수 산술 연산, 논리 연산: 덧셈, 뺄셈, AND, OR, 곱, 나눗셈
데이터 이동	load-stores (메모리에서 레지스터로 load, 레지스터에서 메모리로 store)
컨트롤	브랜치, 점프, procedure 콜과 리턴, 트랩
시스템	운영체제 시스템 콜, 가상메모리 관리 명령어
플로팅 포인트	플로팅 포인트 연산: 덧셈, 곱셈, 나눗셈, 비교
십진법	십진법 덧셈, 곱셈, decimal-to-character 전환
문자열	문자열 이동, 비교, 탐색
그래픽	픽셀 및 vertex 연산, 압축/해제 연산

가장 많이 실행되는 명령어는 가장 단순한 연산들이다. 예를 들어, 정수 프로그램을 돌리는 경우 인텔 80x86에서는 10개의 단순한 명령어가 실행된 명령어의 96%를 차지한다.

80x86의 Top 10 명령어들

이러한 명령어들은 앞 표의 variation으로서 명령어가 포함하는 데이터 타입에 따라 달라지며, 모든 컴퓨터의 모든 응용에서 찾아볼 수 있다.

---

5. Control Flow를 위한 명령어

브랜치와 점프 명령어의 행동 측정은 다른 응용들과는 다르기 때문에, 이 챕터에서는 이전의 내용들과 거의 공통점이 없는 control flow 명령어의 사용을 조사할 것이다. Control flow 변화의 유형은 다음 4가지로 분류할 수 있다.

• Conditional branches
• Jumps
• Procedure calls
• Procedure returns

이 명령어들의 상대적인 빈도는 다음과 같다. Conditional branch가 가장 우세한 것을 알 수 있다.

load-store 컴퓨터에서 벤치마크를 돌린 경우

Control Flow 명령어를 위한 주소 모드

Control flow 명령어의 목적지 주소destination address는 항상 지정되어야 한다. 대부분의 경우에서 목적지는 명시적으로 지정된다. 이외 주요 예외 케이스는 컴파일 시간에 타겟에 대한 리턴값이 정해지지 않는 procedure return이다. 목적지를 지정하는 가장 흔한 방법은 PC에 변위를 추가하는 것이다. 이런 종류의 control flow 명령어는 PC-relative라 불린다. PC-relative한 브랜치나 점프는 타겟이 보통 현재 명령어 근처에 있다는 점과 이로 인해 현재 PC와 관련된 위치를 표현하는 데 더 적은 비트를 요구한다는 점에서 이점이 있다. PC-relative addressing을 사용하는 것은 코드가 로드된 지점과 독립적으로 돌아갈 수 있도록 한다. 이러한 position independence 특성은 프로그램이 링크되었을 때 일들을 줄여줄 수 있고, dynamic하게 링크된 프로그램의 실행에 유용하다.

컴파일 시간에 타겟이 알려지지 않은 경우 return과 indirect jump를 구현하기 위해서는 PC-relative addressing 이외의 방법이 필요하다. 타겟을 동적으로 지정하여 런타임에 변할 수 있도록 하는 방법이 필수적이다. 이러한 동적 주소는 타겟 주소를 포함하는 레지스터에 이름을 붙이는 것만큼 간단할 수 있다. 혹은, jump가 어떤 주소 모드도 타겟 주소를 제공하도록 허용할 수도 있다.

이러한 레지스터 indirect jump는 다음 4가지의 중요한 feature에도 유용하다:

• 대부분의 프로그래밍 언어에서의 case나 switch문 (여러 대안 중 하나를 선택)
• C++나 Java 같은 객체 지향 언어에서의 virtual functions나 methods (argument 유형에 따라 서로 다른 루틴을 호출할 수 있게 함)
• C나 C++ 같은 언어에서의 high-order functions나 function pointers (함수를 argument로서 전달하여 객체 지향 프로그래밍의 일부 특성 부여)
• Dynamically shared libraries (프로그램 실행 전 정적으로 로드 및 링크되는 대신, 프로그램에서 실제로 호출될 때만 라이브러리가 런타임에 로드되고 링크됨)

이 모든 네 가지 경우에서 타겟 주소는 컴파일 시간에 알려지지 않기 때문에 보통 레지스터 indirect jump 전에 메모리에서 레지스터로 로드된다.

모든 브랜치들은 일반적으로 타겟을 지정하기 위해 PC-relative addressing을 사용한다. 이러한 변위의 분포를 아는 것은 어떤 브랜치 오프셋을 지원할지 선택하는 데 도을 줄 수 있고, 따라서 명령어 길이와 인코딩에 영향을 줄 수 있다. 다음 그래프는 명령어에서 PC-relative 브랜치들의 변위 분포를 보여준다. 대략 75% 이상의 브랜치가 순방향이다.

타겟과 브랜치 명령어 사이의 명령어 수로 표현한 브랜치 거리

정수 프로그램에서 가장 빈번한 브랜치는 4~8비트로 인코딩 가능한 대상으로 이루어져 있다. 이 결과는 짧은 변위displacement만으로도 브랜치에 대해서 종종 충분하며, 설계자가 더 작은 브랜치 변위를 갖는 더 짧은 명령어를 가짐으로써 인코딩 밀도를 얻을 수 있다는 것을 보여준다. 

Conditional Branch Options

Control flow의 대부분의 변화가 브랜치이기 때문에, 브랜치 조건을 어떻게 지정하는지 결정하는 것은 중요하다. 다음 표는 오늘날 일반적으로 사용되는 기술들과 장단점을 보여준다.

브랜치 조건 평가에 사용되는 기술들과 장단점.

Condition code는 다른 목적으로도 사용되는 ALU 연산에 의해 설정될 수 있음에도 불구하고, 프로그램 측정 결과는 이들이 드물게 발생한다는 것을 보여준다. 조건 코드의 주요 구현 문제는 조건 코드가 명령어의 비트에 의해 제어되기보다 큰(또는 무작위로 선택된) 일부 명령어에 의해 설정될 때 발생한다. Compare and branch 컴퓨터는 종종 비교를 제한하고 조건 레지스터를 사용하여 더 복잡한 비교를 수행한다. 

브랜치의 가장 주목할 만한 특성 중 하나는 많은 수의 비교는 단순한 테스트이며 대부분 0과 비교된다는 것이다. 따라서, 어떤 아키텍처는 compare and branch 명령어가 사용되는 경우 이러한 비교를 특별한 케이스로 분리하기도 한다. 다음 그래프는 conditional branching에서 서로 다른 comparison의 빈도를 나타낸다.

Less than or equal 브랜치가 가장 우세한 것을 확인할 수 있다. 

Procedure Invocation Options

Procedure call과 returns는 control transfer를 포함하며 몇 state를 절약해 줄 수도 있다. 적어도 리턴 주소는 어딘가, 때때로 특별 링크 레지스터 혹은 그냥 GPR에 저장되어야 한다. 오래된 아키텍처는 많은 레지스터를 저장하는 메카니즘을 제공하는 반면, 최신 아키텍처는 컴파일러가 각 저장되고 회복되는 레지스터마다 store과 load를 생성하도록 요구한다. 

호출 지점(call site) 자체에서 혹은 호출되는 procedure 내부에서인지에 따라 레지스터 저장에 사용되는 두 가지 기본적인 규칙이 있다.

• Caller saving: 호출하는 procedure가 호출 이후에도 접근을 위해 보존되어야 하는 레지스터를 저장. 호출되는 procedure는 레지스터에 대해 걱정하지 않아도 된다.
• Callee saving: caller saving과 정반대로, 호출되는 procedure가 사용하고자 하는 레지스터를 저장해야 하며, 호출하는 procedure는 신경쓰지 않아도 된다.

서로 다른 두 개의 procedure에서 globally visible한 값들에 대한 접근 패턴 때문에 caller save가 반드시 사용되어야 하는 경우가 있다. 예를 들어, procedure P1이 procedure P2를 호출하고 두 procedure 모두 전역변수 x를 조작한다고 가정하자. 만약 P1이 x를 레지스터에 할당했다면, P2에 대한 호출 이전에 P2가 아는 위치에 x를 저장해야 할 필요가 있다. 호출된 procedure가 레지스터에 할당된 양에 접근할 수 있는 시점을 컴파일러가 발견하는 능력은 별개의 컴파일이 가능한 경우에 복잡해진다. P2가 x를 건드리지 않을 수 있지만 다른 procedure(P3)을 호출할 수 있다. 이는 x에 액세스할 수 있지만 P2와 P3은 개별적으로 컴파일된다. 이러한 복잡성 때문에 대부분의 컴파일러는 호출 중에 접근될 수 있는 모든 변수를 caller가 저장한다.

caller나 callee 중 하나가 사용될 수 있는 경우, 어떤 프로그램은 callee save일 때 최적일 수도 있고 또 어떤 프로그램은 caller save일 때 최적일 수도 있다. 결과적으로, 오늘날 사용되는 대부분의 실제 시스템은 두 메카니즘을 조합하여 사용한다.  

요약

Control flow 명령어는 가장 자주 실행되는 명령어 중 하나이다. conditional branch에 대한 다양한 옵션이 존재하지만, 새로운 아키텍처에서는 브랜치 주소가 브랜치 위 또는 아래의 수백 개의 명령어로 이동할 수 있어야 할 것으로 기대된다. 이러한 요구사항은 최소 8 비트의 PC-relative 변위를 제안한다. 또한, return을 비롯한 현재 시스템의 많은 기능을 지원하기 위해 점프 명령어에 대한 레지스터 indirect 및 PC-relative 주소 지정도 기대된다.

이제 어셈블리 언어 프로그래머나 컴파일러 작성자가 보는 수준에서의 명령어 아키텍처 투어를 마쳤다. displacement, immediate, register indirect 주소 모드를 가진 load-store 아키텍처를 선호하는 경향이 있다는 것까지 확인해 보았다. 이 데이터들은 8-, 16-, 32-, 64-비트의 정수 및 32-, 64-비트의 플로팅 포인트 데이터이다. 이 명령어들은 단순한 연산, PC-relative conditional branches, 점프, procedure call을 위한 점프 및 링크 명령어, procedure return을 위한 register indirect jump를 포한다. 이제, 이 아키텍처를 하드웨어가 실행하기 쉬운 형태로 표현하는 방법을 살펴보자.

---

6. 명령어 집합 인코딩

위에 언급된 선택지들은 명령어들이 프로세서의 실행을 위해 이진 표현으로 인코딩되는 방식에 영향을 준다. 이 표현은 컴파일된 프로그램의 크기뿐만 아니라 프로세서의 구현에도 영향을 준다. 이때 프로세서는 표현을 디코딩하여 빠르게 해당 연산과 피연산자를 찾아내야 한다. 연산은 보통 opcode라 불리는 한 필드에 지정된다. 앞으로 살펴보겠지만, 연산과 주소 모드를 어떻게 인코딩할 것인지가 중요한 결정이다.

이 결정은 주소 모드의 범위와, opcode와 모드 간의 독립 정도에 따라 달라진다. 하나의 메모리 피연산자와 오직 한두 개의 주소 모드만을 갖는 load-store 컴퓨터에서는 주소 모드는 opcode의 일부로 인코딩될 수 있다. 명령어를 인코딩할 때, 레지스터 개수와 주소 모드의 수는 모두 명령어 크기에 중요한 영향을 미친다. 이는 레지스터 필드와 주소 모드 필드가 단일 명령어 내에서 여러 번 나타날 수 있기 때문이다. 사실 대부분의 명령어에서 많은 비트들이 opcode 지정보다 주소 모드와 레지스터 필드 인코딩에 더 많이 사용되고 있다. 설계자는 명령어 집합을 인코딩할 때 몇 가지 경쟁적인 force들의 균형을 잘 맞춰야 한다.

1. 가능한 많은 레지스터와 주소 모드를 가지려는 욕구
2. 레지스터와 주소 모드의 필드의 크기가 일반적인 명령어 및 전반적인 프로그램의 크게이 미치는 영향
3. 명령어를 파이프라인 구현을 쉽게 처리할 수 있는 길이로 인코딩하려는 욕구. 최소한, 설계자는 명령어가 임의의 비트 길이보다는 바이트의 배수가 되길 원한다. 많은 데스크탑/서버 설계자는 평균 코드 크기를 희생하고 고정된 길이의 명령어를 사용하기를 선택했다.

다음 그림은 명령어 집합을 인코딩하는 인기 있는 세 가지 선택지를 보여준다. 

• variable: 거의 모든 주소 모드를 모든 작업과 함께 사용할 수 있도록 한다. 많은 주소 모드와 연산이 있는 경우 적합하다. 각 address specificer는 주소 모드와 해당 피연산자에 대한 specifier 길이를 결정한다. 사용되지 않은 필드는 포함되지 않으므로 코드로 표현하면 가장 작다.
• fixed: 연산과 주소모드를 opcode로 결합한다. 보통 모든 명령어에 대해 단일 크기만 가지고 있을 것이다. 주소 모드와 연산이 적은 경우 적합하다. 같은 수의 피연산자만 요구한다. 보통 코드 크기는 가장 크다.
• hybrid: variable과 fixed의 절충안. opcode에 의해 지정되는 여러 가지 포맷을 가지며, 주소 모드 지정에 한두 개의 필드 및 피연산 주소를 추가하게 된다.

variable encoding과 fixed encoding의 트레이드오프는 프로그램 크기와 프로세서의 디코딩 용이성이다. Variable은 프로그램을 나타내는 데 가능한 적은 비트를 사용하려고 하지만, 개별 명령어는 크기와 수행할 작업량 면에서 매우 다양할 수 있다. 

variable length, fixed length, hybrid 명령어 인코딩 방식

이 예시에서 add는 두 개의 피연산자를 갖는 32 비트 정수 덧셈 명령어를 뜻하며, 이 opcode는 1바이트를 차지한다. 80x86 주소 지정자address specifier는 1 또는 2바이트로, src/dest 레지스터(EAX)와 주소 모드(이 경우 displacement), 그리고 base 레지스터(EBX)를 나타낸다. 32비트 모드에서, 주소 필드의 크기는 1바이트 혹은 4바이트이다. 1000은 2^8보다 크므로, 전체 명령어의 길이는 1(opcode)+1(주소 지정자)+4(주소 필드 for 1000)=6바이트가 된다. 

* 지난 글을 참고하면, add EAX, 1000(EBX)는 displacement 주소 모드로, Regs[EAX] ← Regs[EAX] + Mem[1000+Regs[EBX]] 를 의미한다는 것을 알 수 있다.

80x86 명령어의 길이는 1에서 7바이트이다. 80x86 프로그램은 보통 고정 포맷을 사용하는 RISC 아키텍처보다 작다. 

variable과 fixed라는 두 극단의 명령어 집합 디자인을 바탕으로, 크기의 variability와 다양한 아키텍처의 일은 줄이면서도 코드 크기를 줄이기 위해 여러가지 명령어 길이를 제공할 수 있는, 두 방법을 합친 hybrid 접근법이 자연스레 떠오르게 된다. hybrid 인코딩 방식의 예시를 간단히 살펴보자.

Reduced Code Size in RISCs

RISC 컴퓨터가 임베디드 응용에서 사용되기 시작하면서, 32비트 고정 포맷은 비용 및 작은 코드 크기 면에서 중요한 책임을 지니게 되었다. 이에 여러 제조업체에서 16비트와 32비트 명령어를 모두 제공하는 RISC 명령어의 새로운 하이브리드 버전을 제공했다. 좁은 명령어는 더 적은 연산, 더 작은 주소/immediate 필드, 더 적은 레지스터, 그리고 기존 RISC의 3개 주소 형식이 아닌 2개의 주소 형식을 지원한다. 

이전 섹션에서 논의한 명령어 집합 설계의 구성요소에 대한 결정은 variable과 fixed 인코딩 중에서 설계자가 선택할 수 있는지를 결정한다. 선택권이 주어진다면, 성능보다 코드 크기에 관심 있는 설계자는 variable 인코딩을, 코드 크기보다 성능에 관심 있는 설계자는 fixed 인코딩을 선택할 것이다.