Referans yeri - Locality of reference

Olarak bilgisayar biliminin , referans mevkiinde olarak da bilinen, mevkiinde ilkesi , tekrar tekrar kısa bir süre içinde bellek konumlarında aynı kümesini erişmek için bir işlemci eğilimidir. İki temel referans yerellik türü vardır - zamansal ve uzamsal konum. Zamansal yerellik, belirli verilerin ve/veya kaynakların nispeten kısa bir süre içinde yeniden kullanılması anlamına gelir. Uzamsal konum ( veri konumu olarak da adlandırılır ), nispeten yakın depolama konumlarında veri öğelerinin kullanımını ifade eder. Sıralı yerellik, uzamsal yerelliğin özel bir durumu, veri öğeleri düzenlendiğinde ve bunlara doğrusal olarak erişildiğinde, örneğin öğelerin tek boyutlu bir dizide çaprazlanması gibi meydana gelir .

Yerellik, bilgisayar sistemlerinde meydana gelen bir tür öngörülebilir davranıştır. Güçlü sergileyen sistemler referans mevkiinde gibi tekniklerin kullanılması yoluyla performans optimizasyonu için iyi adaylardır önbelleğe alma , ön yükleme bellek ve gelişmiş için dal prediktörü olarak boru hatları tek bir işlemci çekirdeği aşamasında.

yerellik türleri

Birkaç farklı referans yeri türü vardır:

  • Zamansal konum : Bir noktada belirli bir bellek konumuna başvurulursa, aynı konuma yakın gelecekte tekrar başvurulması muhtemeldir. Aynı bellek konumuna bitişik referanslar arasında zamansal yakınlık vardır. Bu durumda, sonraki başvuruların gecikmesini azaltmak için başvurulan verilerin bir kopyasını daha hızlı bellek deposunda depolamaya çalışmak yaygındır. Zamansal konum, mekansal konumun özel bir durumudur (aşağıya bakınız), yani olası konum mevcut konumla aynı olduğunda.
  • Uzamsal konum : Belirli bir zamanda belirli bir depolama konumuna başvurulursa, yakın gelecekte yakın bellek konumlarına başvurulması muhtemeldir. Bu durumda, sonraki referans için daha hızlı erişim hazırlamanın faydalı olduğu mevcut referansın etrafındaki alanın boyutunu ve şeklini tahmin etmeye çalışmak yaygındır.
    • Bellek konumu (veya veri konumu ): Açıkça bellekle ilgili olan uzamsal konum .
  • Dal konumu : Uzamsal-zamansal koordinat uzayında yolun ileriye dönük kısmı için yalnızca birkaç olası alternatif varsa. Bu, bir talimat döngüsünün basit bir yapıya sahip olduğu veya küçük bir koşullu dallanma talimatları sisteminin olası sonucunun küçük bir dizi olasılıkla sınırlı olduğu durumdur. Şube yerleşimi tipik olarak mekansal yerleşim değildir, çünkü birkaç olasılık birbirinden çok uzakta yer alabilir.
  • Equidistant locality : Mekânsal konum ile şube konumu arasındaki orta yol . Konumlara eşit uzaklıkta bir düzende erişen bir döngü düşünün, yani uzamsal-zamansal koordinat uzayındaki yol noktalı bir çizgidir. Bu durumda, basit bir doğrusal fonksiyon, yakın gelecekte hangi konuma erişileceğini tahmin edebilir.

Sıklıkla ortaya çıkan zamansal ve mekansal yerellikten yararlanmak için bilgi depolama sistemlerinin çoğu hiyerarşiktir . Eşit uzaklık genellikle bir işlemcinin çeşitli önemsiz olmayan artış yönergeleri tarafından desteklenir. Şube konumu için, çağdaş işlemciler gelişmiş şube tahmincilerine sahiptir ve bu tahmin temelinde işlemcinin bellek yöneticisi makul alternatiflerin verilerini toplamaya ve önceden işlemeye çalışır.

alaka

