Reducing coherency traffic volume in chip multiprocessors through pointer analysis

Abstract

Çok çekirdekli işlemcilerdeki (CMP) çekirdek sayısı arttıkça önbellek tutarlılığını verimli bir şekilde sağlamak zorlaşmaktadır. Dinleme temelli protokoller küçük çaplı sistemler için uygun çözümler olsa da bant genişliğine bindirdikleri ek yükten dolayı daha geniş sistemler için verimli olmamaktadırlar. Bu sebepten geniş çaplı CMP'ler dizin temelli çözümlere ihtiyaç duyarlar. Dizinin görevi bütün bellek bloklarının hangi çekirdeğin önbelleğinde kopyasının bulunduğunu tutmaktır. Dizin sadece ilgili blokları tutan önbelleklere mesaj yollar ve önbelleğe yapılan eş zamanlı erişim isteklerini düzenler. Dizin temelli protokoller çok sayıda çekirdeğe ölçeklenirken, başarım, ağ trafiği ve bant genişliği önemli problemler olmaktadır.Bu tezde, paylaşımlı bellek kullanan CMP'lerde dizin temelli protokollerin verimini arttıracak yazılım temelli bir çözüm sunmaktayız. Çok iş parçacıklı uygulamalarda, veri erişimlerinin bazıları önbellek tutarlılığını bozmaz ancak yine de çekirdekler arasında tutarlılık mesajları üretir. Örneğin, salt okunur (özel) veriler bu kategoride değerlendirilebilir. Öte yandan, verilere en az iki çekirdeğin eriştiği ve bunların en az birinin bir yazma işlemi olduğu takdirde ilgili erişilen veriye paylaşılan veriler denir. Önerdiğimiz sistemde, özel veriler ve paylaşılan veriler derleme zamanı belirlenir ve önbellek tutarlılık protokolü yalnızca paylaşılan veriler için uygulanır. Bu çalışmada, yaklaşımımızı iki aşamalı olarak uyguluyoruz. İlk olarak, bir programı analiz etmek ve özel komutlarını, yani derleme zamanında özel veriyi yükleyen veya depolayan talimatları işaretlemek için Andersen'in işaretçi analizini kullanıyoruz. İkinci olarak, Sniper Multi-Core Simulator kullanarak önerilen donanım ayarlarında testleri çalıştırıyoruz. Yaklaşımımızı test etmek için SPLASH-2 ve PARSEC-2.1 paralel uygulamalarını kullandık. Simülasyon sonuçları, yaklaşımımızın döngü sayısını, dinamik rastgele erişimli bellek (DRAM) erişimlerini ve tutarlılık trafiğini azalttığını göstermektedir.

With increasing number of cores in chip multiprocessors (CMPs), it gets more challenging to provide cache coherency efficiently. Although snooping based protocols are appropriate solutions to small scale systems, they are inefficient for large systems because of the limited bandwidth. Therefore, large scale CMPs require directory based solutions where a hardware structure called directory holds the information. This directory keeps track of all memory blocks and which core's cache stores a copy of these blocks. The directory sends messages only to caches that store relevant blocks and also coordinates simultaneous accesses to a cache block. As directory based protocols scaled to many cores, performance, network-on-chip (NoC) traffic, and bandwidth become major problems.In this thesis, we present software mechanisms to improve effectiveness of directory based cache coherency on CMPs with shared memory. In multithreaded applications, some of the data accesses do not disrupt cache coherency, but they still produce coherency messages among cores. For example, read-only (private) data can be considered in this category. On the other hand, if data is accessed by at least two cores and at least one of them is a write operation, it is called shared data. In our proposed system, private data and shared data are determined at compile time, and cache coherency protocol only applies to shared data. We implement our approach in two stages. First, we use Andersen's pointer analysis to analyze a program and mark its private instructions, i.e instructions that load or store private data, at compile time. Second, we run the program in Sniper Multi-Core Simulator/cite{Carlson} with the proposed hardware configuration. We used SPLASH-2 and PARSEC-2.1 parallel benchmarks to test our approach. Simulation results show that our approach reduces cycle count, dynamic random access memory (DRAM) accesses, and coherency traffic.