스택 머신

Stack machine
오토마타 이론의 스택 머신에 대해서는, 푸시 다운 오토마톤을 참조해 주세요.

컴퓨터 과학, 컴퓨터 엔지니어링 및 프로그래밍 언어 구현에서 스택 머신은 컴퓨터 프로세서 또는 가상 머신으로, 주요 상호작용은 푸시다운 스택 간에 단수명의 일시적 값을 이동하는 것입니다.하드웨어 프로세서의 경우 하드웨어 스택이 사용됩니다.스택을 사용하면 필요한 프로세서레지스터 수가 대폭 줄어듭니다.스택 머신은 추가 로드/스토어 조작 또는 여러 스택을 통해 푸시다운 오토마타를 확장하므로 튜링 완료입니다.

설계.

대부분의 또는 모든 스택머신 명령에서는 오퍼랜드가 스택에서 생성되어 결과가 스택에 배치되는 것으로 가정하고 있습니다.스택은 3개 이상의 입력 또는 여러 결과를 쉽게 보유하기 때문에 풍부한 연산 세트를 계산할 수 있습니다.스택 머신 코드(일명 p-code)에서는 명령어는 동작을 명령하는 opcode만을 가지며 제로 주소 포맷으로 [1]알려진 상수, 레지스터 또는 메모리 셀을 식별하는 추가 필드는 없습니다.이것에 의해, 명령 디코딩이 큰폭으로 심플화됩니다.브랜치, 로드 즉시 및 로드/스토어 명령에는 인수 필드가 필요하지만 스택머신에서는 이러한 빈번한 케이스가 opcode와 함께 콤팩트한 비트그룹에 들어가도록 배치하는 경우가 많습니다.이전 결과에서 오퍼랜드의 선택은 명령 순서를 지정하여 암묵적으로 이루어집니다.일부 스택 시스템 명령 집합은 하드웨어를 직접 구동하는 것이 아니라 가상 시스템의 해석적인 실행을 목적으로 합니다.

정수 상수 오퍼랜드가 푸시됩니다.Push또는Load Immediate지침들.메모리는 종종 다른 방법으로 접근합니다.Load또는Store메모리 주소를 포함하거나 스택 내의 값에서 주소를 계산합니다.모든 실용적인 스택머신에는 명시적인 주소 계산 없이 로컬 변수와 정식 파라미터에 액세스하기 위한 로드스토어 연산코드의 변형이 있습니다.이것은, 현재의 Top-of-Stack 주소로부터의 오프셋 또는 안정된 프레임 베이스 레지스터로부터의 오프셋에 의해서 행해집니다.

명령 집합은 데이터 레지스터나 메인 메모리 셀이 아닌 표현식 스택에서만 작동하는 포스트픽스(폴란드어 역 표기법) 연산을 사용하여 대부분의 ALU 액션을 수행합니다.대부분의 산술 표현식은 포스트픽스 표기법으로 쉽게 변환할 수 있기 때문에 고급 언어를 실행하는 데 매우 편리합니다.

표현식 A*(B-C) + (D+E)의 이진 구문 트리

예를 들어 A*(B-C)+(D+E)라는 표현식을 폴란드어 역표기로 A B C - * D E + + 라고 합니다.단순한 가상 스택머신에서 이를 컴파일하여 실행하면 다음과 같은 형식이 됩니다.

# 스택 내용(맨 왼쪽 = 맨 위 = 가장 최근): A # 푸시 B # B 푸시 C # C A 뺄셈 # B-C A 곱하기 # A*(B-C) 푸시 D # D *(B-C) 푸시 E # E D A*(B+C) add ## A*(B-C)+(D+E)

산술 연산 'subtract', 'multiply' 및 'add'는 스택의 최상위 두 오퍼랜드에 작용합니다.컴퓨터는 양쪽 오퍼랜드를 스택의 최상위(최신) 값에서 가져옵니다.컴퓨터는 이 두 값을 계산된 차이, 합계 또는 곱으로 바꿉니다.즉, 명령의 피연산자는 스택에서 "팝"되고 그 결과는 스택으로 "푸시"되어 다음 명령을 위해 준비됩니다.

스택 머신은 식 스택과 콜 리턴 스택을 분리하거나 하나의 통합 구조로 할 수 있습니다.스택 머신의 명령어를 분리하면 인터랙션과 설계의 복잡함을 줄이고 파이프라인 처리를 할 수 있기 때문에 일반적으로 실행 속도가 빨라집니다.

컴파일된 스택코드를 최적화할 수 있습니다.컴파일러 출력의 백엔드 최적화는 코드 [2][3]및 잠재적으로 성능을 크게 향상시키고 컴파일러 자체의 글로벌 최적화를 통해 더 [4]많은 이점을 얻을 수 있는 것으로 입증되었습니다.

스택 스토리지

일부 스택 머신에는 레지스터 파일로 구현되는 제한된 크기의 스택이 있습니다.ALU는 인덱스를 사용하여 액세스합니다.큰 레지스터 파일은 많은 트랜지스터를 사용하기 때문에 이 방법은 작은 시스템에만 적합합니다.일부 기계에는 메모리 내에 식 스택과 별도의 레지스터 스택이 모두 있습니다.이 경우 소프트웨어 또는 인터럽트에 의해 이들 간에 데이터가 이동할 수 있습니다.일부 머신에는 메모리 액세스를 줄이기 위해 RAM에 어레이로 구현된 크기가 무제한인 스택이 있습니다.명시적인 "메모리로부터의 로드" 명령을 제외하고 피연산자 사용 순서는 데이터 스택 내의 피연산자 순서와 동일하기 때문에 우수한 프리페치를 쉽게 수행할 수 있습니다.

