순서가 맞지 않는 실행

Out-of-order execution

컴퓨터 공학에서, 순서 외 실행(또는 더 공식적으로 동적 실행)은 대부분의 고성능 중앙 처리 장치에서 사용되지 않을 명령 주기를 사용하기 위해 사용되는 패러다임입니다.이 패러다임에서 프로세서는 [2][3]프로그램에서의 원래의 순서가 아닌 입력 데이터 및 실행 [1]유닛의 가용성에 의해 제어되는 순서로 명령을 실행한다.이것에 의해, 프로세서는, 이전의 명령이 완료되는 것을 기다리는 동안 아이돌 상태가 되는 것을 회피할 수 있어 그 사이에 곧바로 [4]독립적으로 실행할 수 있는 다음의 명령을 처리할 수 있습니다.

역사

순서 외 실행은 제한된 형태의 데이터 흐름 계산으로, 1970년대와 1980년대 초반 컴퓨터 아키텍처의 주요 연구 영역이었습니다.

이 주제에 대한 중요한 학술 연구는 예일 패트와 그의 HPSM [5]시뮬레이터에 의해 주도되었다.제임스 E의 논문. 1985년에 출판된 Smith와 A. R. Pleszkun은 순서가 맞지 않는 기계에서 예외의 정확한 동작을 어떻게 유지할 수 있는지를 설명함으로써 이 체계를 완성했다.

순서 외의 실행을 최초로 사용한 머신은 CDC 6600(1964)으로, 스코어보드를 사용해 경합을 해결했습니다.그러나 6600에서는 쓰기 후 쓰기(WAW) 경합 처리가 부족하여 대신 스톨을 선택했습니다.이 상황을 손튼은 [6]퍼스트 오더 컨플릭트라고 불렀다.읽기 후 쓰기(RAW) 충돌 해결('Second Order Conflict')[7]과 읽기 후 쓰기(WAR) 충돌 해결('Third Order Conflict')[8]은 모두 완료되었지만, 6600에는 완전한 순서 외 실행이 가능하다고 선언하기에 충분하지만 정확한 예외 처리가 없었습니다.브런치가 프로그램 [9]카운터에서 7단어 이내로 제한된 "명령 스택"에 있는 위치만 있으면 브런치 예측의 초기 및 제한된 형식이 가능했다.

약 3년 후, IBM System/360 Model 91(1966)은 완전히 순서가 뒤바뀐 실행을 가능하게 하는 Tomasulo의 알고리즘을 도입했습니다.1990년에 IBM은 최초의 고장 마이크로프로세서 POWER1을 선보였습니다. 고장 마이크로프로세서 POWER1은 고장 난 실행이 부동 소수점 명령으로 제한됩니다(모델[10] 91에서도 마찬가지).

1990년대에 들어서면서 순서가 맞지 않는 실행이 더욱 보편화되었고 IBM/Motorola Power에 소개되었습니다.PC 601(1993년), 후지쯔/HAL SPARC64(1995년), 인텔 Pentium Pro(1995년), MIPS R10000(1996년), HP PA-8000(1996년), AMD K5(1996년), DEC Alpha 21264(1996년).이러한 경향에 대한 주목할 만한 예외로는 Sun UltraSPARC, HP/Intel Itanium, Intel Atom에서 Silvermont [11]Architecture까지 및 IBM POWER6가 있습니다.

순서가 뒤바뀐 기술의 높은 논리적 복잡성은 1990년대 중반까지 주류 기계에 도달하지 못한 이유입니다.비용에 민감한 시장을 위해 설계된 많은 로우엔드 프로세서는 구현에 필요한 실리콘 영역이 크기 때문에 여전히 이 패러다임을 사용하지 않습니다.저전력 소비는, 순서부여 실행(OOE) 설계에서는 달성하기 어려운 또 하나의 설계 목표입니다.

기본 개념

OoO 실행을 이해하기 위해서는 먼저 두 가지를 순서대로 설명하고 비교할 수 있도록 하는 것이 유용합니다.명령은 즉시 완료할 수 없습니다. 시간이 걸립니다(복수 주기).따라서 결과는 필요한 부분에 뒤처지게 됩니다.순서대로 의존관계를 추적해야 합니다.그러나 그 접근법은 매우 세련되지 않다: 매번 멈춘다.OoO는 아래와 같이 훨씬 더 정교한 데이터 추적 기술을 사용합니다.

