토마술로 알고리즘

Tomasulo's algorithm

Tomasulo의 알고리즘은 명령을 동적으로 스케줄링하기 위한 컴퓨터 아키텍처 하드웨어 알고리즘으로, 순서가 맞지 않는 실행을 가능하게 하고 여러 실행 유닛을 보다 효율적으로 사용할 수 있도록 합니다.1967년 IBM의 Robert Tomasulo에 의해 개발되었으며 IBM System/360 Model 91의 부동 소수점 단위로 [1]처음 구현되었습니다.

Tomasulo 알고리즘의 주요 혁신은 하드웨어의 레지스터 이름 변경, 모든 실행 유닛의 예약 스테이션, 계산된 값이 필요한 모든 예약 스테이션에 브로드캐스트되는 공통 데이터 버스(CDB)입니다.이러한 개발을 통해 스코어보드나 기타 이전 알고리즘을 사용하면 중단될 수 있는 명령의 병렬 실행을 개선할 수 있습니다.

Robert Tomasulo는 [2]알고리즘에 대한 그의 업적으로 1997년에 Eckert-Mauchly 상을 받았습니다.

구현 개념

토마술로의 부동소수점 단위

Tomasulo 알고리즘 구현에 필요한 개념은 다음과 같습니다.

공통 데이터 버스

CDB(Common Data Bus)는 예약 스테이션을 기능 장치에 직접 연결합니다.Tomasulo에 따르면 "동시성을 장려하면서 우선순위를 유지한다"[1]: 33 고 한다.여기에는 다음 두 가지 중요한 효과가 있습니다.

  1. 기능 유닛은 부동소수점 레지스터를 사용하지 않고 어떤 조작의 결과에도 액세스 할 수 있기 때문에, 파일 읽기 포토에의 액세스에 대한 경합을 해소하는 것을 기다리지 않고, 결과를 기다리는 복수의 유닛을 속행할 수 있습니다.
  2. 위험 감지 및 제어 실행이 배포됩니다.예약 스테이션은 단일 전용 위험 유닛이 아닌 명령을 실행할 수 있는 시기를 제어합니다.

지시서

명령이 순차적으로 발행되며, 이러한 명령에 의해 발생하는 예외와 같은 일련의 명령의 효과가 순서대로 프로세서에서 발생하는 것과 같은 순서로 발생하도록 되어 있습니다.이러한 명령들이 순서 없이(즉, 비순차적으로) 실행된다는 사실에 관계없이 말입니다.

등록명 변경

Tomasulo의 알고리즘은 레지스터 이름을 변경하여 순서를 벗어난 실행을 올바르게 수행합니다.모든 범용 및 예약 스테이션 레지스터는 실제 값 또는 자리 표시자 값을 보유합니다.발행 스테이지 중에 행선지 레지스터에 실값을 사용할 수 없는 경우는, 최초로 플레이스 홀더 값이 사용됩니다.자리 표시자 값은 실제 값을 생성하는 예약 스테이션을 나타내는 태그입니다.장치가 완료되고 CDB에서 결과를 브로드캐스트하면 자리 표시자가 실제 값으로 바뀝니다.

각 기능 유닛에는 1개의 예약 스테이션이 있습니다.예약 스테이션은 조작과 오퍼랜드를 포함한 단일 명령 실행에 필요한 정보를 보유하고 있습니다.기능 유닛은 명령어에 필요한 모든 소스 오퍼랜드가 실제일 때 처리를 시작합니다.

예외

실질적으로 예외에 대한 충분한 상태 정보를 이용할 수 없는 예외가 있을 수 있습니다.이 경우 프로세서는 '불확정' 예외라고 불리는 특별한 예외를 발생시킬 수 있습니다.프로세서 상태는 프로그램 순서로만 변경되므로 순서대로 구현하면 부정확한 예외가 발생할 수 없습니다(RISC 파이프라인 예외 참조).

"정확한" 예외가 발생한 프로그램은 예외를 수행한 특정 명령을 확인할 수 있으며 예외 지점에서 다시 시작하거나 다시 실행할 수 있습니다.다만, 「불확실한」예외가 발생하고 있는 경우는, 통상, 재기동이나 재실행은 할 수 없습니다.이것은, 시스템이 예외를 취한 특정의 순서를 판별할 수 없기 때문입니다.

명령 라이프 사이클

다음 3가지 단계는 각 명령이 발행된 시점부터 실행이 완료될 때까지 진행되는 단계입니다.

범례 등록

  • Op - 오퍼랜드에서 수행 중인 작업을 나타냅니다.
  • Qj, Qk - 관련 소스 오퍼랜드를 생성하는 예약 스테이션(0은 값이 Vj, Vk임을 나타냅니다)
  • Vj, Vk - 소스 오퍼랜드의 값
  • A - 로드 또는 저장소의 메모리 주소 정보를 유지하는 데 사용됩니다.
  • 통화 중 - 사용 중인 경우 1, 사용 중인 경우 0
  • Qi - (레지스터 유닛만) 이 레지스터에 결과를 저장해야 하는 예약 스테이션입니다(공백 또는 0인 경우 이 레지스터를 대상으로 하는 값은 없습니다).