Yerelliğin birkaç nedeni vardır. Bu nedenler, duruma göre ya ulaşılacak hedefler ya da kabul edilecek koşullardır. Aşağıdaki nedenler ayrık değildir ; aslında, aşağıdaki liste en genel durumdan özel durumlara doğru gider:

  • Öngörülebilirlik : Yerellik, bilgisayar sistemlerinde yalnızca bir tür öngörülebilir davranıştır.
  • Programın Yapısı : Yerellik, karar verilebilir sorunları ele almak için bilgisayar programlarının oluşturulma şekli nedeniyle sıklıkla ortaya çıkar. Genellikle ilgili veriler, depolamada yakın konumlarda depolanır. Hesaplamadaki yaygın bir kalıp, her seferinde bir tane olmak üzere birkaç öğenin işlenmesini içerir. Bu, çok fazla işlem yapılırsa, tek öğeye birden fazla kez erişileceği ve dolayısıyla geçici referans yerelliğine yol açacağı anlamına gelir. Ayrıca, bir sonraki öğeye geçmek, bir sonraki öğenin okunacağını, dolayısıyla bellek konumları tipik olarak yığınlar halinde okunduğundan, referansın uzamsal yerelliğini ifade eder.
  • Doğrusal veri yapıları : Yerellik genellikle kodun dizilere veya diğer veri yapılarına dizinlere göre başvurma eğiliminde olan döngüler içermesi nedeniyle oluşur. Sıralı yerellik, uzaysal konumun özel bir durumu, ilgili veri öğelerinin doğrusal olarak düzenlenmesi ve bunlara erişilmesiyle ortaya çıkar. Örneğin, tek boyutlu bir dizideki öğelerin temel adresten en yüksek öğeye basit geçişi, dizinin bellekteki sıralı konumunu kullanır. Eşit uzaklık, doğrusal geçiş, aynı yapı ve boyuta sahip bitişik veri yapılarının daha uzun bir alanı üzerinde olduğunda, her yapının tamamı yerine her yapının karşılıklı olarak karşılık gelen öğelerine eriştiğinde oluşur. Bu, bir matrisin sıralı bir satır matrisi olarak temsil edildiği ve matrisin tek bir sütununa erişmenin gerekli olduğu durumdur.
  • Bellek hiyerarşisi kullanımının verimliliği : Rastgele erişimli bellek , programcıya herhangi bir zamanda herhangi bir yerde okuma veya yazma yeteneği sunsa da, uygulamada gecikme ve verim , referans yerinin arttırılmasıyla geliştirilen önbelleğin verimliliğinden etkilenir . Referansın zayıf konumu, önbellek bozulmasına ve önbellek kirliliğine neden olur ve bundan kaçınmak için, yerelliği zayıf olan veri öğeleri önbellekten atlanabilir.

Genel kullanım

Çoğu zaman referansların önemli bir kısmı kümeler halinde toplanırsa ve bu kümeler sisteminin şekli iyi tahmin edilebilirse, performans optimizasyonu için kullanılabilir. Optimizasyon tekniklerini kullanarak yerellikten yararlanmanın birkaç yolu vardır . Yaygın teknikler şunlardır:

  • Referansların lokalitesinin arttırılması (genellikle yazılım tarafında)
  • Referansların yerelliğinden yararlanma: Genel olarak donanım tarafında elde edilen zamansal ve uzamsal yerellik, hiyerarşik depolama donanımı tarafından büyük harfle yazılabilir. Eşit uzaklık, işlemcilerin uygun şekilde özelleştirilmiş yönergeleri tarafından kullanılabilir, bu olasılık yalnızca donanımın sorumluluğunda değildir, aynı zamanda yapısının söz konusu özel yönergeleri çağıran ikili bir programı derlemeye uygun olup olmadığı da yazılımın sorumluluğundadır. Şube konumu daha ayrıntılı bir olasılıktır, bu nedenle daha fazla geliştirme çabasına ihtiyaç vardır, ancak bu tür bir yerde gelecekteki keşifler için diğerlerine kıyasla çok daha büyük bir rezerv vardır.

Mekansal ve zamansal yerellik kullanımı

hiyerarşik bellek

Ana madde: Bellek hiyerarşisi

