An MLIR-Based Compilation Framework for Control Flow Management on Coarse Grained Reconfigurable Arrays

기술 요약: 제어 흐름 관리를 위한 MLIR 기반의 CGRA용 컴파일 프레임워크

문제 정의
코스 그레인 재구성 가능 배열(Coarse-Grained Reconfigurable Arrays, CGRA)은 집약적인 워크로드를 가속화하는 데 높은 유연성과 효율성을 제공하지만, 컴파일의 복잡성이라는 중대한 장벽에 직면해 있습니다. 기존의 최첨단(SoA) 컴파일러들은 범위가 제한적이어서, 주로 단일 루프를 위한 데이터 흐름 그래프(DFG)만을 처리하며 제어 흐려 그래프(CFG)에 대한 지원은 거의 제공하지 못합니다. 결과적으로, 이들은 제어 흐름 관리를 호스트 프로세서에 오프로딩하거나 제어 흐름 분기를 처리하기 위해 임의의 하드웨어 유닛에 의존하는 경우가 많습니다. 이러한 방식은 기본 블록(basic block) 전환 시 발생하는 빈번한 데이터 교환과 명령어 및 데이터 재구성 비용으로 인해 상당한 런타임 오버헤드를 초래합니다. 또한, 재구성을 피하기 위해 사용하는 프로그램 카운터(Program Counter, PC) 기반 방식은 기본 블록 실행을 중첩할 수 없기 때문에 루프 수준의 병렬성을 활용하지 못하는 경우가 많습니다.

방법론
저자들은 MLIR(Multi-Level Intermediate Representation) 인프라를 기반으로 구축된 모듈형 엔드 투 엔드 컴파일 프레임워크를 제안합니다. 이 프레임워크는 모든 프로세싱 엘리먼트(PE)가 전역 프로그램 카운터에 의해 실행을 제어되는 균질한 PC 기반 CGRA를 대상으로 하며, 이를 통해 런타임 재구성 없이 시분할(multi-context) 실행을 가능하게 합니다.

본 방법론은 다음과 같은 몇 가지 핵심 단계로 진행됩니다:

