스택 머신

컴퓨터 과학, 컴퓨터 공학 및 프로그래밍 언어 구현체에서 스택 머신(stack machine)은 주된 상호 작용이 짧게 존재하는 임시 값을 푸시 다운 스택으로 이동시키거나 스택에서 이동시키는 컴퓨터 프로세서 또는 프로세스 가상 머신이다. 하드웨어 프로세서의 경우 하드웨어 스택이 사용된다. 스택을 사용하면 필요한 프로세서 레지스터의 수가 크게 줄어든다. 스택 머신은 추가적인 로드/저장 연산 또는 여러 스택을 통해 푸시다운 자동 기계를 확장하며, 따라서 튜링 완전하다.

 설계 
대부분 또는 모든 스택 머신 명령어는 피연산자가 스택에서 오고 결과가 스택에 놓인다고 가정한다. 스택은 두 개 이상의 입력 또는 한 개 이상의 결과를 쉽게 담을 수 있으므로 풍부한 연산 집합을 계산할 수 있다. 스택 머신 코드(때로는 p-코드라고도 불림)에서 명령어는 종종 연산을 명령하는 명령 코드만을 가지며, 상수, 레지스터 또는 메모리 셀을 식별하는 추가 필드를 가지지 않는데, 이를 제로 주소 형식이라고 한다. 대부분의 명령어가 명시적인 주소를 포함하지 않는 방식으로 작동하는 컴퓨터는 제로 주소 명령어를 사용한다고 말한다. 이는 명령어 디코딩을 크게 단순화한다. 분기, 즉시 로드, 로드/저장 명령어는 인자 필드를 필요로 하지만, 스택 머신은 이러한 명령어의 빈번한 경우에도 명령 코드와 함께 비트의 압축된 그룹에 맞도록 배열하는 경우가 많다. 이전 결과에서 피연산자를 선택하는 것은 명령어 순서에 의해 암묵적으로 수행된다. 일부 스택 머신 명령어 집합은 하드웨어를 직접 구동하기보다는 가상 머신의 해석적 실행을 위해 의도되었다.

정수 상수 피연산자는  또는  명령어로 푸시된다. 메모리는 종종 메모리 주소를 포함하거나 스택의 값에서 주소를 계산하는 별도의  또는  명령어를 통해 접근된다. 모든 실용적인 스택 머신은 명시적인 주소 계산 없이 지역 변수 및 형식 매개변수에 접근하기 위한 로드-저장 명령 코드의 변형을 가진다. 이는 현재 스택의 최상단 주소로부터의 오프셋이나 안정적인 프레임 기반 레지스터로부터의 오프셋을 통해 이루어질 수 있다.

명령어 집합은 대부분의 ALU 동작을 데이터 레지스터나 주 메모리 셀이 아닌 표현식 스택에서만 작동하는 후위 (역폴란드 표기법) 연산으로 수행한다. 대부분의 산술 표현식이 후위 표기법으로 쉽게 번역될 수 있기 때문에 이는 고급 언어 실행에 매우 편리할 수 있다.

섬네일|표현식 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
  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'는 스택의 최상위 두 피연산자에 작용한다. 컴퓨터는 스택의 최상위(가장 최근) 값에서 두 피연산자를 모두 가져온다. 컴퓨터는 그 두 값을 계산된 차이, 합계 또는 곱으로 대체한다. 즉, 명령어의 피연산자는 스택에서 "팝"되고, 그 결과는 다음 명령어를 위해 스택에 "푸시"된다.

스택 머신은 표현식 스택과 호출-반환 스택을 분리하거나 하나의 통합된 구조로 가질 수 있다. 이들이 분리되어 있다면, 스택 머신의 명령어는 더 적은 상호 작용과 더 적은 설계 복잡성으로 파이프라인될 수 있으므로, 일반적으로 더 빠르게 실행될 것이다.

컴파일된 스택 코드의 최적화는 충분히 가능하다. 컴파일러 출력의 백엔드 최적화는 코드 개선에 크게 기여하며, 잠재적으로 성능을 향상시키는 것으로 입증되었고, 컴파일러 자체 내의 전역 최적화는 추가적인 이득을 얻는다.

 스택 저장소 
일부 스택 머신은 레지스터 파일로 구현된 제한된 크기의 스택을 가지고 있다. ALU는 이를 인덱스로 접근한다. 큰 레지스터 파일은 많은 트랜지스터를 사용하므로 이 방법은 작은 시스템에만 적합하다. 몇몇 머신은 메모리에 표현식 스택과 별도의 레지스터 스택을 모두 가지고 있다. 이 경우 소프트웨어 또는 인터럽트가 그들 사이에서 데이터를 이동시킬 수 있다. 일부 머신은 RAM의 배열로 구현된 무제한 크기의 스택을 가지고 있으며, 메모리 접근을 줄이기 위해 몇 개의 "스택 최상단" 주소 레지스터에 의해 캐시된다. 명시적인 "메모리에서 로드" 명령어를 제외하고, 피연산자 사용 순서는 데이터 스택의 피연산자 순서와 동일하므로 우수한 선반입을 쉽게 달성할 수 있다.

