스코어보드

Scoreboarding

스코어보딩은 CDC 6600 컴퓨터에서 처음 사용되는 중앙 집중식 방법입니다.이 방법은 명령어를 동적으로 스케줄링하기 위해 경합이 발생하지 않고 하드웨어를 사용할 [1]수 있을 때 명령을 순서대로 실행할 수 있도록 합니다.

스코어보드에서는 모든 명령의 데이터 의존성이 항상 기록, 추적 및 엄수됩니다.지시는 스코어보드가 이전에 발행된("비행 중") 지침과 충돌하지 않는다고 판단했을 경우에만 공개됩니다.명령이 발행하는 것이 안전하지 않거나 리소스가 부족하여 정지된 경우, 스코어보드는 정지된 명령이 발행되기 전에 모든 의존 관계가 해결될 때까지 명령 실행 흐름을 모니터링합니다.본질적으로: 읽기 작업은 쓰기 위험이 없는 경우 진행되며 쓰기 작업은 읽기 위험이 없는 경우 진행됩니다.

스코어보딩은 기본적으로 데이터플로우 언어에서 볼 수 있는 동일한 기본 알고리즘의 하드웨어 구현으로, 프로그래밍 언어 런타임에 동일한 논리가 적용되는 Directed Acyclic Graph를 만듭니다.

스테이지

명령은 순서대로 디코딩되며 다음 4단계를 거칩니다.

  1. 문제: 시스템은 이 지침에 따라 읽고 쓸 레지스터와 WAR, RAW 및 WAW 경합이 감지되는 위치를 확인합니다.RAW 및 WAR 위험은 다음 단계에서 필요하므로 의존성 매트릭스(원래 6600 설계에서 SR NOR 래치로 구성)를 사용하여 기록한다.동시에 엔트리가 두 번째 매트릭스에 기록되고 명령 순서는 지시 비순환 그래프로 기록된다.출력 의존성을 피하기 위해(WAW – Write after Write) 동일한 레지스터에 쓰려는 명령이 완료될 때까지 명령이 정지됩니다.필요한 기능 유닛이 현재 사용 중일 때도 명령은 정지됩니다.*처음부터 끝까지 100% 추적 가능한 경우를 제외하고 지시사항은 발행되지 않습니다*
  2. 읽기 피연산자: 명령이 발행되어 필요한 하드웨어 모듈(손턴의 책에서 계산 유닛이라고 함)에 올바르게 할당된 후 유닛은 모든 피연산자를 사용할 수 있을 때까지 기다립니다.다른 모든 장치에서 쓰기 종속성(RAW – 쓰기 후 읽기)이 삭제된 경우에만 읽기가 진행됩니다.Register File Port 경합을 피하기 위해 Priority Picker는 하나의 Computational Unit(계산 유닛)을 선택합니다(여러 유닛에 위험이 없는 경우).
  3. 실행:모든 오퍼랜드를 가져오면 계산 유닛이 실행을 시작합니다.결과가 준비되면 스코어보드에 알립니다.
  4. 결과 쓰기:이 단계에서는 결과가 준비되었지만 아직 대상 레지스터에 기록되지 않았습니다.장치에 모든 위험(WAR – 읽기 후 쓰기)이 없을 때까지 쓰기가 진행되지 않을 수 있습니다.여기서 추가 지연은 레지스터 파일 포트의 가용성에 따른 것뿐입니다.6600에서는 priority 피커를 사용하여 쓰기 포트당 하나의 결과를 선택했습니다.기입이 완료되면, 유닛은 비지 상태가 되어, 모든 위험과 상태가 폐기됩니다."섀도" 기능이 있는 고급(확장, 정밀) 스코어보드에서만 결과 쓰기 단계가 방지(지연)됩니다.원래 6600에는 이 기능이 없었습니다.

읽기 작업은 쓰기 위험이 없는 경우에만 진행되며, 쓰기 작업은 읽기 위험이 없는 경우에만 진행된다는 점에 유의하십시오.이것은 논리적이지만 기대에 어긋난다.특히, 다른 장치에 레지스터의 현재 값을 읽을 수 있는 기회를 주기 위해 새 값으로 덮어쓰기 전에 읽기를 기다려야 합니다.따라서 WaR 위험이 없을 때까지 쓰기가 대기해야 합니다.

data 구조

