Özel örgü ara bağlantı ağlarında temel çizge algoritmalarının tasarımı ve analizi
Routing and path algorithms in interconnection network graphs and analysis of algorithms
- Tez No: 859672
- Danışmanlar: DOÇ. DR. BURHAN SELÇUK, DOÇ. DR. MUHAMMED KAMİL TURAN
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2024
- Dil: Türkçe
- Üniversite: Karabük Üniversitesi
- Enstitü: Lisansüstü Eğitim Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 133
Özet
Bu tezde, 2 boyutlu örgü çizgelerinin alt çizgeleri olan Bağlantılı Kare Ağ Çizgeleri (CSNG) (2022, 2023) ve Fraktal Kübik Ağ Çizgeleri (FCNG) (2015) üzerinde temel çizge problemleri çalışılmıştır ve bu problemler için çalışma zamanı ve çizge maliyeti açısından daha iyi sonuçlar elde edilmesi hedeflenmektedir. CSNG ve FCNG çizgeleri, iletişim ağı veya ara bağlantı ağları olarak adlandırılan ağların bir çeşididir. Ara bağlatı ağları düğümler arasında verimli bir şekilde veri aktarımı yapmak üzere tasarlanmışlardır ve büyük ölçekli bilgi işlem sistemlerinin mimarisinde kritik bir bileşen olarak rol oynamaktadırlar. Bu çizgeler özyinelemeli olarak tanımlanmış, ara bağlantı ağlarında sıklıkla tercih edilen hiperküpün türevleridir. Çizgelerin tanımlanmasında herbir düğümün etiketleri arasında bir bitlik değişimi esas alan gray kod kullanılmıştır. CSNG üzerine yapılan çalışmanın odak noktası hiperküp yardımıyla CSNG için temel çizge problemlerine çözüm bulan algoritmalar geliştirmektir. CSNG çizgesinde kapalı Hamilton yolunu bulan verimli bir algoritma önerilmiştir. Bunula birlikte çizgedeki düğümleri 2 boyutlu düzlemde haritalanmasını ve tek noktaya yönlendirmesini gerçekleştiren algoritmalar önerilmiştir. Fakat bu algoritmalar 2 boyutlu örgü çizgelerindeki tek noktaya yönlendirme algoritması ile aynı çalışma zamanına sahip olduğundan, çalışma zamanını iyileştirmek için etiketleme ve tek noktaya yönlendirme algoritmalarında paralelleştirme yapılarak işlem birimi sayısına göre daha iyi sonuçlar elde edilmiştir. Bunun yanısıra, CSNG için hiperküp yayın algoritmalarının bir benzerleri önerilmiştir. Fraktal yapılar birçok temel alanda kullanılan birbirini tekrar eden geometrik yapılardır. FCNG aynı CSNG gibi bir hiperküp varyant olarak tanımlanmış bir fraktal çizgedir. FCNG için daha önce ortaya konulmamış olan yeni topolojik özellikler elde edilmiştir. FCNG üzerinde yönlendirme ve en kısa yol problemleri için yeni bir strateji tanıtılmış ve bu stratejiyi kullanan özyinelemeli algoritmalar önerilmiştir. Ağ düğümlerini 2 boyutlu düzlemde haritalamak için bir algoritma ve en kısa yolu oluşturmak için kullanılan algoritmalar önerilmiş ve çalışma süreleri hesaplanmıştır. Yönlendirme ve en kısa yol problemleri için çalışma süreleri 2 boyutlu örgü ağlarda verilen algoritmalar ile benzer sonuçlar vermiş olsa da bu problemler için FCNG çizgesinin kullanımı ağ oluşum maliyetini düşürmüştür.
Özet (Çeviri)
In this thesis, basic graph problems on the subgraphs of 2D mesh graphs, Connected Square Network Graphs (CSNG) (2022, 2023) and Fractal Cubic Network Graphs (FCNG) (2015), are studied with the aim of obtaining better results in terms of runtime and graph cost for these problems. CSNG and FCNG graphs are a variant of interconnection networks. Interconnection networks are designed to efficiently transfer data between nodes and are a critical component in the architecture of large-scale computing systems. These graphs are recursively defined derivatives of the hypercube, which is often preferred in interconnection networks. The graphs are defined using gray code based on a one-bit exchange between the labels of each node. The focus of the work on CSNG is to develop algorithms that solve basic graph problems for CSNG using hypercubes. An efficient algorithm that finds the closed Hamiltonian path in a CSNG graph is proposed. In addition to this, algorithms have been proposed for mapping the nodes in the graph in the 2D plane and unicast routing. Since these algorithms have the same runtime as the unicasting algorithm in 2D mesh graphs, in order to improve the runtime, the labeling and unicasting algorithms are parallelized to achieve better results with respect to the number of processing units. In addition, similar hypercube broadcast algorithms are proposed for CSNG. Fractal structures are repeating geometric structures used in many fundamental fields. FCNG is a fractal graph defined as a hypercube variant, just like CSNG. New topological properties have been obtained for FCNG that have not been introduced before. A new strategy for routing and shortest path problems on FCNG is introduced and recursive algorithms using this strategy are proposed. An algorithm for mapping network nodes in 2D plane and algorithms for shortest path generation are proposed and their running times are calculated. Although the running times for the routing and shortest path problems are similar to the algorithms for 2D mesh networks, the use of the FCNG graph for these problems reduces the network construction cost.
Benzer Tezler
- Yeni Cami'nin akustik açıdan performans değerlendirmesi
Evaluation of the acoustical performance of the New Mosque
EVREN YILDIRIM
Yüksek Lisans
Türkçe
2003
Mimarlıkİstanbul Teknik ÜniversitesiMimarlık Ana Bilim Dalı
PROF. DR. SEVTAP YILMAZ DEMİRKALE
- Evaluation of reverse electrodialysis (RED) system performance with various compositions of salt solutions for production of salinity gradient energy (SGE)
Tuzluluk farkına dayalı enerji (SGE) üretimi için farklı bileşimlerde tuz çözeltileri ile ters elektrodiyaliz (RED) sisteminin performans değerlendirmesi
TUĞÇE ZEYNEP KAYA
Yüksek Lisans
İngilizce
2021
Kimya MühendisliğiEge ÜniversitesiKimya Mühendisliği Ana Bilim Dalı
PROF. DR. NALAN KABAY
DR. ÖĞR. ÜYESİ ENVER GÜLER
- Synthesis of hexagonal boron nitride in the existance of fluxing agents
Hegzagonal bor nitrürün erime noktası düşürücü maddeler varlığında sentezi
MUHAMMED ÖZ
Doktora
İngilizce
2013
KimyaAbant İzzet Baysal ÜniversitesiMalzeme Bilimi ve Mühendisliği Bilim Dalı
PROF. DR. ÇETİN BOZKURT
- Ankara İş ve İşçi Bulma Kurumu Mesleki Rehabilitasyon Merkezinde iğne oyası ile uğraşan özürlüler üzerine bir araştırma
This study (research) made on handicapped persons. Who make needleworks, at Ankara association of work and workman findation
İPEK MERT
Yüksek Lisans
Türkçe
1998
El SanatlarıGazi ÜniversitesiEl Sanatları Eğitimi Ana Bilim Dalı
YRD. DOÇ. DR. H. SERPİL ORTAÇ