명령 스케줄링

Instruction scheduling

컴퓨터 과학에서 명령 스케줄링은 명령 수준의 병렬 처리를 개선하기 위해 사용되는 컴파일러 최적화로, 명령 파이프라인이 있는 기계에서 성능을 향상시킵니다.보다 간단하게 말하면, 코드의 의미를 변경하지 않고, 다음의 조작을 시도합니다.

  • 지시 [1]순서를 조정하여 파이프라인의 정지를 방지합니다.
  • 잘못된 작업 또는 의미론적으로 모호한 작업(일반적으로 미묘한 명령 파이프라인 타이밍 문제 또는 인터록되지 않은 리소스 관련)을 피하십시오.

파이프라인 정지(pipeline stall)는 구조적 위험(프로세서 자원 한계), 데이터 위험(다른 명령에 필요한 한 명령의 출력) 및 제어 위험(분기)에 의해 발생할 수 있다.

데이터 위험

명령 스케줄은 일반적으로 단일 기본 블록에서 수행됩니다.특정 방식으로 블록의 명령을 재배치하는 것이 해당 블록의 동작을 보존하는지 여부를 판단하기 위해서는 데이터 의존성의 개념이 필요합니다.의존성에는 세 가지 유형이 있으며, 세 가지 데이터 위험도 있습니다.

  1. 쓰기 후 읽기(RAW 또는 "참"):명령 1은 명령 2에서 나중에 사용한 값을 씁니다.명령 1이 먼저 와야 합니다. 그렇지 않으면 명령 2가 새 값이 아닌 이전 값을 읽습니다.
  2. 읽기 후 쓰기(WAR 또는 "안티"):명령 1은 명령 2에 의해 나중에 덮어쓰게 되는 위치를 읽습니다.명령 1이 먼저 와야 합니다. 그렇지 않으면 이전 값이 아닌 새 값이 읽힙니다.
  3. 쓰기 후 쓰기(WAW 또는 "출력"):두 가지 명령어는 모두 같은 위치를 씁니다.그것들은 원래의 순서로 일어나야 합니다.

기술적으로는 네 번째 유형인 Read after Read(RAR 또는 "입력")가 있습니다.두 지침 모두 같은 위치를 읽습니다.입력 의존성은 두 문의 실행 순서를 제한하지 않지만 배열 요소의 스칼라 치환에 유용합니다.

이 세 가지 의존관계를 확실히 하기 위해 의존관계 그래프를 작성합니다.이 그래프는 각 정점이 명령어이고 의존관계로 인해 내가 앞에2 와야 하는 경우1 I에서12 I까지의 가장자리가 있는 방향 그래프입니다.루프 캐리어 종속성이 생략된 경우 종속성 그래프는 유도 비순환 그래프입니다.그러면 이 그래프의 모든 종류의 토폴로지가 유효한 명령 스케줄입니다.그래프의 가장자리는 일반적으로 종속성의 지연 시간으로 레이블이 지정됩니다.파이프라인이 정지하지 않고 타깃명령어를 진행하기 전에 경과해야 하는 클럭사이클 수입니다.

알고리즘

토폴로지 정렬을 찾기 위한 가장 간단한 알고리즘이 자주 사용되며 목록 스케줄링이라고 합니다.개념적으로 종속성 그래프의 소스를 반복적으로 선택하고 현재 명령 일정에 추가한 후 그래프에서 제거합니다.이로 인해 다른 정점이 소스가 될 수 있으며, 이는 스케줄링에도 고려됩니다.그래프가 비어 있으면 알고리즘이 종료됩니다.

좋은 일정에 도착하기 위해서는 좌판을 막아야 한다.이는 스케줄링할 다음 명령 선택에 따라 결정됩니다.많은 휴리스틱이 일반적으로 사용되고 있습니다.

  • 이미 스케줄된 명령에서 사용되는 CPU 리소스가 기록됩니다.후보자가 사용 중인 리소스를 사용하는 경우 우선 순위가 떨어집니다.
  • 후보자가 관련된 지연 시간보다 이전 후보자에 더 가깝게 스케줄 되어 있는 경우 우선순위는 떨어집니다.
  • 후보자가 그래프의 핵심 경로에 있으면 우선 순위가 높아집니다.이 경험적 접근은 로컬 의사결정 프로세스에서 어떤 형태로든 사전 예측을 제공합니다.
  • 후보를 선택하는 것이 많은 새로운 원천을 창출할 수 있다면, 그 우선순위는 높아질 것이다.이 경험적 접근은 스케줄러에게 더 많은 자유를 주는 경향이 있습니다.