프로세서 순서

이전의 프로세서에서는, 명령의 처리는, 통상은 다음의 순서로 이루어진 명령 사이클로 행해집니다.

  1. 명령 가져오기.
  2. 입력 오퍼랜드를 사용할 수 있는 경우(예를 들어 프로세서 레지스터에서), 명령은 적절한 기능 유닛에 디스패치됩니다.현재 클럭 사이클 중에 1개 이상의 오퍼랜드를 사용할 수 없는 경우(일반적으로 메모리에서 가져오기 때문에), 프로세서는 사용할 수 있을 때까지 정지합니다.
  3. 명령은 적절한 기능 유닛에 의해 실행됩니다.
  4. 기능 유닛은 결과를 레지스터 파일에 다시 씁니다.

순서 있는 프로세서는 (결국) 쓸 파이프라인을 기록하는 간단한 "비트 벡터"를 가지고 있는 경우가 많습니다.입력 오퍼랜드 중 하나가 이 벡터에 대응하는 비트를 설정하고 있는 경우, 명령은 정지합니다.기본적으로 벡터는 레지스터 위험으로부터 보호하는 매우 단순한 역할을 수행합니다.따라서 순서 외 실행은 2D 매트릭스를 사용하는 반면, 순서 외 실행은 위험 [citation needed]회피를 위해 1D 벡터를 사용합니다.

고장난 프로세서

이 새로운 패러다임은 명령 처리를 다음 단계로 나눕니다.

  1. 명령 가져오기.
  2. 명령 큐(명령 버퍼 또는 예약 스테이션이라고도 함)로의 명령 디스패치.
  3. 명령어는 입력 오퍼랜드를 사용할 수 있을 때까지 큐에서 대기합니다.명령은 이전 명령보다 먼저 대기열을 벗어날 수 있습니다.
  4. 명령은 해당 기능 유닛에 발행되고 해당 유닛에 의해 실행됩니다.
  5. 결과가 큐잉됩니다.
  6. 이전의 모든 명령어가 레지스터 파일에 결과를 다시 쓴 후에만 이 결과가 레지스터 파일에 다시 기록됩니다.이것은 졸업 또는 은퇴 단계라고 불립니다.

OoOE 처리의 주요 개념은 프로세서가 작업을 수행하는 데 필요한 데이터를 사용할 수 없을 때 발생하는 정지 클래스를 피할 수 있도록 하는 것입니다.상기 개요에서 OoOE 프로세서는 데이터 누락으로 인해 명령이 완전히 처리될 준비가 되지 않았을 때 순서 프로세서의 (2)단계에서 발생하는 스톨을 회피한다.

OoOE 프로세서는 이러한 "슬롯"을 준비된 다른 명령으로 시간 내에 채우고 마지막에 결과를 다시 정렬하여 명령이 정상적으로 처리된 것처럼 보이게 합니다.원래의 컴퓨터 코드로 명령어가 정렬되는 방법을 프로그램 순서라고 합니다.프로세서에서는 데이터 순서, 즉 프로세서의 레지스터에서 데이터, 오퍼랜드가 이용 가능하게 되는 순서로 처리됩니다.어느 순서에서 다른 순서로 변환해, 출력의 논리적인 순서를 유지하기 위해서는, 꽤 복잡한 회로가 필요합니다.프로세서 자체가 명령을 무작위로 실행합니다.

OoOE 처리의 이점은 명령 파이프라인이 깊어지고 메인 메모리(또는 캐시 메모리)와 프로세서의 속도 차이가 커짐에 따라 커집니다.최신 머신에서는 프로세서가 메모리보다 몇 배 빠르게 동작하기 때문에 프로세서가 데이터가 도착하기를 기다리는 동안 다수의 명령을 처리할 수 있습니다.

디스패치 및 문제 디커플링으로 인해 문제가 발생할 수 있습니다.

