6 Mart 2010 Cumartesi

Cache Sistemleri

Bu yazı ile yeni bir yazı serisine başlamış bulunmaktayım. Umarım düzenli olarak devam ettiririm. C derneğinde Sistem Programlama ve ile İleri C 1 kursuna başladım. Gerçekten İstanbul'da imkanı olan her programcının 1 kez uğramış olması gereken bir yer. Bu devirde C mi öğrenilir kardeşim? diyenler olabilir ama C herşeyin başlangıcı ve kaynağıdır onu bilmeyen diğerlerini de tam bilemez diye düşünüyorum.(Ya da IRC'de bana dedikleri gibi char* in 2009?) Bu yazı seirisinde C derneğinde tuttuğum notları ve yazdığım kodları buraya koymaya çalışacağım. Umarım bana ve buraya gelenlere bir faydası dokunur ...

  1. Cache Sistemleri
Bilgisayar sistemlerinde pekçok durumda bir yavaş bellek ve hızlı bellek vardır. Yavaş bellek ucuz olduğundan boldur. Hızlı bellek daha küçük miktardadır ve pahalıdır. Örn, RAM hızlı disK yavaş belleği temsil eder. Ya da cpu'nun içindeki bellek hızlı belleği normal RAM yavaş belleği temsil edebilir.
Bu tür durumlarda yavaş belleğin belli bir bölümü hızlı bellekte tutulur. Ve yavaş belleğe erişim miktarı azaltılmaya çalışılır. Bu tür sistemlere cache sistemleri denilmektedir.Bilgi elde edileceği zaman önce hızlı belleğe başvurulur ,hızlı belleğe cache de denir. Burada varsa
doğrudan alınır.Yoksa yavaş belleğe başvurulur. Bilginin alınma hızına cache hit,yoksa cache miss olur. Bir cache sisteminin amacı cache hit oranını yükseltmektir. Buna cache performansı denir. Cache performansı şu öğeler etkiler :
- cache miktarı büyüklüğü,şüphesiz hızlı bellek ne kadar çok olursa yavaş belleğin o kadadr büyük bölümü tutulur performans artar.
- Yavaş belleğin hangi bölümünün tutulacağını belirlemek de önemlidir. Buna cache startejisi denir.
- Cache'in read only veya r/w olması performansı etkiler.

Read Only cache sistemi; hızlı bellek yalnızca okuma amaçlı kullanılır. Bilgi yazılırken doğrudan yavaş belleğe yazılır. Böylece elektril kesilme gibi durumlarda bilgi kaybı engellenir. r/w cache sistemlerine hem okuma hem yazma yapılır.


2.Cache Stretejileri

Cache sistemleri tek bloklu yada çok bloklu tasarlanır. Tek bloklu (single cache line) sistemlerinde yavaş belleğin ardışıl cache kadar bölümü cache'tet tutlur. şüphesz yavaş belleğin hangi bölümünün cache'te olduğu not alınmalıdır. Tek bloklu sistemler ardışıl erişimlerin yoğun olduğu durumlarda etkin olabilmektedir. Fakat ardışıl erişimler söz konusu değilse bu sistemde etkinlik çok azalır. Alternativ yöntem çok bloklu cache (multi cache line) sistemidir. Çok bloklu sistemlerde yavaş bellek bloklara ayrılır. Cache bellek de aynı biçimde bloklanmaktadır.
Böylece yavaş belleğin farklı blokları aynı anda cache içinde bulunur. Bir bölgeye erişilmek istendiğinde önce ,cache'teki bloklarda bu bölgenin olup olmadığına bakılır.
Cache içinde yavaş belleğin hangi blokları tutulmalıdıır? Şüphesiz en çok kulalnılan blokların cache'te tutulması ilk akla gelen yöntemdir.
Fakat bu nasıl tespit eidlir ?
Strateji olarak 2 durum önemlidir. Yavaş belleğin hangi bölümü hızlı bellekte tutulacaktır ve hızlı belleğin hangi bölümü atılacaktır? Bu konuda kullanılan algoritmalar vardır. Özellikle cache sistemlerinde bilgiyi çıkarma işlemi koyma işleminden daha önemlidir. Gelecekteki durum bilinmediğine göre bir chache miss oluştuğunda herzman yavaş belleğin o bloğunun cache'e çekilmesi yoluna gidilebilir. Aksi takdirede yavaş bloğun her kısmı için istatistik yapmak gerekir. Önemli cache startejileri (atım)şunlardır :

  • LFU (Least frequently used):
Bu alg.'da en az cache hit almış cache bloğu cache'ten çıkartılır. Bu yöntemi uyugulamak için her cache bloğu bir sayaçla kontrol edilir.Her cache hit'te sayaç arttırılır,sonra sayacı en düşük olan blok çıkartılır. Şüphesiz yeni alınan blok için ortalama bir sayaç değeri verilmelidir.

  • LRU (Least recently used)
