토마술로 알고리즘

2. 구현 개념

토마술로 알고리즘을 구현하려면 다음과 같은 개념이 필요하다.

• 명령어 순서(Instruction Order): 명령어는 순서대로 발행되지만, 실행은 순서대로 이루어지지 않는다. 명령어 시퀀스에 의해 발생된 예외와 같은 효과는 비순차적(아웃 오브 오더) 실행에도 불구하고 인오더 프로세서에서와 동일한 순서로 발생한다.^[1]

• 레지스터 이름 변경(Register Renaming): 레지스터 이름 변경을 사용하여 비순차적 실행을 올바르게 수행한다. 모든 범용 레지스터와 예약 스테이션 레지스터는 실제 값 또는 자리 표시자 값을 가진다. 발행 단계에서 대상 레지스터에 실제 값을 사용할 수 없는 경우, 초기에는 자리 표시자 값이 사용된다. 자리 표시자 값은 실제 값을 생성할 예약 스테이션을 나타내는 태그이다. 장치가 완료되어 공통 데이터 버스(CDB)에서 결과를 브로드캐스트하면 자리 표시자는 실제 값으로 바뀐다. 기능 유닛은 여러 슬롯으로 구성된 예약 스테이션을 사용하며, 각 슬롯은 연산 종류, 연산 대상 데이터 등 하나의 명령을 실행하는 데 필요한 정보를 보관한다. 기능 유닛은 명령어에 필요한 입력 데이터가 모두 "실제 값"이 되면 실행을 시작한다.

• 예외(Exceptions): 명령어는 순차적으로 발행되므로, 명령어 시퀀스의 효과는 마치 순차적으로 실행되는 것처럼 보여야 한다. 예를 들어, 명령어에 의해 발생된 예외는 비순차적으로 실행되고 있다는 사실과 관계없이, 순차적 프로세서에서와 동일한 순서로 발생해야 한다.^[1]
• 정확 예외: 예외가 발생한 특정 명령을 결정할 수 있어 프로그램이 예외 지점에서 다시 시작하거나 재실행할 수 있다.^[1]
• 불정확 예외: 예외가 발생한 특정 명령을 결정할 수 없어 프로그램이 일반적으로 다시 시작하거나 재실행할 수 없다.^[1]

2. 1. 공통 데이터 버스 (Common Data Bus, CDB)

• 피연산자 데이터 중 사용할 수 없는 것이 있는 경우
• 공통 데이터 버스(CDB)를 감시하여, 계산이 완료될 때까지 대기한다.
• 피연산자 데이터가 사용 가능해지면, 해당 예약 스테이션에 이 데이터를 배치한다.
• 피연산자 데이터가 모두 사용 가능해지면
• 명령이 로드 또는 스토어인 경우
• 베이스 주소가 사용 가능하면, 유효 주소를 계산한다.
• 유효 주소를 로드 또는 스토어 버퍼에 저장한다.
• 명령이 로드인 경우
• 메모리 유닛이 사용 가능해지는 즉시, 명령을 실행한다.
• 명령이 스토어인 경우
• 메모리 유닛에 보내기 전에, 값이 저장될 때까지 대기한다.
• 그 외의 경우에는, 산술 논리 연산 장치(ALU) 연산
• 해당 기능 유닛에서 명령을 실행한다.

• 명령이 ALU 연산인 경우
• 결과가 사용 가능해지면
• CDB에 쓰고, CDB로부터 결과를 기다리는 레지스터나 예약 스테이션에 쓴다.
• 저장인 경우
• 이 단계에서 데이터를 메모리에 쓴다.

2. 2. 명령어 순서 (Instruction Order)

2. 3. 레지스터 이름 변경 (Register Renaming)

