명령어 스케줄링

컴퓨터 과학에서 **명령어 스케줄링**(Instruction scheduling)은 명령어 수준 병렬성을 향상시키기 위해 사용되는 컴파일러 최적화 기법으로, 명령어 파이프라인을 사용하는 시스템의 성능을 향상시킨다. 간단히 말해서, 코드의 의미를 변경하지 않으면서 다음을 수행하려고 한다.

* 명령어 순서를 재배열하여 파이프라인 지연을 방지한다.
* 불법적이거나 의미상 모호한 작업(일반적으로 미묘한 명령어 파이프라인 타이밍 문제 또는 비연동 리소스와 관련됨)을 피한다.

파이프라인 지연은 구조적 위험(프로세서 리소스 제한), 데이터 위험(한 명령어의 출력이 다른 명령어에 의해 필요함), 제어 위험(분기)으로 인해 발생할 수 있다.

## 데이터 위험
명령어 스케줄링은 일반적으로 단일 기본 블록에서 수행된다. 블록의 명령어를 특정 방식으로 재배열하는 것이 해당 블록의 동작을 보존하는지 확인하기 위해 데이터 종속성 개념이 필요하다. 세 가지 유형의 종속성이 있으며, 이는 세 가지 데이터 위험이기도 하다.
# 쓰기 후 읽기(RAW 또는 "True"): 명령어 1이 명령어 2가 나중에 사용할 값을 쓴다. 명령어 1이 먼저 와야 하며, 그렇지 않으면 명령어 2가 새 값 대신 이전 값을 읽게 된다.
# 읽기 후 쓰기(WAR 또는 "Anti"): 명령어 1이 명령어 2에 의해 나중에 덮어씌워질 위치를 읽는다. 명령어 1이 먼저 와야 하며, 그렇지 않으면 새 값 대신 이전 값을 읽게 된다.
# 쓰기 후 쓰기(WAW 또는 "Output"): 두 명령어가 모두 동일한 위치에 쓴다. 이들은 원래 순서대로 발생해야 한다.

기술적으로 네 번째 유형인 읽기 후 읽기(RAR 또는 "Input")도 있다. 두 명령어 모두 동일한 위치를 읽는다. 입력 종속성은 두 명령문의 실행 순서를 제한하지 않지만, 배열 요소의 스칼라 교체에 유용하다.

세 가지 유형의 종속성을 존중하도록 하기 위해 종속성 그래프를 구성한다. 종속성 그래프는 각 정점이 명령어이고, I1이 종속성으로 인해 I2보다 먼저 와야 한다면 I1에서 I2로 가는 간선이 있는 유향 그래프이다. 루프 전달 종속성을 제외하면 종속성 그래프는 유향 비순환 그래프이다. 그러면 이 그래프의 모든 위상 정렬이 유효한 명령어 스케줄이 된다. 그래프의 간선은 일반적으로 종속성의 지연 시간으로 레이블이 지정된다. 이는 파이프라인이 지연 없이 대상 명령어를 진행하기 전에 경과해야 하는 클럭 사이클 수이다.

## 알고리즘

위상 정렬을 찾는 가장 간단한 알고리즘은 자주 사용되며 리스트 스케줄링으로 알려져 있다. 개념적으로, 이 알고리즘은 종속성 그래프의 소스를 반복적으로 선택하여 현재 명령어 스케줄에 추가하고 그래프에서 제거한다. 이로 인해 다른 정점이 소스가 될 수 있으며, 이들도 스케줄링을 위해 고려된다. 그래프가 비어 있으면 알고리즘이 종료된다.

좋은 스케줄을 만들기 위해서는 지연을 방지해야 한다. 이는 스케줄링될 다음 명령어의 선택에 따라 결정된다. 일반적으로 다음과 같은 휴리스틱이 사용된다.

* 이미 스케줄링된 명령어가 사용하는 프로세서 리소스가 기록된다. 후보가 점유된 리소스를 사용하면 우선순위가 떨어진다.
* 후보가 관련 지연 시간보다 선행 명령어에 더 가깝게 스케줄링되면 우선순위가 떨어진다.
* 후보가 그래프의 임계 경로에 있으면 우선순위가 올라간다. 이 휴리스틱은 그렇지 않은 경우 국부적인 결정 과정에서 일종의 선행 조회를 제공한다.
* 후보를 선택하면 많은 새로운 소스가 생성되면 우선순위가 올라간다. 이 휴리스틱은 스케줄러에게 더 많은 자유를 생성하는 경향이 있다.

