ÖZEL ÖRGÜ ARA BAĞLANTI AĞLARINDA TEMEL ÇİZGE ALGORİTMALARININ TASARIMI VE ANALİZİ

Abstract

Ö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ğlantı 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 her bir düğümün etiketleri arasında bir bitlik değişimi esas alan gri 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.

ABSTRACT

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.