• 명령어는 순서대로 발행되지만, 실행은 순서대로 이루어지지 않는다. 명령어 시퀀스가 미치는 결과(예외 발생 등)는 파이프라인화되지 않은 프로세서와 동일해야 한다.
• 모든 범용 레지스터 및 예약 스테이션 레지스터는 "실제 값" 또는 "가상 값"을 저장한다. 명령어 발행 과정에서 연산 결과를 출력하는 레지스터를 사용할 수 없는 경우, 처음에는 가상 값이 사용된다. 실제 값을 계산하는 기능 유닛은 가상 값으로 할당되며, 기능 유닛이 연산을 완료하면 가상 레지스터의 값이 실제 값으로 변환된다.
• 기능 유닛은 예약 스테이션을 여러 슬롯에서 사용한다. 각 슬롯은 연산 종류, 연산 대상 데이터 등 하나의 명령을 실행하는 데 필요한 정보를 보관한다. 기능 유닛은 명령어에 필요한 입력 데이터가 모두 "실제 값"이 되면 실행을 시작한다.

• 명령 큐의 맨 앞에서 다음 명령을 가져온다.
• 명령으로 처리할 데이터가 레지스터에 있는 경우
• 사용하지 않는 예약 스테이션이 있으면 (즉, 기능 유닛을 사용할 수 있는 경우) 명령을 발행한다.
• 사용하지 않는 예약 스테이션이 없으면 (즉, 기능 유닛을 사용할 수 없는 경우) 예약 스테이션이나 버퍼가 준비될 때까지 명령의 실행을 중지한다.
• 명령으로 처리할 데이터가 레지스터에 없는 경우 가상 값을 사용하여 결과를 계산하는 기능 유닛의 상태를 추적한다.

2. 4. 예약 스테이션 (Reservation Station)

• 명령어는 순서대로 발행되지만, 실행은 순서대로 이루어지지 않는다. 이는 파이프라인화되지 않은 프로세서와 동일한 결과를 보장하기 위함이다.
• 범용 레지스터 및 예약 스테이션 레지스터는 "실제 값" 또는 "가상 값"을 저장한다.
• 가상 값: 명령어 발행 시점에 연산 결과를 출력하는 레지스터를 사용할 수 없을 때 사용된다.
• 실제 값: 기능 유닛이 연산을 완료하면 가상 레지스터의 값은 실제 값으로 변환된다.
• 기능 유닛은 여러 슬롯으로 구성된 예약 스테이션을 사용한다.
• 각 슬롯은 연산 종류, 연산 대상 데이터 등 하나의 명령을 실행하는 데 필요한 정보를 보관한다.
• 기능 유닛은 명령어에 필요한 입력 데이터가 모두 "실제 값"이 되면 실행을 시작한다.
• 발행 단계에서 모든 데이터와 예약 스테이션이 준비되면 명령이 실행되고, 그렇지 않으면 일시 정지된다.
• 이 시점에서 레지스터 이름이 변경되어 WAR 및 WAW 해저드를 방지한다.

• 명령으로 처리할 데이터가 레지스터에 있는 경우:
• 사용 가능한 예약 스테이션이 있으면 명령을 발행한다.
• 사용 가능한 예약 스테이션이 없으면 예약 스테이션이나 버퍼가 준비될 때까지 명령 실행을 중지한다.
• 명령으로 처리할 데이터가 레지스터에 없는 경우: 가상 값을 사용하여 결과를 계산하는 기능 유닛의 상태를 추적한다.

• 로드 또는 스토어 명령어:
• 베이스 주소가 사용 가능하면 유효 주소를 계산한다.
• 유효 주소를 로드 또는 스토어 버퍼에 저장한다.
• 로드 명령어는 메모리 유닛이 사용 가능해지는 즉시 실행한다.
• 스토어 명령어는 메모리 유닛에 보내기 전에 값이 저장될 때까지 대기한다.
• 그 외의 명령어: 해당 기능 유닛에서 산술 논리 연산 장치(ALU) 연산을 실행한다.

2. 5. 예외 (Exceptions)

3. 명령어 생명주기

토마술로 알고리즘에서 각 명령어는 발행된 시점부터 실행이 완료될 때까지 다음 세 단계를 거친다.^[3]

• 단계 1: 발행 (Issue)
• 단계 2: 실행 (Execute)
• 단계 3: 결과 쓰기 (Write Result)

3. 1. 단계 1: 발행 (Issue)