Hiyerarşik bellek, uzamsal ve zamansal yerellikten yararlanan ve bellek hiyerarşisinin çeşitli düzeylerinde kullanılabilen bir donanım optimizasyonudur. Sayfalama, açıkça zamansal ve uzamsal yerellikten yararlanır. Önbellek, geçici yerellikten yararlanmanın basit bir örneğidir, çünkü özel olarak tasarlanmış, daha hızlı ancak daha küçük bir bellek alanıdır ve genellikle yakın zamanda başvurulan verileri ve verileri yakın zamanda başvurulan verilerin yakınında tutmak için kullanılır, bu da potansiyel performans artışlarına yol açabilir.

Bir önbellekteki veri öğeleri, ana bellekte uzamsal olarak yakın olan veri öğelerine mutlaka karşılık gelmez; ancak, veri öğeleri her seferinde bir önbellek satırına getirilir . Bu, uzamsal yerelliğin yeniden önemli olduğu anlamına gelir: bir öğeye başvurulursa, birkaç komşu öğe de önbelleğe alınır. Son olarak, birbirine çok yakın başvurulan sonuçlar makine kayıtlarında tutulabildiğinden, zamansal yerellik en alt düzeyde bir rol oynar . Bazı programlama dilleri ( C gibi ), programcının belirli değişkenlerin kayıtlarda tutulmasını önermesine izin verir.

Veri konumu, normal programların tipik bir bellek referans özelliğidir (birçok düzensiz bellek erişim modeli mevcut olsa da). Hiyerarşik bellek düzenini karlı hale getirir. Bilgisayarlarda, veri erişimlerini hızlandırmak için bellek bir hiyerarşiye bölünmüştür. Bellek hiyerarşisinin alt seviyeleri daha yavaş, ancak daha büyük olma eğilimindedir. Böylece, bir program, bellek hiyerarşisinin üst seviyelerinde önbelleğe alınırken belleği kullanırsa ve hiyerarşinin üst seviyelerine, gelecekte kısa sürede kullanılacak verilerin yerini alacak başka verileri getirmekten kaçınırsa, daha yüksek performans elde edecektir. Bu bir idealdir ve bazen elde edilemez.

Tipik bellek hiyerarşisi (erişim süreleri ve önbellek boyutları, tartışma amacıyla 2013 itibariyle kullanılan tipik değerlerin yaklaşık değerleridir; hiyerarşideki gerçek değerler ve gerçek düzey sayıları değişiklik gösterir):

  • CPU kayıtları (8–256 kayıt) – işlemcinin en içteki çekirdeğinin hızıyla anında erişim
  • L1 CPU önbellekleri (32 KB - 512  KB ) – her bir çekirdeğe özel olarak sahip olunan en içteki bellek veriyolu hızıyla hızlı erişim
  • L2 CPU önbellekleri (128 KB - 24  MB ) – ikiz çekirdek arasında paylaşılan bellek veriyolu hızıyla biraz daha yavaş erişim
  • L3 CPU önbellekleri (2 MB - 32  MB ) – aynı işlemcinin daha da fazla çekirdeği arasında paylaşılan bellek veriyolu hızıyla daha da yavaş erişim
  • Ana fiziksel bellek ( RAM ) (256 MB - 64  GB ) – hızı, işlemci ile anakart üzerindeki bellek modülleri arasındaki uzaysal mesafeler ve genel donanım arayüzleri ile sınırlı olan yavaş erişim
  • Disk ( sanal bellek , dosya sistemi ) (1 GB - 256  TB ) – bilgisayarın ana kartı ile disk aygıtları arasındaki daha dar (bit genişliğinde), fiziksel olarak çok daha uzun veri kanalı nedeniyle çok yavaş ve yavaş donanım arayüzünün üstünde gerekli olan yabancı yazılım protokolü
  • Uzak bellek (diğer bilgisayarlar veya bulut) (pratik olarak sınırsız) – hız çok yavaştan aşırı yavaşa değişir

Modern makineler, daha düşük bellek bloklarını bellek hiyerarşisinin bir sonraki düzeyine okuma eğilimindedir. Bu, kullanılan belleğin yerini alırsa, işletim sistemi hangi verilere en az (veya en son) erişileceğini tahmin etmeye ve bunları bellek hiyerarşisinde aşağı taşımaya çalışır. Tahmin algoritmaları, donanım karmaşıklığını azaltmak için basit olma eğilimindedir, ancak biraz daha karmaşık hale geliyorlar.