명령 실행을 제어하기 위해 스코어보드는 다음 세 가지 상태 테이블을 유지합니다.

  • 순서 상태:실행 중인 각 명령에 대해 4가지 단계 중 어느 단계에 있는지 나타냅니다.
  • 기능 유닛 상태:각 기능 유닛의 상태를 나타냅니다.각 기능 유닛은 테이블의 9개의 필드를 유지합니다.
    • 통화 중: 장치가 사용 중인지 여부를 나타냅니다.
    • Op: 유닛에서 수행하는 작업(MUL, DIV 또는 MOD 등)
    • Fi: 수신처 레지스터
    • Fj,Fk: 소스 레지스터 번호
    • Qj,Qk: 소스 레지스터j F, F를k 생성하는 기능 유닛
    • Rj,Rk: F, F가k 준비가j 되어 있고 아직 읽히지 않은 것을 나타내는 플래그.
  • 등록 상태:각 레지스터에 대해 결과를 기록할 함수 단위를 나타냅니다.

원래의 6600 알고리즘

스코어보드 제어의 상세한 알고리즘은, 원래의 특허에 기재되어 있습니다.

함수 문제(op, dst, src1, src2)가 발생할 때까지 기다립니다(!Busy [ FU ]AND ! Result [ dst ] ; // FU 는, op Busy [ 를 실행할 수 있는 기능 유닛이 될 수 있습니다.FU] ← 예; Op[FU] ← Op; Fi[FU] ← dst; Fj[FU] ← src1; Fk[FU] ← src2; Qj[FU] ← 결과[src1]; Qkj[FU] ← 결과j[src2]
함수 read_operands(FU)는 (Rj[FU] ANDk R[FU]), Rj[FU] ← No, Rk[FU] ← No;
function execute(FU) // FU가 해야 할 모든 작업을 실행합니다.
write_back(FU) 함수 wait to ('fj {(F[f])' Fi[)FU] 또는j R[f]=No) 및 (Fk[f] fi F[FU] ORk R[f]=No)}: Q[f]←FU이면jj FDo를 예측하고 R[f]←Yeskk, Q[f]←FU이면 R[f]←Yes; Result [Fi]FU] ← 0; // 0은 레지스터의 결과 RegFile[Fi]를 생성하지 않음을 의미합니다.FU]] ← 계산값; 통화중[FU] ← 아니요;

언급

Thornton의 책은 현대 컴퓨팅 용어보다 앞선다.

  • 함수 단위(파이프라인)는 "계산 단위"라고 불렸습니다.
  • First Order Conflict(첫 번째 주문 충돌)[2]은 모든 유닛이 사용 중이기 때문에 양쪽 스톨을 커버하고 WAW 충돌도 커버했습니다.
  • "Second Order Conflict"는 RAW [3]충돌에 사용된 용어입니다.
  • "제3의 질서 충돌"은 전쟁 문제를 [4]다루었다.

"First Order" 충돌이 감지된 문제 단계에서만 시간 지연이 발생했습니다.Tomasulo 알고리즘과 같은 다른 기법에서는 레지스터 이름을 변경하여 WAW 의존성을 추가로 해결합니다.원래의 CDC 6600은 설계자가 제품을 납품해야 한다는 이유만으로 WAW 위험 추적을 하지 않았을 가능성이 높으며, 그 후 7600으로 넘어갔습니다.대신 시간을 끄는 것이 가장 편리한 옵션이었습니다.등록 이름을 스코어보드에 추가할 수 없는 기술적 이유는 없습니다.

두 알고리즘의 분석은 Luke Leighton에 의해 수행되었고 Tomasulo 알고리즘과 6600 Scoreboard [5]알고리즘 사이의 동등성을 보여주는 변환 프로세스가 간략히 설명되었다.WAW의 위험 해결은 원래 알고리즘에서 누락되어 있습니다.6600은 [6]쓰기 위험이 처음 발생했을 때 정지합니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Thornton, James E. (1965). "Parallel operation in the control data 6600". Proceedings of the October 27–29, 1964, fall joint computer conference, part II: very high speed computer systems. AFIPS '64. San Francisco, California: ACM. pp. 33–40. doi:10.1145/1464039.1464045.
  2. ^ 손턴(1970, 페이지 125)
  3. ^ 손턴(1970년, 페이지 126
  4. ^ 손튼 1970, 127페이지
  5. ^ Tomasulo를 스코어보드로 변환
  6. ^ Thornton, James (1970). Design of a Computer: The Control Data 6600 (PDF). p. 126. ISBN 9780673059536.
  • Glenford Myers, "마이크로프로세서 칩에 스코어보드 등록", 미국 특허 4891753

외부 링크