명령어 발행 단계에서는 모든 피연산자와 예약 스테이션이 준비되면 실행을 위해 명령이 발행되고, 그렇지 않으면 지연된다. 이 단계에서 레지스터 이름이 변경되어 WAR 및 WAW 해저드가 제거된다.^[3]

• 명령 큐의 맨 앞에서 다음 명령을 가져온다. 명령 피연산자가 현재 레지스터에 있으면
• 일치하는 기능 유닛을 사용할 수 있는 경우 명령을 발행한다.
• 그렇지 않으면, 사용 가능한 기능 유닛이 없으므로 스테이션이나 버퍼가 비어 있을 때까지 명령을 지연시킨다.
• 그렇지 않으면 피연산자가 레지스터에 없는 것으로 간주하고 가상 값을 사용한다. 기능 유닛은 피연산자를 생성하는 기능 유닛을 추적하기 위해 실제 값을 계산해야 한다.

의사 코드^[3]

명령 상태	대기	작업 또는 부기
FP 연산	스테이션 r영어 비어 있음
로드 또는 저장	버퍼 r영어 비어 있음
로드 전용
저장 전용

• 발행 단계에서는 모든 데이터와 예약 스테이션의 준비가 완료되면 명령이 실행되고, 그렇지 않으면 일시 정지된다.
• 레지스터의 이름은 이 시점에서 변경되어 WAR 및 WAW에 의한 해저드를 발생시키지 않도록 한다.
• 명령 큐의 맨 앞에서 다음 명령을 가져온다.
• 명령으로 처리할 데이터가 레지스터에 있는 경우
• 사용하지 않는 예약 스테이션이 있는 경우 (즉, 기능 유닛을 사용할 수 있는 경우) 명령을 발행한다.
• 사용하지 않는 예약 스테이션이 없는 경우 (즉, 기능 유닛을 사용할 수 없는 경우) 예약 스테이션이나 버퍼가 준비될 때까지 명령의 실행을 중지한다.
• 명령으로 처리할 데이터가 레지스터에 없는 경우 가상 값을 사용하여 결과를 계산하는 기능 유닛의 상태를 추적한다.

3. 2. 단계 2: 실행 (Execute)

실행 단계에서는 명령어 연산이 실제로 수행된다. 명령어는 필요한 모든 피연산자가 사용 가능해질 때까지 기다리며, 이는 RAW (Read After Write) 위험을 방지한다. 메모리를 통한 위험을 막기 위해 유효 주소를 계산하여 프로그램의 정확성을 유지한다.

• 하나 이상의 피연산자가 아직 사용 가능하지 않은 경우: 공통 데이터 버스(CDB)에서 피연산자가 사용 가능해질 때까지 기다린다.
• 모든 피연산자가 사용 가능하게 되면:
• 명령어가 로드 또는 저장인 경우:
• 기본 레지스터가 사용 가능할 때 유효 주소를 계산하고 로드/저장 버퍼에 배치한다.
• 명령어가 로드인 경우: 메모리 장치가 사용 가능해지는 즉시 실행한다.
• 명령어가 저장인 경우: 메모리 장치로 보내기 전에 저장할 값을 기다린다.
• 명령어가 산술 논리 장치(ALU) 연산인 경우: 해당 기능 장치에서 명령어를 실행한다.

의사 코드^[3]

명령어 상태	대기 조건	작업 또는 부기
부동 소수점 연산	(RS[r].Qj = 0) and (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. 3. 단계 3: 결과 쓰기 (Write Result)

결과 쓰기 단계에서 산술 논리 연산 장치(ALU) 연산의 결과는 레지스터에 다시 기록되고 저장 연산은 메모리에 다시 기록된다.

• 명령어가 ALU 연산인 경우
• 결과를 사용할 수 있는 경우: CDB(공통 데이터 버스)에 결과를 쓰고, 여기서 레지스터와 이 결과를 기다리는 모든 예약 스테이션에 쓴다.
• 명령어가 저장 명령어인 경우: 이 단계에서 데이터를 메모리에 쓴다.

의사 코드

명령어 상태	대기	작업 또는 기록
부동 소수점 연산 또는 로드	실행 완료 및 CDB 사용 가능
저장	실행 완료