Yonga-üstü-ağlar için uygulamaya özgü yeniden yapılandırılabilir topoloji tasarımı
Application-specific reconfigurable topology design for network-on-chips
Yazar: PINAR KÜLLÜ
Danışman: PROF. DR. SÜLEYMAN TOSUN
Hacettepe Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2020
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Entegre devre boyutlarındaki hızlı azalma, her nesilde tek bir yongaya daha fazla bileşen yerleştirmeyi mümkün kılar. Bileşenlerdeki artış, geleneksel kablolama tabanlı iletişim yöntemlerinden daha iyi bir iletişim mekanizması gerektirse de, teknoloji boyutlarının daralması nedeniyle artan kalıcı arızaları tolere etmek için yeni tasarım algoritmalarına ihtiyaç vardır. Bu sorunu çözmek ve çok büyük sistemlerde iletişim taleplerine ayak uydurmak için Yonga-üstü-Ağ (YüA) paradigması geliştirilmiştir. Bir YüA mimarisi tasarlanırken, tasarımcılar bant genişliği, performans, enerji tüketimi, maliyet, yeniden kullanılabilirlik ve hataya dayanıklılık gibi çeşitli kriterleri dikkate almalıdır. 

Tez kapsamında ilk olarak, belirli bir uygulama için tasarlanmış bir YüA mimarisinde tek kalıcı bağlantı hatasını tolere edebilen hataya dayanıklı bir topoloji oluşturma yöntemi sunulmuştur. Oluşturulan topolojiler, uygulamanın iletişim düğümleri arasında en az iki alternatif yol sağlayarak hataya dayanıklılık sağlar. Yöntem, halka topolojisine dayalı bir başlangıç popülasyonu üreten ve genetik operatörler aracılığıyla enerji tüketimi açısından daha iyi düzensiz topolojiler oluşturan genetik algoritma tabanlı bir yöntemdir. Önerilen yöntemin amaç işlevi, ağ iletişiminden kaynaklanan enerji tüketimini en aza indirmektir. 

Uygulamaya özgü oluşturulan hata kaldırabilir topolojilerde sistem bileşenleri arasında en az iki yol bulunmaktadır. Ancak yonganın çalışma sürecinde bağlantılar üzerinde bir hata ortaya çıkarsa veriler doğru bir şekilde hedef yönlendiriciye iletilemez. Bu nedenle bu tarz topolojiler için, hataları sistemin çalışması sırasında dinamik olarak tespit edebilecek ve hatanın durumuna göre paketi alternatif yollardan hedef yönlendiriciye iletebilecek bir yapı tasarlanmıştır.

Yonga-üstü-Ağlarda örgü topolojisi tasarım için en yaygın olarak kullanılan topoloji olmasına rağmen, ağ tıkanıklığı ve enerji tüketimi gibi çeşitli sorunları vardır. Yeniden yapılandırılabilir ağ topolojisi, ağ tıkanıklığını azaltmak için daha fazla eşleme ve yönlendirme seçeneği sunduğu için geleneksel ağa iyi bir alternatiftir. Bununla birlikte, yeniden yapılandırılabilir örgü yapıları için verimli eşleme ve yönlendirme algoritmaları sayısı oldukça azdır. Tez çalışması kapsamında, eş zamanlı olarak, uygulama düğümlerini yeniden yapılandırılabilir ağ yapısı üzerinde eşleyen ve enerji minimizasyonu amacıyla iletişim çiftleri arasındaki yönlendirme yollarını belirleyen genetik algoritma (GA) tabanlı bir yöntem önerilmiştir. 

Son olarak, düzenli ve düzensiz YüA topolojilerinin avantajlarını birleştiren iki aşamalı yeni bir yöntem sunulmuştur. İlk adımda, yöntem, alanı ve enerjiyi optimize etmek için en az miktarda yönlendirici ve bağlantı kullanan ve bu nedenle iletişim düğümleri arasında sadece bir yönlendirme yolu bulunan düzensiz topolojiyi, hataya dayanıklı hale getirmek için yeniden yapılandırılabilir ağ topolojisine eşlemektedir. İkinci aşamada ise, yerleştirilen düğümler arasındaki yollara karar verilmektedir.

Abstract:
The rapid reduction in integrated circuit dimensions makes it possible to place more components on a single chip in each generation. While the increase in components requires a better communication mechanism than traditional wiring-based communication methods, new design algorithms are needed to tolerate increasing permanent failures due to shrinking technology dimensions. To solve the problem, the network-on-chip (NoC) paradigm was developed to keep pace with the communication demands on these very large systems. When designing a Network-on-Chip (NoC) architecture, designers must consider various criteria such as bandwidth, performance, energy consumption, cost, re-usability, and fault tolerance.

Within the scope of the thesis, firstly we provide a fault-tolerant topology generation method that can tolerate single permanent link failure on a NoC architecture that is designed for a particular application. The generated topologies provide fault-tolerance by providing at least two alternative paths between the application's communicating nodes. The method is a genetic algorithm based method, which generates an initial population based on ring topology and produces better irregular topologies in terms of energy consumption through genetic operators. The objective function of the proposed method is to minimize the energy consumption resulting from network communication.

There are at least two paths between system components in an application-specific fault tolerant topologies. However, if a fault occurs on the links during the chip's running time, the data cannot be correctly transmitted to the destination router. Therefore, we propose a mechanism that detects errors dynamically during the runtime and transmits packets to the destination routers by alternative paths according to the fault condition.

Although mesh topology is most commonly used topology for NoC design, it has several problems such as network congestion and energy consumption. Reconfigurable mesh topology is a good alternative to traditional mesh since it gives more mapping and routing options for reducing network congestion. However, design automation tools still lack efficient mapping and routing algorithms for reconfigurable meshes. In this study, we propose a genetic algorithm (GA) based method that simultaneously maps the application nodes on 2D reconfigurable mesh structure and determines the routing paths between communicating pairs with the objective of energy minimization.

Finally, we present a novel two-step method that combines the advantages of regular and irregular NoC topologies. In the first step, it maps the irregular topology, which uses the least amount of routers and links to minimize the area and energy and offers only one routing path between communicating nodes, to the reconfigurable network topology. In the second step, the method decides the paths between the placed nodes.