matris çarpımı

Yaygın bir örnek, matris çarpımıdır : 

for i in 0..n
  for j in 0..m
    for k in 0..p
      C[i][j] = C[i][j] + A[i][k] * B[k][j];

Döngü sırasını jve için değiştirerek, kbüyük matris çarpımlarındaki hızlanma, en azından bitişik dizi öğelerini son boyuta koyan diller için çarpıcı hale gelir. Bu matematiksel sonucu değiştirmez, ancak verimliliği artırır. Bu durumda "büyük", her matriste yaklaşık olarak 100.000'den fazla öğe veya matrislerin L1 ve L2 önbelleklerine sığmayacağı şekilde yeterli adreslenebilir bellek anlamına gelir. 

for i in 0..n
  for k in 0..p
    for j in 0..m
      C[i][j] = C[i][j] + A[i][k] * B[k][j];

Bu hızlandırmanın nedeni, ilk durumda, okumaların A[i][k]önbellekte olmasıdır ( kindeks bitişik, son boyut olduğundan), ancak B[k][j]değildir, bu nedenle üzerinde bir önbellek kaçırma cezası vardır B[k][j]. C[i][j]alakasız, çünkü iç döngüden dışarı çekilebilir -- döngü değişkeni var k. 

for i in 0..n
  for j in 0..m
    temp = C[i][j]
    for k in 0..p
      temp = temp + A[i][k] * B[k][j];
    C[i][j] = temp

İkinci durumda, okumaları ve yazmaları C[i][j]önbellekte, okumaları B[k][j]önbellekte ve okumaları A[i][k]iç döngüden çıkarılabilir. 

for i in 0..n
  for k in 0..p
    temp = A[i][k]
    for j in 0..m
      C[i][j] = C[i][j] + temp * B[k][j];

Böylece, ikinci örnekte iç döngüde önbellek kaçırma cezası yokken, ilk örnekte önbellek cezası var.

2014 yılındaki bir işlemcide, ikinci durum, C ile yazıldığında ve ile derlendiğinde , ilk durumdan yaklaşık beş kat daha hızlıdır gcc -O3. (Demonte edilen kodun dikkatli bir incelemesi, ilk durumda GCC'nin SIMD talimatlarını kullandığını ve ikinci durumda kullanmadığını, ancak önbellek cezasının SIMD kazancından çok daha kötü olduğunu gösterir.)

Yukarıdaki örnekte, bloklama adı verilen bir teknik kullanılarak zamansal konum da iyileştirilebilir . Daha büyük matris, eşit boyutlu alt matrislere bölünebilir, böylece daha küçük bloklara bellekteyken birkaç kez başvurulabilir (çarpılabilir). Bu örneğin SIZE x SIZE boyutlarındaki kare matrisler için işe yaradığını, ancak uygun olduğunda SIZE_I, SIZE_J ve SIZE_K değiştirilerek rastgele matrisler için kolayca genişletilebileceğini unutmayın. 

for (ii = 0; ii < SIZE; ii += BLOCK_SIZE)
  for (kk = 0; kk < SIZE; kk += BLOCK_SIZE)
    for (jj = 0; jj < SIZE; jj += BLOCK_SIZE)
      maxi = min(ii + BLOCK_SIZE, SIZE);
      for (i = ii; i < maxi; i++)
        maxk = min(kk + BLOCK_SIZE, SIZE);
        for (k = kk; k < maxk; k++)
          maxj = min(jj + BLOCK_SIZE, SIZE);
          for (j = jj; j < maxj; j++)
            C[i][j] = C[i][j] + A[i][k] * B[k][j];

Yukarıdaki çözümün zamansal konumu sağlanmıştır, çünkü bir blok, devam etmeden önce birkaç kez kullanılabilir, böylece daha az sıklıkla belleğe girip çıkar. Ardışık bellek adreslerine sahip öğeler, bellek hiyerarşisini birlikte yukarı çekme eğiliminde olduklarından, uzaysal konum iyileştirilir.

Ayrıca bakınız

Referanslar

bibliyografya