RyuJIT에서 유전자 알고리즘을 사용한 레지스터 최적화

RyuJIT에서 유전자 알고리즘을 사용한 레지스터 할당 최적화

유전자 알고리즘은 거대한 탐색 공간을 가진 문제에서 직관에 반하는 해답을 찾는 데 탁월합니다. 예를 들어, RyuJIT 컴파일러의 레지스터 할당을 위한 휴리스틱 순서 최적화가 그렇죠. 자유 레지스터와 점유 레지스터를 선택하는 딱딱한 순서 대신, .NET 팀 연구원들은 "hot" 루프에서 스필을 줄이고 PerfScore를 개선하는 더 효율적인 순서를 실험적으로 찾아냈습니다.

고정 휴리스틱 순서의 문제점

RyuJIT의 선형 스캔 레지스터 할당(LSRA) 알고리즘은 메서드 컴파일 중 레지스터를 선택하기 위해 17개의 휴리스틱을 사용합니다. 처음 13개는 자유 레지스터에, 마지막 4개는 점유 레지스터에 적용됩니다. 기본적으로 순서는 엄격하게 고정되어 있습니다: ABCDEFGHIJKLMNOPQ. 이 접근 방식은 최적이지 않을 수 있습니다. 루프 밖 변수에 자유 레지스터가 소진되면 루프 안에서 점유 레지스터의 값을 반복적으로 스필하게 되어 코드 크기가 불어났고 성능이 저하됩니다.

실제 사례: 한 벤치마크에서 루프 안 모든 변수가 동일한 레지스터를 사용해 지속적인 스필/리로드 작업이 발생했습니다. 이는 레지스터 부족 때문이 아니라 휴리스틱이 항상 자유 레지스터를 우선시했기 때문으로, 장기적으로 최선이 아닌 선택이었습니다.

동적 순서를 위한 LSRA 리팩토링

대안 순서를 테스트하기 위해 개발자들은 다음 변경을 적용했습니다:

• 각 휴리스틱을 __forceinline 속성을 가진 별도 메서드로 이동시켜 오버헤드를 피했습니다.
• 기호(A–Q)를 해당 메서드 포인터에 매핑하는 해시 테이블을 만들었습니다.
• 휴리스틱 순서를 정의하는 17개의 고유 기호 문자열을 받는 COMPlus_JitLsraOrdering 환경 변수를 도입했습니다.

이제 원하는 조합으로 JIT를 실행할 수 있습니다. 예:

set COMPlus_JitLsraOrdering=PEHDCGAIJNLKOBFMQ

이렇게 하면 점유 레지스터 휴리스틱(예: P는 PREV_REG_OPT)을 먼저 적용한 후 자유 레지스터를 적용해 핵심 코드 구간을 위해 자유 레지스터를 아낄 수 있습니다.

PerfScore로 효과 측정

PerfScore는 생성된 코드의 실행 비용을 가중치로 평가한 점수로, 레지스터 할당 품질을 평가합니다. 명령어 지연과 처리량을 반영하며, 특히 루프 내 스필/필 작업(mov [rsp], reg / mov reg, [rsp])에 민감합니다.

superpmi 도구는 이러한 지표로 두 clrjit.dll 버전을 비교합니다:

• CodeSize — 전체 기계어 코드 크기
• InstructionCount — 명령어 수
• PerfScore — 주요 목표 지표

최적화 목표는 PerfScore 최소화입니다. 하지만 탐색 공간은 엄청납니다: 17! ≈ 3.56 × 10¹⁴개의 가능한 순열. 클러스터에서도 완전 탐색은 불가능합니다.

유전자 알고리즘 적용

이런 문제에 유전자 알고리즘(GA)이 딱 맞습니다:

• Chromosome: 휴리스틱 순서를 정의하는 17개의 고유 기호(A–Q) 문자열.
• Fitness function: 테스트 빌드 세트의 평균 PerfScore 음수값(PerfScore가 낮을수록 적합도 높음).
• Crossover operator: 기호 고유성을 유지하는 순서 기반 교차(PMX 등).
• Mutation: 두 위치 무작위 교환.

알고리즘은 다음과 같이 반복됩니다:

• 무작위 개체군 초기화(예: 100개 염색체).
• superpmi로 각 개체 적합도 계산.
• 상위 부모 선택(토너먼트 또는 룰렛 선택).
• 교차와 돌연변이로 자손 생성.
• 개체군 갱신; 수렴할 때까지 반복.

결과와 한계

실험 결과 일부 순열은 기본값 대비 전체 PerfScore를 0.5–1.2% 줄였습니다. 중첩 루프와 많은 임시 변수가 있는 메서드에서 가장 큰 이득을 봤습니다.

다만 유의할 점:

• 개선이 보편적이지 않음: 한 순서가 일부 메서드를 돕지만 다른 메서드를 해칠 수 있음.
• GA 자체 오버헤드가 큼: 수천 번의 superpmi 실행 필요.
• 최적 순서는 아키텍처(x64 vs Arm64)와 워크로드 프로필에 따라 다름.

주요 교훈

• 실제 시나리오에서 고정 LSRA 휴리스틱 순서는 최적이지 않을 수 있음.
• COMPlus_JitLsraOrdering으로 소스 코드 변경 없이 순서 조정 가능.
• 유전자 알고리즘은 팩토리얼 복잡도 탐색 공간에서 빛남.
• PerfScore는 레지스터 할당 품질의 신뢰할 수 있는 지표.
• 고처리량 시스템에서 1% 미만 PerfScore 감소도 중요.

— Editorial Team