Skorbord - Scoreboarding

Skorbordlama , ilk olarak CDC 6600 bilgisayarında kullanılan, talimatların herhangi bir çakışma olmadığında ve donanım mevcut olduğunda sıra dışı bir şekilde yürütülebilmesi için dinamik olarak zamanlanması için kullanılan merkezi bir yöntemdir .

Bir puan tablosunda, her talimatın veri bağımlılıkları günlüğe kaydedilir, izlenir ve her zaman kesinlikle gözlemlenir. Talimatlar, yalnızca skorbord önceden verilmiş ("uçuşta") talimatlarla herhangi bir çelişki olmadığını belirlediğinde yayınlanır. Bir talimat verilmesi güvenli olmadığı için (veya yetersiz kaynak bulunduğundan) durdurulursa, skorbord, durdurulan talimat verilmeden önce tüm bağımlılıklar çözülene kadar yürütme talimatlarının akışını izler. Özünde: okumalar, yazma tehlikesi olmadığında devam eder ve yazmalar, okuma tehlikesi olmadığında devam eder.

Scoreboarding, esasen, veri akışı dillerinde görülen aynı temel algoritmanın bir donanım uygulamasıdır ve programlama dili çalışma zamanında aynı mantığın uygulandığı bir Yönlendirilmiş Döngüsel Grafik oluşturur .

Aşamalar