을 고려해보자. 이것은 ; ; 로 컴파일된다. RAM에 완전히 저장된 스택을 사용하면 메모리 내 스택에 대한 암묵적인 쓰기 및 읽기가 발생한다.
 X 로드, 메모리에 푸시
 1 로드, 메모리에 푸시
 메모리에서 2개의 값 팝, 더하기, 결과를 메모리에 푸시
총 5개의 데이터 캐시 참조가 발생한다.

이 다음 단계는 단일 스택 최상단 레지스터를 가진 스택 머신 또는 인터프리터이다. 위의 코드는 다음과 같이 작동한다.
 빈 TOS 레지스터에 X 로드 (하드웨어 머신인 경우) 또는 TOS 레지스터를 메모리에 푸시, X를 TOS 레지스터에 로드 (인터프리터인 경우)
 TOS 레지스터를 메모리에 푸시, 1을 TOS 레지스터에 로드
 왼쪽 피연산자를 메모리에서 팝, TOS 레지스터에 추가하고 그곳에 둔다
최악의 경우 총 3개의 데이터 캐시 참조가 발생한다. 일반적으로 인터프리터는 비어 있는지 추적하지 않는데, 그럴 필요가 없기 때문이다. 스택 포인터 아래의 모든 것은 비어 있지 않은 값이며, TOS 캐시 레지스터는 항상 활성 상태로 유지된다. 하지만 일반적인 자바 인터프리터는 프로그램과 스택이 짧은 데이터 값과 넓은 데이터 값을 혼합하여 가지므로 이 방식으로 스택 최상단을 버퍼링하지 않는다.

하드웨어 스택 머신이 2개 이상의 최상단 스택 레지스터 또는 레지스터 파일을 가지고 있다면, 이 예에서는 모든 메모리 접근이 회피되고 데이터 캐시 사이클은 1개뿐이다.

 역사 및 구현 
두 개의 값만 레지스터에 저장해야 하고, 제한된 미리 정의된 피연산자 집합이 추가 피연산자, 함수 및 서브루틴의 정의를 통해 확장될 수 있는 이러한 방법의 설명은 1961년 로버트 S. 바턴이 학회에서 처음 제공했다.

 상업용 스택 머신 

하드웨어에서 직접 실행된 스택 명령어 집합의 예시는 다음과 같다.
 콘라트 추제의 Z4 (1945) 컴퓨터는 2단계 스택을 가졌다.
 버로스 대형 시스템 아키텍처 (1961년부터)
 잉글리시 일렉트릭 KDF9 머신. 1964년 처음 출시된 KDF9는 19단계 깊이의 산술 레지스터 푸시다운 스택과 서브루틴 반환 주소를 위한 17단계 깊이의 스택을 가졌다.
 콜린스 라디오 콜린스 적응형 처리 시스템 미니컴퓨터 (CAPS, 1969년부터) 및 로크웰 콜린스 고급 아키텍처 마이크로프로세서 (AAMP, 1981년부터).
 1981년 4월 27일 출시된 제록스 댄딜라이언과 제록스 데이브레이크는 스택 머신 아키텍처를 사용하여 메모리를 절약했다.
 UCSD 파스칼 p-머신( 파스칼 마이크로엔진 등)은 가상 스택 머신으로 컴파일하여 명령어 집합이 열악하고 RAM이 적은 초기 8비트 마이크로프로세서에서 완전한 학생 프로그래밍 환경을 지원했다.
 MU5 및 ICL 2900 시리즈. 하이브리드 스택 및 누산기 머신. 누산기 레지스터는 메모리 스택의 최상단 데이터 값을 버퍼링했다. 로드 및 저장 명령 코드의 변형은 해당 레지스터가 메모리 스택으로 유출되거나 그곳에서 다시 로드되는 시점을 제어했다.
 HP 3000 (클래식, PA-RISC 아님)
 HP FOCUS 마이크로프로세서 기반의 HP 9000 시스템.
 탠덤 컴퓨터 T/16. HP 3000과 유사하지만, 레지스터 스택이 메모리 스택으로 유출되거나 메모리 스택에서 다시 채워지는 시점을 마이크로코드가 아닌 컴파일러가 제어했다.
 아트멜 MARC4 마이크로컨트롤러.
 RTX2000, RTX2010, F21 및 PSC1000과 같은 여러 "포스 칩".
 세툰 3진법 컴퓨터는 스택을 사용하여 균형 3진법을 수행했다.
 패트리어트 사이언티픽의 이그나이트 스택 머신은 찰스 H. 무어가 설계했으며, 선도적인 기능 밀도 벤치마크를 보유하고 있다.
 사브 에릭슨 스페이스 토르 방사선 경화 마이크로프로세서.
 인모스 트랜스퓨터.
 ZPU FPGA 시스템을 감독하도록 설계된 물리적으로 작은 CPU.
 일부 기술용 휴대용 계산기는 괄호 키 대신 키보드 인터페이스에 역폴란드 표기법을 사용한다. 이것은 스택 머신의 한 형태이다. 덧셈 키는 두 피연산자가 이미 사용자에게 보이는 스택의 올바른 최상위 위치에 있음에 의존한다.

 가상 스택 머신 
