The performance of data parallel programs suffers from the latencies caused by the memory access and synchronization. These latencies are affected by the grain size and the scheduling policy for the frains since they influence the memory reference patterns and the time required for synchronization among processors. In this thesis, to explore the causes of these latencies, data parallel programs are experimenting with varying their grain sizes under two scheduling policies through execution-driben simulations. From this simulation, we found the best grain size and scheduling policy for each simulated parallel programs and analyze the causes inducing those results.
The experiment also shows that most of the cache misses are observed from cache conflict misses, even when using smaller data size than the sum of processor caches. The reason is that address spaces accessed by a grain size interfere with oach other, and the interference causes cashe conflict misses. To reduce these cache conflict misses, we propose tailoring the grain size on the basis of the periodicityof the addressing on direct mapped caches and the constant-stride accesses on data parallel programs. Since the tailored grain size does not map the grains to the same location in the cache, cache conflict misses are reducee. Simulation results show that the tailored grain size substantially improves program performance through the reduction of conflict misses on direct-mapped caches. These reduced cache misses provide both more scalable performance for tested parallel programs and less average memory access latency rather than when set associative caches are used.
To reduce cache conflict misses, a merging-arrays technique can be used when data structures are allocated. However, when a program accesses the multiple arrays in the same dimension using the different index values, the existing merging-arrays technique results in useless prefetches on the cache block with multiple words. To address this problem, we propose a stride merging-arrays technique results in useless prefetches on the cachs block with multiple words. To address this problem, we propose a stride merging-arrays technique based on a grain size of parallel programs. The proposed merging technique uses a grain size as a unit for merging arrays. Simulation results show that the stride merging-arrays technique improves cache performance, due to not only the reduction of cache conflict misses but also useful prefetches on cache blocks. This enhanced cache performance also provides the more scalable performance for tested parallel programs.
In a multiprogrammed system, the operation system performs context switches to support multiple programs simultaneously. However, if the data loaded into caches are replaced before they are completely reused, the performance of programs suffers from cache pollution. In particular, for the programs with good cache locality, such as blocked programs, a scheduling mechanism of keeping cache locality against context switching is essential to achieving good processor utilization. To solve this requirement, we propose a preemption-safe policy to exploit the cacche locality of blocked programs in a multiprogrammed system. The proposed policy delays context switching until a block is fully reused, but also compensates for the monopolized processor time on processor scheduling mechanisms. Our simulation results show that in a situation where blocked programs are run on multiprogrammed shared-memory multiprocessors, the proposed policy improbes the performance of these programs due to a decrease in cache misses. In such situations, it also has a beneficial impact on the overall system performance due to the enhanced processer utilization.
Barriers are widely used for synchronization in parallel programs. Since processor arrived earlier than others should wait at the barrier, processor utilization decreases. Even if the same number of grains is allocated to each processor, barrier waiting rimes are affected by both varying the number of instructions and of cache misses within in grains. Furthermore, the lack of functionality in the existing barrier primitive further increases the barrier waiting time. To reduce the barrier waiting time, we propose two-phase barrier dividing single synchronization stage into two stages. On a synchronization operation, since the proposed barrier provides the non-blocking property, the barrier waiting time substantially decreases. Simulation results show that the reduced barrier waiting times attributed to the two-phased barrier are quite valuable for enhancing the performance of parallel programs.
데이터 병렬 프로그램의 성능은 메모리 참조 대기 시간 및 동기화를 위한 대기 시간에 의하여 제한을 받는다. 이러한 대기 시간들은 그레인 크기나 그레인들에 대한 스케줄링 정책이 메모리 참조 형태와 병렬 처리에 참여한 프로세서들 사이의 동기화 시간에 영향을 미치기 때문이다. 본 논문에서는 이런 지연 시간들의 변화 원인들을 연구하기 위하여 수행 구동 시험기를 사용하여 다양한 캐쉬 크기와 종류들을 갖는 공유 메모리 다중 처리기 시스템들을 구성하였고, 구축된 시스템들에서 데이터 병렬 프로그램들을 다양한 그레인 크기 및 스케줄링 정책들에서 수행하였다. 이러한 실험을 통하여 선택된 각각의 병렬 프로그램에서 가장 좋은 성능을 나타내는 그레인 크기 및 스케줄링 정책을 찾으며 이런 결과를 도출한 원인들을 상기의 대기 시간들을 측정하여 분석했다.
병렬 프로그램의 데이터 크기가 계산에 참여한 모든 프로세서들의 캐쉬 총합 보다 작을 경우에도 캐쉬 충돌 실패(cache conflict miss)는 프로그램 성능 저하에 커다란 영향을 미친다. 특히 직접 사상 캐쉬(direct-mapped cache)는 간단한 하드웨어 구조와 빠른 처리 기능을 보유했음에도 불구하고 주소 사상(mapping)시 단일 캐쉬 블록을 사용하므로 지나친 캐쉬 충돌 실패를 발생한다. 이러한 원인은 각각의 프로세서에 할당된 그레인들이 제한된 캐쉬 공간에서 서로간에 주소간섭(address interference)을 발생하기 때문이다. 이런 현상을 방지하기 위하여 본 논문에서는 직접 사상 캐쉬의 주소분주(addressing)주기성과 데이터 병렬 프로그램에서 그레인 크기와 그레인 스케줄링 정책을 제안한다. 제안된 방법은 각각의 프로세서에 할당된 그레인들이 캐쉬 공간내에서 같은 위치에 사상되지 않게 하므로 주소 간섭 현상을 제거하여 캐쉬 충돌 실패를 감소시킨다.
캐쉬 충돌 실패를 줄이기 위하여 배열 병합(array merging)기법이 사용되고 있다. 그러나 프로그램이 서로 다른 색인 값들을 가지고 서로 다른 배열들을 접근할 때 기존의 배열 병합은 다중 워드(multiple words)들로 구성된 캐쉬 라인(cache lines)들에서 프로세서에서 사용하지 않는 데이터들을 선인출(prefectching)하는 현상을 보인다. 이러한 원인은 병렬 프로그램의 그레인 크기를 고려하지 않고 배열들을 병합하므로 발생된다. 본 논문에서는 이러한 문제를 해결하기 위하여 그레인 크기를 배열 병합을 위한 병합 단위로 사용한 스트라이드 배열 병합을 제안한다. 제안된 방식은 캐쉬 충돌을 감소시킬 뿐만 아니라 각각의 프로세서가 사용하는 그레인들내의 데이터들이 다중 워드로 구성된 캐쉬 라인들에 순차적으로 적재되므로 유용한 데이터 선인출이 이루어지게 한다.
다중 프로그래밍 환경에서 운영체제는 시스템의 시간 할당량(quantum)에 따라서 프로세스들에 대하여 문맥교환(context switching)을 수행한다. 문맥교환은 현재 수행중인 프로세스 문맥의 저장과 다음에 수행되는 프로세스 문맥의 적재라는 비용 뿐만 아니라 캐쉬 메모리의 성능에도 커다란 영향을 미친다. 즉, 캐쉬에 적재된 데이터들이 빈번한 문맥 교환에 의하여 다른 프로그램의 데어트들로 대체되는 경우 캐쉬 메모리를 사용하는 목적인 캐쉬 구역성(cache locality)은 손상 받는다. 특히, 블록 프로그램들과 같이 캐쉬 구역성에 크게 의존하는 프로그램은 문맥 교환으로부터 캐쉬 구역성을 보존하는 스케줄링이 필요하다. 본 논문에서는 시간 공유(time sharing) 다중 프로그램 환경에서 블록 프로그램이 수행될 때, 하나의 블록에 대한 계산이 완료될 때 까지 운영체제가 해당 프로세서들의 문맥 교환을 지연시키므로 블록 프로그램의 캐쉬 구역성을 이용할 수 있는 선점 안전(preemption-safe) 정책을 제안한다. 제안된 정책은 블록 프로그램에 대한 캐쉬 성능 향상을 통하여 블록 프로그램의 성능을 향상시키고 또한 선점 안전 정책에 의한 선점 기간이 종료된 후 블록 프로그램이 미리 사용한 프로세서 시간에 대한 보상을 다른 프로그램들에게 하므로 시스템의 전체적 성능을 향상시킨다.
배리어는 병렬처리시 프로세스간 동기화를 위하여 운영체제에서 제공되는 동기화 프리미티브이다. 그러나 배리어에 일찍 도착한 프로세스들은 나머지 프로세스들이 배리어에 도착할 때 까지 배리어에서 기다리게 되므로 프로세서의 활용률이 떨어진다. 특히, 각각의 프로세스에게 같은 개수의 그레인들을 배당하여 수행하여도 프로세스들의 캐쉬 실패 차이 및 그레인내의 제어흐름의 변화는 배리어에서의 대기시간에 영향을 미친다. 이러한 배리어 대기 시간은 기존 운영체제에서 제공하는 배리어들의 기능성(functionality) 부족에 의하여 더욱 증가 된다. 즉, 기존의 배리어의 경우 배리어에 일찍 도착한 프로세스들은 아직 도착하지 않은 프로세스들이 부분적으로 수행 완료한 그레인들에 관한 정보를 얻을 수 없기 때문이다. 이러한 정보를 얻을 수 있을 경우 현재와 같이 배리어에 일찍 도착한 프로세스들이 배리어에서의 맹목적 대기 현상은 피할수있다. 본 논문에서는 이러한 문제점을 해결하기 위하여 기존 배리어의 단일 동기화 단계를 두 단계로 확장한 두 단계 배리어(two phased barrier)를 제안한다. 제안된 두 단계 배리어는 동기화가 수행될 때 무 정지(non blocking)기능을 제공할 수 있으므로 배리어 대기시간을 감소시킬 수 있다.