Talimatlar sırayla çözülür ve aşağıdaki dört aşamadan geçer.

  1. Sorun : Sistem, bu talimat tarafından hangi kayıtların okunup yazılacağını kontrol ediyor ve WAR ve RAW ve WAW çakışmalarının tespit edildiği yer. RAW ve WAR tehlikeleri, aşağıdaki aşamalarda ihtiyaç duyulacağı için bir Bağımlılık Matrisi (orijinal 6600 tasarımında SR NOR mandallarından oluşturulmuştur) kullanılarak kaydedilir. Eşzamanlı olarak, talimat sırasını Yönlendirilmiş Döngüsel Grafik olarak kaydeden ikinci bir Matrise bir giriş kaydedilir . Çıktı bağımlılıklarını önlemek için ( WAW – Write after Write) komut, aynı register'a yazmayı amaçlayan komutlar tamamlanana kadar durdurulur. Talimat, gerekli işlevsel birimler şu anda meşgul olduğunda da durdurulur. *Baştan sona %100 izlenebilir olmadıkça hiçbir talimat verilmez*.
  2. İşlenenleri oku : Bir talimat verildikten ve gerekli donanım modülüne (Thornton'ın kitabında Hesaplama Birimi olarak adlandırılır) doğru bir şekilde tahsis edildikten sonra, Birim tüm işlenenler kullanılabilir hale gelene kadar bekler. Yalnızca okuma , diğer tüm Birimlerden yazma bağımlılıkları ( RAW – Yazdıktan Sonra Oku) çıkarıldığında devam eder. Kayıt Dosya Bağlantı Noktası çekişmesini önlemek için, Öncelik Seçici bir Hesaplama Birimi seçer (birkaç Birimin tehlikeden arındırılmış olması durumunda).
  3. Yürütme : Tüm işlenenler alındığında, Hesaplama Birimi yürütmeye başlar. Sonuç hazır olduktan sonra skorbord bildirilir.
  4. Sonuç Yaz : Bu aşamada sonuç hazırdır ancak hedef kaydına henüz yazılmamıştır. Ünite tüm ( WAR – Okumadan Sonra Yazma) tehlikelerinden temizlenene kadar yazma işlemi devam etmeyebilir . Buradaki tek ek gecikmeler, kayıt dosyası bağlantı noktalarının kullanılabilirliğine bağlıdır: 6600'de, yazma bağlantı noktası başına bir sonuç seçmek için bir Öncelik Seçici kullanıldı. Bir kez yazıldığında, ünite artık meşgul değil olarak işaretlenir ve tüm tehlikeler ve durum atlanır. Yalnızca "Gölge" özelliğine sahip gelişmiş (arttırılmış, kesin) puan tablolarında Sonuç Yazma aşamasının önleneceğini (geciktirileceğini) unutmayın. Orijinal 6600 bu yeteneğe sahip değildi.

Sadece içinde devam Okur yukarıda not etmek önemlidir yokluğunda ait yazma tehlikeler ve bu yazma içinde devam yokluğunda arasında Oku tehlikeler. Bu mantıklıdır ancak beklentilere karşı kontrendikedir. Özellikle, diğer birimlere bir kayıttaki mevcut değeri okuma fırsatı vermek için , yenisiyle üzerine yazmadan önce Yazmaların okumadan sonra yazmak için beklemesi gerektiğini unutmayın . Bu nedenle, yazarlar neden WaR tehlikelerinin yokluğuna kadar beklemek zorundadır .

Veri yapısı

Talimatların yürütülmesini kontrol etmek için puan tablosunda üç durum tablosu bulunur:

  • Komut Durumu : Yürütülen her komut için dört aşamadan hangisinde olduğunu gösterir.
  • İşlevsel Birim Durumu : Her bir işlevsel birimin durumunu gösterir. Her fonksiyon birimi tabloda 9 alan tutar:
    • Meşgul: Ünitenin kullanılıp kullanılmadığını gösterir.
    • Op: Ünitede gerçekleştirilecek işlem (örn. MUL, DIV veya MOD)
    • F i : Hedef kaydı
    • F j ,F k : Kaynak-kayıt numaraları
    • Q j ,Q k : F j , F k kaynak kayıtlarını üretecek fonksiyonel birimler
    • R j ,R k : F j , F k'nin ne zaman hazır olduğunu ve henüz okunmadığını gösteren bayraklar .
  • Kayıt Durumu : Her kayıt için hangi fonksiyon biriminin sonuçları ona yazacağını belirtir.

Orijinal 6600 algoritması

Orijinal patentte ana hatlarıyla belirtilen çetele kontrolü için ayrıntılı algoritma aşağıda açıklanmıştır: 

 function issue(op, dst, src1, src2)
    wait until (!Busy[FU] AND !Result[dst]); // FU can be any functional unit that can execute operation op
    Busy[FU] ← Yes;
    Op[FU] ← op;
    Fi[FU] ← dst;
    Fj[FU] ← src1;
    Fk[FU] ← src2;
    Qj[FU] ← Result[src1];
    Qk[FU] ← Result[src2];
    Rj[FU] ← Qj[FU] == 0;
    Rk[FU] ← Qk[FU] == 0;
    Result[dst] ← FU;

 function read_operands(FU)
    wait until (Rj[FU] AND Rk[FU]);
    Rj[FU] ← No;
    Rk[FU] ← No;

 function execute(FU)
    // Execute whatever FU must do

 function write_back(FU)
    wait until (∀f {(Fj[f]≠Fi[FU] OR Rj[f]=No) AND (Fk[f]≠Fi[FU] OR Rk[f]=No)})
    foreach f do
        if Qj[f]=FU then Rj[f] ← Yes;
        if Qk[f]=FU then Rk[f] ← Yes;
    Result[Fi[FU]] ← 0; // 0 means no FU generates the register's result
    RegFile[Fi[FU]] ← computed value;
    Busy[FU] ← No;

Uyarılar

Thornton'ın kitabı, modern bilgi işlem terminolojisinin öncesine dayanmaktadır.

  • İşlev Birimleri (boru hatları) "Hesaplama Birimleri" olarak adlandırıldı.
  • "First Order Conflict", tüm Birimlerin meşgul olması nedeniyle hem duraklamayı hem de WAW çakışmasını kapsıyordu .
  • "İkinci Derece Çatışma", RAW çatışması için kullanılan terimdi .
  • "Üçüncü Derece Çatışması", SAVAŞ çatışmasını kapsıyordu .

Durma, yalnızca sorun aşamasında, "Birinci Derece" çakışmaları algılandığında meydana geldi. Tomasulo algoritması gibi bazı diğer teknikler, ek olarak kayıt yeniden adlandırma ile WAW bağımlılıklarını çözer . Orijinal CDC 6600 , tasarımcılarının ürünü teslim etmesi gerektiğinden muhtemelen WAW tehlike takibine sahip değildi ve ardından 7600'e geçti: bunun yerine oyalamak en uygun seçenekti. Kayıtların yeniden adlandırılmasının Skorbordlara eklenmemesi için teknik bir neden yoktur .

Her iki algoritmanın bir analizi Luke Leighton tarafından yapıldı ve Tomasulo algoritması ile 6600 Scoreboard algoritması arasındaki denkliği gösteren bir dönüşüm süreci özetlendi. WAW tehlikeleri çözümü, orijinal algoritmada gerçekten eksiktir: 6600, Yazma Tehlikesinin ilk ortaya çıkışında duracaktır.

Ayrıca bakınız

Referanslar

  • Glenford Myers , "Bir mikroişlemci çipinde çetele kaydı", Amerika Birleşik Devletleri Patenti 4891753

Dış bağlantılar