Cache Coherence

BM 311 Bilgisayar Mimarisi Dersi

Cache Coherence ve Cache Coherence

Protokolleri Araştırma Ödevi

Kasım 2009

GİRİŞ

Bu araştırma ödevinde cache coherency problemi, bu problemin neden kaynaklandığı, problemin çözümü için geliştirilmiş protokoller araştırılmıştır. Bu probleme çözüm getiren protokollerin nasıl sınıflandırıldı, birbirlerine göre ne tür avantajları ve dezavantajarı olduğu incelenmiştir. Protokollerin izahında şekil ve grafiklerden yararlanılmıştır. Günümüzde hangi protokollerin neden daha fazla tercih edildikleri konusuna değinilmiştir ve bunun nedenleri araştırılmasına gayret gösterilmiştir. Tüm bu araştırmalara başlanmadan önce önbellek kavramı üzerinde de durulmuş ve özümsenmiştir. Neden önbellek kullanıldığı irdelenmiş, günümüzün vazgeçilmezi olan çok çekirdekli işlemcilerinde önbellek kullanımının nasıl olduğu araştırılmıştır.

Cache ve Cache Coherency

Cache’in dilimizdeki karşılığı önbellek, coherency’nin karşılığı da uyum, tutarlıktır. Yani cache coherency kavramı önbellek tutarlığı anlamına gelmektedir.

Cache yapısı işlemcilerde hızı arttırmak için kullanılan bir yapıdır. Cache işlemcilerin gelişim tarihine bakılırsa işlemcilerin hızının arttırılması noktasında önemli bir kilometre taşıdır. İşlemciler yürütecekleri komutları ve üzerinde değişiklik/işlem yapacakları verileri bilgisayarın hafızasından alırlar. Bilgisayarlarda kullanılan hafızalarda saklanan bit başına fiyat ile bir bite erişim süresi arasında ters orantı vardır. Yani bir bite erişim süresi ne kadar arttırılırsa o hafıza elemanının bit başına maliyeti de o derece artmaktadır. Bu nedenle bilgisayardaki tüm hafıza birimlerinin hızı teknolojini bize verdiği son hızda değildir. Öyle olsaydı bilgisayarlar kimsenin alamayacağı derecede pahalı olurdu. Maliyet-performans ilişkisi göz önünde bulundurulduğunda bilgisayarlarda hem yavaş çalışan, saklama kapasitesi fazla olan ve bit başına maliyeti az olan hafıza elemanları, hem de bit başına maliyeti fazla olan, saklama kapasitesi düşük ama bir bite erişim süresi fazla olan hafıza elemanları birlikte kullanılmak durumundadır. Bu sayede bilgisayar endüstrisi yüksek hızlı ve nispeten ucuz bilgisayarlar üretebilmektedirler. Cache bellek teknolojisi de bu amaca hizmet etmektedir. İşlemciye yakın konumlanırlar ve hızları fazladır. Boyutları ise RAM belleğe ve sabitdiske oranla oldukça küçüktür.

Günümüzün vazgeçilmezlerinden biri de çok çekirdekli işlemcilerdir. Bilgisayar endüstrisinde çok çekirdekli işlemci teknolojisi cache bellek teknolojisinden sonra ortaya çıkmıştır ancak bu teknoloji cache bellek teknolojisinin öneminden bir şey eksiltmemiştir. Cache bellekle birlikte birden fazla işlemcinin kullanılması tutarlılık probleminin doğmasına neden olmuştur. Birden fazla işlemci bir programı çalıştırırken ya da bir veri işlenirken bir değişken cachede tutuluyorsa ve bu değişkene cacheden birinci işlemci erişiyor, ardından da ikinci işlemci erişiyorsa ikinci işlemcinin eriştiği alanın daha önce birinci işlemci tarafından değiştirilmiş olma olasılığı ortaya çıkıyor. Bu durumda ikinci işlemci alması gereken asıl veriyi alamıyor, bunun yerine birinci işlemcinin değiştirdiği veriyi alıyor.(Bakın Şekil-1) Bunun sonucunda da ikinci işlemci yanlış input aldığından sonucu da hatalı üretiyor, bu hatanın diğer hesaplamalara da sirayet etmesi kuvvetle muhtemel hale geliyor. Bu durum literatürde “Cache Coherency Problem” olarak geçmektedir. Bu problem aslında daha genel bir bilgisayar ya da hafıza problemi olan memory coherency’nin bir alt dalı, bir parçasıdır. Bu parça cachelerle ilgili olduğundan bu adı alır. Coherency kelimesi yerine bazı kaynaklarda coherence kelimesi de kullanılmaktadır. İkisi de aynı kavramı/sorunu ifade etmekte kullanılır.