소프트웨어에서 해석되는 가상 스택 머신의 예시:
 웨트스톤 알골 60 해석 코드 (버로스 B6500의 일부 기능이 기반됨)
 UCSD 파스칼 p-머신; 버로스와 매우 유사함
 니클라우스 비르트 p-코드 머신
 스몰토크
 자바 가상 머신 명령어 집합 (추상 명령어 집합만 스택 기반이며, 예를 들어 썬 자바 가상 머신인 핫스팟은 실제 인터프리터를 소프트웨어로 구현하지 않고 수기로 작성된 어셈블리 스텁으로 구현함)
 웹어셈블리 바이트코드
 닷넷 프레임워크의 공통 중간 언어 (CIL) 명령어 집합을 위한 가상 실행 시스템 (VES) (ECMA 335)
 포스 프로그래밍 언어, 특히 내장 가상 머신
 어도비의 포스트스크립트
 썬 마이크로시스템즈의 썬 레이 스마트카드 식별을 위한 SwapDrop 프로그래밍 언어
 어도비의 액션스크립트 가상 머신 2 (AVM2)
 이더리움의 EVM
 C파이썬 바이트코드 인터프리터
 루비 YARV 바이트코드 인터프리터
 루비니우스 가상 머신
 유닉스의 bs (프로그래밍 언어)는 제공된 입력 언어 형식을 역폴란드 표기법으로 전환한 후 가상 스택 머신을 사용하여 명령을 처리한다.
 dc (컴퓨터 프로그램) 유닉스 프로그램 중 가장 오래된 프로그램 중 하나
 루아 (프로그래밍 언어) C API
 디 오픈 네트워크 스마트 계약을 위한 톤 가상 머신 (TVM)

 하이브리드 머신 

순수 스택 머신은 동일한 객체에서 여러 필드에 접근하는 절차에 대해 매우 비효율적이다. 스택 머신 코드는 각 포인터+오프셋 계산을 위해 객체 포인터를 다시 로드해야 한다. 이에 대한 일반적인 해결책은 스택 머신에 일부 레지스터 머신 기능을 추가하는 것이다: 주소를 저장하는 데 전용으로 사용되는 가시적인 레지스터 파일과 로드 및 간단한 주소 계산을 위한 레지스터 스타일 명령어. 레지스터가 완전히 범용인 경우는 드문데, 그럴 경우 표현식 스택과 후위 명령어를 가질 강력한 이유가 없기 때문이다.

또 다른 일반적인 하이브리드는 레지스터 머신 아키텍처에서 시작하여 스택 머신의 푸시 또는 팝 연산을 에뮬레이트하는 또 다른 메모리 주소 모드를 추가하는 것이다: '메모리 주소 = 레지스터; 레지스터 += 명령어.변위'. 이는 DEC의 PDP-11 미니컴퓨터에서 처음 사용되었다. 이 기능은 VAX 컴퓨터와 모토로라 6809 및 M68000 마이크로프로세서에 계승되었다. 이를 통해 초기 컴파일러에서 더 간단한 스택 방법을 사용할 수 있었다. 또한 스택 인터프리터 또는 스레드 코드를 사용하는 가상 머신을 효율적으로 지원했다. 그러나 이 기능은 레지스터 머신 자체 코드를 순수 스택 머신 코드만큼 압축적으로 만드는 데 도움이 되지 않았다. 또한 실행 속도는 레지스터 아키텍처에 잘 컴파일되었을 때보다 느렸다. 스택 최상위 포인터를 드물게 (호출 또는 반환당 한 번) 변경하는 것이 각 프로그램 문장 전체에서 계속해서 위아래로 움직이는 것보다 빠르며, 메모리 참조를 완전히 피하는 것이 훨씬 빠르다.

최근에는 소위 2세대 스택 머신이 주소 레지스터 역할을 하는 전용 레지스터 컬렉션을 채택하여 데이터 스택에서 메모리 주소 지정 작업을 덜어냈다. 예를 들어, MuP21은 "A"라고 불리는 레지스터에 의존하는 반면, 최신 GreenArrays 프로세서는 A와 B 두 개의 레지스터에 의존한다.

