Abstract
An algorithmic template capable of modeling the multi-level parallelism and the temporal/spatial locality of multiprocessors and accelerators is proposed and effective algorithms can be derived from this template delivering unprecedented performance portability over GPU and multicore CPU. The construction of effective loop nest optimizers and parallelizers remains challenging despite decades of work in the area. Due to the increasing diversity of loop-intensive applications and to the complex memory/computation hierarchies in modern processors, optimization heuristics are pulled towards conflicting goals, highlighting the lack of a systematic approach to optimizing locality and parallelism. Acknowledging these conflicting demands on loop nest optimization, we propose an algorithmic template capable of modeling the multi-level parallelism and the temporal/spatial locality of multiprocessors and accelerators. This algorithmic template orchestrates a collection of parameterizable, linear optimization problems over a polyhedral space of semantics-preserving transformations. While the overall problem is not convex, effective algorithms can be derived from this template delivering unprecedented performance portability over GPU and multicore CPU. We discuss the rationale for this algorithmic template and validate it on representative computational kernels/benchmarks.
초록
루프 네스트 최적화 및 병렬화는 여전히 도전적인 과제이다. 루프 중심의 응용 프로그램의 다양성과 현대 프로세서의 복잡한 메모리/계산 계층 구조로 인해 최적화 알고리즘은 상충되는 목표를 가진다. 이를 해결하기 위해 다중 수준의 병렬성과 멀티프로세서 및 가속기의 시간적/공간적 지역성을 모델링하는 알고리즘 템플릿을 제안한다. 이 템플릿은 파라미터화된 선형 최적화 문제의 모음을 조정하여 폴리헤드랄 공간에서 변환을 수행한다. 비록 전체 문제는 비볼록하지만, 이 템플릿을 통해 효과적인 알고리즘을 도출하여 GPU와 멀티코어 CPU에서 성능 휴대성을 제공한다. 대표적인 계산 커널/벤치마크를 통해 이를 검증한다.
1. 서론
현대 컴퓨터 아키텍처는 병렬성 수준이 증가하고 메모리 계층 구조가 깊어지며 복잡해지고 있다. 성능 휴대성을 확보하려면 비볼록 최적화 문제를 모델링해야 한다. Pluto 알고리즘은 10년 전에 루프 네스트 최적화를 위해 중요한 기여를 했지만, 현대 프로세서 아키텍처는 깊은 메모리 계층 구조를 모델링해야 한다. 이를 해결하기 위해 매개변수화된 스케줄링 문제와 최적화 목표의 템플릿을 제안한다.
2. 배경
폴리헤드랄 프레임워크는 프로그램의 규칙적인 부분을 선형 대수적으로 표현한다. 루프와 조건문으로 둘러싸인 명령문과 다차원 배열을 표현할 수 있다. 제어 흐름의 폴리헤드랄 모델링은 명령문 인스턴스를 다차원 논리적 실행 날짜로 매핑하며, 이는 스케줄이라고 한다. 변환이 프로그램 의미를 유지하려면 모든 종속성이 만족되어야 한다.
3. isl에서의 폴리헤드랄 스케줄링
3.1 스케줄링 문제 공식화
스케줄러는 유효성, 근접성, 일치성 관계를 통해 명령문 인스턴스의 실행 순서를 결정한다.
3.2 아핀 변환
의존 거리도 재사용 거리이므로 이를 최소화하면 지역성이 향상된다. 음수 계수를 허용하여 최적화를 수행하며, 이는 실행 거리를 최소화하는데 사용된다.
3.3 진행과 유연성 보장
스케줄러는 이전 결과와 선형 독립적인 벡터를 찾아야 한다. 이를 위해 비독립적 솔루션을 찾으면 제약 조건을 추가하여 해결한다.
3.4 교체 가능한 밴드 및 타일링
밴드는 루프 타일링을 위한 충분 조건을 만족하며, 스케줄러는 이를 사용하여 병렬성을 최적화한다.
3.5 데이터 종속 그래프 클러스터링
스케줄러는 데이터 종속 그래프의 강한 연결 성분을 분리하여 클러스터 간의 스케줄을 계산한다.
4. 공간 효과를 위한 통합 모델
4.1 라인 기반 접근 모델링
메모리 계층 구조는 연속적인 메모리 셀 그룹을 접근하는 것이 특징이다. 이를 모델링하여 공간 근접 관계를 정의한다.
4.2 공간 및 시간 근접 관계
공간 근접 관계는 인접한 배열 요소에 접근하는 명령문 인스턴스를 연결한다. 이는 시간 근접 관계와 결합하여 최적화를 수행한다.
4.3 적은 공간 근접 관계 유지
공간 근접 관계를 최대한 적게 유지하면서 최적화를 수행한다.
4.4 공간 근접 관계의 그룹화 및 우선 순위화
접근 패턴이 다른 관계를 그룹화하여 우선 순위를 정하고, 이를 통해 최적화를 수행한다.
4.5 많은 공간 근접 관계 유지
더 많은 공간 근접 관계를 유지하기 위해 ILP 문제를 정의하고, 이를 통해 최적화를 수행한다.
4.6 CPU 타겟을 위한 스케줄링
CPU에서는 내부 루프가 연속적인 배열 요소를 접근하도록 하여 공간 지역성을 최적화한다.
4.7 GPU 타겟을 위한 스케줄링
GPU에서는 병렬성을 최대한 활용하도록 스케줄링하고, 타일링 후 최적화를 수행한다.
5. 실험 평가
다양한 벤치마크를 사용하여 제안된 알고리즘의 성능을 평가하였다.
5.1 구현 세부 사항
isl 및 ppcg의 확장으로 알고리즘을 구현하였다.
5.2 실험 프로토콜
다양한 플랫폼에서 성능을 비교하였다.
5.3 순차 코드 성능
순차 코드에서 제안된 스케줄러의 성능을 평가하였다.
5.4 병렬 CPU 코드 성능
병렬 코드에서 성능을 평가하였으며, 다양한 벤치마크에서 성능 향상을 확인하였다.
5.5 Affine+Syntactic 접근법과의 비교
PolyAST와 비교하여 유사한 성능을 보였다.
5.6 병렬 GPU 코드 성능
GPU에서 제안된 알고리즘의 성능을 평가하였다.
6. 논의 및 향후 연구
알고리즘 설계 선택과 확장 가능성에 대해 논의하였다.
7. 관련 연구
다양한 폴리헤드랄 스케줄링 알고리즘과의 비교를 통해 제안된 접근법의 우수성을 입증하였다.
8. 결론
다중 수준 병렬성과 메모리 계층을 고려한 아핀 스케줄링 알고리즘 템플릿을 제안하였다. 대표적인 벤치마크를 통해 이를 검증하였다.
Figure
figure 1
figure 2
figure 3