고려하다X+1컴파일 대상:Load X;Load 1;Add스택이 RAM에 완전히 저장되어 있으면 메모리 내 스택의 암묵적인 기입과 읽기가 이루어집니다.

  • X를 로드하고 메모리에 푸시
  • 로드 1, 메모리에 푸시
  • 메모리에서 2개의 값을 팝하여 결과를 추가하고 메모리에 푸시합니다.

총 5개의 데이터 캐시 참조에 사용됩니다.

다음 단계는 단일 탑 오브 스택 레지스터를 사용하는 스택 머신 또는 인터프리터입니다.위의 코드는 다음과 같습니다.

  • 빈 TOS 레지스터(하드웨어 머신의 경우)에 X를 로드하거나 메모리에 TOS 레지스터를 푸시하고 TOS 레지스터에 X를 로드합니다(인터프리터의 경우).
  • TOS 레지스터를 메모리에 푸시하고 1을 TOS 레지스터에 로드합니다.
  • 왼쪽 피연산자를 메모리에서 팝하고 TOS 레지스터에 추가한 후 그대로 둡니다.

최악의 경우 총 5개의 데이터 캐시 참조에 사용됩니다.일반적으로 인터프리터는 빈 공간을 추적할 필요가 없기 때문에 추적하지 않습니다.스택 포인터 아래의 값은 비어 있지 않고 TOS 캐시 레지스터는 항상 핫 상태로 유지됩니다.단, 프로그램과 스택에는 짧은 데이터 값과 넓은 데이터 값이 혼재되어 있기 때문에 일반적인 Java 인터프리터는 스택 탑오브 스택을 이러한 방식으로 버퍼링하지 않습니다.

유선 연결된 스택머신에 2개 이상의 탑스택 레지스터 또는 레지스터 파일이 있는 경우 이 예에서는 모든 메모리접근은 회피되고 데이터 캐시 사이클은 1개뿐입니다.

이력 및 구현

추가 피연산자, 함수 및 서브루틴의 정의에 의해 확장될 수 있는 제한된 사전 정의된 피연산자 세트를 가진 한 번에 두 개의 값만 레지스터에 보유해야 하는 방법에 대한 설명은 1961년 [5][6]Robert S. Barton에 의해 처음 제공되었다.

시판용 스택

다음 항목도 참조하십시오.고급 언어 컴퓨터 아키텍처

하드웨어에서 직접 실행되는 스택명령어 세트의 예는 다음과 같습니다.

  • Konrad Zuse의 [7][8]Z4(1945) 컴퓨터.
  • Burroughs의 대형 시스템 아키텍처(1961년 이후)
  • 영국 전기 KDF9 기계1964년에 처음 제공된 KDF9는 19레벨의 딥 푸시다운 레지스터 스택과 서브루틴 리턴 주소를 위한 17레벨의 딥 스택을 가지고 있었다.
  • Collins Radio Collins Adaptive Processing System 미니컴퓨터(1969년 이후)와 Rockwell Collins Advanced Architecture Microprocessor([9]1981년 이후)입니다.
  • 1981년 4월 27일에 도입된 제록스 민들레는 메모리를 [10][11]절약하기 위해 스택 머신 아키텍처를 이용했다.
  • UCSD Pascal p-machine(Pascal MicroEngine 및 기타 많은 제품)은 가상 스택 머신으로 컴파일하여 명령 세트가 불량하고 RAM이 적은 초기 8비트 마이크로프로세서에서 완전한 학생 프로그래밍 환경을 지원했습니다.
  • MU5 및 ICL 2900 시리즈하이브리드 스택 및 어큐뮬레이터 머신축전지 레지스터가 메모리 스택의 상위 데이터 값을 버퍼링했습니다.레지스터가 메모리 스택으로 유출되거나 거기에서 새로고침될 때 제어되는 로드 및 저장소 운영 코드의 변형입니다.
  • HP 3000 (클래식, PA-RISC 아님)
  • 탠덤 컴퓨터 T/16HP 3000과 마찬가지로 레지스터 스택이 메모리 스택으로 유출되거나 메모리 스택에서 다시 채워질 때 마이크로 코드가 아닌 컴파일러가 제어되는 것을 제외합니다.
  • Atmel MARC4 마이크로컨트롤러[12]
  • RTX2000, RTX2010, F21[14] 및 PSC1000[15][16] 등의 몇 가지 '포스 칩'[13]
  • Setun Ternary 컴퓨터는 스택을 사용하여 균형 잡힌 3진법을 수행했습니다.
  • Bernd Paysan의 4stack 프로세서에는 4개의 [17]스택이 있습니다.
  • Charles H. Moore가 설계한 Patriot Scientific의 Ignite 스택 머신은 최고의 기능 밀도 벤치마크를 보유하고 있습니다.
  • Saab Ericsson Space Thor 방사선 경화[18] 마이크로프로세서
  • Inmos 트랜스퓨터
  • ZPU FPGA 시스템을 [19]감시하도록 설계된 물리적으로 작은 CPU.
  • GreenArrays, Inc.[20][21][22]의 144 프로세서 GA144 칩의 F18A 아키텍처.
  • 일부 테크니컬 핸드헬드 계산기에서는 키보드인터페이스에 괄호키 대신 폴란드어 역표기를 사용합니다.이것은 스택 머신의 한 형태입니다.Plus 키는 2개의 오퍼랜드가 이미 사용자가 볼 수 있는 스택의 맨 위 위치에 있어야 합니다.

가상 스택 머신