새로운 패러다임의 차이점 중 하나는 디스패치스텝을 이슈스텝에서 분리하여 졸업스텝을 실행스텝에서 분리할 수 있는 큐의 작성입니다.패러다임의 초기 명칭은 분리된 아키텍처였습니다.이전의 순서 있는 프로세서에서는, 이러한 스테이지가 꽤 록 스텝의 파이프라인 방식으로 동작했습니다.

최종 결과가 올바른 한, 프로그램의 명령은 원래 지정된 순서로 실행되지 않을 수 있습니다.버퍼를 사용하여 파이프라인 프로세서의 실행 단계에서 가져오기 및 디코딩 단계를 분리합니다.

버퍼의 목적은 컴퓨터 프로그램에서 메모리 액세스를 분할하고 함수를 실행하여 두 가지 사이의 [12]미세한 병렬성을 이용하여 고성능을 달성하는 것입니다.이것에 의해, 프로세서의 관점으로부터 모든 메모리 레이텐시를 효과적으로 숨길 수 있습니다.

이론적으로는 버퍼가 클수록 throughput이 증가할 수 있습니다.다만, 프로세서의 브랜치 설정이 잘못되어 있는 경우는, 버퍼 전체를 플래시 할 필요가 있어, 많은 클럭 사이클이 낭비되어 효율이 저하하는 일이 있습니다.또한 버퍼가 클수록 더 많은 열이 발생하고 더 많은 다이 공간을 사용합니다.이러한 이유로 오늘날 프로세서 설계자는 멀티 스레드 설계 방식을 선호합니다.

디커플링된 아키텍처는 일반적으로 제어 부하가 높은 코드를 [13]잘 처리하지 못하기 때문에 범용 컴퓨팅에서는 유용하지 않다고 생각됩니다.제어 부하가 높은 코드에는 운영 체제 커널에서 자주 발생하는 중첩된 분기 등이 포함됩니다.디커플링된 아키텍처는 VLIW(Very Long Instruction Word)[14] 아키텍처의 스케줄링에 중요한 역할을 합니다.

명령이 잘못된 순서로 발행될 수 있는 빈도를 줄이는 잘못된 피연산자 종속성을 피하기 위해 레지스터 이름 변경이라는 기술이 사용됩니다.이 방식에서는 아키텍처에 의해 정의된 것보다 더 많은 물리 레지스터가 있습니다.물리 레지스터는 태그 부착되므로 동일한 아키텍처 레지스터의 여러 버전이 동시에 존재할 수 있습니다.

실행 및 라이트백 디커플링으로 프로그램 재시작 가능

결과의 큐는 브랜치 오예측이나 예외/트랩 등의 문제를 해결하기 위해 필요합니다.결과 큐를 사용하면 예외 후에 프로그램을 재시작할 수 있습니다. 이 경우 프로그램 순서에 따라 명령을 완료해야 합니다.큐를 사용하면 오래된 분기 명령의 예측 오류와 오래된 명령의 예외로 인해 결과를 폐기할 수 있습니다.

아직 해결되지 않은 분기를 지나 명령을 발행하는 기능을 추측 실행이라고 합니다.

마이크로아키텍처 선택지

  • 명령어는 집중형 큐에 디스패치됩니까, 아니면 여러 분산형 큐에 디스패치됩니까?
IBM PowerPC 프로세서는 서로 다른 기능 유닛에 분산된 큐를 사용하는 반면, 순서가 맞지 않는 다른 프로세서는 중앙 집중식 큐를 사용합니다.IBM은 분산 큐에 예약 스테이션이라는 용어를 사용합니다.
  • 실제 결과 큐가 있습니까?아니면 레지스터 파일에 직접 결과가 기록됩니까?후자의 경우 큐잉 기능은 비행 중인 각 명령의 레지스터 이름 변경 정보를 유지하는 레지스터 맵에 의해 처리된다.