Burada uzun süredir cache hit almayan blokların çıkrtılaması yoluna gidilir. Bu yöntem pekçok sistem için daha etkilidir. Bu yöntemle tipik olarak cache bloklarından ya da onların numaralarından bir bağlı liste oluşturlup ve bir cache hit oluştuğunda o blok bağlı listenin en önüne alınır. böylece bağlı listenin en arkasında son zmanalarda en az kullanılan bloklar kalmış olur. Cache'ten blok atılacağı zaman burdan atılır. LRU yöntemi pekçok olay için iyi bir performans oluşturmaktadır. Örneğin linux işletim sistemi çekirdeklerinde kullanılan cache sistemlerinin çoğu lru'dur.

  • Hibrit Modeller
Bu yöntemlerde birkaç algoritma yöntemin ortalaması dikkate alınır. Örn hem lfu hem de lru değerleri kontrol edilebilir. İkisinin toplam durumuna göre bir karar uygulanır.

  • MRU (Most recently used)
Bazı sistemlerde son erişilen bölgelerin (blokların) gelecekte kullanım miktarlarının azalacağı bilinmektedir. Bu durumda tam tersi olarak cache'ten son zamanlarda en sık kullanılanı atmak uyugun bir yöntemdir. Böyle sistemler ile az karşılaşılmaktadır.

  • MFU (Most frequently used)
Bazı sistemlerde bir bloğun kullanımı arttıkça gelecekte onu kullanım azalır. Örn, belli bir sistemde eğer her bloğun benzer miktarda erişildiğini biliyosak bu durumda cache'te o zamana kadar en kullanılmışı atmak daha mantıklı olur.

3.Cache sistemlerinin kullanılmasına yönelik tipik yöntemler

OS'lerde tamamen çekirdek düzeyinde aşağı seviyeli disk cache sistemi oluşturulur. Buna UNIX dünyasında "buffer cache" denilmektedir. OS'nin çekirdeği son eirşilen disk bloklarını ram'de kullanılmayan bölgelerde saklar ve disk erişimin azaltmaya çalışır. disk cache sistemi disk erişimlerini %70 azaltır. OS'nin en önemli performans konularından birini oluşturur. Örn linux sistemleri mevcut kullanılmayan RAM'i disk cache olarak kullanılmaktadır. Bu cache sistemi r/w'dir. WIN ve UNIX sistemleri genellikle "delayed write" kullanırlar. Bu yöntemde yazma işlemi sırasında diske değil cache'e yazılır. Fakat, cache'in tazelenmesi için çok beklenmez.OS'nin bu amaçla kullanılan kernel treadleri belli periyotlarda cache bloklarını inceler dirty olanları diske yazar. Böylece elektrik kesilmesi gibi durumlarda kayıp ciddi boyutta olmamaktadır.
Memory stick'ler teknoloji olarak belirli sayıda yazmaya izin vermektedir.(Bu yazma sayıları artmaktadır) İşletim sistemleri bu tür aygıtlara yazma yaparken hem hız için hem de bu gerekçe ile cache sistemi kullanabilmektedir. Örn win sistemlerinde bu durum ayarlanabilir.
Yeni win sistemlerinde default durum read only cache sistemidir. Örn linux sistemlerinde r/w kullanılır.
Bugün kullandığımız pc'lerde de donanımsal düzeyde bellek sistemi için cache kullanılmaktadır.
Eskiden cpu'lar yavaştı ve dramlar cpu'lardan daha hızlıydı. Fakat zaman geçtikçe cpu'lar dramlara göre çok hızlandılar. Başa baş noktası 80286 işlemcilerinin kullanıldığı AT makinalarda yakalandı.(80 lerin sonu) Bu cpular 16mhz'de çalışıyordu ve o zamanki ramler 60ns. Bundan sonra artık boardlara cache sistemi eklenmiştir.İlk cache sistemi cpunun dışındaydı vs sram'lerden oluşuyordu. CPU önce sram'e sonra dram'e başvuruyordu. Cpular daha da hızlanınca cpu'nun içine de cache koyulmaya başlandı. Böylece dram 2 aşamada cachelenmekteydi. Cpu'nun içeresindeki cache'e l1 cache diğerine l2 cache deniyordu. Son yıllarda dışsal cache de cpu'nun içeresine kondu. cpu'nun cache miktarını performansta önemli etkisi vardır.Buradaki cache yazılımsal değil tamamen donanımsaldır.

5 Mart 2010 Cuma

New Theme And New Posts

Hi all, who came here to the end of the world by accident :) I decided to post more often to my blog than before (i hope). Therefore new starts need changes ... I changed my blog theme so it is cooler now with a penguin above :) I'm not a designer and dont have idea how to make those cool things so my friend (a great designer) ADK helped me with it. Big thanks goes to him! Btw,you should hire him you wont be sorry believe me :) Well what is going on in my life ?

- After GSOC 2009 i finished my school,so now i'm a Computer Science Engineer (heh it sounds cool), though i dont feel like one.
- I worked for a while as Django/Python freelancer
- Now working as full time developer for Inomera A.Ş. on Netmera Social Platform.
- While writing that post i'm reading my C notes for the course i started.

Well thats, all nothing exciting in my life sorry :) I hope to post here more geeky stuff as i find some free time.