Tomasulo algoritması

Tomasulo algoritması, bir işlemcinin buyrukları program sırasından bağımsız olarak, veri bağımlılıkları el verdikçe yürütmesini sağlayan bir donanım algoritmasıdır. IBM'de çalışan Robert Tomasulo tarafından geliştirilen algoritma, ilk kez 1967'de piyasaya sürülen IBM System/360 Model 91 bilgisayarının kayan nokta biriminde kullanılmıştır. Algoritma, çağdaş sırasız yürütüm yapan işlemcilerin temelini oluşturur.

Sıralı yürütmede bir buyruk, kendisinden önceki buyruklar bitmeden başlayamaz; bu durum, işlenenleri henüz hazır olmayan bir buyruğun, hazır olan sonraki buyrukları da bekletmesine yol açar. Tomasulo algoritması, işlenenleri hazır olan buyrukları öne alarak bu beklemeleri azaltır ve işlem birimlerinin daha verimli kullanılmasını sağlar. Ayrıca yazmaçların yeniden adlandırılması yoluyla, gerçek bir veri bağımlılığından kaynaklanmayan sahte bağımlılıkları (yazmaçların yeniden kullanımından doğan) ortadan kaldırır.

Buyrukların yeniden sıralanabilmesi, aralarındaki bağımlılıkların hangisinin gerçek hangisinin yalnızca ad kaynaklı olduğunun ayırt edilmesine dayanır.

Gerçek veri bağımlılığı (İngilizce: true data dependence), bir buyruğun bir başkasının ürettiği değeri okumasıdır. Bu bağımlılık veriyi taşır ve hiçbir düzenekle kaldırılamaz; ancak beklenmesi gerekir. Tomasulo algoritmasının bu bağımlılık karşısında yaptığı, değeri üreten birimin etiketini bekleyen buyruğa vermek ve değer üretilir üretilmez onu doğrudan iletmektir.

Karşıt bağımlılık (İngilizce: anti-dependence) bir buyruğun okuduğu yazmaca sonraki bir buyruğun yazmasıyla, sonuç bağımlılığı (İngilizce: output dependence) ise iki buyruğun aynı yazmaca yazmasıyla ortaya çıkar. Bu ikisinde buyruklar arasında akan bir değer yoktur; sıra kısıtı yalnızca ikisinin de aynı adı kullanmasından doğar. Yazmaç sayısı sınırlı olduğundan derleyici aynı yazmacı kısa aralıklarla yeniden kullanır ve bu sahte kısıtlar bol miktarda üretilir.

Algoritmanın kilit fikri, mimari yazmaç adını değerin gerçek üreticisiyle değiştirmesidir. Bir buyruk dağıtıldığında hedef yazmacı, o buyruğu tutan bekleme alanının etiketiyle işaretlenir; sonraki buyruklar o yazmacı okuduklarında yazmacın kendisini değil, bu etiketi alırlar. Aynı yazmaca yazan bir başka buyruk dağıtıldığında işaret yeni etiketle değiştirilir ve eski değeri bekleyenler bundan etkilenmez. Böylece karşıt ve sonuç bağımlılıkları donanımda kendiliğinden ortadan kalkar; sıralamayı kısıtlayan tek şey gerçek veri bağımlılığı olarak kalır.

Algoritma üç ana donanım öğesine dayanır:

• Bekleme alanları (İngilizce: reservation stations): Her işlem biriminin önünde bulunan, yürütülmeyi bekleyen buyrukları ve işlenenlerini tutan ara belleklerdir. Bir buyruk, işlenenleri henüz hazır değilse bekleme alanında, kendisini üretecek buyruğun etiketini bekleyerek durur.
• Yeniden adlandırma: Mimari yazmaçlar, bekleme alanlarının etiketleriyle eşlenir; böylece aynı yazmacı kullanan birbirinden bağımsız buyruklar arasındaki sahte bağımlılıklar kaldırılır.
• Ortak veri yolu (İngilizce: common data bus): Bir işlem birimi sonucu hesapladığında, sonucu hem yazmaçlara hem de o sonucu bekleyen tüm bekleme alanlarına aynı anda yayımlayan ortak bağlantıdır.