Şekil-1

Tutarlılık sorununun üç temel nedeni vardır. Bunlar:

1-Yazılabilir verilerin paylaşılması(Sharing of writable data)

2-Proseslerin yer değiştirmesi(Process migration)

3-Giriş Çıkış hareketleri(I/O activities)

Tutarlık problemi genellikle çok çekirdekli işlemcilerin L1 önbellekleriyle L2 paylaşımlı önbellekleri arasında yaşanmaktadır. Bu durum Şekil-2 de gösterilmektedir.

Şekil 2

Şekildeki numaralar takip edilecek olursa problem net bir şekilde gözükmektedir. Burada L1 1. İşlemcinin özel önbelleği, L1 ikinci işlemcinin özel önbelleği ve L2 iki işlemcinin de kullanabildiği genel önbellek olmak üzere toplamda üç adet önbellek bulunmaktadır. 1. İşlemcinin özel belleğine ikinci işlemci, ikinci işlemcinin özel belleğine de birinci işlemci doğrudan erişemez, buradaki değişiklikleri göremez. 1. Adımda L2 de x değişkenin değeri 100 olarak tutulmaktadır, 2. Adımda bu değer 1. İşlemcinin L1 önbelleği tarafından okunur. 3. Adımda aynı okuma işlemini bu sefer 2. İşlemcinin önbelleği yapar. 4. Adımda 1. İşlemci x değişkeninin değerini 120 olarak değiştirir ve bunu kendi özel önbelleğinde tutar, 5. Adımda bu sefer 2. İşlemci x değerini değiştirir ve 90 yapar. 2. İşlemci de yaptığı değişikliği kendi önbelleğinde tutar. Ardından 6. Adımda 1. İşlemci L2 genel önbelleğine x değişkeninin değerini 120 olarak yazar, 7. Adımda da 2. İşlemci L2 genel önbelleğine erişir ve x değerini 90 olarak kaydeder. Bu noktada 1. İşlemcinin 6. Adımda gerçekleştirdiği x=120 kaydı kaybolmuş olur. İşte bu tutarlık sorunudur.

Önbellek tutarlılığı konusunda veri yapılarına yaklaşılacak olursa, veri aşağıdaki üç ana başlıkta sınıflandırılır. Bu sınıflandırılma konunun daha iyi kavranması açısından önemlidir.

·         Sadece okunabilir(read only) veriler. Bu tür veriler herhangi bir cache coherence probleminde neden olmadan kopyalanarak çoğaltılabilir ve taşınabilir.

·         Paylaşılan yazılabilir veri yapıları. Bu veri yapısının kullanıldığı işlemlerde cache coherency problemi görülür.

·         Özel yazılabilir veri yapıları (private writable data structures). Bu yapıdaki veriler sadece ait oldukları processlerin taşınması sonucunda cache coherency’ye neden olurlar.

Tutarlık Sorununun Çözümünde Kullanılan Yaklaşımlar

Önbelleğin tutarlık probleminin önüne geçmek için çeşitli protokoller geliştirilmiştir. Bu protokolleri temelde iki ana bölümde sınıflandırabiliriz. Yazılım tabanlı protokoller ve donanım tabanlı protokoller.

1-Yazılım Tabanlı Çözümler

Her bir işlemciye bir önbellek tahsis edilir. Bu önbelleklere memory’den veri alınırken sadece read-only veriler ve paylaşılmayan veriler alınır. Bu tanımın dışında kalan veriler önbelleğe alınmaz, memoryde kalır, bu sayede karışıklık temelden halledilmiş olunur. Hangi verinin alınıp hangi verinin alınmayacağını derleyici belirler ve verileri önbelleklenebilir ve önbelleklenemez olarak işaretler. Cache alınacak verinin alınıp alınmaması noktasındaki kararı esasen derleyici vermiş olur. Bu yöntem sorunu halletmesine rağmen birçok verinin önbelleğe alınmasını engellediğinden istenen performans artışını sağlayamaz.

Bir başka yazılım tabanlı çözümünde ise writable veriler sadece bir cachde tutulur. Bellek bloklarının durumunun tutulduğu bir tablo kullanılır. Bu sayede blokların read-only mi yoksa read/write mı olduğu kontrol edilebilir. Yalnızca okunabilenlerin tüm cachlerde kopyaları vardır. Read/write bloğu ise sadece bir önbellekte tutulur. Bu sayede r/w da bir değişkenin değeri değiştirildiğinde diğer önbellekler bundan etkilenmez.