## 위상 순서
명령어 스케줄링은 레지스터 할당 전 또는 후에, 또는 전후 모두 수행될 수 있다. 레지스터 할당 전에 수행하는 장점은 최대 병렬성을 얻을 수 있다는 것이다. 레지스터 할당 전에 수행하는 단점은 레지스터 할당자가 사용 가능한 레지스터 수를 초과하는 레지스터를 사용해야 할 수 있다는 것이다. 이로 인해 스필/필 코드가 도입되어 해당 코드 섹션의 성능이 저하된다.

스케줄링되는 아키텍처에 잠재적으로 불법적인 조합(명령어 연동 부족으로 인해)을 가진 명령어 시퀀스가 있는 경우, 명령어는 레지스터 할당 후에 스케줄링되어야 한다. 이 두 번째 스케줄링 패스는 스필/필 코드의 배치도 개선한다.

스케줄링이 레지스터 할당 후에만 수행되면, 레지스터 할당으로 인해 스케줄러가 가능한 명령어 이동량을 제한하는 잘못된 종속성이 도입될 것이다.

## 유형
명령어 스케줄링에는 여러 유형이 있다.
# 로컬(기본 블록) 스케줄링: 명령어는 기본 블록 경계를 넘을 수 없다.
# 전역 스케줄링: 명령어는 기본 블록 경계를 넘을 수 있다.
# 모듈러 스케줄링: 내부 루프의 다른 반복을 인터리빙하여 명령어 수준 병렬성을 높이는 방법인 소프트웨어 파이프라이닝을 생성하는 알고리즘.
# 트레이스 스케줄링: 전역 스케줄링을 위한 최초의 실용적인 접근 방식으로, 트레이스 스케줄링은 가장 자주 실행되는 제어 흐름 경로를 최적화하려고 한다.
# 슈퍼블록 스케줄링: 트레이스 "측면 진입점"에서 제어 흐름 경로를 병합하려고 시도하지 않는 트레이스 스케줄링의 단순화된 형태이다. 대신 코드는 하나 이상의 스케줄로 구현될 수 있어 코드 생성기를 크게 단순화한다.

## 컴파일러 예시
GNU 컴파일러 모음은 (명령어 집합 및 스케줄링 모두) 또는 (스케줄링만) 플래그를 사용하여 명령어 스케줄링을 수행하는 것으로 알려진 컴파일러 중 하나이다. 각 마이크로아키텍처에 대한 명령어 지연 시간 및 어떤 명령어가 병렬로 실행될 수 있는지(또는 이에 상응하게 각 "포트"가 무엇을 사용하는지)에 대한 설명을 사용하여 작업을 수행한다. 이 기능은 GCC가 지원하는 거의 모든 아키텍처에서 사용할 수 있다.

버전 12.0.0까지 LLVM/Clang의 명령어 스케줄링은 명령어 집합 및 스케줄링 모두에 대해 (LLVM 용어로 라고 함) 스위치만 허용했다. 버전 12부터 x86에 대해서만 () 지원이 추가되었다.

지연 시간 및 포트 사용 정보 출처는 다음과 같다.
* GCC 및 LLVM
* 아그네르 포그, x86 아키텍처에 대한 광범위한 데이터를 수집한다.
* InstLatx64는 AIDA64를 사용하여 x86 CPU에 대한 데이터를 수집한다.
* uops.info는 x86 마이크로아키텍처에 대한 지연 시간, 처리량 및 포트 사용 정보를 제공한다.

LLVM의 는 모든 시스템에서 특히 x86이 아닌 시스템에 대한 정보를 수집하는 데 사용할 수 있어야 한다.

## 같이 보기
* 분기 예측
* 코드 생성
* 명령어 장치
* 비순차적 명령어 처리

## 각주

## 추가 자료
*   (트레이스 스케줄링)
*  (Percolation scheduling)
*  (Global scheduling)
* 

분류:컴파일러 최적화