맨위로가기

스택 머신

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

스택 머신은 대부분의 명령어가 스택에서 피연산자를 가져와 스택에 결과를 저장하는 컴퓨터 아키텍처이다. 명령어는 연산 코드만 포함하고, 상수, 레지스터 또는 메모리 셀을 식별하는 추가 필드가 없어 명령어 디코딩을 단순화한다. 스택 머신은 후위 표기법(역 폴란드 표기법) 연산을 사용하여 ALU 작업을 수행하며, 가상 머신과 하드웨어 구현 모두에서 사용된다. 장점으로는 코드 밀도가 높고, 컴파일러 구현이 용이하며, 컨텍스트 스위칭이 빠르다는 점이 있다. 단점으로는 레지스터 머신에 비해 데이터 캐시 접근이 많고, 순수한 스택 머신에서는 명령어 재정렬이 어렵다는 점이 있다.

2. 설계

대부분의 스택 머신 명령어는 피연산자를 스택에서 가져오고 연산 결과를 다시 스택에 저장하는 것을 기본 원리로 삼는다. 스택은 여러 개의 입력 값이나 결과 값을 쉽게 관리할 수 있어 다양한 연산을 효율적으로 처리할 수 있다. 스택 머신 코드는 종종 p-코드라고도 불리며, 명령어는 주로 연산 코드(opcode)만으로 구성되고 상수, 레지스터, 메모리 주소 등을 명시하는 추가 필드가 없는 경우가 많다. 이를 제로 주소 형식(0-address format)이라고 부르며, 이 방식은 명령어 해독 과정을 크게 단순화시킨다.[1]

물론 분기(branch), 즉시 로드(load immediate), 로드/저장(load/store) 명령어처럼 추가 정보(인수 필드)가 필요한 경우도 있지만, 스택 머신은 이러한 경우에도 연산 코드와 인수를 비트(bit) 단위로 묶어 간결하게 표현하도록 설계되는 경우가 많다. 어떤 피연산자를 사용할지는 명령어의 순서에 따라 암묵적으로 결정된다. 일부 스택 머신 명령어 집합은 실제 하드웨어를 직접 제어하기보다는 가상 머신에서 해석되어 실행되도록 설계되기도 한다.

정수형 상수 값은 Push나 Load Immediate 같은 명령어를 통해 스택에 직접 저장된다. 메모리에 접근할 때는 별도의 Load 또는 Store 명령어를 사용하며, 이 명령어들은 접근할 메모리 주소를 직접 포함하거나 스택에 있는 값을 이용해 주소를 계산한다. 실제 사용되는 대부분의 스택 머신은 지역 변수나 형식 매개변수에 접근할 때, 명시적인 주소 계산 없이 현재 스택 포인터(stack pointer)나 프레임 포인터(frame pointer)로부터의 상대적인 위치(offset)를 이용하는 로드/저장 명령어 변형을 제공한다.

명령어 집합은 대부분의 산술 논리 장치(ALU) 연산을 데이터 레지스터나 주기억장치가 아닌, 표현식 스택(expression stack) 상에서 직접 수행한다. 이때 연산 방식은 후위 표기법(postfix notation) 또는 역 폴란드 표기법(Reverse Polish Notation, RPN)을 따른다. 예를 들어 덧셈(ADD) 명령어는 스택의 가장 위에 있는 두 값을 피연산자로 사용하고, 두 값을 스택에서 제거(pop)한 뒤 덧셈 결과를 다시 스택에 저장(push)한다. 대부분의 산술 표현식은 후위 표기법으로 쉽게 변환될 수 있어, 고급 프로그래밍 언어를 실행하는 데 매우 편리하다.

표현식 ''A''*(''B''-''C'') + (''D''+''E'')에 대한 이진 구문 트리


예를 들어, ''A''*(''B''-''C'')+(''D''+''E'')라는 수식을 후위 표기법으로 표현하면 ''A'' ''B'' ''C'' - * ''D'' ''E'' + + 가 된다. 이를 가상의 스택 머신에서 실행하는 과정은 다음과 같다.

(스택 내용은 가장 왼쪽이 최상단(가장 최근) 값을 의미한다.)

  • push A 실행 후 스택: `A`
  • push B 실행 후 스택: `B A`
  • push C 실행 후 스택: `C B A`
  • subtract 실행 후 스택: `(B-C) A` (C와 B를 꺼내 빼고 결과를 넣음)
  • multiply 실행 후 스택: `A*(B-C)` ((B-C)와 A를 꺼내 곱하고 결과를 넣음)
  • push D 실행 후 스택: `D A*(B-C)`
  • push E 실행 후 스택: `E D A*(B-C)`
  • add 실행 후 스택: `(D+E) A*(B-C)` (E와 D를 꺼내 더하고 결과를 넣음)
  • add 실행 후 스택: `A*(B-C)+(D+E)` ((D+E)와 A*(B-C)를 꺼내 더하고 결과를 넣음)


