Arıza kaldırabilir yonga-üstü-ağlar için topoloji oluşturma, uygulama eşleme ve yönlendirme algoritmalarının tasarlanması
Designing topology generation, application mapping, and routing algorithms for fault-tolerant network-on-chips
Yazar: VAHID BABAEI AJABSHIR
Danışman: PROF. DR. İMAN ASKERBEYLİ ; DOÇ. DR. SÜLEYMAN TOSUN
Ankara Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2015
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Hata toleransı = Fault tolerance

Özet:
Entegre devrelerin teknoloji boyutları çok hızlı bir şekilde küçüldüğünden yongalar üstündeki transistör yoğunluğu buna bağlı olarak oldukça fazla artmaktadır. Her teknoloji neslinde küçülen nanometre boyutları daha yoğun yonga tasarımlarına izin verirken üretilen bütünleşmiş devreler aşınmalara daha hassas olmakta ve üretim hatalarına neden olmaktadır. Yonga üstündeki yapıda oluşan bir tek bağ hatası bile uygulamanın bileşenleri arasındaki haberleşmeyi durdurup tüm yongayı kullanışsız hale getirebilir. Bu çalışmada Yonga-üstü-Ağ (YüA) haberleşmesiyle tasarlanmış hatalı yongaların kullanışlı hale getirilmesi amaçlanmaktadır. Bu çalışmada özellikle uygulamaya özgü YüA tasarımları için hata kaldırabilen düzensiz topoloji oluşturma yöntemi sunulmuştur. Tasarlanan YüA topolojisi varsayılan yönlendirme yolunda bir bağ hatası varsa başka bir yoldan yönlendirme yapabilmeye izin vermektedir.
Çalışmamız üç ana bölümden oluşmaktadır:
Hata kaldırabilen topoloji oluşturma (HKTO): HKTO yöntemindeki amacımız, yönlü çizge ile ifade edilen n düğümlü bir uygulama için her biri p kapı içeren yönlendirici düğümler kullanarak her bir yönlendiriciden diğer yönlendiricilere en az iki farklı yol olacak şekilde bir topoloji oluşturmaktadır. Bu amacı gerçekleştirebilmek için tasarladığımız tekrarlamalı algoritma ilk önce kaç tane yönlendirici gerektiğini bulmaktadır. Daha sonra, tamamen bağlantılı hata kaldıramayan topolojileri rastgele üretir. Bir sonraki aşamada algoritmamız oluşturulan topolojileri hata kaldırabilir yapmak için fazladan bağlar ekler. En sonunda ise oluşturulan birbirinden farklı topoloji kümesinin içinden ortalama yol uzunluğu en az olanı seçer.
Uygulama eşlemesi: Hata kaldırabilir topolojiyi oluşturduktan sonra, verilen uygulama haberleşen kaynaklar arasındaki enerji tüketimini en aza indirmeyi amaçlayan benzetimli tavlama (BT) tabanlı bir eşleme algoritması ile eşlenmektedir.
Hata kaldırabilen yönlendirme oluşturma (HKYO): Eğer yongada herhangi bir bağ hatası yoksa enerji tüketimi en az olan temel yönlendirme kullanılmaktadır. Fakat, eğer herhangi bir bağ üzerinde hata var ise muhtemelen daha fazla enerji tüketimi ve hız kaybına neden olacak farklı bir yönlendirme kullanılmalıdır. Yönlendirme tablosu oluşturmadaki amacımız, tüm tek bağ hatalarını kapsayabilen en az sayıda yönlendirme tablosunu oluşturabilmektedir. Yönlendirme seçeneği, yonganın dış bacaklarından seçilebilmektedir. Eğer m tane farklı yönlendirme seçeneğimiz varsa, ⌈〖log〗_2^m ⌉ tane bacak yongaya eklenmelidir. Bu bağlamada bağ hatalarının alt kümelerini kapsayabilen en az sayıdaki yönlendirme tablolarını oluşturabilen tekrarlamalı bir algoritma geliştirilmiştir.

Abstract:
As the technology sizes of integrated circuits (ICs) scale down rapidly, current transistor densities on chips dramatically increase. While nanometer feature sizes allow denser chip designs in each technology generation, fabricated ICs become more susceptible to wear-outs causing production failures. Even a single link failure within an on-chip fabric can halt communication between application blocks, which makes the entire chip useless. In this study, we aim to make faulty chips designed with Network-on-Chip (NoC) communication usable. Specifically, we present a fault-tolerant irregular topology-generation method for application-specific NoC designs. Designed NoC topology allows a different routing path if there is a link failure on the default routing path. 
Our work is divided into three major parts as follows:
Fault-tolerant topology generation (FTTG): Given an application as a directed graph with n nodes and a set of routers each having p ports, our goal is to design a topology such that each router can reach to any other router with at least two alternative path. To achieve this goal, we designed an iterative algorithm that first decides the number of routers to be utilized. Then, it randomly generates fully connected non-fault-tolerant topologies. After that, it adds extra links to make the topology fault-tolerant. It then selects a topology with minimum average path length from the generated non-isomorphic topology set.
Application mapping: After generating fault tolerant topology, we map the given application using a simulated-annealing (SA) based mapping algorithm with an objective of minimizing the total energy consumption of communication resources.
Fault-Tolerant routing generation (FTRG): If there is no link failure exists in the chip, we use the default, minimum-energy consuming shortest path routing. However, if there is a link failure on any link, we should use different routing, probably with more energy consumption and some performance overhead. Our goal in routing table generation is to create minimum number of routing options that cover all single link failures. The number of routing options is selected by external pins of the chip. If we have m different routing options, we place ⌈〖log〗_2^m ⌉ external pins to select the routing table. We used iterative algorithm that generates routing tablet hat covers a subset of link failures.