인텔 x86 계열 마이크로프로세서는 대부분의 연산에 레지스터 스타일(누산기) 명령어 집합을 사용하지만, x87, 인텔 8087 부동 소수점 산술에는 스택 명령어를 사용하며, 이는 iAPX87 (8087) 보조 프로세서부터 시작되었다. 즉, 프로그래머가 접근할 수 있는 부동 소수점 레지스터는 없고, 80비트 너비의 8단계 깊이 스택만 있다. x87은 연산 수행을 위해 x86 CPU에 크게 의존한다.

 호출 스택 및 스택 프레임을 사용하는 컴퓨터 
대부분의 현재 컴퓨터(어떤 명령어 집합 스타일이든)와 대부분의 컴파일러는 메모리에 큰 호출-반환 스택을 사용하여 현재 활성 상태인 모든 프로시저 또는 함수의 짧게 존재하는 지역 변수 및 반환 링크를 구성한다. 중첩된 각 호출은 메모리에 새로운 스택 프레임을 생성하며, 이는 해당 호출이 완료될 때까지 지속된다. 이 호출-반환 스택은 특수 주소 레지스터와 명령어의 특수 주소 모드를 통해 하드웨어에 의해 전적으로 관리될 수 있다. 또는 일반 레지스터와 레지스터+오프셋 주소 모드를 사용하여 컴파일러가 따르는 일련의 규칙에 불과할 수도 있다. 또는 그 중간일 수도 있다.

이 기술은 현재 레지스터 머신에서도 거의 보편적이므로, 이 모든 머신을 스택 머신이라고 부르는 것은 도움이 되지 않는다. 이 용어는 단일 명령문의 부분을 평가하기 위해 표현식 스택과 스택 전용 산술 명령어도 사용하는 머신에 일반적으로 사용된다.

컴퓨터는 일반적으로 프로그램의 전역 변수와 현재 가장 안쪽 프로시저 또는 함수의 지역 변수(최상위 스택 프레임)에 직접적이고 효율적으로 접근할 수 있도록 제공한다. 호출자의 스택 프레임 내용에 대한 '상위 수준' 주소 지정은 일반적으로 필요하지 않으며 하드웨어에서 직접 지원되지 않는다. 필요한 경우 컴파일러는 프레임 포인터를 추가적인 숨겨진 매개변수로 전달하여 이를 지원한다.

일부 버로스 스택 머신은 특수 주소 모드와 모든 외부 스코프의 프레임 주소를 담는 특수 '디스플레이' 레지스터 파일을 통해 하드웨어에서 직접 상위 수준 참조를 지원한다. 현재 MCST 옐브루스만이 하드웨어에서 이를 수행했다. 니클라우스 비르트가 CDC 6000용 최초의 파스칼 컴파일러를 개발했을 때, 그는 완전한 프레임 포인터 배열을 계속 업데이트하는 것보다 프레임 포인터를 체인으로 전달하는 것이 전반적으로 더 빠르다는 것을 발견했다. 이 소프트웨어 방식은 상위 수준 참조가 없는 C와 같은 일반적인 언어에 대해 오버헤드를 추가하지도 않는다.

동일한 버로스 머신은 작업 또는 스레드의 중첩도 지원했다. 작업과 그 생성자는 작업 생성 시점에 존재했던 스택 프레임을 공유하지만, 생성자의 후속 프레임이나 작업 자체의 프레임은 공유하지 않는다. 이는 선인장 스택에 의해 지원되었으며, 그 레이아웃 다이어그램은 변경주선인장의 몸통과 팔을 닮았다. 각 작업은 자체 스택과 소유한 프레임을 담는 자체 메모리 세그먼트를 가졌다. 이 스택의 기본은 생성자 스택의 중간에 연결되어 있다. 일반적인 평면 주소 공간을 가진 머신에서는 생성자 스택과 작업 스택이 하나의 힙에 별도의 힙 객체로 존재한다.

일부 프로그래밍 언어에서는 외부 범위 데이터 환경이 항상 시간적으로 중첩되지 않는다. 이러한 언어는 프로시저 '활성 레코드'를 선형 스택에 추가된 스택 프레임으로 구성하기보다는 별도의 힙 객체로 구성한다.

포스와 같이 지역 변수 및 매개변수 명명이 없는 간단한 언어에서는 스택 프레임이 반환 분기 주소 및 프레임 관리 오버헤드 외에는 아무것도 포함하지 않을 것이다. 따라서 반환 스택은 프레임 대신 순수 반환 주소를 저장한다. 반환 스택은 호출 설정 및 반환 흐름을 개선하기 위해 데이터 값 스택과 분리되어 있다.

 레지스터 머신과의 비교 

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

 명령어 