이처럼 산술 연산 명령어('subtract', 'multiply', 'add')는 스택의 최상단 값 두 개를 피연산자로 사용한다. 명령어 실행 시 피연산자들은 스택에서 제거되고, 연산 결과가 다시 스택에 저장되어 다음 명령어에서 사용될 수 있도록 한다.

스택 머신은 표현식 계산을 위한 스택과 서브루틴 호출 및 복귀 주소 저장을 위한 호출 스택(call stack)을 분리하여 가질 수도 있고, 하나의 통합된 스택으로 관리할 수도 있다. 스택을 분리하면 각 스택의 용도가 명확해지고 상호 간섭이 줄어들어 명령어 파이프라인 처리가 용이해지는 등 일반적으로 더 빠른 실행 속도를 기대할 수 있다. 데이터 처리용 스택(데이터 스택)과 함수 호출용 스택(리턴 스택)을 분리하는 방식은 배로스 B5000, Forth, PostScript, 자바 가상 머신 등 여러 시스템에서 채택되었다. 이 방식은 스택 관리 부담을 줄여 전체적인 성능 향상에 기여한다.

휴렛 팩커드(HP)의 일부 계산기 모델은 스택 머신 원리를 사용자 인터페이스에 적용한 것으로 유명하다. 이 계산기들은 값을 스택에 넣는 'Enter' 키가 특징이며, 역폴란드 표기법 방식으로 연산을 수행한다. 예를 들어 덧셈을 하려면, `[숫자 1] Enter [숫자 2] +` 순서로 키를 누른다. 이 과정에서 숫자 1과 2가 순서대로 스택에 저장(push)되고, '+' 키를 누르면 스택에서 두 숫자를 꺼내(pop) 더한 후 그 결과를 다시 스택에 저장(push)한다.

레지스터를 주로 사용하는 머신(레지스터 머신)에서도 시뮬레이션을 통해 스택 머신처럼 동작하게 만들 수 있으며, 이를 "가상 스택 머신"이라고 부르기도 한다.

2. 1. 스택 저장소

(인터프리터의 경우. 하드웨어 머신은 더 적을 수 있음)다중 스택 상단(TOS) 레지스터 또는 레지스터 파일 사용0회 (메모리 접근 없음)
(데이터 캐시 사이클 1회 발생)



위 표에서 볼 수 있듯이, 스택 상단 레지스터를 사용하거나 레지스터 파일을 활용하면 메모리 접근 횟수를 크게 줄여 연산 속도를 높일 수 있다. 특히 여러 개의 스택 상단 레지스터를 사용하는 경우, 메모리 접근 없이 레지스터 내에서 대부분의 연산을 처리할 수 있어 효율성이 극대화된다.

3. 계산의 스택 모델

컴퓨터 과학의 오토마타 이론에서 "스택 머신"은 메모리에 임의 접근할 수 없고, LIFO(Last In, First Out) 방식의 스택만을 사용하는 계산 모델이다. 이는 순수한 이론상의 모델이며, 실제 컴퓨터는 메모리의 특정 주소를 지정하여 접근할 수 있다는 점에서 차이가 있다.

스택 머신은 하나 또는 여러 개의 스택을 가질 수 있다. 프로그램의 초기 입력은 첫 번째 스택의 초기 상태로 주어지며, 다른 스택들은 비어있는 상태에서 시작한다. 스택 머신은 각 시점마다 '리드 상태' 또는 '라이트 상태' 중 하나를 가지게 된다. 각 상태는 해당 스택에서 읽어야 할(팝) 값의 개수 또는 스택에 써야 할(푸시) 값의 개수를 정의한다. 라이트 상태에서는 스택에 쓸 심볼과 다음으로 이동할 상태가 지정된다. 리드 상태에서는 알파벳의 각 문자에 대해, 해당 문자를 읽었을 때 이동할 다음 상태가 지정된다. 또한, 리드 상태에서는 스택이 비어 있을 경우 이동할 상태도 정의된다. 스택 머신은 특정 '정지 상태'에 도달하면 작동을 멈춘다.

스택을 하나만 가진 스택 머신은 계산 모델로서 능력이 제한적이다. 예를 들어, '0'이 n번 나온 뒤 '1'이 같은 횟수(n번)만큼 나오는 언어(0n1n)와 같은 비교적 단순한 언어도 인식하지 못한다. 1-스택 머신의 계산 능력은 유한 오토마톤보다는 높지만, 결정적 푸시다운 오토마톤보다는 낮다.