Her bekleme alanı, tuttuğu buyruğu yürütülebilir duruma gelene dek tanımlayan birkaç alandan oluşur. Yapılacak işlemin türü, iki işlenen için birer değer alanı ve birer etiket alanı, alanın dolu olup olmadığını bildiren bir im ve bellek buyruklarında kullanılan bir adres alanı bulunur.

İşlenen alanlarının ikili kullanımı algoritmanın işleyişini taşır. Bir işlenenin değeri dağıtım anında hazırsa değer alanına yazılır ve etiket alanı boş bırakılır; hazır değilse değer alanı boş kalır, etiket alanına o değeri üretecek bekleme alanının etiketi konur. Yürütme, iki etiket alanı da boşaldığında, bir başka deyişle iki işlenen de değer olarak elde edildiğinde başlar.

Yazmaçların hangi buyruk tarafından üretileceğini izlemek için ayrıca bir eşleme çizelgesi tutulur. Bu çizelge her mimari yazmaç için, o yazmaca en son yazacak buyruğun bekleme alanı etiketini saklar; etiket yoksa yazmacın kendi değeri geçerlidir. Dağıtım sırasında okunan her işlenen bu çizelgeden geçirilir ve buyruk ya değeri ya da bir etiketi alır.

Ortak veri yolunda bir sonuç yayımlandığında bütün bekleme alanları, kendi etiket alanlarını yayımlanan etiketle karşılaştırır. Eşleşen alan, gelen değeri kendi değer alanına yazar ve etiketini siler. Bu karşılaştırma bütün alanlarda aynı anda yapılır; algoritmanın donanım maliyetinin önemli bir bölümü buradan gelir.

Her buyruk üç aşamadan geçer:

1. Dağıtım: Buyruk, uygun bir bekleme alanına yerleştirilir; işlenenleri hazırsa değerleri, değilse onları üretecek birimlerin etiketleri kaydedilir.
2. Yürütme: Bir buyruğun tüm işlenenleri hazır olduğunda ilgili işlem birimi onu yürütür. Birden çok buyruğun işlenenleri aynı anda hazırsa, bunlar program sırasından bağımsız olarak yürütülebilir.
3. Sonuç yazma: Hesaplanan sonuç ortak veri yoluna yayımlanır; bu sonucu bekleyen bütün bekleme alanları ve yazmaçlar değeri aynı anda alır.

Aşağıdaki dört buyruk, algoritmanın hangi bağımlılığı nasıl ele aldığını bir arada gösterir. Çarpmanın toplamadan belirgin biçimde uzun sürdüğü varsayılmıştır.

Örnek buyruk dizisi

#	Buyruk	Bir önceki buyruklarla ilişkisi
1	fmul f2, f4, f6	işlenenleri hazır, uzun sürer
2	fadd f8, f2, f10	1'in sonucunu okur (gerçek veri bağımlılığı)
3	fsub f2, f12, f14	1 ile aynı yazmaca yazar (sonuç bağımlılığı)
4	fadd f16, f2, f18	3'ün sonucunu okur

Birinci buyruk bir çarpma bekleme alanına yerleştirilir; iki işleneni de hazır olduğundan yürütmeye başlar. Eşleme çizelgesinde f2 yazmacı bu alanın etiketiyle işaretlenir.

İkinci buyruk bir toplama bekleme alanına girer. f2 yazmacını okurken çizelgeden değeri değil çarpma alanının etiketini alır ve beklemeye geçer. f10 hazır olduğundan değer olarak yazılır.

Üçüncü buyruk asıl noktayı gösterir. İşlenenleri hazır olduğu için, birinci buyruk henüz f2 yazmacına yazmamış olmasına karşın hemen yürütülebilir. Dağıtımda eşleme çizelgesindeki f2 işareti bu buyruğun bekleme alanının etiketiyle değiştirilir. İkinci buyruk bundan etkilenmez, çünkü beklediği etiketi dağıtım anında kendi içine almıştır. Sonuç bağımlılığı böylece ortadan kalkar.