소프트웨어에서 해석되는 가상 스택 시스템의 예:

하이브리드 머신

디지털 기능과 아날로그 기능을 모두 갖춘 하이브리드 컴퓨터와 혼동하지 마십시오.

순수 스택 머신은 동일한 객체에서 여러 필드에 액세스하는 프로시저에는 매우 비효율적입니다.스택 머신코드는 각 포인터+오프셋 계산에 대해 오브젝트 포인터를 새로고침해야 합니다.이를 위한 일반적인 수정은 스택머신에 몇 가지 레지스터 머신 기능을 추가하는 것입니다.즉, 주소를 유지하는 전용의 가시적인 레지스터 파일, 로드 및 간단한 주소 계산을 수행하기 위한 레지스터 스타일의 명령입니다.레지스터가 완전히 범용적인 것은 드문 일이며, 그렇게 되면 표현식 스택과 포스트픽스 명령이 있어야 할 강력한 이유가 없기 때문입니다.

또 다른 일반적인 하이브리드는 레지스터 머신 아키텍처에서 시작하여 스택 머신의 푸시 또는 팝 동작을 에뮬레이트하는 또 다른 메모리 주소 모드인 'memaddress = reg; reg += instr.html'을 추가하는 것입니다.이것은 DEC의 PDP-11 미니컴퓨터에서 처음 사용되었습니다.이 기능은 VAX 컴퓨터 및 Motorola 6800 및 M68000 마이크로프로세서에서 수행되었습니다.이를 통해 초기 컴파일러에서는 보다 단순한 스택 방식을 사용할 수 있게 되었습니다.또한 스택 인터프리터 또는 스레드 코드를 사용하여 가상 머신을 효율적으로 지원했습니다.그러나 이 기능은 레지스터 머신의 자체 코드가 순수한 스택머신 코드만큼 작아지는 데 도움이 되지 않았습니다.또한 레지스터 아키텍처로 컴파일할 때보다 실행 속도가 느렸습니다.Top-of-Stack 포인터를 변경하는 것은 각 프로그램 스테이트먼트 전체에서 계속적으로 위아래로 이동하는 것보다 (콜 또는 리턴마다 1회씩) 가끔만 변경하는 것이 빠릅니다.또, 메모리 참조를 완전하게 회피하는 것도 고속입니다.

보다 최근에, 소위 2세대 스택 머신은 주소 레지스터로 기능하는 전용 레지스터 컬렉션을 채택하여 메모리 주소 지정 작업을 데이터 스택에서 오프로드했습니다.예를 들어, MuP21은 "A"라는 레지스터에 의존하며, 보다 최근의 GreenArrays 프로세서는 A와 [21]B라는 두 개의 레지스터에 의존합니다.

인텔 x86 시리즈 마이크로프로세서에는 대부분의 동작에 대해 레지스터 스타일(어큐뮬레이터) 명령어가 설정되어 있습니다만, 8086 및 8088용 iAPX87(8087) 코프로세서의 x87, 인텔 8087 부동소수점 연산에는 스택 명령이 사용됩니다.즉, 프로그래머가 접근할 수 있는 부동소수점 레지스터는 없고 80비트 폭의 8레벨 딥 스택만 있습니다.x87은 조작을 지원하기 위해 x86 CPU에 크게 의존하고 있습니다.

콜 스택 및 스택프레임을 사용하는 컴퓨터

대부분의 현재 컴퓨터(명령어 세트 스타일)와 대부분의 컴파일러는 메모리의 큰 콜 리턴 스택을 사용하여 단기간의 로컬 변수를 정리하고 현재 액티브한 모든 프로시저 또는 함수의 링크를 반환합니다.네스트된 콜마다 메모리 내에 새로운 스택프레임이 생성됩니다.이 프레임은 콜이 완료될 때까지 유지됩니다.이 Call-Return 스택은 설명서의 특수한 주소 레지스터 및 특수한 주소 모드를 통해 하드웨어에 의해 완전히 관리될 수 있습니다.또는 범용 레지스터와 레지스터+오프셋 주소 모드를 사용하여 컴파일러에 이은 일련의 규칙일 수도 있습니다.아니면 그 사이에 있는 것일 수도 있어요.

이 기술은 현재 레지스터 머신에서도 거의 보편화되어 있기 때문에 이 모든 머신을 스택머신이라고 부르는 것은 도움이 되지 않습니다.이 용어는 일반적으로 식 스택 및 스택 전용 산술 명령을 사용하여 단일 문의 조각을 평가하는 기계용으로 예약되어 있습니다.

컴퓨터는 일반적으로 프로그램의 글로벌 변수와 현재 가장 안쪽 프로시저 또는 함수인 최상위 스택 프레임의 로컬 변수에 대한 직접적이고 효율적인 액세스를 제공합니다.통상, 발신자의 스택프레임의 컨텐츠의 「업 레벨」어드레싱은 불필요하며, 하드웨어에 의해서 직접 서포트되는 것은 아닙니다.필요한 경우 컴파일러는 프레임포인터를 숨겨진 추가 파라미터로 전달함으로써 이를 지원합니다.

일부 Burrough 스택 머신은 하드웨어에서 직접 상위 레벨의 참조를 지원하며, 특수한 주소 모드와 모든 외부 스코프의 프레임 주소를 저장하는 특수 '디스플레이' 레지스터 파일을 제공합니다.이후의 컴퓨터 라인은 하드웨어에서 이 기능을 하지 않았습니다.Niklaus Worth가 CDC 6000을 위한 최초의 파스칼 컴파일러를 개발했을 때, 그는 프레임 포인터의 완전한 배열을 지속적으로 업데이트하는 것보다 프레임 포인터를 체인으로 전달하는 것이 전반적으로 더 빠르다는 것을 알게 되었다.또한 이 소프트웨어 방법에서는 C와 같이 상위 수준의 참조가 없는 공통 언어에 대한 오버헤드가 추가되지 않습니다.