반면, 여러 개의 스택을 가진 스택 머신은 튜링 머신과 동일한 계산 능력을 가진다. 예를 들어, 스택 2개를 가진 머신은 튜링 머신의 동작을 모방할 수 있다. 이때 하나의 스택은 튜링 머신 테이프의 헤드 위치 왼쪽 부분을, 다른 하나는 오른쪽 부분을 대신하는 방식으로 작동한다.

4. 스택 머신형 명령어 집합

스택 머신형 명령어 집합에서는 대부분의 명령어가 피연산자를 스택에서 가져오고 연산 결과를 다시 스택에 저장한다고 가정한다. 예를 들어, 덧셈(ADD) 명령은 스택의 가장 위에 있는 두 값을 암묵적인 피연산자로 사용하여 더하고, 그 합을 다시 스택 맨 위에 저장(푸시)한다. 이 과정에서 피연산자로 사용된 두 값은 스택에서 제거(팝)된다. 스택은 여러 개의 입력 값이나 결과 값을 쉽게 다룰 수 있어 다양한 연산을 효율적으로 처리할 수 있다.

이러한 방식 때문에 스택 머신 코드는 종종 '''0 주소 형식'''이라고 불린다. 대부분의 명령어는 연산 코드(opcode)만으로 구성되며, 레지스터 번호나 메모리 주소, 즉시 값(immediate value) 등을 명시적으로 지정할 필요가 없다.[1] 이는 명령어 디코딩 과정을 크게 단순화하는 장점이 있다. 물론 분기(branch), 즉시 로드(load immediate), 로드/저장(load/store)과 같이 인수가 필요한 명령어도 있지만, 스택 머신은 이러한 경우에도 연산 코드와 인수를 비트(bit) 단위로 묶어 간결하게 표현하는 경우가 많다. 어떤 피연산자를 사용할지는 명령어의 순서에 따라 암묵적으로 결정된다. 일부 스택 머신 명령어 집합은 실제 하드웨어를 직접 구동하기보다는 가상 머신(virtual machine)에서 해석되어 실행되도록 설계되기도 한다.

정수 상수 같은 피연산자는 `Push`나 `Load Immediate` 같은 명령어를 통해 스택에 직접 푸시된다. 메모리에 접근할 때는 주로 별도의 `Load` 또는 `Store` 명령어를 사용하며, 이 명령어들은 메모리 주소를 직접 포함하거나 스택에 있는 값을 이용해 주소를 계산한다. 실제 사용되는 대부분의 스택 머신은 지역 변수(local variable)나 형식 매개변수(formal parameter)에 접근할 때 명시적인 주소 계산 없이도 가능하도록 로드-저장 명령어의 변형된 형태를 제공한다. 이는 현재 스택 포인터로부터의 상대적 위치(offset)나 프레임 포인터 레지스터로부터의 오프셋을 이용하는 방식으로 구현된다.

스택 머신의 명령어 집합은 대부분의 산술 논리 장치(ALU) 연산을 데이터 레지스터나 주 메모리가 아닌 표현식 스택(expression stack) 상에서 수행한다. 이는 후위 표기법(postfix notation) 또는 역폴란드 표기법(Reverse Polish Notation, RPN)과 유사한 방식이다. 많은 산술 표현식이 역폴란드 표기법으로 쉽게 변환될 수 있기 때문에, 고급 프로그래밍 언어를 실행하는 데 매우 편리하다.

예를 들어, ''A''*(''B''-''C'')+(''D''+''E'')라는 표현식은 역폴란드 표기법으로 ''A'' ''B'' ''C'' - * ''D'' ''E'' + + 와 같이 나타낼 수 있다. 이를 가상의 스택 머신에서 실행하는 과정은 다음과 같다.

# 스택 내용 (왼쪽이 가장 위, 가장 최근 데이터):

push A # A

push B # B A

push C # C B A

subtract # B-C A

multiply # A*(B-C)

push D # D A*(B-C)

push E # E D A*(B-C)

add # D+E A*(B-C)

add # A*(B-C)+(D+E)

`subtract`, `multiply`, `add`와 같은 산술 연산 명령어는 스택의 가장 위에 있는 두 피연산자에 대해 작동한다. 컴퓨터는 이 두 값을 스택에서 꺼내(팝) 계산한 뒤, 그 결과를 다시 스택에 넣는다(푸시).