스택 머신은 더 높은 코드 밀도를 가진다. 6비트 이하로 쉽게 맞출 수 있는 일반적인 스택 머신 명령어와 달리, 레지스터 머신은 피연산자를 선택하기 위해 ALU 명령어당 2개 또는 3개의 레지스터 번호 필드를 필요로 한다. 가장 밀도가 높은 레지스터 머신은 명령어당 평균 약 16비트와 피연산자를 사용한다. 레지스터 머신은 또한 로드-저장 명령 코드에 더 넓은 오프셋 필드를 사용한다. 스택 머신의 압축된 코드는 캐시에 더 많은 명령어를 자연스럽게 담을 수 있으므로 더 나은 캐시 효율성을 달성하여 메모리 비용을 줄이거나 주어진 비용으로 더 빠른 메모리 시스템을 허용할 수 있다. 또한 대부분의 스택 머신 명령어는 매우 단순하며, 하나의 명령 코드 필드 또는 하나의 피연산자 필드로만 구성된다. 따라서 스택 머신은 각 명령어를 디코딩하는 데 매우 적은 전자 자원을 필요로 한다.

스택 머신으로 컴파일된 프로그램은 레지스터 머신이나 메모리-메모리 머신으로 컴파일된 프로그램보다 더 많은 명령어를 실행해야 한다. 각 변수 로드나 상수는 해당 값을 사용하는 명령어에 묶이지 않고 자체적인 별도의 Load 명령어를 필요로 한다. 분리된 명령어는 간단하고 빠르게 실행될 수 있지만, 총 명령어 수는 여전히 더 많다.

대부분의 레지스터 인터프리터는 레지스터를 숫자로 지정한다. 그러나 호스트 머신의 레지스터는 인덱스 배열로 접근할 수 없으므로 가상 레지스터를 위해 메모리 배열이 할당된다. 따라서 레지스터 인터프리터의 명령어는 다음 명령어로 생성된 데이터를 전달하기 위해 메모리를 사용해야 한다. 이는 미세 공정 규칙(예: 하스웰 x86과 같이 회로 속도를 향상시키지 않고 더 빠른 트랜지스터)으로 만들어진 마이크로프로세서에서 레지스터 인터프리터가 훨씬 느려지게 만든다. 이들은 메모리 접근에 여러 클록이 필요하지만, 레지스터 접근에는 한 클록만 필요하다. 레지스터 파일 대신 데이터 포워딩 회로가 있는 스택 머신의 경우, 스택 인터프리터는 호스트 머신의 메모리 대신 스택의 최상위 몇 개의 피연산자에 대해 호스트 머신의 레지스터를 할당할 수 있다.

스택 머신에서 명령어에 사용되는 피연산자는 항상 고정된 위치(하드웨어 설계에서 항상 메모리 위치 0일 수 있는 스택의 바닥)에서 알려진 오프셋(스택 포인터에 설정됨)에 있으므로, 캐시 내 또는 CPU 내 저장 공간이 많은 메모리 주소나 인덱스 번호를 저장하는 데 사용되는 것을 절약할 수 있다. 이는 이러한 레지스터와 캐시를 비흐름 계산에 사용할 수 있도록 보존할 수 있다.

 임시/지역 값 
일부 업계 관계자들은 스택 머신이 레지스터 머신보다 임시 값 및 지역 변수에 대해 더 많은 데이터 캐시 사이클을 실행한다고 믿는다.

스택 머신에서는 임시 값이 종종 메모리로 유출되는 반면, 많은 레지스터를 가진 머신에서는 이러한 임시 값들이 일반적으로 레지스터에 남아 있다. (그러나 이러한 값들은 종종 프로시저 정의의 끝, 기본 블록 또는 최소한 인터럽트 처리 중에 메모리 버퍼로 "활성화 프레임"에 유출되어야 한다). 메모리로 유출된 값은 더 많은 캐시 사이클을 추가한다. 이러한 유출 효과는 스택 최상단 값을 버퍼링하는 데 사용되는 숨겨진 레지스터의 수, 중첩된 프로시저 호출의 빈도, 호스트 컴퓨터 인터럽트 처리 속도에 따라 달라진다.

최적화 컴파일러를 사용하는 레지스터 머신에서는 가장 많이 사용되는 지역 변수가 스택 프레임 메모리 셀이 아닌 레지스터에 남아 있는 것이 매우 일반적이다. 이는 해당 값을 읽고 쓰는 데 필요한 대부분의 데이터 캐시 사이클을 제거한다. 활성 변수 분석을 수행하고 따라서 주요 변수를 장기간 스택에 유지하기 위한 "스택 스케줄링"의 개발은 이러한 우려를 해소하는 데 도움이 된다.

반면에 레지스터 머신은 중첩된 프로시저 호출을 넘나들며 많은 레지스터를 메모리로 유출해야 한다. 어떤 레지스터를 언제 유출할지는 호출의 동적 깊이가 아니라 컴파일 시간에 정적으로 결정된다. 이는 고급 스택 머신 구현보다 더 많은 데이터 캐시 트래픽을 유발할 수 있다.

 공통 부분 표현식 
