With increasing number of cores in multi-core system, multiple threads share a cache. Although shared caches allow the dynamic allocation of limited cache capacity among cores, traditional LRU replacement policies often cannot prevent negative interference among cores.
To address the contention problem in shared caches, cache partitioning and application scheduling techniques have been extensively studied. Cache partitioning measures the benefit related to the amount of allocated cache capacity of each thread and enforces the cache allocation to each core to maximize overall benefits with limited cache capacity. On the other hand, application scheduling by operating systems groups the least interfering applications for each shared cache, when multiple shared caches exist in systems. Although application scheduling can mitigate the contention problem without any extra hardware support, its effect can be limited for some severe contentions. Although the two techniques can have mutual impacts on each other, their interactions have not been studied much so far.
This thesis investigates mutual interactions of the two techniques in systems with multiple shared cache domains. To truly understand the interactions of partitioning and scheduling, we evaluate all the possible mixes from a set of applications, instead of using a few selected mixes. Evaluation results show that scheduling can have a significant impact on the overall performance and fairness among cores both with and without partitioning, although partitioning can mitigate the negative effect of bad scheduling. In some cases that scheduling-only scheme cannot reduce cache contentions, partitioning recovers the performance potential cannot be improved with scheduling-only schemes. Moreover, effective scheduling often lowers the required accuracy of partitioning techniques to achieve the same optimal performance.
Firstly, based on the observations, we propose partition-aware heuristic scheduler which maps threads on cores regardless of the support of cache partitioning. By examining all possible mixes from a set of applications, we show that the proposed partition-aware heuristic scheduler performs within 2\% of the optimal performance.
Secondly, we propose a low cost solution, based on application scheduling with a simple cache insertion control. Instead of using a full hardware-based cache partitioning mechanism, the proposed technique mostly relies on application scheduling. It selectively uses LRU insertion to the shared caches, which can be added with negligible hardware changes from the current commercial processor designs. The evaluation shows that the proposed technique can mitigate the cache contention problem effectively, close to the ideal scheduling and partitioning.
멀티코어 프로세서는 여러 개의 코어를 탑재하여 만든 프로세서로서 기존의 고성능 프로세서들의 한계였던 높은 전력 소모와 발열 문제를 해결하는 대안으로서 많이 사용되고 있다. 멀티코어 프로세서에서는 여러 개의 코어가 캐시 메모리를 공유하여 사용하는 공유 캐시 구조 (Shared Cache) 가 많이 사용되고 있다. 공유 캐시 구조에서는 하나의 코어가 사용 가능한 캐시 메모리의 크기가 커짐에 따른 성능 향상을 기대할 수 있지만, 여러 코어에서 동시에 수행되는 응용프로그램들 간의 캐시 메모리에 대한 경쟁 (Cache Contentions)이 발생하게 되면 성능의 저하를 가져올 수 있다. 따라서 멀티코어 프로세서의 높은 성능을 위해서는 효율적인 캐시 메모리 관리가 필요하다.
이러한 캐시자원 경쟁(Cache Contentions) 문제를 해결하여 멀티코어 프로세서의 성능을 향상시키기 위한 많은 연구가 진행되었는데, 제한된 캐시 공간을 여러 코어가 나누어 사용함으로서 경쟁을 피하고 성능을 향상시키고자 하는 하드웨어 기반의 캐시 파티셔닝 (Cache Partitioning) 기법들과 비교적 경쟁으로 인한 성능 저하가 적은 응용프로그램들이 하나의 캐시를 공유하도록 프로그램이 수행되는 코어 위치를 조정하는 소프트웨어 기반의 스케줄링 (Application Scheduling) 기법들이 많이 연구되어 왔다. 캐시 분할 기법은 캐시자원 경쟁을 효과적으로 없앨 수 있지만, 하드웨어를 추가해야 하는 오버헤드가 존재한다. 반면, 스케줄링은 하드웨어를 추가하지 않고도 캐시 경쟁 문제를 효과적으로 해결할 수 있지만, 공유 캐시가 시스템에 두개 이상 존재할 때만 적용 가능하고, 스케줄링 기법만으로는 해결이 불가능한 상황이 존재한다는 한계점이 있다.
본 연구에서는 이런 캐시자원 경쟁(Cache Contentions) 문제를 실험을 통해 정량적으로 분석한다. 특히, 기존의 많은 연구들이 몇 개의 실험 군을 선택해서 문제를 해결하는 것과는 달리, 가능한 모든 실험 군을 선택하여 분석함으로서 실험의 신뢰도를 높인다. 실험을 통해서는 캐시자원 경쟁 문제가 실제로 얼마나 자주 발생하는지, 또 경쟁으로 인한 성능 저하는 얼마나 심각한지를 분석하고, 파티셔닝이나 스케줄링 기법들이 이러한 캐시자원 경쟁 문제를 해결하는데 얼마나 효과적인지, 하드웨어와 소프트웨어 기반의 두 가지 방식이 시스템에서 어떤 식으로 상호작용하는지에 초점을 맞추어 분석한다. 분석한 결과, 캐시자원 경쟁 문제는 많은 연구들에서 가정하는 것보다 실제 상황에서는 빈도가 상대적으로 낮다는 것과 그 경우에는 성능 저하의 폭이 크다는 것, 또한 하드웨어와 소프트웨어 기반의 파티셔닝과 스케줄링 기법은 캐시자원 문제를 해결하는 방식이 서로 다르기 때문에 두 가지 방법 다 캐시 메모리 성능을 향상시키는데 효과적이며 서로 상호보완적인 관계를 가진다는 것을 보인다.
실험을 통해 분석한 결과를 바탕으로, 본 연구에서는 먼저 하드웨어의 구현을 고려한 스케줄링 기법을 제안한다. 소프트웨어 레벨에서 구현되는 스케줄링 기법은 하드웨어에서 캐시 메모리를 관리하는 방법을 고려해서 프로그램이 수행되는 코어의 위치를 조절해 줌으로서 성능을 향상시킨다. 프로그램이 수행되는 코어의 위치를 조절하기 위해 여러 응용 프로그램이 캐시를 공유할 때 시스템의 성능을 예측하는 모델링 기법을 제안하고, 이를 활용하여 알고리즘 복잡도가 낮고 코어 수가 많은 환경에서도 적용 가능한 스케줄링 기법을 제안한다.
또한 본 연구에서는, 하드웨어와 소프트웨어 기반의 파티셔닝과 스케줄링 기법이 상호작용하는 방식에 착안하여 캐시 메모리 성능 향상을 위해 두 가지 기법을 모두 사용하되, 각 방식의 장점만 취하여 하드웨어 오버헤드를 최소한으로 하는, 실제 시스템에서 쉽게 적용 가능한 방법을 제안한다. 본 연구에서 제안한 방법은 소프트웨어와 하드웨어가 협업해서 캐시자원 경쟁 문제를 해결하는데, 소프트웨어 레벨에서는 스케줄링을 통해 대부분의 캐시자원 경쟁 문제를 해결함으로서 하드웨어에서 필요한 기능을 최소화하고, 하드웨어 레벨에서는 스케줄링만으로는 해결되지 않는 경우에만 간단한 형태의 추가적인 하드웨어를 구현해 성능을 개선한다. 또한 실험을 통해 기존의 복잡한 기법들을 사용하지 않아도 본 연구에서 제안한 간단한 방법으로도 충분히 좋은 캐시 메모리 성능을 얻을 수 있음을 보인다. 이러한 방식은 점점 코어의 개수가 늘어나고 캐시 구조가 복잡해지는 환경에서도 사용 가능한 실용적인 방법으로서 향후 연구에 좋은 방향을 제시할 수 있을 것으로 기대된다.