스택 머신은 표현식 계산에 사용되는 스택과 함수 호출 및 복귀 주소 저장에 사용되는 호출 스택(call stack)을 분리하여 가질 수도 있고, 하나의 통합된 스택으로 사용할 수도 있다. 스택을 분리하면 각 스택의 용도가 명확해지고 상호 간섭이 줄어들어 명령어 파이프라인 처리가 용이해지므로 일반적으로 실행 속도가 더 빨라질 수 있다.

컴파일된 스택 코드에 대한 최적화도 활발히 연구되었다. 컴파일러의 백엔드 최적화를 통해 코드 품질을 크게 개선하고 성능을 향상시킬 수 있으며, 컴파일러 자체의 전역 최적화를 통해 추가적인 성능 향상을 기대할 수 있다.

스택 머신은 구현 방식에 따라 몇 가지 유형으로 나뉜다. 어떤 스택 머신은 레지스터 파일(register file)을 작은 크기의 스택으로 사용한다. ALU는 인덱스를 이용해 이 레지스터 스택에 접근한다. 레지스터 파일은 많은 트랜지스터를 필요로 하므로 주로 소규모 시스템에 적합하다. 다른 방식으로는 스택 자체를 주기억장치(RAM)에 두고, 스택의 최상단을 가리키는 포인터 레지스터를 사용하는 것이다. 배로스 B5000(Burroughs B5000)이나 HP 3000이 이 방식의 예시다. 드물게는 메모리상의 스택과 레지스터 파일 스택을 별도로 가지는 구현도 있다. B5000의 경우, 스택 상단의 두 데이터는 CPU 레지스터에 캐시처럼 보관하고 나머지 스택 데이터는 메인 메모리에 두는 방식을 사용했다.

회로 소자가 고속화되면서 메모리 접근과 같은 배선 지연이 성능 병목 현상이 되자, 스택을 계층적 캐시 구조에 담는 구현 방식이 등장했다. 명시적인 로드 명령어를 사용하지 않는 한, 스택 내 피연산자는 스택 상단부터 순서대로 사용된다. 따라서 스택 상단 부분을 고속의 기억 장치(캐시나 레지스터)에 우선적으로 보관하는 것만으로도 효과적인 프리페치(prefetch)가 가능해져 배선 지연의 영향을 줄일 수 있다. 많은 가상 스택 머신에서는 스택 상단을 메모리 영역이 아닌 호스트 머신의 레지스터로 구현한다. FPGA 상의 JAVA 프로세서인 JOP는 레지스터 파일보다 더 빠른 래치 회로(latch circuit)를 스택 상단 두 개 데이터 저장에 할당하기도 한다.

스택 기반 명령어 집합을 가진 머신은 여러 개의 스택을 가질 수도 있다. 스택이 두 개일 경우, 하나는 데이터 처리를 위한 '데이터 스택', 다른 하나는 서브루틴 호출 시 복귀 주소를 저장하는 '리턴 스택'(호출 스택)으로 사용된다. 데이터 스택과 리턴 스택을 분리하면 스택 관리 오버헤드를 줄여 전체적인 동작 속도를 크게 향상시킬 수 있다. 이 방식은 배로스 B5000, Forth, PostScript 등에서 독립적으로 개발되었으며, Java 가상 머신(Java Virtual Machine)에서도 사용된다.

휴렛 팩커드(Hewlett-Packard)의 계산기 중 일부는 스택 머신을 조작 모델로 사용한다. 이 계산기들은 값을 스택에 넣는 'Enter' 키가 특징적이다. 예를 들어 덧셈을 하려면 "숫자 1", "Enter", "숫자 2", "+" 순서로 키를 누른다. 이 조작으로 두 숫자가 스택에 푸시된 후, '+' 키를 누르면 두 숫자가 팝되어 더해지고 그 결과가 다시 스택에 푸시된다. 이런 방식을 사용하는 계산기를 역폴란드 표기법 계산기라고 부르기도 한다.

스택 머신은 레지스터 머신(register machine)이나 어큐뮬레이터 머신(accumulator machine)과 비교된다. 레지스터 머신은 여러 개의 고속 레지스터를 사용하여 임시 값을 저장하고, 어큐뮬레이터 머신은 단 하나의 특수 레지스터(어큐뮬레이터)를 중심으로 연산을 수행한다. 초기 컴퓨터 중에는 임시 레지스터 없이 항상 메모리 간 연산을 수행하는 방식도 있었다. 레지스터를 사용하는 일반적인 컴퓨터 아키텍처에서도 스택 머신을 시뮬레이션할 수 있으며, 이를 "가상 스택 머신"이라고 부른다.

5. 역사 및 구현