위상순서

명령 스케줄링은 레지스터 할당 전후에 또는 레지스터 할당 전후에 모두 수행할 수 있습니다.레지스터를 할당하기 전에 이 작업을 수행하면 최대 병렬이 발생한다는 장점이 있습니다.레지스터 할당 전에 이 작업을 수행하는 것의 단점은 레지스터 할당자가 사용 가능한 레지스터 수를 초과하여 사용할 필요가 있다는 것입니다.이로 인해 누출/충전 코드가 도입되어 해당 코드 섹션의 성능이 저하됩니다.

(명령 인터락 부족으로 인해) 잘못된 조합이 있을 수 있는 명령 시퀀스가 아키텍처에 있는 경우 레지스터 할당 후 명령을 예약해야 합니다.이 두 번째 일정 패스는 유출/채움 코드의 배치도 개선합니다.

스케줄링이 레지스터 할당 후에만 이루어지면 레지스터 할당에 의해 잘못된 의존관계가 발생하여 스케줄러에 의해 가능한 명령 모션의 양을 제한할 수 있습니다.

종류들

명령 스케줄링에는 몇 가지 유형이 있습니다.

  1. 로컬(기본 블록) 스케줄링: 명령은 기본 블록 경계를 넘어 이동할 수 없습니다.
  2. 글로벌 스케줄링: 명령은 기본 블록 경계를 넘어 이동할 수 있습니다.
  3. 모듈로 스케줄링: 내부 루프의 다른 반복을 인터리빙하여 명령 수준의 병렬성을 높이는 소프트웨어 파이프링을 생성하는 알고리즘입니다.
  4. 트레이스 스케줄링: 글로벌스케줄링의 첫 번째 실용적인 접근법인 트레이스 스케줄링은 가장 자주 실행되는 제어 흐름 경로를 최적화하려고 합니다.
  5. 슈퍼블록 스케줄링: 트레이스 "사이드 입구"에서 제어 흐름 경로를 병합하지 않는 단순한 형태의 트레이스 스케줄링입니다.대신 코드를 여러 일정에 따라 구현할 수 있으므로 코드 생성기가 크게 간소화됩니다.

컴파일러 예시

GNU 컴파일러 컬렉션은 명령 스케줄링을 실행하는 것으로 알려진 컴파일러 중 하나입니다.-march(명령어 세트와 스케줄링 모두) 또는-mtune(스케줄링만) 플래그각 마이크로아키텍처(architecture)에 대해 명령 지연에 대한 설명과 병렬로 실행할 수 있는 명령(또는 각 명령의 "포트")을 사용합니다.이 기능은 GCC가 [2]지원하는 거의 모든 아키텍처에서 사용할 수 있습니다.

버전 12.0.0까지는 LLVM/Clang 명령 스케줄은-march(호출된target-cpu명령어 세트와 스케줄링을 모두 지원하는 LLVM 용어) 스위치입니다.버전 12 에서는, 다음의 서포트가 추가되고 있습니다.-mtune(tune-cpu)의 경우만.[3]

지연 시간 및 포트 사용률에 대한 정보 출처:

  • GCC 및 LLVM
  • Agner Fog, x86 [4]아키텍처의 광범위한 데이터를 컴파일합니다.
  • InstLatx64: AIDA64를 사용하여 x86 [5]CPU에서 데이터를 수집합니다.

LLVM의llvm-exegesis는 모든 머신, 특히 x86 이외의 [6]머신에 대한 정보를 수집하기 위해 사용할 수 있어야 합니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Su, Ching-Long; Tsui, Chi-Ying; Despain, Alvin M. (1994). Low Power Architecture Design and Compilation Techniques for High-Performance Processors (PDF) (Report). Advanced Computer Architecture Laboratory. ACAL-TR-94-01. (콜드 스케줄링)
  2. ^ "x86 Options". Using the GNU Compiler Collection (GCC).
  3. ^ "⚙ D85384 [X86] Add basic support for -mtune command line option in clang". reviews.llvm.org.
  4. ^ "Software optimization resources. C++ and assembly. Windows, Linux, BSD, Mac OS X". Agner Fog.
  5. ^ "x86, x64 Instruction Latency, Memory Latency and CPUID dumps". instlatx64.atw.hu. 페이지의 "댓글" 링크도 참조하십시오.
  6. ^ "llvm-exegesis - LLVM Machine Instruction Benchmark". LLVM 12 Documentation.

추가 정보