Irregular reduction is one of the important computation patterns in the scientific application such as computer-based simulations for fluid dynamics or molecular dynamics. An effective compilation framework for parallelizing irregular reductions on high performance architectures is therefore important for the future computational science. Meanwhile, explicitly managed memory hierarchies have been proposed in the design of many-core processors. When hundreds or thousands of cores are embedded within one chip, software controlled memory hierarchies are particularly necessary to build scalable processor architectures.
The irregularity in data accesses patterns presents several challenges for programmers to exploit those architectures. Managing memory hierarchy in software requires a lot of programming efforts and tends to be error-prone. The difficulties are even worse for applications with irregular data access patterns. Another problem caused by the irregular accesses is that they hinder the extraction of data-level parallelism for fine-grained parallel functional units such as multimedia extensions. The lack of effective analysis for irregular accesses limits the optimization opportunity for both compilers and moderate programmers.
In this work, we propose a compilation framework for parallelizing irregular reduction on architectures with explicitly managed memory hierarchy. To relieve the burden of memory management from programmers, we develop a work-sharing construct for structuring parallel tasks, mapping the parallel tasks to processing units and scheduling data transfers between the memory hierarchies. A vectorization technique is also presented to address the challenges arose in the presence of array indirection, such as disjoint memory references, unknown alignment, dependence cycles, etc.
We experimentally evaluate the effectiveness of our techniques for several irregular reduction kernels on the Cell processor embedded in a Sony PlayStation3. The results show that the work-sharing construct achieves speedups of 8 to 14 on the six available SPEs, and the vectorization technique achieves the average speedup of 2.87, which is 1.8 times faster than the previous automatic vectorization techniques.
비정규 병합 계산(irregular reduction)은 유체역학, 분자동역학 등 컴퓨터를 이용한 과학 계산 시뮬레이션 프로그램에 긴요하게 사용되는 계산 형태이다. 비정규 병합 계산 코드를 고성능 컴퓨터에 적합하게 컴파일하는 것은 앞으로의 계산 과학 분야에서 중요한 문제가 된다. 한편 멀티코어 프로세서의 코어의 수가 점점 늘어나면서, 회로를 단순화하고 성능을 향상시키는 수단으로 명시적 관리 메모리 구조가 제안되었다. 이러한 구조의 프로세서는 기존에 비해 높은 최대 성능을 가지나 이를 충분히 활용하기 위해서는 소프트웨어가 직접 하드웨어를 관리해야 하는 어려움이 있다. 특히 비정규 병합 계산의 불규칙적인 데이터 접근 패턴은 소프트웨어적인 메모리 관리의 어려움을 더욱 가중시킨다. 비정규 병합 계산을 컴파일 할 때 고려해야 할 또 다른 문제는 각 코어가 가지고 있는 여러 계산 회로(functional units)를 최대한 활용하는 방법을 찾는 것이다. 불규칙한 데이터 접근은 컴파일러 혹은 프로그래머가 계산에 내재된 데이터 수준 병렬성을 찾는 것을 어렵게 만들어 벡터 명령어를 이용한 병렬 처리를 비효율적으로 만든다.
본 논문에서는 명시적 관리 메모리 구조를 가진 멀티코어 프로세서에서 비정규 병합 계산을 효과적으로 수행할 수 있도록 하는 컴파일러 기술을 제안한다. 우선 메모리 관리를 용이하게 하기 위해 비정규 병합 계산을 각각 접근하는 데이터의 위치에 따라 여러 부분으로 나누고, 나누어진 작업을 여러 코어에 할당한 다음, 각 코어가 할당된 작업을 처리하기 위해 필요한 데이터를 효율적으로 주고 받을 수 있도록 하는 작업 공유 방법(work-sharing construct)을 개발했다. 또한 이에 더해, 각 코어의 병렬 계산 회로를 충분히 활용할 수 있도록 벡터 명령어를 이용한 코드 생성 기법을 개발했다. 제안된 방법은 배열의 간접 지정(array indirection)에 의한 문제, 즉 인접하지 않은 위치를 접근하거나 주소의 정렬 위치를 모르는 메모리 명령어들의 벡터화 방법 및 데이터 간의 순환 의존(dependence cycle) 문제를 다룬다.
제안된 컴파일 방법을 다양한 비정규 병합 계산에 적용하여 실험한 결과, 제안된 작업 공유 방법을 통해 병렬화된 코드는 병렬화하지 않은 원래의 코드에 비해 8-14배 빠르게 실행되었고, 벡터 명령어를 이용한 코드 생성은 기존의 벡터 코드 생성 방법에 비해 약 1.8배 개선된 평균 2.87배의 성능 향상을 보였다.