Yazılım tabanlı çözümler donanım tabanlı çözümlere oranla daha yavaştırlar. Bu nedenle fazla tercih edilmezler.

2-Donanım Tabanlı Çözümler

Donanım tabanlı çözümler yazılım tabanlılara oranla daha fazla tercih edilmektedirler. Donanım tabanlı çözümler de temelde iki başlık altında toplanırlar. Snooping ve Directory protokolleridir. Bir başka değişle trafik gözetleme ve dizin protokolleridir.

2.1- Snooping

Bus yapısının kullanıldığı çok çekirdekli işlemcilerde kullanılırlar. Önbellek denetleyicisi sürekli bus’ı izler. Burada busı izlemesinin sebebi diğer önbelleklerde writable bir değişkenin değerinin değişip değişmediğinin kontrolüdür. Eğer kendisi bir değişkenin değerini değiştirmişse bunu bus aracılığıyla diğer tüm birimlere yollar. Bu sayede her değişiklikten her birimin haberi olur. Ancak birim sayısı arttıkça taktir edileceği gibi bustaki trafik de artmaktadır ve bu da performansı olumsuz etkilemektedir. Bu modelin ölçeklenebilirliği diğer donanım tabanlı modele göre azdır. Böyle bir dezavantaja sahip olmasına rağmen yazılım tabanlı çözümlerden daha iyi bir performans sergiler.

Şekil 3

Şekil 4

Snooping(trafik gözetleme) protokollerinin tercih edilme nedeni directory protokollerine göre uygulanmasının daha kolay olmasıdır. Ayrıca bu protokolün daha verimli çalışmasını sağlayan yöntemlerde vardır. Bunlardan kısaca bahsedecek olursak:

·         Protokol yayın sayısı azaltılarak işletilir.  Bu yaklaşıma Coarse-grain coherence tracking adı verilir.

·         Protokoldeki arabağlantılar daha güçlü bir hale getirilmek üzere güncellenir. Örneğin protokol ring arabağlantı ile çalıştırılabilir.

2.2-Directory

Bu protokollerde bellek erişim sıraları bir dizin tarafından takip edilir.

Şekil 5

 Başka bir ifadeyle hangi bellekte ne tarz değişiklikler yapıldığı bir veya birden fazla dizinde tutulur, bu sayede tutarsızlık yaratacak eylemlerin yapılmasına izin verilmez. Bu çözüm bazen deadlocka neden olsada özellikle fazla sayıda işlemcinin birbirine bağlandığı sistemlerde kullanılmaya uygundur. Örneğin 64 ya da daha fazla işlemcisi olan bir sistemde snooping kullanmak çok zor olacaktır, bus da oluşacak trafik yoğun olacağından, ancak directory kullanımı böyle bir sistem için daha uygun olacaktı.

Tutarlık Sorununun Çözümünde Kullanılan Protokoller

            Protokollerin birçoğu isimlerini mümkün durumların baş harfinden alır. Aşağıdaki protokollerin hepsi cache coherence problemini çözmek için tasarlanmıştı.

MSI protokolü

Protokolün 3 durumu vardır. Bunlar:

Modified: Blok değiştirilmiştir.

Shared:  Blok değiştirilmemiş ve en az bir önbellekte bulunmaktadır.

Invalid: bu durumdaki blok geçersizdir.

Protokolün daha iyi anlaşılması için aşağıdaki şekil incelenebilir.

Şekil 6

Bu şekilde iki tane cache arasındaki değiştirilebilirlik gösterilmektedir. Örneğin modified durumdaki bir bloğa diğer cachein modified bloğu erişemezken invalid durumundaki bloğu erişebilir.

Bu protokol SGI 4D’de kullanılmıştır.

Günümüzde çoğu sistem bu protokolün varyasyonlarını kullanır. Örneğin MESI protokolü bu protokoldeki durumların yanında trafiği azaltmak amacıyla bir de exclusive durumunu barındırı. Keza MOSI protokolü de MSI’ın geliştirilmesiyle ortaya çıkmıştır, fazladan owned durumunu içinde barındırır.

 MESI Protokolü

           

 Yukarıda bahsettiğim gibi MSI protokolünün biraz gelişmiş halidir. Durumların üçünü yukarıda açıkladığım için tekrar yazmıyorum.  University of Illinois’de geliştirildiği için İllinois protokolü olarak da adlandırılır.

Başka önbellekte bu blok yok.

Exclusive:

MOSI protokolü

Owned durumu o bloğa hangi işlemcinin sahip olduğunu gösterir. 3 durumu daha vardır, yukarıda da bahsettiğim gibi bu 3 durum MSI’ınkilerle aynıdır. MSI’dan daha verimlidir. Bunu sağlayan da fazladan kullanılan owned durumudur.