스테이지 1: 문제

발행 단계에서는 모든 오퍼랜드와 예약 스테이션이 준비되거나 정지된 경우 실행 명령이 발행됩니다.이 단계에서 레지스터의 이름을 변경하여 WAR 및 WAW 위험을 제거합니다.

  • 명령 큐의 선두에서 다음 명령을 가져옵니다.명령 오퍼랜드가 현재 레지스터에 있는 경우,
    • 일치하는 기능 유닛을 사용할 수 있는 경우 지침을 발행합니다.
    • 그 이외의 경우는, 사용 가능한 기능 유닛이 없기 때문에, 스테이션 또는 버퍼가 빈 상태가 될 때까지 명령을 정지합니다.
  • 그렇지 않으면 오퍼랜드가 레지스터에 없다고 가정하고 가상값을 사용할 수 있습니다.피연산자를 생성하는 기능 단위를 추적하려면 기능 단위가 실제 값을 계산해야 합니다.
유사[3]: 180 코드
명령 상태 까지 기다리다 행동 또는 부기
쟁점. 역.r 비었다 
한다면 (Register Stat(등록 상태)[rs].기¦0) {  RS[r].QJ ← Register Stat(등록 상태)[rs].기 } 또 다른 {  RS[r].VJ ← 레지스[rs];  RS[r].QJ ← 0; } 한다면 (Register Stat(등록 상태)[rt].기¦0) {   RS[r].큐 ← Register Stat(등록 상태)[rt].기; } 또 다른 {  RS[r].Vk ← 레지스[rt];   RS[r].큐 ← 0; } RS[r].바빠 ← 네.; Register Stat(등록 상태)[rd].기 ← r;
로드 또는 저장 버퍼 r이 비어 있습니다. 
한다면 (Register Stat(등록 상태)[rs].기¦0) {  RS[r].QJ ← Register Stat(등록 상태)[rs].기; } 또 다른 {  RS[r].VJ ← 레지스[rs];  RS[r].QJ ← 0; } RS[r].A ← imm; RS[r].바빠 ← 네.;
로드만 
Register Stat(등록 상태)[rt].기 ← r;
스토어만 
한다면 (Register Stat(등록 상태)[rt].기¦0) {  RS[r].큐 ← Register Stat(등록 상태)[rt].기; } 또 다른 {  RS[r].Vk ← 레지스[rt];  RS[r].큐 ← 0 };
토마술로 알고리즘의[4] 예

스테이지 2: 실행

실행 단계에서는 명령 조작을 실행한다.모든 피연산자를 사용할 수 있을 때까지 이 단계에서 명령이 지연되어 RAW 위험을 제거합니다.메모리를 통한 위험을 방지하기 위해 효과적인 주소 계산을 통해 프로그램 정확성을 유지합니다.

  • 피연산자 중 하나 이상을 아직 사용할 수 없는 경우: CDB에서 피연산자를 사용할 수 있을 때까지 기다립니다.
  • 모든 오퍼랜드를 사용할 수 있는 경우 명령어가 로드 또는 스토어인 경우
    • 베이스 레지스터를 사용할 수 있을 때 유효한 주소를 계산하여 로드/스토어 버퍼에 배치합니다.
      • 명령이 로드인 경우: 메모리 장치를 사용할 수 있는 즉시 실행
      • 또는 명령이 스토어인 경우: 값이 저장될 때까지 기다린 후 메모리 장치로 전송합니다.
  • 그렇지 않으면 명령은 산술 로직 유닛(ALU) 연산입니다. 그러면 해당 기능 유닛에서 명령을 실행합니다.
유사[3] 코드
명령 상태 까지 기다리다 행동 또는 부기
FP 동작 
(RS[r]Qj = 0) 및 (RS[r]).Qk = 0)

계산 결과: 오퍼랜드는 Vj 및 Vk입니다.

1단계 로드/저장 RS[r].Qj = 0& r은 로드 스토어 큐의 선두입니다. 
RS[r].A ← RS[r].VJ + RS [r]A;
순서 2의 로드 1단계 로드 완료

에서 읽다Mem[RS[r].A]

스테이지 3: 쓰기 결과

쓰기 결과 단계에서는 ALU 연산 결과를 레지스터에 다시 쓰고 저장 연산 결과를 메모리에 다시 쓴다.

  • 명령이 ALU 작업인 경우
    • 결과를 이용할 수 있는 경우 CDB에 기입하여 레지스터 및 이 결과를 기다리는 예약 스테이션에 기입합니다.
  • 또는 명령이 스토어인 경우: 이 단계에서 데이터를 메모리에 씁니다.
