Geri Dön

Design and permutation routing algorithms of rearrangeable networks

Ayarlanabilir şebekelerin dizaynı ve permutasyon yönlendirme algoritmaları

PDF İndir

  1. Tez No: 709935
  2. Yazar: HASAN ÇAM
  3. Danışmanlar: PROF. DR. JOSE A.B. FORTES
  4. Tez Türü: Doktora
  5. Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
  6. Anahtar Kelimeler: Dinamik tasarım, M-matrisler, Nivelman ağları, Statik anahtar, Dynamic design, M-matrices, Nivelman networks, Static switch
  7. Yıl: 1992
  8. Dil: İngilizce
  9. Üniversite: Purdue Unıversıty
  10. Enstitü: Yurtdışı Enstitü
  11. Ana Bilim Dalı: Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: Belirtilmemiş.

Ö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

  1. Tez No

    155688

    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

    Türkçe

    2004

    Endüstri ve Endüstri MühendisliğiGazi Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF.DR. BERNA DENGİZ

  2. Tez No

    66858

    Çok değerli lojik

    Multiple-valued logic

    CEM TIĞCI

    Yüksek Lisans

    Türkçe

    Türkçe

    1997

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı

    PROF. DR. AHMET DERVİŞOĞLU

  3. Tez No

    1014367

    Tıbbi biyokimya laboratuvar ölçümlerinden elde edilen verilerin koroner arter hastalığı alt grupları ve hastalığın prognozu ile ilişkilendirilmesi: Bir makine öğrenme çalışması

    Association of medical biochemistry laboratory measurements with coronary artery disease subgroups and prognosis: A machine learning study

    ESRA KAFKAS

    Tıpta Uzmanlık

    Türkçe

    Türkçe

    2026

    BiyokimyaKafkas Üniversitesi

    Tıbbi Biyokimya Ana Bilim Dalı

    PROF. DR. EBUBEKİR BAKAN

  4. Tez No

    39204

    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

    Türkçe

    1994

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Kontrol ve Otomasyon Mühendisliği Ana Bilim Dalı

    PROF. DR. A. EMRE HARMANCI

  5. Tez No

    1016626

    In-plant milk-run system design using ERP data

    Fabrika içi milk-run sisteminin ERP verileri kullanılarak tasarımı

    HARUN ERFİDAN

    Yüksek Lisans

    İngilizce

    İngilizce

    2026

    Endüstri ve Endüstri MühendisliğiDokuz Eylül Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. ÖZCAN KILINÇCI

Geri Dön