Dördüncü buyruk f2 yazmacını okuduğunda çizelgeden üçüncü buyruğun etiketini alır; doğru üreticiyi beklemesi kendiliğinden sağlanmış olur.

Üçüncü buyruk kısa sürdüğü için sonucunu önce yayımlar. Ortak veri yolundaki etiketi gören dördüncü buyruk değeri alır ve yürütmeye geçer; eşleme çizelgesinde f2 hâlâ bu etiketi taşıdığından yazmaç öbeği de değeri yazar. Uzun süren çarpma daha sonra bittiğinde kendi etiketini yayımlar; bunu bekleyen ikinci buyruk değeri alır, ama yazmaç öbeği almaz. f2 yazmacının işareti artık başka bir buyruğa ait olduğundan, geç biten çarpma daha yeni bir değeri ezmemiş olur.

Yazmaçlar arasındaki bağımlılıklar dağıtım anında yazmaç adından okunabilir; bellek erişimlerinde ise durum farklıdır, çünkü iki erişimin aynı yeri kullanıp kullanmadığı ancak adresleri hesaplandıktan sonra bilinir. Bu yüzden yükleme ve saklama buyrukları kendi ara belleklerinde tutulur ve iki aşamada ilerler: önce taban yazmacı ile eklenti toplanarak adres bulunur, sonra erişim yapılır.

Adresler belli olduktan sonra karşılaştırma yapılabilir. Bir yükleme, kendisinden önce gelen ve henüz tamamlanmamış bir saklamayla aynı adresi kullanıyorsa beklemek zorundadır; farklı adresleri kullanıyorlarsa yükleme öne alınabilir. Adresi henüz hesaplanmamış bir saklama varsa, ondan sonraki yüklemelerin çakışıp çakışmadığı bilinemez ve algoritmanın seçtiği tutum beklemektir.

Özgün gerçekleştirimde bu ayrım, Model 91'in bellek yolundaki ara bellek düzeniyle birlikte tasarlanmıştı; erişimler sıraya konurken aritmetik birimler çalışmayı sürdürebiliyordu.

Tomasulo algoritması, yazmaçların yeniden adlandırılması, dinamik çizelgeleme ve ortak veri yolu üzerinden sonuç yayımlama gibi fikirleriyle çağdaş yüksek başarımlı işlemci tasarımını derinden etkilemiştir. Bu kavramlar, öngörüye dayalı yürütme ve yeniden sıralama belleği gibi tekniklerle birleştirilerek günümüz çoklu buyruk başlatımlı işlemcilerinde yaygın biçimde kullanılır.

Ortak veri yolu, Tomasulo algoritmasının en özgün öğelerinden biridir. Bir işlem birimi sonucu hesapladığında, bu sonuç yalnızca yazmaca yazılmaz; aynı anda, o değeri bekleyen bütün bekleme alanlarına da yayımlanır. Böylece bir sonucu bekleyen birden çok buyruk, ara adıma gerek kalmadan değeri doğrudan ve eşzamanlı olarak alır. Bu "yayımla ve dinle" düzeneği, sonuçların yazmaç öbeğinden tekrar okunmasını beklemeden iletilmesini sağlayarak gecikmeyi azaltır.

Buyrukları donanımda yeniden sıralayan ilk düzen Tomasulo algoritması değildir. CDC 6600, 1964'te skor tahtası adı verilen bir düzenle buyrukları işlenenleri hazır oldukça yürütüyordu. İki düzen aynı amacı taşır, ama ad kaynaklı bağımlılıkları ele alışlarıyla ayrılırlar.