초기 인텔의 비순서 프로세서는 재순서 버퍼라고 불리는 결과 큐를 사용하고, 이후 대부분의 비순서 프로세서는 레지스터 맵을 사용합니다.
보다 정확하게는:인텔 P6 패밀리 마이크로프로세서는 ROB(재순서 버퍼)와 RAT(레지스터 에일리어스 테이블)를 모두 갖추고 있습니다.ROB는 주로 브런치 오판 복구에 의해 동기 부여되었습니다.
인텔 P6 패밀리는 최초의 OoOE 마이크로프로세서 중 하나였지만 NetBurst 아키텍처로 대체되었습니다.수년 후 Netburst는 훨씬 더 높은 작동 주파수의 가능성을 가정한 긴 파이프라인으로 인해 막다른 골목임이 입증되었습니다.재료는 열 문제로 인해 설계의 야심찬 시계 목표치에 맞출 수 없었고, NetBurst에 기반한 이후 Tejas와 Jayhawk는 취소되었습니다.인텔은 코어 및 Nehalem 마이크로아키텍처의 기반으로 P6 설계를 되돌렸습니다.후속 Sandy Bridge, Ivy Bridge 및 Haswell 마이크로아키텍처는 P6에서 사용되는 순서 변경 기술에서 벗어나 EV6 및 P4에서 순서 변경 기술을 채택하고 있지만 [15][16]파이프라인이 다소 짧습니다.

「 」를 참조해 주세요.

Wikibook Microprocessor Design에는 다음 항목에 대한 페이지가 있습니다.고장난 실행

레퍼런스

  1. ^ Kukunas, Jim (2015). Power and Performance: Software Analysis and Optimization. Morgan Kaufman. p. 37. ISBN 9780128008140.
  2. ^ "Out-of-order execution" (PDF). cs.washington.edu. 2006. Retrieved 2014-01-17. don't wait for previous instructions to execute if this instruction does not depend on them
  3. ^ "The Centennial Celebration". Regis High School. 2011-03-14. Retrieved 2022-06-25. The algorithm "allows sequential instructions that would normally be stalled due to certain dependencies to execute non-sequentially" (also known as out of order execution).
  4. ^ "Out-of-order Execution". pcguide.com. Retrieved 2014-01-17. This flexibility improves performance since it allows execution with less 'waiting' time.
  5. ^ Hwu, W.; Patt, Yale N. (1986). HPSm, a high performance restricted data flow architecture having minimal functionality. ISCA '86 Proceedings of the 13th annual international symposium on Computer architecture. ACM. pp. 297–306. ISBN 978-0-8186-0719-6. Retrieved 2013-12-06.
  6. ^ 손턴(1970, 페이지 125)
  7. ^ 손턴(1970년, 페이지 126
  8. ^ 손튼 1970, 127페이지
  9. ^ 손턴 1970, 페이지 112,123
  10. ^ Tomasulo, Robert Marco (1967), "An Efficient Algorithm for Exploiting Multiple Arithmetic Units" (PDF), IBM Journal of Research and Development, 11 (1): 25–33, CiteSeerX 10.1.1.639.7540, doi:10.1147/rd.111.0025, S2CID 8445049, archived from the original (PDF) on 2018-06-12
  11. ^ Anand Lal Shimpi (2013-05-06). "Intel's Silvermont Architecture Revealed: Getting Serious About Mobile". AnandTech.
  12. ^ Smith, J. E. (1984). "Decoupled access/execute computer architectures". ACM Transactions on Computer Systems. 2 (4): 289–308. CiteSeerX 10.1.1.127.4475. doi:10.1145/357401.357403. S2CID 13903321.
  13. ^ Kurian, L.; Hulina, P. T.; Coraor, L. D. (1994). "Memory latency effects in decoupled architectures" (PDF). IEEE Transactions on Computers. 43 (10): 1129–1139. doi:10.1109/12.324539. S2CID 6913858. Archived from the original (PDF) on 2018-06-12.
  14. ^ Dorojevets, M. N.; Oklobdzija, V. (1995). "Multithreaded decoupled architecture". International Journal of High Speed Computing. 7 (3): 465–480. doi:10.1142/S0129053395000257.
  15. ^ Kanter, David (2010-09-25). "Intel's Sandy Bridge Microarchitecture".
  16. ^ "The Haswell Front End - Intel's Haswell Architecture Analyzed: Building a New PC and a New Intel".

추가 정보