동일한 Burroughs 머신도 작업 또는 스레드의 중첩을 지원했습니다.태스크와 태스크 생성자는 태스크 생성 시 존재했던 스택 프레임을 공유하지만 작성자의 후속 프레임이나 태스크의 자체 프레임은 공유하지 않습니다.이것은 선인장의 줄기와 팔을 닮은 배치도를 가진 선인장 더미에 의해 지탱되었다.각 작업에는 스택과 소유한 프레임을 유지하는 자체 메모리 세그먼트가 있었습니다.이 스택의 베이스는 작성자 스택의 중앙에 링크되어 있습니다.일반적인 플랫주소 공간이 있는 머신에서는 작성자 스택과 태스크스택은 하나의 힙에 별도의 힙오브젝트가 됩니다.

일부 프로그래밍 언어에서는 외부 범위 데이터 환경이 항상 시간 내에 중첩되지 않습니다.이러한 언어에서는 절차 '액티베이션 레코드'를 선형 스택에 추가된 스택 프레임이 아니라 개별 힙 개체로 구성합니다.

로컬 변수나 파라미터의 이름이 없는 Fourth 등의 간단한 언어에서는 스택프레임에는 리턴 브랜치주소와 프레임 관리 오버헤드만 포함됩니다.따라서 리턴 스택은 프레임이 아닌 베어 리턴 주소를 유지합니다.리턴 스택은 콜 셋업 및 리턴 플로우를 개선하기 위해 데이터 값 스택과는 별개입니다.

레지스터 머신과의 비교

스택 머신은 종종 레지스터 배열에 값을 유지하는 레지스터 머신과 비교됩니다.레지스터 머신은 스택과 같은 구조를 이 어레이에 저장할 수 있지만 레지스터 머신은 스택인터페이스를 우회하는 명령을 가지고 있습니다.등록 머신은 통상적으로 스택 [24]머신보다 성능이 뛰어나며 스택 머신은 하드웨어 시스템에서 틈새 기업으로 자리매김하고 있습니다.그러나 스택 머신은 [25]단순하고 구현이 쉽기 때문에 가상 머신을 구현하는 데 자주 사용됩니다.

지침들

스택 머신은 코드 밀도가 높아집니다.6비트 이하의 일반적인 스택머신 명령과는 달리 레지스터 머신은 오퍼랜드를 선택하기 위해 ALU 명령당2개 또는 3개의 레지스터 번호 필드가 필요합니다.가장 밀도가 높은 레지스터 머신은 명령당 평균 약 16비트와 오퍼랜드를 더합니다.레지스터 머신에서는 로드 스토어 연산 코드에 대해 넓은 오프셋 필드도 사용합니다.스택 머신의 콤팩트한 코드는 자연스럽게 캐시에 더 많은 명령어를 넣기 때문에 캐시 효율을 높이고 메모리 비용을 절감하거나 특정 비용으로 더 빠른 메모리 시스템을 구현할 수 있습니다.또한 대부분의 스택머신 명령어는 매우 단순하며 opcode 필드 또는 operand 필드를 1개만 사용합니다.따라서 스택머신은 각 명령어를 디코딩하는 데 필요한 전자자원이 거의 없습니다.

프로그램은 레지스터 머신 또는 메모리 투 메모리 머신으로 컴파일할 때보다 스택 머신으로 컴파일할 때 더 많은 명령을 실행해야 합니다.각 변수 부하 또는 상수에는 값을 사용하는 명령 내에 번들되는 대신 개별 부하 명령이 필요합니다.분리된 명령이 단순하고 빠르게 실행될 수 있지만 총 명령 수는 여전히 더 높습니다.

대부분의 레지스터 인터프리터는 레지스터를 번호로 지정합니다.그러나 호스트 시스템의 레지스터는 인덱스 배열에서 액세스할 수 없으므로 메모리 배열이 가상 레지스터에 할당됩니다.따라서 레지스터 인터프리터의 명령은 생성된 데이터를 다음 명령으로 전달하기 위해 메모리를 사용해야 합니다.이로 인해 미세한 프로세스 규칙으로 만들어진 마이크로프로세서에서는 인터프리터가 훨씬 느려집니다(즉, Haswell x86과 같은 회로 속도를 개선하지 않고 더 빠른 트랜지스터).메모리 액세스에는 몇 개의 클럭이 필요하지만 레지스터 액세스에는 1개의 클럭만 필요합니다.레지스터 파일 대신 데이터 포워딩 회로가 있는 스택 머신의 경우 스택 인터프리터는 호스트 머신의 메모리 대신 스택의 상위 여러 오퍼랜드에 호스트 머신의 레지스터를 할당할 수 있습니다.

스택 머신에서는 명령에 사용되는 오퍼랜드는 항상 고정 위치(하드웨어 설계에서는 항상 메모리 위치0에 있을 수 있는 스택의 하단)에서 기존의 오프셋(스택 포인터로 설정)에 있기 때문에 귀중한 캐시 내 또는 CPU 내 스토리지를 사용하여 많은 메모리 주소 또는 인덱스 번호를 저장할 필요가 없습니다.이것에 의해, 이러한 레지스터와 캐시가 비플로우 [citation needed]계산에 사용하기 위해서 보존될 가능성이 있습니다.

임시/로컬 값

