Design and permutation routing algorithms of rearrangeable networks
Ayarlanabilir şebekelerin dizaynı ve permutasyon yönlendirme algoritmaları
- Tez No: 709935
- Danışmanlar: PROF. DR. JOSE A.B. FORTES
- Tez Türü: Doktora
- Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 1992
- Dil: İngilizce
- Üniversite: Purdue University
- Enstitü: Yurtdışı Enstitü
- Ana Bilim Dalı: Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 225
Özet
Bilgisayar sistemlerinin işlemcileri ve bellekleri arasinda iletişimi sağlayan shuffle-exchange isimlendirilen şebekede permutasyonların dengeli matrisler kullanılarak gerçekleştirilmesi literatürde anlatılmaktadır. Bu permutasyonların bilgisayar sistemlerinin işlemcileri ve belleklerinde kullanılan diğer şebekelerinde de gerçekleştirilmesi için, bu tez“çerçeve”geliştirdi ve dengeli matrisler ile arasindaki ilişkileri detayli olarak inceledi. Dengeli matrisleri, çerçeve, graf teorisi, yönlendirme algoritmalarını kullanarak, bazı bilgisayar sistemlerinin iletişim şebekelerinde (örneğin Benes, 2n-1 tabakalı shuffle-exchange, reverse baseline) hangi permutasyonların gerçekleştirildiğini tesbit eden ve bu permutasyonların özelliklerini analiz eden metodlar geliştirdi. N adet girdisi ve N adet çıktısı olan bir bilgisayar iletişim şebekesi N! permutasyonun her birisini tek pasda gerçekleştirebiliyorsa, bu şebekeye ayarlanabilir anlamina gelen“rearrangeable”denir. Benes ve Clos olarak bilinen ayarlanabilir şebekelerdir. Bu tez bu konularda yeni ispatlar geliştirmiştir. Ayrica, uzun süredir ispat edilmemiş olan (2n-1) tabakali shuffle-exchange şebekesinin de ayarlanabilir olduğunu gösterdi. Bu ispatı yaparken, Omega isimli şebekenin üzerinde iki pas yapılırsa, onun da ayarlanabilir bir şebeke olduğunu gösterdi. Bu tez kontrollu çevirgeç ve konsantratör'leri kullanarak, dört tane ayarlanabilir ve otomatik yönlendirme yapabilen şebekeler geliştirdi. Bu şebekelerin permutasyonları gerçekleştirirken gereken yayilma zamanlarını hesapladı. Bu şebekelerde birbirini takip eden her iki tabakanın arasına extra linkler, multiplexer, demultiplexer ekleyerek olabilecek hatalara karşı daha dayanıklı olmasını sağladı.
Özet (Çeviri)
Balanced matrices are presented in the literature to identify the permutations realized by the shuffle-exchange network. In order to extend this work to the other interconnection networks and to facilitate the identification of permutations, this thesis introduces the concept of a frame and illustrations of different frames. The relationships between balanced matrices and frames are discussed in detail. Within the framework of balanced matrices, frames and graph theory, routing algorithms are developed to route permutations through some interconnection networks such as Benes, (2n-1)-stage shuffle-exchange, reverse baseline, a cascade of reverse baseline and (n-l)-stage shuffle-exchange, etc. The permutations realized by the subnetworks of these networks are identified and the properties of the permutations are analyzed. An interconnection network with N inputs and N outputs is said to be rearrangeable if it realizes every one of the N! permutations in a single pass. Benes network, which is a member of Clos' type networks, is a well-known rearrangeable network. In this thesis, using balanced matrices, frames and graph theory, new proofs are provided for the rearrangeability of some networks such as Benes, three-stage Clos, reduced ΩNΩ-1N, etc. New rearrangeable networks whose topologies are very similar to Benes network are designed. A long-standing open question of whether the (2n-l)-stage shuffle-exchange network is rearrangeable is answered affirmatively. An important corollary of this result is the proof that two passes through Omega network are sufficient and necessary to implement any permutation. In addition to rearrangeability, fault-tolerance and the type of routing algorithm used in setting up the switches are the key issues in designing an interconnection network. In this thesis, four different self-routing rearrangeable networks, constructed from digit-controlled switches and concentrators, are presented. These networks use the destination tag routing scheme to realize any arbitrary permutation. One of these networks has O(log22 N) gate-level delay with a very small constant and use O(N2 log2 N) VLSI-level hardware. The propagation time of this network is less than that of any self-routing permutation network presented to date. Intrastage links, multiplexers and demultiplexers are added to this network to make it fault-tolerant.
Benzer Tezler
- Çok değerli lojik
Multiple-valued logic
CEM TIĞCI
Yüksek Lisans
Türkçe
1997
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. AHMET DERVİŞOĞLU
- Birleşi eniyileme problemleri için oto-kontrollü yerel arama yöntemi
Self-controlled local search method for combinatorial optimization problems
ÇİĞDEM ALABAŞ
Doktora
Türkçe
2004
Endüstri ve Endüstri MühendisliğiGazi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF.DR. BERNA DENGİZ
- Paralel işaret işleme sistemi ve bir uygulama
A Parallel signal processing system and an application
FATİH KURUGÖLLÜ
Yüksek Lisans
Türkçe
1994
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiKontrol ve Otomasyon Mühendisliği Ana Bilim Dalı
PROF. DR. A. EMRE HARMANCI
- Eksik blok tasarımlarında parametrik olmayan metotlar
Eksik blok tasarimlarinda parametrik olmayan metotlar
HASAN HÜSEYİN GÜL
- İlköğretim 8. sınıf düzeyinde permütasyon ve olasılık ünitesinin bilgisayar destekli tasarımı
A design of computer assisted instraction of the permutation and probability unit at 8th grade in primary school
GÜLCAN ÖZTÜRK
Yüksek Lisans
Türkçe
2005
Eğitim ve ÖğretimBalıkesir ÜniversitesiOrtaöğretim Fen ve Matematik Alanları Eğitimi Ana Bilim Dalı
Y.DOÇ.DR. AYŞEN KARAMETE