Adaptive source routing and route generation for multicomputers

Abstract

ÖZET ÇOK İŞLEMCİLİ BİLGİSAYARLARDA UYARLANABİLİR KAYNAK DA?ITIMI VE YOL ÜRETİMİ Yücel Aydoğan Bilgisayar ve Enformatik Mühendisliği, Yüksek Lisans Danışman: Doç. Dr. Cevdet Aykanat Temmuz, 1995 Ölçeklenebilir çokişlemcili bilgisayarlar herhangi iki işlemci arasında birden fazla haberleşme yolu sağlayan bağlantı ağları üzerine kurulan sistemlerdir. Bu tür ağlarda yol seçimi haberleşme performansım etkileyen önemli bir etk endir. Uyarlanabilir Kaynak Dağıtımı (UKD), uyarlanabilir dağıtım ve kaynak dağıtımı yöntemlerini birleştiren ve her ikisinin de avantaj lanna sahip olan bir dağıtım yöntemi olarak önerilmiştir. Her paket tam uyarlanabilir, kısmi uyarlanabilir yada uyarlamasız şekilde yöneltilir. UKD yöntemi kilitlenme sınırlamalarının sağlandığı herhangi bir ağ topolojisi kullanımına izin verir. Uyarlanabilir kaynak dağıtımı ve uyarlamasız rastlantısal dağıtım yöntemleri benzetim yapılarak karşılaştırılmıştır. Ayrıca çokişlemcili bilgisayar ağlarında işlemciler arasında uyarlanabilir yollar üreten bir yöntem önerilmiştir. Üretilen uyarlanabilir yollar her işlemcinin belleğindeki yol çizelgelerinde saklanır. Bu yöntem yüksek veri iletişim kapasitesi ve işlemciler arası güvenilir iletişimi sağlar. Önerilen yöntem ile IBM SP2 çokişlemcisi ağları kullanılarak deneyler yapılmış ve sağlanan veri iletişim kapasitesi ve işlemcilerde yol çizelgesi oluşturma zamanları ölçülmüştür. Yöntemin çokişlemcili bilgisayarlarda par alel işlemesi ile elde edilen verim de deneysel olarak sunulmuştur. Anahtar Sözcükler: Uyarlanabilir Dağıtım, Çokişlemcili Bilgisayarlar, Bağlantı Ağlan, Paralel İşleme iv

ABSTRACT ADAPTIVE SOURCE ROUTING AND ROUTE GENERATION FOR MULTICOMPUTERS Yücel Aydoğan M.S. in Computer Engineering and Information Science Advisor: Assoc. Prof. Cevdet Aykanat July, 1995 Scalable multicomputer are based upon interconnection networks that typi cally provide multiple communication routes between any given pair of proces sor nodes. In such networks, the selection of the routes is an important prob lem because of its impact on the communication performance. We propose the adaptive source routing (ASR) scheme which combines adaptive routing and source routing into one which has the advantages of both schemes. In ASR, the degree of adaptivity of each packet is determined at the source processor. Every packet can be routed in a fully adaptive or partially adaptive or non- adaptive manner, all within the same network at the same time. The ASR scheme permits any network topology to be used provided that deadlock con straints are satisfied. We evaluate and compare performance of the adaptive source routing and non-adaptive randomized routing by simulations. Also we propose an algorithm to generate adaptive routes for all pairs of processors in any multistage interconnection network. Adaptive routes are stored in a route table in each processor's memory and provide high bandwidth and reliable in- terprocessor communication. We evaluate the performance of the algorithm on IBM SP2 networks in terms of obtained bandwidth, time to fill in the route tables, and efficiency exploited by the parallel execution of the algorithm. Keywords: Adaptive Routing, Multicomputers, Interconnection Networks, Par allel Processing m