Memory latency is becoming an overwhelming bottleneck in current computer performance, and efficient data management of on-chip memory is getting more and more important. In an attempt to overcome this, explicitly managed memory hierarchy architectures aiming to reduce the performance gap between memory and processor were developed. Simultaneous and in-flight memory transactions such as DMA are used to transfer data between main-memory and on-chip memory in these architectures. However, such approach makes software development more and more complicated.
In order to parallelize irregular reductions on explicitly managed memory hierarchies, a newly designed algorithm is required to maximize the potential of multi-core processors. In this paper, we introduce two mechanisms to exploit explicitly managed memory hierarchies for irregular reductions: (i) region-based computation that minimizes the frequency and total amount of data transfers, and (ii) computation interleaving that aggressively hides the latency of data transfer by combining multiple sparse computations with a dense one. Computation interleaving outperforms traditional multiple buffering technique when there are many communication-bound regions.
We experimentally evaluate the effectiveness of our scheme for irregular reduction kernels on the Cell processor embedded in Sony PlayStation3. Experiment results show the overall speedups of up to 14 on the six available SPEs. Computation interleaving reduces the communication latency by up to 50% compared to the typical multiple buffering.
메모리 대기시간이 컴퓨터 성능의 병목지점이 됨에 따라, on-chip 메모리의 효율적인 관리는 점차 중요해지고 있다. 오늘날, 이러한 문제를 해결하기 위해서 프로세서와 메모리의 성능 차이를 줄이기 위한 명시적 메모리 관리 아키텍처의 개발 연구가 진행되고 있고, 이러한 아키텍처는 DMA와 같은 동시 다발적인 메모리 접근 메커니즘을 제공한다. 하지만, 이러한 아키텍처는 소프트웨어의 개발을 더욱 복잡하고 어렵게 만든다. 명시적 메모리 관리 구조에서의 불규칙 계산의 병렬화는 멀티 코어 프로세서의 성능 최대화를 위해 기존의 알고리즘의 재디자인을 필요로 한다. 이 논문에서는 다음의 두 가지 메커니즘을 통하여 이러한 아키텍처에서의 성능 향상을 꾀한다. (i) region 기반 연산을 통하여 데이터 이동양과 횟수를 줄임, (ii) 연산 끼워넣기를 통하여 데이터 이동의 오버헤드를 감춤. 논문에서 제안한 방법의 성능 측정을 위하여 우리가 사용한 기기는 Cell 프로세서가 내장된 Sony Playstation3 이다. 실험 결과, 우리의 방법은 단일 쓰레드의 성능과 비교하여 최대 14배의 성능 향상을 이루었고, 기존의 멀티플 버퍼링과 비교하여 최대 50%의 메모리 오버헤드를 줄였다.