레지스터 머신에서는 공통 부분 표현식(동일한 결과 값으로 여러 번 사용되는 부분 표현식)을 한 번만 평가하고 그 결과를 빠른 레지스터에 저장할 수 있다. 이후의 재사용에는 시간이나 코드 비용이 들지 않고, 단지 레지스터 참조만 필요하다. 이 최적화는 간단한 표현식(예: 변수 X 또는 포인터 P 로드)뿐만 아니라 덜 일반적인 복잡한 표현식의 속도를 높인다.

반면에 스택 머신에서는 결과가 두 가지 방법 중 하나로 저장될 수 있다. 첫째, 결과를 메모리의 임시 변수를 사용하여 저장할 수 있다. 저장 및 후속 검색은 추가적인 명령어와 추가적인 데이터 캐시 사이클을 필요로 한다. 이는 부분 표현식 계산 비용이 메모리에서 가져오는 시간보다 더 많이 드는 경우에만 이득이 되며, 대부분의 스택 CPU에서는 거의 항상 그렇다. 간단한 변수 및 포인터 가져오기에는 결코 가치가 없는데, 이들은 접근당 동일한 데이터 캐시 사이클 비용을 이미 가지고 있기 때문이다. 과 같은 표현식에는 약간의 가치가 있을 뿐이다. 이러한 간단한 표현식은 연쇄형 프로그래밍 언어 이외의 언어로 작성된 프로그램에서 중복되고 최적화 가능한 표현식의 대부분을 차지한다. 최적화 컴파일러는 프로그래머가 원본 코드에서 피할 수 있었던 중복성에 대해서만 이득을 얻을 수 있다.

두 번째 방법은 계산된 값을 데이터 스택에 남겨두고 필요에 따라 복제하는 것이다. 이는 스택 항목을 복사하는 연산을 사용한다. 스택은 CPU의 사용 가능한 복사 명령에 대해 충분히 얕은 깊이여야 한다. 수동으로 작성된 스택 코드는 종종 이 접근 방식을 사용하며, 범용 레지스터 머신과 유사한 속도를 달성한다. 불행히도, 최적의 "스택 스케줄링"을 위한 알고리즘은 프로그래밍 언어에서 널리 사용되지 않는다.

 파이프라이닝 
현대 머신에서 데이터 캐시에서 변수를 가져오는 시간은 기본 ALU 연산에 필요한 시간보다 종종 몇 배나 길다. 메모리 로드가 해당 변수를 필요로 하는 명령어보다 몇 사이클 일찍 시작될 수 있다면 프로그램은 중단 없이 더 빠르게 실행된다. 복잡한 머신은 깊은 파이프라인과 동시에 여러 명령어를 검사하고 실행하는 "비순차적 명령어 처리"를 통해 이를 수행할 수 있다. 레지스터 머신은 훨씬 더 간단한 "순차적" 하드웨어, 얕은 파이프라인, 그리고 약간 더 똑똑한 컴파일러를 사용하여도 이를 수행할 수 있다. 로드 단계는 별도의 명령어가 되며, 해당 명령어는 코드 시퀀스에서 훨씬 일찍 정적으로 스케줄링된다. 컴파일러는 그 사이에 독립적인 단계를 배치한다.

메모리 접근 스케줄링에는 명시적이고 여분의 레지스터가 필요하다. 마이크로아키텍처의 일부 측면을 프로그래머에게 노출하지 않고는 스택 머신에서 불가능하다. A B - 표현식의 경우 B는 마이너스 단계 직전에 평가되고 푸시되어야 한다. 스택 순열이나 하드웨어 멀티스레딩이 없으면 로드 B가 완료될 때까지 기다리는 동안 상대적으로 유용한 코드를 거의 넣을 수 없다. 스택 머신은 깊은 비순차적 실행 파이프라인으로 한 번에 많은 명령어를 처리하거나, 더 가능성 있는 방법으로 스택을 순열하여 로드가 완료되는 동안 다른 작업을 수행하거나, Unisys A9 시스템처럼 다른 프로그램 스레드의 실행을 인터리브하여 메모리 지연을 해결할 수 있다. 그러나 오늘날 점점 더 병렬화되는 계산 부하는 과거에 단점으로 지적되었던 것이 아닐 수도 있음을 시사한다.

스택 머신은 레지스터 머신의 피연산자 페치 단계를 생략할 수 있다. 예를 들어, 자바 최적화 프로세서 (JOP) 마이크로프로세서에서 스택의 최상위 2개 피연산자는 레지스터 파일보다 빠른 데이터 포워딩 회로로 직접 들어간다.

 비순차적 명령어 처리 
토마술로 알고리즘은 데이터가 사용 가능해지면 명령어를 발행하여 명령어 수준 병렬성을 찾는다. 개념적으로 스택의 위치 주소는 레지스터 파일의 레지스터 인덱스와 다르지 않다. 이 관점은 토마술로 알고리즘의 비순차적 명령어 처리를 스택 머신과 함께 사용할 수 있도록 허용한다.