1961년 로버트 S. 바턴은 학회 발표를 통해 스택 머신의 개념을 처음으로 제시했다. 이 방식은 레지스터에 한 번에 두 개의 값만 유지하며, 제한된 사전 정의된 피연산자 집합을 사용하고 추가적인 피연산자, 함수, 서브루틴 정의를 통해 확장하는 구조를 가진다.

순수 스택 머신은 동일한 객체의 여러 필드에 접근하는 절차에서 비효율적인 면이 있는데, 이는 각 접근마다 객체 포인터를 스택에 다시 로드해야 하기 때문이다. 이러한 한계를 극복하기 위해 다양한 하이브리드 방식이 등장하게 되었다.

5. 1. 상용 스택 머신

하드웨어에서 직접 실행되는 스택 명령어 집합을 사용하는 상용 머신의 예는 다음과 같다.

5. 2. 가상 스택 머신

소프트웨어로 해석되는 가상 스택 머신의 예는 다음과 같다.

5. 3. 하이브리드 머신

순수 스택 머신은 동일한 객체의 여러 필드에 접근하는 데 비효율적인 면이 있다. 이는 각 접근마다 객체 포인터와 오프셋 계산을 반복해야 하기 때문이다. 이를 해결하기 위한 일반적인 방법 중 하나는 스택 머신에 레지스터 머신의 일부 기능을 도입하는 것이다. 주소 저장을 위한 레지스터 파일을 두고, 레지스터 스타일 명령어로 로드나 간단한 주소 계산을 수행하는 방식이다. 다만, 레지스터를 완전한 범용 목적으로 사용하면 스택 머신의 장점인 표현식 스택과 후위 표기법 명령어 사용의 의미가 줄어든다.

반대로, 레지스터 머신 아키텍처에 스택 머신의 푸시(push) 또는 팝(pop) 연산을 모방하는 메모리 주소 지정 방식을 추가하는 하이브리드 방식도 있다. 이 방식은 DEC의 PDP-11 미니컴퓨터에서 처음 사용되어 널리 알려졌으며, 이후 VAX 컴퓨터, Motorola 6809 및 M68000 마이크로프로세서에도 적용되었다. 이 방식은 초기 컴파일러가 스택을 더 쉽게 다룰 수 있게 하고, 스택 인터프리터나 스레드 코드를 사용하는 가상 머신을 효율적으로 지원하는 장점이 있다. 그러나 코드가 순수 스택 머신만큼 간결하지 않고, 실행 속도도 레지스터 아키텍처에 맞게 최적화된 코드보다 느릴 수 있다. 특히 스택 연산을 빈번하게 사용하는 것은 성능 저하를 유발할 수 있다.

비교적 최근의 '2세대 스택 머신'은 데이터 스택에서 메모리 주소 지정 부담을 덜기 위해 전용 주소 레지스터를 사용한다. 예를 들어, MuP21 프로세서는 'A' 레지스터를, GreenArrays 프로세서는 'A'와 'B' 두 개의 레지스터를 사용한다.[15]

x86 계열 마이크로프로세서는 대부분의 연산에 레지스터 스타일 명령어 집합을 사용하지만, x87 부동 소수점 연산에는 스택 명령어를 사용한다. 이는 인텔 8087 보조 프로세서 시절부터 이어진 방식으로, 프로그래머가 직접 접근할 수 있는 부동 소수점 레지스터 대신 80비트 너비의 8단계 깊이 스택을 사용한다. x87 연산은 x86 CPU의 지원에 크게 의존한다. 현대의 64비트 x64 아키텍처에서는 호환성을 위해 x87 FPU가 남아있지만, 일반적으로 사용되는 SSE의 부동 소수점 연산은 레지스터 지향 명령으로 바뀌었다.

6. 레지스터 머신과의 비교

스택 머신은 종종 레지스터 배열에 값을 저장하는 레지스터 머신과 비교된다. 레지스터 머신은 이 배열에 스택과 유사한 구조를 저장할 수도 있지만, 스택 인터페이스를 우회하는 명령어를 가지고 있다는 점에서 차이가 있다. 일반적으로 레지스터 머신이 스택 머신보다 성능이 우수하다는 평가를 받으며, 스택 머신은 하드웨어 시스템에서는 특정 분야에서 주로 사용된다. 그러나 스택 머신은 구조가 단순하고 구현이 용이하여 가상 머신 구현에 자주 채택된다.
코드 밀도 및 명령어 구조스택 머신은 레지스터 머신보다 더 높은 코드 밀도를 가진다. 스택 머신의 명령어는 피연산자가 스택에 있음을 암묵적으로 가정하는 경우가 많아, 연산 코드만 포함하는 0 주소 형식[1]을 사용하는 경우가 많다. 이는 6비트 이하로도 표현 가능할 정도로 작다. 반면, 레지스터 머신은 ALU 명령어마다 피연산자를 지정하기 위해 두 개 또는 세 개의 레지스터 번호 필드가 필요하며, 명령어당 평균 약 16비트를 사용한다. 로드-스토어 연산 코드에서도 레지스터 머신은 더 넓은 오프셋 필드를 사용한다.