업계 일각에서는 스택 머신이 레지스터 [26]머신보다 임시 값 및 로컬 변수에 대해 더 많은 데이터 캐시 사이클을 실행한다고 믿고 있습니다.

스택 머신에서는 일시적인 값은 메모리에 흘리는 경우가 많은 반면 레지스터가 많은 머신에서는 보통 레지스터에 남아 있습니다(다만, 이러한 값은 프로시저의 정의의 마지막에 있는 「액티베이션 프레임」이나 적어도 인터럽트 처리중에 메모리 버퍼에 흘릴 필요가 있습니다).메모리로 유출된 값은 캐시 사이클을 더 많이 추가합니다.이 유출 효과는 top-of-stack 값을 버퍼링하는 데 사용되는 숨겨진 레지스터의 수, 중첩된 프로시저 호출 빈도 및 호스트 컴퓨터 인터럽트 처리 속도에 따라 달라집니다.

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

한편, 레지스터 머신은, 네스트 된 프로시저 콜에 걸쳐, 레지스터의 상당수를 메모리에 흘릴 필요가 있습니다.콜의 동적 깊이가 아닌 컴파일 시에 어떤 레지스터를 언제 흘릴지 결정합니다.이것에 의해, 고도의 스택 머신의 실장보다 데이터 캐시 트래픽이 많아질 가능성이 있습니다.

일반적인 하위 표현식

레지스터 머신에서 공통 서브 표현식(같은 결과값으로 여러 번 사용되는 서브 표현식)을 단 한 번만 평가하고 그 결과를 고속 레지스터에 저장할 수 있다.이후의 재사용에는 시간이나 코드 비용이 들지 않으며 레지스터 참조만 가능합니다.이 최적화를 통해 단순 표현식(예: 변수 X 또는 포인터 P 로딩) 및 덜 일반적인 복잡한 표현식 속도가 향상됩니다.

반면 스택 머신의 경우 두 가지 방법 중 하나로 결과를 저장할 수 있습니다.첫째, 메모리에 임시 변수를 사용하여 결과를 저장할 수 있습니다.저장 및 후속 검색에는 추가 명령과 추가 데이터 캐시 사이클이 필요합니다.대부분의 스택 CPU에서는 거의 항상 그렇듯이 서브 표현식 계산이 메모리에서 가져오는 것보다 시간 내에 비용이 더 많이 드는 경우에만 이 작업이 성공합니다.단순 변수 및 포인터 가져오기에는 이미 액세스당 1개의 데이터 캐시 사이클 비용이 동일하기 때문에 결코 가치가 없습니다.다음과 같은 표현에 대해서는 극히 일부만 가치가 있습니다.X+1이러한 간단한 표현은 비연결형 언어로 작성된 프로그램에서 다중되고 최적화 가능한 표현식의 대부분을 차지합니다.최적화 컴파일러는 프로그래머가 소스 코드에서 피할 수 있었던 중복성에서만 승리할 수 있습니다.

두 번째 방법은 계산된 값을 데이터 스택에 남겨두고 필요에 따라 복제합니다.스택 엔트리를 복사하기 위한 조작이 사용됩니다.스택의 깊이는 CPU의 사용 가능한 복사 명령에 충분히 얕아야 합니다.손으로 쓴 스택 코드는 종종 이 방법을 사용하며 범용 레지스터 [27][8]머신과 같은 속도를 달성합니다.유감스럽게도 최적의 "스택 스케줄링"을 위한 알고리즘은 프로그래밍 언어에서 널리 사용되지 않습니다.

파이프라인

최신 시스템에서는 데이터 캐시에서 변수를 가져오는 시간이 기본 ALU 작업에 필요한 시간보다 몇 배 더 긴 경우가 많습니다.프로그램이 메모리 로드를 해당 변수를 필요로 하는 명령보다 몇 사이클 먼저 시작할 수 있으면 중단 없이 더 빠르게 실행됩니다.복잡한 머신에서는, 심도 있는 파이프 라인과 동시에 많은 명령어를 검사해 실행하는 「오동작 실행」을 통해서, 이 작업을 실시할 수 있습니다.레지스터 머신은 훨씬 더 간단한 "순서대로" 하드웨어, 얕은 파이프라인 및 약간 더 스마트한 컴파일러를 사용하여 이를 수행할 수도 있습니다.로드 스텝은 개별 명령어가 되며, 이 명령어는 코드 시퀀스의 훨씬 전에 정적으로 스케줄 됩니다.컴파일러는 독립된 스텝을 사이에 둡니다.

메모리 액세스를 스케줄링하려면 명시적인 예비 레지스터가 필요합니다.스택 머신에서는 마이크로 아키텍처의 일부 측면이 프로그래머에게 노출되지 않으면 불가능합니다.식 A B -의 경우, B는 Minus 스텝 직전에 평가되고 푸시되어야 합니다.스택의 치환이나 하드웨어의 멀티스레딩이 없으면 로드B가 완료될 때까지 기다리는 동안 비교적 적은 수의 유용한 코드를 삽입할 수 있습니다.스택 머신은 많은 명령어를 동시에 처리하는 깊이 있는 순서 외 실행 파이프라인을 갖추어 메모리 지연을 회피할 수 있습니다.또한 부하가 완료되는 동안 다른 워크로드에서 작업할 수 있도록 스택을 허용하거나 Unisys A9 시스템과 [28]같이 다른 프로그램 스레드의 실행을 인터레이스할 수 있습니다.그러나 오늘날 병렬 컴퓨팅 부하가 증가하고 있는 것은 이것이 과거에 밝혀진 단점은 아닐 수 있음을 시사합니다.