스택 머신에서의 비순차적 명령어 처리는 많은 이론적 및 실제적 어려움을 줄이거나 피하는 것으로 보인다. 인용된 연구는 이러한 스택 머신이 명령어 수준 병렬성을 활용할 수 있으며, 그 결과 하드웨어는 명령어에 대한 데이터를 캐시해야 함을 보여준다. 이러한 머신은 스택에 대한 대부분의 메모리 접근을 효과적으로 우회한다. 그 결과는 로드-스토어 아키텍처 머신과 비교할 만한 처리량(클럭당 명령어)을 달성하며, 훨씬 더 높은 코드 밀도(피연산자 주소가 암시적이기 때문)를 제공한다.

연구에서 제기된 한 가지 문제는 로드-스토어 아키텍처 머신의 한 가지 작업에 대해 약 1.88개의 스택 머신 명령어가 필요하다는 것이었다. 따라서 경쟁력 있는 비순차적 스택 머신은 명령어를 추적하기 위해("발행 스테이션") 약 두 배 많은 전자 자원을 필요로 한다. 이는 명령어 캐시, 메모리 및 명령어 디코딩 회로의 절감으로 상쇄될 수 있다.

 내부적으로 더 빠른 레지스터 머신을 숨김 
일부 간단한 스택 머신은 개별 레지스터 수준까지 완전히 맞춤화된 칩 설계를 가지고 있다. 스택 주소 레지스터의 최상단과 N개의 스택 데이터 버퍼는 별도의 개별 레지스터 회로에서 구축되며, 별도의 가산기와 임시 연결을 사용한다.

그러나 대부분의 스택 머신은 레지스터 파일 내에 N개의 데이터 버퍼가 함께 저장되고 읽기/쓰기 버스를 공유하는 더 큰 회로 구성 요소로 만들어진다. 디코딩된 스택 명령어는 해당 숨겨진 레지스터 파일에 대한 하나 이상의 순차적 동작으로 매핑된다. 로드 및 ALU 연산은 몇 개의 최상위 레지스터에 작용하며, 암시적인 유출 및 채우기는 최하위 레지스터에 작용한다. 디코더는 명령어 스트림을 압축적으로 만들 수 있다. 그러나 코드 스트림이 대신 기본 레지스터 파일을 직접 조작하는 명시적인 레지스터 선택 필드를 가졌다면, 컴파일러는 모든 레지스터를 더 잘 활용할 수 있었고 프로그램은 더 빠르게 실행되었을 것이다.

마이크로프로그래밍된 스택 머신이 그 예이다. 내부 마이크로코드 엔진은 일종의 RISC와 같은 레지스터 머신이거나 여러 레지스터 파일을 사용하는 VLIW와 같은 머신이다. 작업별 마이크로코드에 의해 직접 제어될 때, 해당 엔진은 동일한 작업에 대한 동등한 스택 코드에 의해 간접적으로 제어될 때보다 사이클당 훨씬 더 많은 작업을 완료한다.

HP 3000 및 탠덤 T/16의 목적 코드 번역기가 또 다른 예시이다. 이들은 스택 코드 시퀀스를 동등한 RISC 코드 시퀀스로 번역했다. 사소한 '로컬' 최적화는 스택 아키텍처의 오버헤드를 대부분 제거했다. 여분의 레지스터는 반복되는 주소 계산을 제거하는 데 사용되었다. 번역된 코드는 원본 머신과 대상 머신 간의 불일치로 인해 여전히 많은 에뮬레이션 오버헤드를 유지했다. 이러한 부담에도 불구하고, 번역된 코드의 사이클 효율성은 원래 스택 코드의 사이클 효율성과 일치했다. 그리고 원본 코드를 최적화 컴파일러를 통해 레지스터 머신으로 직접 재컴파일했을 때 효율성은 두 배로 증가했다. 이는 스택 아키텍처와 비최적화 컴파일러가 기본 하드웨어 성능의 절반 이상을 낭비하고 있었음을 보여준다.

레지스터 파일은 데이터 캐시를 통한 메모리 참조에 비해 높은 대역폭과 매우 낮은 지연 시간을 가지므로 컴퓨팅에 좋은 도구이다. 간단한 머신에서 레지스터 파일은 두 개의 독립적인 레지스터를 읽고 세 번째 레지스터를 쓰는 것을 모두 하나의 ALU 사이클에서 1사이클 이하의 지연 시간으로 허용한다. 반면에 해당 데이터 캐시는 사이클당 하나의 읽기 또는 쓰기(둘 다 아님)만 시작할 수 있으며, 읽기는 일반적으로 두 ALU 사이클의 지연 시간을 가진다. 이는 처리량의 3분의 1이며 파이프라인 지연은 두 배이다. 애슬론과 같이 사이클당 두 개 이상의 명령어를 완료하는 복잡한 머신에서는 레지스터 파일이 네 개 이상의 독립적인 레지스터를 읽고 두 개의 다른 레지스터를 쓰는 것을 모두 하나의 ALU 사이클에서 1사이클 지연 시간으로 허용한다. 반면에 해당 이중 포트 데이터 캐시는 사이클당 두 개의 읽기 또는 쓰기만 시작할 수 있으며, 여러 사이클의 지연 시간을 가진다. 다시 말하지만, 이는 레지스터 처리량의 3분의 1이다. 추가 포트가 있는 캐시를 구축하는 것은 매우 비싸다.