스택 머신의 컴팩트한 코드는 캐시에 더 많은 명령어를 저장할 수 있게 하여 캐시 효율성을 높이고, 이는 메모리 비용 절감이나 더 빠른 메모리 시스템 구축으로 이어질 수 있다. 또한, 대부분의 스택 머신 명령어는 연산 코드나 피연산자 필드 하나로 구성되어 매우 단순하므로, 명령어 디코딩에 필요한 전자 자원이 적다.

그러나 프로그램은 스택 머신으로 컴파일될 때 레지스터 머신보다 더 많은 명령어를 실행해야 하는 경향이 있다. 모든 변수 로드나 상수는 값을 사용하는 명령어와 분리된 별도의 'Load' 명령어가 필요하기 때문이다. 개별 명령어는 단순하고 빠르게 실행될 수 있지만, 전체 명령어 수는 늘어난다.
성능 및 효율성


구현 및 특징
가상 머신 및 인터프리터가상 스택 머신용 인터프리터는 메모리 주소 지정 로직이 단순하고 연산 코드 종류가 적어 레지스터 머신용 인터프리터보다 구현하기 쉽다. 그러나 인터프리터 실행 속도는 스택 머신 방식이 더 느린 경향이 있다. 이는 특히 분기 예측이 어려운 인터프리터의 N-way 스위치 점프 때문에 호스트 머신의 실행 파이프라인이 자주 비워지기 때문이다. 이러한 이유로 자바를 위한 달빅 가상 머신이나 루아 5.0 이후 버전은 효율성을 위해 가상 레지스터 머신 방식을 채택했다. 하지만 최근 마이크로프로세서의 분기 예측기 성능 향상으로 간접 점프 예측 능력이 개선되면서 스택 인터프리터의 성능 저하 요인이 일부 완화되었다.
하이브리드 형태순수 스택 머신은 동일 객체의 여러 필드에 접근하는 등의 작업에 비효율적일 수 있어, 실제로는 레지스터 머신의 특징을 일부 결합한 하이브리드 형태가 많다. 주소 계산을 위한 전용 레지스터를 두거나(예: MuP21, GreenArrays 프로세서), 레지스터 머신에 스택의 푸시/팝과 유사한 메모리 주소 지정 모드를 추가하는 방식(예: DEC의 PDP-11, VAX, Motorola 6809 및 M68000)이 있다. Intel x86 프로세서도 기본적으로 레지스터 머신이지만, x87, Intel 8087 부동 소수점 연산에는 스택 구조를 사용한다.

7. 장점

; 객체 코드의 간결함

: 피연산자를 명시적으로 지정할 필요가 없어 개별 명령어가 일반적으로 작다. 대략 6비트 정도로도 충분한 경우가 많다. 분기 명령어, 즉시 로드 명령어, 로드/저장 명령어 등 일부 명령어는 피연산자가 필요하지만, 이 경우에도 스택 상의 값을 피연산자로 활용하여 명령어 크기를 줄일 수 있다. 이전 명령어의 결과가 스택에 자동으로 저장(푸시)되어 다음 명령에서 이를 암묵적으로 사용할 수 있다는 장점이 있다. 이는 역폴란드 표기법과 유사한 방식이다. 반면, 레지스터 머신은 ALU 명령어에서 2개 또는 3개의 레지스터를 지정해야 하므로 명령어당 최소 16비트 이상이 필요하다. 어큐뮬레이터 머신은 피연산자가 하나지만, 복잡한 계산 시 임시 변수에 값을 저장하기 위한 불필요한 로드/저장 명령어가 추가로 필요하다. 스택 머신은 역폴란드 표기법처럼 괄호 없이 표현 가능하므로 임시 변수 저장이 거의 발생하지 않는다.

: 프로시저나 함수의 지역 변수 및 인수에 접근하기 위해 스택 머신에도 로드/저장과 유사한 명령어가 존재한다. 이는 스택의 최상단 주소로부터의 상대 주소(오프셋)를 이용하거나, 프레임의 기준 주소를 가리키는 레지스터에 오프셋을 더하는 방식으로 구현된다. 이는 레지스터 머신의 "레지스터+오프셋" 주소 지정 방식과 유사하지만, 일반적으로 레지스터 머신의 오프셋 필드가 더 크다.