스택 머신은 레지스터 [27]머신의 오퍼랜드 가져오기 단계를 생략할 수 있습니다.예를 들어 Java Optimized Processor(JOP; Java 최적화 프로세서) 마이크로프로세서에서는 스택의 상위2개의 오퍼랜드가 레지스터 [29]파일보다 빠른 데이터 전송 회선에 직접 들어갑니다.

순서가 맞지 않는 실행

Tomasulo 알고리즘은 데이터가 사용 가능해지면 명령을 발행하여 명령 수준의 병렬 처리를 찾습니다.개념적으로 스택 내의 위치 주소는 레지스터 파일의 레지스터 인덱스와 다르지 않다.이 뷰에서는 Tomasulo 알고리즘을 스택머신에서 순서대로 실행할 수 있습니다.

스택 머신에서의 순서가 어긋나는 실행은 이론적으로나 실제적인 [30]많은 문제를 줄이거나 회피하는 것으로 보입니다.인용된 연구에 따르면 이러한 스택 머신은 명령 수준의 병렬 처리를 이용할 수 있으며, 결과 하드웨어는 명령의 데이터를 캐시해야 합니다.이러한 머신은 스택에 대한 대부분의 메모리 액세스를 효과적으로 바이패스합니다.그 결과, 스루풋(클럭당 명령)이 RISC 레지스터 머신에 필적합니다(피연산자 주소는 암묵적이기 때문에) 코드 밀도가 훨씬 높아집니다.

이 연구에서 제기된 문제 중 하나는 레지스터 머신의 RISC 명령의 작업을 수행하려면 약 1.88 스택 머신 명령이 필요하다는 것입니다.따라서 경쟁사의 고장난 스택 머신은 명령을 추적하기 위해 약 2배의 전자 자원을 필요로 합니다(「발행 스테이션」).이는 명령 캐시와 메모리 및 명령 디코딩 회로의 절약을 통해 보완될 수 있습니다.

고속 레지스터 머신을 내부에 숨깁니다.

심플한 스택머신 중에는 개별 레지스터 레벨까지 완전히 커스터마이즈된 칩 설계가 있는 것도 있습니다.스택 어드레스 레지스터의 탑과 스택데이터 버퍼의 N 탑은 개별 레지스터 회선으로 구성되어 별도의 애드혹 접속이 있습니다.

그러나 대부분의 스택 머신은 레지스터 파일 내에 N개의 데이터 버퍼가 함께 저장되어 읽기/쓰기 버스를 공유하는 더 큰 회로 컴포넌트에서 구축됩니다.디코딩된 스택명령어는 숨겨진 레지스터 파일상의 1개 이상의 순차 액션에 매핑됩니다.로드와 ALU ops는 상위 레지스터 몇 개에 작용하고 암묵적인 유출과 충전은 하위 레지스터에 작용합니다.디코더를 사용하면 명령 스트림을 소형화할 수 있습니다.그러나 코드 스트림에 기본 레지스터 파일을 직접 조작하는 명시적인 레지스터 선택 필드가 있다면 컴파일러는 모든 레지스터를 더 잘 사용할 수 있고 프로그램은 더 빨리 실행될 것이다.

마이크로프로그래밍된 스택 머신이 그 예입니다.내부 마이크로코드 엔진은 RISC와 같은 레지스터 머신 또는 여러 레지스터 파일을 사용하는 VLIW와 같은 머신입니다.작업 고유의 마이크로코드에 의해 직접 제어되는 경우 엔진은 동일한 작업에 대해 동등한 스택코드에 의해 간접적으로 제어되는 경우보다 사이클당 훨씬 많은 작업을 완료할 수 있습니다.

HP 3000 및 Tandem T/16의 오브젝트코드 트랜슬레이터도 [31][32]그 예입니다.스택 코드 시퀀스를 동등한 RISC 코드 시퀀스로 변환했습니다.사소한 '로컬' 최적화를 통해 스택 아키텍처의 오버헤드가 상당 부분 제거되었습니다.스페어 레지스터는 반복적인 주소 계산을 배제하기 위해 사용되었습니다.변환된 코드는 원래 머신과 타깃 머신 간의 불일치로 인해 여전히 많은 에뮬레이션 오버헤드를 유지하고 있었습니다.이러한 부담에도 불구하고 변환된 코드의 사이클 효율은 원래 스택 코드의 사이클 효율과 일치했습니다.그리고 컴파일러의 최적화를 통해 소스 코드를 레지스터 머신에 직접 재컴파일 했을 때 효율이 두 배로 향상되었습니다.이는 스택 아키텍처와 최적화되지 않은 컴파일러가 기본 하드웨어의 절반 이상을 낭비하고 있음을 나타냅니다.

레지스터 파일은 데이터 캐시를 통한 메모리 참조에 비해 대역폭이 높고 대기 시간이 매우 짧기 때문에 컴퓨팅에 적합한 도구입니다.단순한 기계에서 레지스터 파일은 2개의 독립된 레지스터를 읽고 3번째 레지스터를 쓸 수 있으며, 모두 1사이클 이하의 레이텐시로 하나의 ALU 사이클로 쓸 수 있다.한편, 대응하는 데이터 캐시는 사이클당 1개의 읽기 또는1개의 쓰기(둘 다 아님)만을 개시할 수 있습니다.읽기는 일반적으로 2개의 ALU 사이클의 지연이 있습니다.파이프라인 지연의 2배에 해당하는 처리량의 3분의 1입니다.사이클당 2개 이상의 명령을 완료하는 Athlon과 같은 복잡한 기계에서는 레지스터 파일을 통해 4개 이상의 독립된 레지스터를 읽고 2개의 다른 레지스터를 쓸 수 있으며, 모두 1사이클의 레이텐시를 갖는 하나의 ALU 사이클에서 쓸 수 있습니다.반면 이중 포트 데이터 캐시는 사이클당 읽기 또는 쓰기를 2회만 시작할 수 있으며 지연 시간은 여러 번입니다.다시 말씀드리지만 레지스터 처리량의 1/3입니다.추가 포트를 사용하여 캐시를 구축하는 것은 매우 비용이 많이 듭니다.