1. MLIR 프런트엔드 및 다이얼렉트: 프레임워크는 중간 표현(IR) 수준에서 제어 데이터 흐름 그래프(CDFG)를 표현하기 위해 MLIR 내의 커스텀 cgra 다이얼렉트를 활용합니다. 이는 하드웨어 불가지론적(hardware-agnostic) 최적화와 하드웨어 특정적 변환을 깔끔하게 분리합니다.
2. 미들엔드 변환:
   • 하드웨어 불가지론적 최적화: 프레임워크는 수평 및 수직 기본 블록 병합과 루프 헤드-바디 퓨전(loop head-body fusion)을 포함한 CFG 단순화 기법을 사용합니다. 이러한 변환은 제어 오버헤드를 줄이고 명령어 수준 병렬성(ILP)의 범위를 넓힙니다.
   • 하드웨어 호환성: 메모리 연산은 물리적 주소와 일치하도록 변환되며, 불법 명령어는 대상 CGRA의 명령어 세트 아키텍처(ISA)에 맞게 재작성됩니다.
   • 모듈로 스케줄링 적응: PC 기반 모델(일반적으로 중첩되지 않는 기본 블록을 요구함) 내에서 루프 수준의 병렬성을 활성화하기 위해, 프레임워크는 CFG 적응을 수행합니다. 이는 루프 길이($L'$)가 개시 간격(Initiation Interval, $II$)과 같아지도록 IR을 재구성하여, 여러 반복(iteration)이 단일 기본 블록 구조 내에 캡슐화될 수 있는 새로운 루프 커널을 생성합니다.
3. ILP 및 라이브니스 분석을 통한 CDFG 매핑:
   • 분해: CDFG는 각 기본 블록에 대한 개별 DFG로 분해됩니다. 블록 간 의존성은 블록 간에 전달되는 값을 추적하기 위한 전역 라이브니스(liveness) 분석을 사용하여 관리됩니다.
   • ILP 정식화: 커스텀 정수 선형 계획법(ILP) 모델은 각 기본 블록의 DFG를 CGRA 메시에 매핑합니다. 이 모델은 접근성, 지배(dominance), 라이브니스 및 메모리 일관성 제약 조건을 충족하면서 실행 시간을 최소화합니다.
   • 실패 처리: 라우팅 제한이나 레지스터 오버플로로 인해 ILP 모델이 실패하는 경우, 프레키워크는 사후 매핑 복구 메커니즘을 사용합니다. 이는 값을 메모리로 퇴출하기 위해 이동(move) 연산이나 로드-스토어 쌍을 삽입하는 과정을 포함합니다. 결정적으로, 이 복구 프로세스는 이전에 해결된 기본 블록의 재스케줄링을 피하도록 설계되어 컴파일 효율성을 유지합니다.
4. 백엔드: 최종 단계는 레지스터 할당(그래프 컬러링 사용)과 대상 하드웨어를 위한 바이너리 어셈블리 코드 생성입니다.

주요 기여

• 엔드 투 엔드 프레임워크: 균질한 PC 기반 CGRA에서 임의의 제어 흐를 지원하여 기본 블록 전환 시의 재구성 오버헤드를 제거하는 모듈형 컴파일 프레임워크를 제공합니다.
• 커스텀 MLIR 다이얼렉트: CDFG를 IR 수준에서 직접 표현하는 cgra 다이얼렉트 설계를 통해 하드웨어 불가지론적 최적화를 용이하게 하고 관심사의 분리를 명확히 합니다.
• 라이브니스 기반 ILP 매핑: 라이브니스 분석을 활용하여 기본 블록 매핑을 위한 ILP 모델을 정식화하는 새로운 매핑 방법론을 도입합니다. 이는 재스케줄링 없이 불가능성을 해결하는 복구 메커니즘을 도입하여 매핑 복잡성을 크게 줄입니다.
• 모듈로 스케줄링을 위한 CFG 변환: PC 기반 제어 모델 내에서 모듈로 스케줄링을 지원하기 위해 CFG를 적응시키는 기술(예: 기본 블록 퓨전)을 제공합니다.
• 성능 평가: SoA 방법들과의 포괄적인 비교를 통해 순수 컴파일 최적화를 통한 속도 향상을 입증했습니다.

결과
프레임워크는 다양한 메시 크기(3x3 및 4x4)를 가진 250MHz, 65nm OpenEdge CGRA 템플릿에서 평가되었습니다. 벤치마크에는 컨볼루션, 선형 대수(PolyBench), 신호 처리(MiBench)가 포함되었습니다.

• 런타임 속도 향상: 제안된 프레임워크는 EffiMap(PC 기반 CDFG 매퍼) 대비 평균 2.12배, SAT-MapIt(DFG 매핑 + CPU 지원) 대비 1.48배, Marionette(재구성 가능한 하드웨어를 사용하는 CDFG 매핑) 대비 1.20배의 런타임 속도 향상을 달از성했습니다.
• 최적화 영향: CFG 단순화와 모듈로 스케줄링의 결적인 결합은 상당한 이득을 가져왔습니다. 예를 들어, 모듈로 스케줄링은 루프 길이($L$)를 개시 간격($II$)의 약 두 배로 달성하여, 3x3 CGRA에서 197%, 4x4 CGRA에서 223%의 평균 속도 향상을 기록했습니다.
• 컴파일 범위: 프레크임워크는 분기(divergent branches)와 중첩 루프가 포함된 전체 커널을 성공적으로 매핑했으며, 이는 DFG 전용 전략으로는 타겟팅하기 어려운 영역입니다.

의의 및 주장
본 논문은 현재 CGRA 채택의 주요 제한 사항이 복잡한 제어 흐름에 대한 컴파일 지원 부족이라고 주장합니다. PC 기반 모델을 사용하여 제어 흐름 관리를 완전히 컴파일러 수준으로 전환함으로써, 저자들은 다음을 달성할 수 있음을 보여주었습니다:

1. 재구성 오버헤드 제거: 재구성 가능한 하드웨어 접근 방식에서 발생하는 기본 블록 전환 시의 명령어 및 데이터 재구성 페널티를 피합니다.
2. 루프 수준의 병렬성 활성화: CFG를 재구성하여 모듈로 스케줄링을 지원함으로써 전통적인 PC 기반 모델의 순차적 실행 제한을 극복합니다.
3. 하드웨어 불가지론 달성: 제어 흐름 관리나 데이터 전파를 위한 전용 하드웨어 유닛을 요구하지 않고도 광범위한 애플리케이션을 타겟팅합니다.

저자들은 자신들의 접근 방식이 하드웨어 복잡성이 아닌 소프트웨어 최적화를 통해 고성능을 달성하며, 복잡한 컴퓨팅 커널의 배포를 자동화하는 견고한 경로를 제공한다고 결론짓습니다.