유사[3] 코드
명령 상태 까지 기다리다 행동 또는 부기
FP 동작 또는 부하 R&CDB 이용가능시 실행완료 
 ∀x(한다면 (Register Stat(등록 상태)[x].기 = r) {   레깅스[x] ← 결과;   Register Stat(등록 상태)[x].기 = 0  });  ∀x(한다면 (RS[x].QJ = r) {   RS[x].VJ ← 결과;   RS[x].QJ ← 0;   });  ∀x(한다면 (RS[x].큐 = r) {   RS[x].Vk ← 결과;   RS[x].큐 ← 0;  });  RS[r].바빠 ← 아니요.;
가게 r&RS에 실행 완료[r]Qk = 0 
 메모리[RS[r].A] ← RS[r].Vk;  RS[r].바빠 ← 아니요.;

알고리즘의 개량

Tomasulo 알고리즘의 예약 스테이션, 레지스터 이름 변경, 공통 데이터 버스 개념은 고성능 컴퓨터 설계에 큰 발전을 가져옵니다.

예약 스테이션은 데이터 의존성 및 다양한 스토리지 액세스 시간 및 회선 속도 등 기타 불일치가 있는 경우 피연산자를 기다리는 역할을 담당하므로 기능 유닛이 해방됩니다.이 개선으로 장시간의 부동소수점 지연과 메모리 액세스를 극복할 수 있습니다.특히 이 알고리즘은 캐시 누락에 대해 보다 내성이 있습니다.또한 프로그래머는 최적화된 코드를 구현할 필요가 없습니다.이는 공통 데이터 버스와 예약 스테이션이 함께 작동하여 의존성을 유지하고 [1]: 33 동시성을 장려한 결과입니다.

이 알고리즘은 예약 스테이션에서 명령 오퍼랜드를 추적하고 하드웨어에서 레지스터 이름을 변경함으로써 쓰기 후(RAW)를 최소화하고 쓰기 후(WW) 및 읽기 후(WAR) 컴퓨터 아키텍처의 위험을 제거합니다.이를 통해 [1]: 33 스톨에 필요한 시간 낭비를 줄임으로써 성능이 향상됩니다.

알고리즘의 마찬가지로 중요한 개선점은 설계가 특정 파이프라인 구조에만 국한되지 않는다는 것입니다.이것에 의해, 알고리즘이 복수 이슈 프로세서에 보다 폭넓게 채용될 수 있게 되었습니다.또, 분기 추측을 [3]가능하게 하기 위해서, 알고리즘을 용이하게 확장할 수 있다.: 182

응용 프로그램 및 레거시

IBM 외부에서 Tomasulo의 알고리즘은 System/360 Model 91 아키텍처에서 구현된 후 몇 년 동안 사용되지 않았습니다.그러나 1990년대 동안 다음과 같은 세 가지 이유로 사용량이 크게 증가했습니다.

  1. 캐시가 보편화되자 캐시 누락으로 인한 예측 불가능한 로드 시간 동안 동시성을 유지하는 Tomasulo 알고리즘의 기능은 프로세서에서 유용하게 쓰이게 되었습니다.
  2. 동적 스케줄링과 알고리즘에 의한 브랜치 추측은 프로세서의 명령어 발행이 증가함에 따라 퍼포먼스에 도움이 되었습니다.
  3. 대량 시장 소프트웨어의 확산은 프로그래머들이 특정 파이프라인 구조를 위해 컴파일을 원하지 않는다는 것을 의미했다.이 알고리즘은 어떤 파이프라인 아키텍처에서도 기능할 수 있기 때문에 소프트웨어는 아키텍처 고유의 [3]수정이 거의 필요하지 않습니다.: 183

많은 최신 프로세서는 일반적인 인텔 x86-64 [5][failed verification][6]칩을 포함하여 Tomasulo의 원래 알고리즘에서 파생된 동적 스케줄링 스킴을 구현합니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b c d Tomasulo, Robert Marco (Jan 1967). "An Efficient Algorithm for Exploiting Multiple Arithmetic Units". IBM Journal of Research and Development. IBM. 11 (1): 25–33. doi:10.1147/rd.111.0025. ISSN 0018-8646. S2CID 8445049.
  2. ^ "Robert Tomasulo – Award Winner". ACM Awards. ACM. Retrieved 8 December 2014.
  3. ^ a b c d e Hennessy, John L.; Patterson, David A. (2012). Computer Architecture: A Quantitative Approach. Waltham, MA: Elsevier. ISBN 978-0123838728.
  4. ^ "CSE P548 - Tomasulo" (PDF). washington.edu. Washington University. 2006. Retrieved 8 December 2014.
  5. ^ Intel 64 and IA-32 Architectures Software Developer's Manual (Report). Intel. September 2014. Retrieved 8 December 2014.
  6. ^ Yoga, Adarsh. "Differences between Tomasulo's algorithm and dynamic scheduling in Intel Core microarchitecture". The boozier. Retrieved 4 April 2016.

추가 정보

외부 링크