스택은 대부분의 소프트웨어 프로그램의 구성 요소이며, 사용되는 소프트웨어가 엄밀히 스택 머신이 아닌 경우에도 하드웨어 스택 머신은 프로그램의 내부 작동을 더 밀접하게 모방할 수 있다. 프로세서 레지스터는 높은 열 비용을 가지며, 스택 머신은 더 높은 에너지 효율성을 주장할 수 있다.

 인터럽트 
인터럽트에 응답하려면 레지스터를 스택에 저장한 다음 인터럽트 핸들러 코드로 분기해야 한다. 스택 머신은 대부분의 매개변수가 이미 스택에 있으므로 푸시할 필요가 없기 때문에 인터럽트에 더 빠르게 응답하는 경우가 많다. 일부 레지스터 머신은 여러 레지스터 파일을 즉시 교체할 수 있도록 하여 이 문제를 해결하지만, 이는 비용을 증가시키고 레지스터 파일의 속도를 저하시킨다.

 인터프리터 
가상 스택 머신을 위한 인터프리터는 레지스터 머신을 위한 인터프리터보다 구축하기 쉽다. 메모리 주소 모드를 처리하는 논리가 여러 명령어에 반복되는 대신 한 곳에만 있기 때문이다. 또한 스택 머신은 명령어 코드의 변형이 적은 경향이 있다. 하나의 일반화된 명령어 코드는 메모리 참조 또는 함수 호출 설정의 빈번한 경우와 모호한 코너 케이스를 모두 처리한다. (그러나 코드 밀도는 종종 동일한 연산에 대해 짧은 형식과 긴 형식을 추가하여 향상된다.)

가상 스택 머신을 위한 인터프리터는 다른 스타일의 가상 머신을 위한 인터프리터보다 느린 경우가 많다. 이러한 속도 저하는 현재 x86 칩과 같이 깊은 실행 파이프라인을 가진 호스트 머신에서 실행될 때 가장 심하다.

일부 인터프리터에서는 인터프리터가 다음 명령 코드를 디코딩하고 해당 특정 명령 코드에 대한 단계로 분기하기 위해 N-방향 스위치 점프를 실행해야 한다. 명령 코드를 선택하는 다른 방법은 스레드 코드이다. 호스트 머신의 선반입 메커니즘은 해당 인덱스 또는 간접 점프의 대상을 예측하고 가져올 수 없다. 따라서 호스트 머신의 실행 파이프라인은 호스팅된 인터프리터가 또 다른 가상 명령어를 디코딩할 때마다 다시 시작되어야 한다. 이는 다른 스타일의 가상 머신보다 가상 스택 머신에서 더 자주 발생한다.

예를 들어 자바 프로그래밍 언어가 있다.
이것의 표준 가상 머신은 8비트 스택 머신으로 지정되어 있다. 그러나 안드로이드 스마트폰에 사용되는 자바용 달빅 가상 머신은 효율성을 위해 선택된 16비트 가상 레지스터 머신이다. 산술 명령어는 4비트(또는 그 이상) 명령어 필드를 통해 지역 변수를 직접 가져오거나 저장한다. 마찬가지로 Lua 5.0 버전은 가상 스택 머신을 더 빠른 가상 레지스터 머신으로 교체했다.

자바 가상 머신이 인기를 얻으면서 마이크로프로세서는 간접 점프를 위한 고급 분기 예측기를 사용하기 시작했다. 이러한 발전은 N-방향 점프로 인한 파이프라인 재시작의 대부분을 피하고 스택 인터프리터에 영향을 미치는 명령어 개수 비용의 상당 부분을 제거한다.

 같이 보기 
 스택 지향 프로그래밍 언어
 연쇄형 프로그래밍 언어
 애플리케이션 가상 머신 비교
 SECD 머신
 누산기 머신
 벨트 머신
 랜덤 접근 기계

 각주 

 외부 링크 
 FPGA 내 홈브류 CPU — FPGA를 사용한 홈브류 스택 머신
 Mark 1 FORTH 컴퓨터  — 개별 논리 회로를 사용한 홈브류 스택 머신
 Mark 2 FORTH 컴퓨터  — 비트슬라이스/PLD를 사용한 홈브류 스택 머신
 2세대 스택 컴퓨터 아키텍처 — 스택 머신의 역사와 설계에 대한 논문.

분류:마이크로프로세서
분류:계산 모형