: 과거 메인프레임 시절에는 주 기억 장치 용량이 작았기 때문에 코드 밀도를 높이는 것이 중요했다. 이는 초기 미니컴퓨터와 마이크로컴퓨터 시대에도 마찬가지였다. 최근에는 휴대 기기로 소프트웨어를 다운로드할 때 시간을 단축하기 위해 코드 밀도의 중요성이 다시 부각되고 있다. 코드 밀도가 높으면 캐시 메모리나 명령어 프리페치의 효율이 향상되며, 임베디드 시스템에서는 필요한 ROM 용량을 줄일 수 있다. 다만, 코드 밀도를 지나치게 높이면 실행 성능이 저하될 수도 있다.

: 배로스(Burroughs)의 아키텍처는 스택 머신에 태그(tagged) 메모리 개념을 결합한 예시다. 각 메모리 워드의 일부 비트를 데이터 유형 등을 나타내는 데 사용하여 명령 코드(opcode)를 줄이는 데 기여했다. 즉, 정수인지 부동소수점 수인지는 메모리 워드 자체에 표시되므로 명령어 코드에서 이를 구분할 필요가 없었다. 스택 머신의 특성상 피연산자 지정도 줄어들어 결과적으로 명령어 길이가 짧아졌다.

; 컴파일러의 단순성

: 스택 머신용 컴파일러는 구조가 상대적으로 단순하여 개발하기 쉽다. 특히 코드 생성 과정이 간단하며, 명령어 간의 전후 관계를 크게 고려할 필요 없이 구문 분석 단계와 쉽게 통합될 수 있다. 레지스터 할당 문제를 고민할 필요가 없으며, 상수 참조나 간단한 메모리 참조 최적화 부담도 적다. 덧셈, 인덱스 로드, 함수 호출 등의 명령어는 복잡한 수식이나 중첩된 프로시저 호출에서도 동일한 코드를 사용할 수 있어 컴파일러가 특수한 경우를 처리할 필요가 줄어든다.

: 컴파일러가 단순하다는 것은 메모리 용량이 제한적인 소형 컴퓨터에서도 컴파일러를 구현하고 사용할 수 있다는 장점으로 이어진다. 이는 운영 체제와 같은 시스템 소프트웨어를 고수준 언어로 빠르게 개발하는 것을 가능하게 했다. 배로스 B5000과 HP 3000 시스템이 대표적인 예시다. UCSD p-System이 초기의 8비트 마이크로프로세서를 사용한 저용량 메모리 시스템에서 널리 사용될 수 있었던 이유 중 하나도 가상 스택 머신을 대상으로 코드를 컴파일했기 때문이다.

: 다만, 컴파일러가 단순하다는 것은 컴파일러 최적화의 최신 기술 적용이 상대적으로 어렵다는 단점을 내포하기도 한다. 하지만 스택 머신에서의 컴파일러 최적화가 불가능한 것은 아니다. 백엔드 최적화를 통해 코드 효율을 크게 향상시킨 사례가 있으며[3][4], 전역 최적화를 통해 성능을 더욱 개선한 연구도 존재한다[5].

; 인터프리터의 단순성

: 스택 머신의 명령어 집합 중 일부는 하드웨어로 직접 구현되기보다는 가상 머신 환경에서 인터프리터 방식으로 실행되는 것을 염두에 두고 설계되었다. 가상 스택 머신의 인터프리터는 상대적으로 구축하기 쉽다. 이는 기본적으로 메모리 주소 지정 시 스택의 최상단(top)만 주로 고려하면 되고, 명령어 종류도 비교적 적기 때문이다.

; 프로세서의 상태 수가 적음

: 데이터 스택을 사용하는 머신에서 필수적인 레지스터는 스택의 최상단 주소를 가리키는 레지스터(스택 포인터)와 다음 실행할 명령어의 주소를 가리키는 레지스터(명령 포인터) 정도이다. 따라서 컨텍스트 스위칭이나 인터럽트 발생 시 저장하고 복원해야 할 프로세서 상태 정보가 적다는 장점이 있다.

; 고속 피연산자 액세스

: 레지스터 머신과 달리 명령어 내에 피연산자를 지정하는 별도의 필드가 없으므로, 명령어 자체를 읽고 해석(디코딩)하는 과정과 동시에 해당 명령어가 사용할 피연산자를 스택에서 읽어오는 작업을 병렬로 처리할 수 있다. 또한, 명시적인 로드 명령어를 사용하지 않는 한, 피연산자는 스택의 최상단부터 순서대로 사용된다. 이 예측 가능한 접근 패턴 덕분에 스택의 상단 부분을 레지스터 파일과 같은 고속 저장 공간에 미리 가져와 캐시(cache)해 두는 것만으로도 효과적인 프리페치가 가능하다. 각 명령어의 피연산자는 주로 스택 상단 몇 개 내에서 접근되므로, 이 부분을 캐시하는 대신 명령어 파이프라인 내의 포워딩 회로를 통해 직접 전달하면 레지스터 파일 접근 단계를 생략할 수 있다. 이는 레지스터 머신에 비해 명령어 파이프라인 길이를 줄여 더 높은 동작 클럭 주파수를 달성하거나, 파이프라인 지연(stall)을 줄이는 데 유리하다.