스택은 대부분의 소프트웨어 프로그램의 컴포넌트이기 때문에 사용되는 소프트웨어가 엄밀하게 스택머신이 아닌 경우에도 하드웨어 스택머신은 프로그램의 내부 동작을 보다 밀접하게 모방할 수 있습니다.프로세서 레지스터는 열비용이 높기 때문에 스택머신이 에너지 [20]효율을 높일 수 있습니다.

인터럽트

인터럽트에 대한 응답에는 레지스터를 스택에 저장한 후 인터럽트 핸들러 코드로 분기하는 작업이 포함됩니다.대부분의 파라미터가 이미 스택에 존재하기 때문에 스택머신은 인터럽트에 대해 보다 신속하게 응답합니다.일부 레지스터 머신에서는 즉시[33] 스왑할 수 있는 여러 레지스터 파일을 사용하여 이 문제를 해결하지만, 이로 인해 비용이 증가하고 레지스터 파일의 속도가 느려집니다.

인터프리터

가상 스택 머신의 인터프리터는 레지스터 머신의 인터프리터보다 구축이 용이합니다.메모리 주소 모드를 처리하는 논리는 여러 명령에서 반복되는 것이 아니라 한 곳에서만 이루어집니다.스택 머신에서는 opcode의 변형이 적은 경향이 있습니다.일반화된 opcode는 메모리 참조나 함수 호출 셋업의 빈번한 케이스와 불분명한 코너 케이스 모두를 처리합니다.(단, 코드 밀도는 종종 같은 조작에 대해 짧고 긴 형식을 추가함으로써 향상됩니다.)

가상 스택 시스템의 인터프리터는 종종 다른 유형의 [34]가상 시스템의 인터프리터보다 느립니다.이러한 속도 저하는 현재 x86 칩과 같이 깊은 실행 파이프라인이 있는 호스트 머신에서 실행되는 경우 가장 심각합니다.

일부 인터프리터에서는 인터프리터가 N방향 스위치점프를 실행하여 다음 opcode를 디코딩하고 특정 opcode의 스텝으로 분기해야 합니다.opcode를 선택하는 또 다른 방법은 스레드 코드입니다.호스트 시스템의 프리페치 메커니즘이 인덱싱된 점프 또는 간접 점프 대상을 예측하고 가져올 수 없습니다.따라서 호스트된 인터프리터가 다른 가상 명령을 디코딩할 때마다 호스트 시스템의 실행 파이프라인이 다시 시작되어야 합니다.이 문제는 다른 [35]유형의 가상 시스템보다 가상 스택 시스템에서 더 자주 발생합니다.

한 가지 예는 Java 프로그래밍 언어입니다.표준 가상 시스템은 8비트 스택 시스템으로 지정됩니다.그러나 Android 스마트폰에서 사용되는 Java용 Dalvik 가상 머신은 16비트 가상 레지스터 머신으로, 효율성을 이유로 선택되었습니다.산술 명령은 4비트 이상의 명령 필드를 [36]통해 로컬 변수를 직접 가져오거나 저장합니다.마찬가지로 버전 5.0의 Lua는 가상 스택 시스템을 더 빠른 가상 레지스터 [37][38]시스템으로 교체했습니다.