Şekil 8

MOESI protokolü

            Bu protokol diğer tüm cache coherence protokollerindeki durumların hepsini birden kullanır. MESI protokolündeki dört duruma ilave olarak owned durumu vardır. Bu durum MOSI protokolünde açıklandığı gibidir.

Şekil 9

MERSI protokolü

MERSI protocolü PowerPC G4’de kullanılmıştır. % durumludur. Modified (M), Exclusive (E), Read Only or Recent (R), Shared (S) and Invalid (I).  M, E, S ve I durumları  MESI protokolündeki gibidir. Erişim tablosu aşağıda verilmiştir.

Şekil 10

MESIF Protokolü

Intel tarafından geliştirilmiş bir tutatlık protokolüdür.  5 durumu vardır. Bunlar: Modified (M), Exclusive (E), Shared (S), Invalid (I) ve Forward (F). M, E, S ve I durumları  MESI protokolündeki gibidir. Erişim tablosu aşağıda verilmiştir.

Şekil 11

Write-once protokolü

            İlk olarak 1983 yılında James R. Goodman tarafından ortaya konmuştur. 4 duruma sahiptir.

Invalid: Bu blok hafızadakinin tutarsız bir kopyasıdır.

Valid: Bu blok tutarlı bir yapıya sahiptir, paylaşılabilir ama değiştirilemez.

Reserved: bu blok sadece hafızanın kopyasıdır ancak yine de tutarlıdır.

Dirty: Bu blok hafızadaki bloğun tutarsız bir kopyası olduğunu gözterir. Bir veya birden fazla değiştirilmiştir.

            Protokolün durumlar arası erişim tablosu aşağıda verilmiştir.

Şekil 12

Firefly protokolü

            DEC Firefly’da kullanılmıştır. DEC Systems Research Center tarafından geliştirilmiştir. Üç duruma sahiptir. Bunlar valid-exclusive, shared ve dirtydir. Shared ve dirty durumları yukarıda diğer protokollerde açıkladığım gibidir. Valid-exclusive durumu bloğun memorydeki verinin tutarlı bir kopyası olduğunu ifade eder. Aynı zamanda verinin mevcut önbelleklerde sade bir kopyasının olduğunu  belirtir.

Dragon protokolü

Xerox Dragon çok işlemcili iş istasyonlarında kullanılmıştır. Xerox PARC tarafından geliştirilmiştir. Durumlar arası erişim izin tablosu aşağıdaki gibidir.

Şekil 13

            Beş durum vardır. Bunlar: invalid, clean shared-clean, dirty ve shared-dirty’dir. Bu durumlar MOESI protokolündeki durumlarla örtüşür. Örtüşenlerin sıralaması: IESMO.

Sonuç

Bu araştırma ödevinde cache belleklerin multiprocessorlarda kullanılmadında ortaya çıkan cache coherence problemi araştırılmıştı. Bu problemin işlemcilerin memorydeki bir veriyi kendi özel önbelleklerine aldıklarında tutarsızlık oluşabilmesi olarak tanımlanmıştır ve hangi durumlarda tutarsızlık oluşacağı örnekleriyle ve şekilli anlatımlarla ortaya konmuştur. Bu tutarsızlıkları gidermek için ortaya atılan yaklaşımlar incelenmiştir. Bu yaklaşımlar sınıflandırılmıştır ve birbirleri arasındaki avantaj dezavantajlarına değinilmiştir. Hangi sistemlerde hangi yaklaşımın kullanılmasının performans açısından daha iyi olduğu açıklanmıştır. Literatürde geçen ve bilgisayar endüstrisinde de üretilen ürünlerde kullanılan cache coherence protokollerinden bahsedilmiştir. Bu protokollerin içindeki durumlar açıklanmıştır. Bu durumlara sahip veri blokları arasındaki erişim ilişkisi tablolar yardımıyla gösterilmiştir, bu sayede konu daha iyi kavranmıştır.

Kaynaklar

1.      Handy, Jim. The Cache Memory Book. Academic Press, Inc., 1998. ISBN 0-12-322980-4

2.      http://www.eecg.toronto.edu/parallel/parallel/numachin.hier/node5.html

3.      http://6004.csail.mit.edu/Spring98/Lectures/lect23/sld001.htm

4.      http://www.cmpe.boun.edu.tr/courses/cmpe511/fall2004/Mehmet%20Senvar% 20 -% 20Cache% 20Coherence% 20Protocols.ppt

5.      http://www.cs.wisc.edu/multifacet/theses/michael_marty_phd.pdf