: 이러한 특성은 가상 머신 구현에서도 유용하다. 하드웨어의 포워딩 회로 대신, 스택의 상단 데이터를 호스트 머신의 레지스터에 캐시하는 방식으로 구현하면 메모리 접근 지연의 영향을 줄일 수 있다. 반면, 레지스터 머신을 가상 머신으로 구현할 때는 많은 호스트 머신에서 실행 중에 레지스터 번호를 직접 참조하기 어렵고, 이를 위해 메모리 배열을 사용하는 것이 더 간단하고 빠를 수 있다. 또한, 가상 머신 자체 관리를 위해 호스트 머신의 레지스터가 소모되므로, 가상화 대상 머신의 모든 레지스터를 호스트 레지스터에 할당하기 어려워 메모리 영역을 사용하게 되는 경우가 많다.

8. 단점

스택 머신은 종종 레지스터 배열에 값을 저장하는 레지스터 머신과 비교된다. 레지스터 머신은 이 배열에 스택과 유사한 구조를 저장할 수 있지만, 스택 인터페이스를 우회하는 명령어를 가지고 있다. 일반적으로 레지스터 머신은 스택 머신보다 성능이 뛰어나며, 이러한 이유로 스택 머신은 하드웨어 시스템에서 틈새 시장을 유지해 왔다. 그러나 스택 머신은 단순성과 구현 용이성 때문에 가상 머신 구현에 자주 사용된다.

참조

[1] 서적 Computer Architecture and Organization McGraw-Hill International Book Company 1978
[2] 간행물 Instruction Set for a Single-Chip 32-Bit Processor https://archive.org/[...] Hewlett-Packard 1983-08
[3] 간행물 A Preliminary Exploration of Optimized Stack Code Generation http://www.ece.cmu.e[...]
[4] 간행물 Inter-Boundary Scheduling of Stack Operands: A preliminary Study http://www.complang.[...]
[5] 간행물 Global Stack Allocation : Register Allocation for Stack Machines http://www.complang.[...]
[6] 문서 "Computer Architecture: A Quantitative Approach"
[7] 서적 "Stack Computers: the new wave" http://www.ece.cmu.e[...]
[8] 문서 'Introduction to A Series Systems' http://www.bitsavers[...] Burroughs Corporation
[9] 웹사이트 BOOST: Berkeley's Out of Order Stack Thingy https://www.research[...] Kaushik Ravindran 2016-02-16
[10] 간행물 HP3000 Emulation on HP Precision Architecture Computers http://www.hpl.hp.co[...] 1987-12
[11] 간행물 Migrating a CISC Computer Family onto RISC via Object Code Translation 1992-10
[12] 문서 "Virtual Machine Showdown: Stack vs. Registers" http://usenix.org/ev[...]
[13] 문서 'The Case for Virtual Register Machines' http://www.scss.tcd.[...]
[14] 문서 "Branch Prediction and the Performance of Interpreters - Don't Trust Folklore" https://hal.inria.fr[...]
[15] 간행물 Second-Generation Stack Computer Architecture http://www.eecg.utor[...]
[16] 웹사이트 The KDF9 Computer - 30 Years On http://www.cs.man.ac[...] 2022-12-11
[17] 뉴스 "The World's First Java Processor" http://hokiepokie.or[...] Electronic Engineering Times 1998-01-12
[18] 문서 'MARC4 4-bit Microcontrollers Programmers Guide' http://www.atmel.com[...] Atmel
[19] 웹사이트 Forth chips http://www.colorfort[...]
[20] 웹사이트 F21 Microprocessor Overview http://www.ultratech[...]
[21] 웹사이트 PSC1000 Microprocessor Reference Manual, Patriot Scientific Corporation http://www.forthfrea[...]
[22] 웹사이트 The 4stack processor by Bernd Paysan http://www.jwdt.com/[...]
[23] 웹사이트 'Porting the GNU C Compiler to the Thor Microprocessor' http://lundqvist.dyn[...]
[24] 웹사이트 Instructions — WebAssembly 2.0 (Draft 2024-04-28) https://webassembly.[...] 2024-05-03


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com