Java 가상 머신이 보급된 이후 마이크로프로세서는 간접적인 [39]점프를 위해 고급 분기 예측 변수를 사용해 왔습니다.이를 통해 N-way 점프에 따른 파이프라인 재기동을 대부분 피할 수 있으며 스택인터프리터에 영향을 주는 명령어 카운트 비용도 많이 절감됩니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Beard, Bob (Autumn 1997). "The KDF9 Computer - 30 Years On". Computer RESURRECTION.
  2. ^ Koopman, Jr., Philip John (1994). "A Preliminary Exploration of Optimized Stack Code Generation" (PDF). Journal of Forth Applications and Research. 6 (3).
  3. ^ Bailey, Chris (2000). "Inter-Boundary Scheduling of Stack Operands: A preliminary Study" (PDF). Proceedings of Euroforth 2000 Conference.
  4. ^ Shannon, Mark; Bailey, Chris (2006). "Global Stack Allocation: Register Allocation for Stack Machines" (PDF). Proceedings of Euroforth Conference 2006.
  5. ^ Barton, Robert S. (1961). "A new approach to the functional design of a digital computer". Papers Presented at the May 9-11, 1961, Western Joint IRE-AIEE-ACM Computer Conference. 1961 Western Joint IRE-AIEE-ACM Computer Conference. pp. 393–396. doi:10.1145/1460690.1460736. ISBN 978-1-45037872-7. S2CID 29044652.
  6. ^ Barton, Robert S. (1987). "A new approach to the functional design of a digital computer". IEEE Annals of the History of Computing. 9: 11–15. doi:10.1109/MAHC.1987.10002.
  7. ^ Blaauw, Gerrit Anne; Brooks, Jr., Frederick Phillips (1997). Computer architecture: Concepts and evolution. Boston, Massachusetts, USA: Addison-Wesley Longman Publishing Co., Inc.
  8. ^ a b LaForest, 찰스 에릭(2007년 4월)."2.1루카시에 비치 및 최초 발생치 2.1.2를 독일:콘라트 추제(1910–1995. 2.2 첫번째 세대 스택 컴퓨터의:2.2.1항 Zuse Z4".Second-Generation 스택 컴퓨터 건축(논제)(PDF).워터루, 캐나다:워털루 대학.를 대신하여 서명함. 8,11,...그 2022-01-20에 원래에서Archived(PDF)..(178페이지)[1]2022-07-02 Retrieved.
  9. ^ Greve, David A.; Wilding, Matthew M. (1998-01-12). "The World's First Java Processor". Electronic Engineering Times.
  10. ^ "Mesa Processor Principles of Operation". DigiBarn Computer Museum. Xerox. Retrieved 2019-12-23.
  11. ^ "DigiBarn: The Xerox Star 8010 "Dandelion"". DigiBarn Computer Museum. Retrieved 2019-12-23.
  12. ^ MARC4 4-bit Microcontrollers Programmer's Guide (PDF). Atmel.
  13. ^ "Forth chips". Colorforth.com. Archived from the original on 2006-02-15. Retrieved 2017-10-08.
  14. ^ "F21 Microprocessor Overview". Ultratechnology.com. Retrieved 2017-10-08.
  15. ^ "ForthFreak wiki". GitHub.com. 2017-08-25. Retrieved 2017-10-08.
  16. ^ "A Java chip available -- now!". Developer.com. 1999-04-08. Retrieved 2022-07-07.
  17. ^ "4stack Processor". bernd-paysan.de. Retrieved 2017-10-08.
  18. ^ "Porting the GNU C Compiler to the Thor Microprocessor" (PDF). 1995-12-04. Archived from the original (PDF) on 2011-08-20. Retrieved 2011-03-30.
  19. ^ "ZPU - the world's smallest 32-bit CPU with a GCC tool-chain: Overview". opencores.org. Retrieved 2015-02-07.
  20. ^ a b "Documents". GreenArrays, Inc. F18A Technology. Retrieved 2022-07-07.
  21. ^ a b "colorForth Instructions". Colorforth.com. Archived from the original on 2016-03-10. Retrieved 2017-10-08. (이력적인 이유로 colorForth라고 명명된 F18A 코어의 명령어 세트).
  22. ^ "GreenArrays, Inc". Greenarraychips.com. Retrieved 2017-10-08.
  23. ^ Randell, Brian; Russell, Lawford John (1964). Algol 60 Implementation (PDF). London, UK: Academic Press. ISBN 0-12-578150-4.
  24. ^ Shi, Yunhe; Gregg, David; Beatty, Andrew; Ertl, M. Anton (2005). "Virtual machine showdown: stack versus registers". Proceedings of the 1st ACM/USENIX International Conference on Virtual Execution Environments - VEE '05: 153. doi:10.1145/1064979.1065001. S2CID 811512.
  25. ^ Hyde, Randall (2004). Write Great Code, Vol. 2: Thinking Low-Level, Writing High-Level. Vol. 2. No Starch Press. p. 391. ISBN 978-1-59327-065-0. Retrieved 2021-06-30.
  26. ^ "컴퓨터 아키텍처:정량적 접근법」, John L. 헤네시, 데이비드 앤드류 패터슨: 스택 머신에 대한 논의를 참조하십시오.
  27. ^ a b Koopman, Jr., Philip John. "Stack Computers: the new wave". Ece.cmu.edu. Retrieved 2017-10-08.
  28. ^ Introduction to A Series Systems (PDF). Burroughs Corporation. April 1986. Retrieved 2022-07-07.
  29. ^ "Design and Implementation of an Efficient Stack Machine" (PDF). Jopdesign.com. Retrieved 2017-10-08.
  30. ^ Chatterji, Satrajit; Ravindran, Kaushik. "BOOST: Berkeley's Out of Order Stack Thingie". Research Gate. Kaushik Ravindran. Retrieved 2016-02-16.
  31. ^ Bergh, Arndt; Keilman, Keith; Magenheimer, Daniel; Miller, James (December 1987). "HP3000 Emulation on HP Precision Architecture Computers" (PDF). Hewlett-Packard Journal. Hewlett Packard: 87–89. Retrieved 2017-10-08.
  32. ^ 오브젝트 코드 변환을 통한 CISC 컴퓨터 패밀리의 RISC로의 이행Kristy Andrews, Duane Sand: ASPLOS-V 진행, 1992년 10월
  33. ^ 8051 CPU 매뉴얼, 인텔, 1980
  34. ^ Shi, Yunhe; Gregg, David; Beatty, Andrew; Ertle, M. Anton. "Virtual Machine Showdown: Stack vs. Register Machine" (PDF). Usenix.org. Retrieved 2017-10-08.
  35. ^ Davis, Brian; Beatty, Andrew; Casey, Kevin; Gregg, David; Waldron, John. "The Case for Virtual Register Machines" (PDF). Scss.tcd.ie. Retrieved 2017-10-08.
  36. ^ Bornstein, Dan (2008-05-29). "Presentation of Dalvik VM Internals" (PDF). p. 22. Retrieved 2010-08-16.
  37. ^ "The Implementation of Lua 5.0" (PDF). Lua.org. Retrieved 2017-10-08.
  38. ^ "The Virtual Machine of Lua 5.0" (PDF). Inf.puc-rio.br. Retrieved 2017-10-08.
  39. ^ "Branch Prediction and the Performance of Interpreters - Don't Trust Folklore". Hal.inria.fr. Retrieved 2017-10-08.

외부 링크