Skor tahtasında yeniden adlandırma yoktur. Yazmaç adları buyruğun tamamlanmasına dek olduğu gibi kalır, bu yüzden karşıt ve sonuç bağımlılıkları gerçek kısıt gibi davranır ve donanım bunları bekleterek çözer. Bir buyruk, kendisinden önceki buyruklar okuması gereken yazmacı okuyana dek sonucunu yazamaz; aynı yazmaca yazacak bir başka buyruk hâlâ yürütülüyorsa dağıtım durdurulur. Tomasulo algoritması iki durumu da bekleme alanı etiketleriyle ortadan kaldırdığı için bu duraklamalar oluşmaz.

İkinci ayrım denetimin nerede durduğudur. Skor tahtası merkezîdir; bütün buyrukların ve birimlerin durumunu tek bir birim tutar ve kararları o verir. Tomasulo algoritmasında durum bekleme alanlarına dağıtılmıştır, her alan kendi işlenenlerini kendi izler ve sonuç yazmaç öbeğinden okunmak yerine ortak veri yolundan doğrudan alınır. Sonucun üreticiden tüketiciye yazmaçlara uğramadan geçmesi, gecikmeyi bir çevrim kısaltır.

Algoritmanın kazancı donanımda ödenir. Bir sonuç yayımlandığında bütün bekleme alanları kendi iki etiket alanını yayımlanan etiketle karşılaştırır; bu çağrışımlı karşılaştırma, alan sayısı arttıkça hem alan hem gecikme olarak büyür ve çevrim süresini belirleyen yolun üstünde durur.

Ortak veri yolunun kendisi de bir kısıttır. Yol paylaşımlıdır ve bir çevrimde tek bir sonuç taşır; birden çok işlem birimi aynı çevrimde bitirdiğinde biri geçer, ötekiler bekler. Yolu genişletmek her bekleme alanına fazladan karşılaştırma girişi eklemek demektir, bu yüzden genişlik ucuza artırılamaz.

Bekleme alanları da sayılı bir kaynaktır. Uzun süren bir buyruğun sonucunu bekleyen buyruklar alanları doldurduğunda, işlem birimleri boş olsa bile yeni buyruk dağıtılamaz ve boru hattı durur. Bu yüzden sonraki tasarımlar alan sayısını, işlem birimi sayısını ve yeniden adlandırma kaynaklarını birlikte boyutlandırmış; kimi gerçekleştirimlerde bekleme alanı ile yeniden sıralama belleği tek bir yapıda birleştirilmiştir.

Buyruklar program sırasından bağımsız tamamlandığından, özgün Tomasulo algoritmasında bir kesme ya da kural dışı durum (exception) oluştuğunda işlemcinin tam olarak hangi noktada olduğunu belirlemek güçtür; çünkü sonraki bir buyruk, önceki bir buyruktan daha erken bitmiş olabilir. Bu sorun, daha sonra yeniden sıralama belleğinin algoritmaya eklenmesiyle çözülmüştür: buyruklar sırasız yürütülse de, sonuçların kalıcı hâle gelmesi (emeklilik) program sırasına göre yapılır; böylece kesin (precise) kesmeler desteklenir.

Özgün Tomasulo algoritması yalnızca kayan nokta birimini hedefliyordu ve sonuçları doğrudan yazmaçlara yazıyordu. Çağdaş işlemcilerde algoritma, yeniden sıralama belleği ile birleştirilerek genişletilmiştir. Bu düzende sonuçlar önce yeniden sıralama belleğinde tutulur, ancak program sırası geldiğinde mimari yazmaçlara yazılır. Bu sayede hem öngörüye dayalı yürütme (dallanma sonuçları kesinleşmeden buyrukların yürütülmesi) hem de kesin kesmeler güvenli biçimde desteklenebilir.

Tomasulo algoritması, ilk kez 1967'de IBM System/360 Model 91'de kullanıldıktan sonra yaklaşık yirmi yıl boyunca yaygınlaşmadı; ancak 1990'larda yüksek başarımlı çoklu buyruk başlatımlı işlemcilerin gelişmesiyle yeniden önem kazandı. Robert Tomasulo, bu çalışması nedeniyle 1997'de bilgisayar mimarisi alanının saygın ödüllerinden Eckert–Mauchly Ödülü'ne layık görüldü.

• Boru hattı (bilgisayar)