Approaches for improving the efficiency of parallel maximum clique computation
Paralel maksimum klik hesaplamasının verimliliğini artırmaya yönelik yaklaşımlar
- Tez No: 999168
- Danışmanlar: DR. ÖĞR. ÜYESİ FAHREDDİN ŞÜKRÜ TORUN
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Grafik bölümleme, Paralel hesaplama, Graph partitioning, Parallel computing
- Yıl: 2026
- Dil: İngilizce
- Üniversite: Ankara Yıldırım Beyazıt Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Bilgisayar Mühendisliği Bilim Dalı
- Sayfa Sayısı: Belirtilmemiş.
Özet
Bu çalışma temel olarak paralel maksimum klik hesaplamasını daha verimli hale getirmeye odaklanmaktadır. Bu problem, çizgenin yoğun kısımlarının genellikle önemli bilgiler içerdiği birçok bilimsel ve endüstriyel alanda karşımıza çıkmaktadır. Paralel algoritmalar, işi birden fazla işlemci arasında dağıtarak hesaplama süresini azaltmayı amaçlasa da, performansları büyük ölçüde çizgenin nasıl bölümlendiğine ve iş yükünün ne kadar dengeli dağıtıldığına bağlıdır. Bölümleme iyi yapılmadığında bazı işlemciler boşta kalabilir, haberleşme maliyeti artabilir ve toplam çalışma süresi uzayabilir. Bu tezde, METIS, ParMETIS ve yeni önerilen örtüşme tabanlı bir yaklaşım da dahil olmak üzere farklı bölümleme stratejileri incelenmiştir. Bu yöntemlerin çalışma süresi, yük dengesi ve ölçeklenebilirlik üzerindeki etkileri hem gerçek dünya hem de sentetik veri kümeleri kullanılarak test edilmiştir. Teorik karmaşıklığa odaklanmak yerine, analiz daha çok pratik performansa odaklanmakta ve hangi bölümleme davranışlarının paralel klik aramasında daha iyi sonuçlar verdiğini anlamayı amaçlamaktadır. Bu çalışmanın temel katkılarından biri, katı bölümleme nedeniyle maksimum kliklerin kaybolması problemini ele alan seçici bir örtüşme stratejisidir. Bazı seçilmiş düğümlerin birden fazla bölümde yer almasına izin verilerek, önerilen yöntem bölümler arasındaki önemli bağlantıları korumakta ve kaçırılan klik sayısını azaltmaktadır. Bu sayede, çerçeve iyi bir ölçeklenebilirliği korurken daha doğru sonuçlar elde edebilmektedir. Sonuçlar, paralel maksimum klik hesaplamasının verimliliğinin çizgenin nasıl bölümlendiğine oldukça duyarlı olduğunu göstermektedir. Güncel uygulamalarda çizge boyutları büyüdükçe, dengeli bölümler oluşturmak ve işlemciler arasındaki haberleşme maliyetini de dikkate almak daha önemli hale gelmektedir. Bu tezin sonuçları, gelecekteki algoritma tasarımlarına yol gösterebilecek pratik çıkarımlar sunmayı ve paralel klik arama yöntemlerinin performansını iyileştirmeye katkı sağlamayı amaçlamaktadır.
Özet (Çeviri)
This study mainly focuses on making parallel maximum clique computation more efficient. This problem appears in many scientific and industrial areas, where dense parts of a graph usually contain important information. Although parallel algorithms try to reduce the computation time by distributing the work among multiple processors, their performance strongly depends on how the graph is partitioned and how balanced the workload is. If the partitioning is not done well, some processors may stay idle, communication cost may increase, and the total runtime can become larger. In this thesis, different partitioning strategies are analyzed, including METIS, ParMETIS, and a newly proposed overlapping-based approach. Their effects on runtime, load balance, and scalability are tested using both real-world and synthetic datasets. Instead of focusing on theoretical complexity, the analysis mainly looks at practical performance and tries to understand which partitioning behaviors lead to better results in parallel clique search. One of the main contributions of this work is a selective overlapping strategy that deals with the problem of losing maximum cliques because of strict partitioning. By allowing some selected vertices to exist in more than one partition, the proposed method keeps important connections between partitions and reduces the number of missed cliques. In this way, the framework can achieve more accurate results while still keeping good scalability. The results show that the efficiency of parallel maximum clique computation is very sensitive to how the graph is partitioned. As graph sizes become larger in modern applications, it becomes more important to create balanced partitions and also consider the communication cost between processors. The results of this thesis aim to give practical insights that can be useful for future algorithm designs and can help researchers to improve the performance of parallel clique search methods.
Benzer Tezler
- Fotovoltaik sistemlerde kısmi gölgelenme durumları için hibrit maksimum güç noktası izleyicisi tasarımı
Design of a hybrid maximum power point tracker for partial shading conditions in photovoltaic systems
TUĞBA ŞAHİN
Yüksek Lisans
Türkçe
2025
Elektrik ve Elektronik MühendisliğiSakarya ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. MEHMET BAYRAK
- Implementation of the YOLOv8 convolutional neural network block on FPGA
YOLOv8 evrişimsel sinir ağı bloğunun FPGA üzerinde gerçeklenmesi
CELİLŞAMİL İLHAN
Yüksek Lisans
İngilizce
2025
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
DR. TANKUT AKGÜL
- Effect of tip flow on vortex induced vibration of circular cylinders
Dairesel silindirlerin girdap kaynaklı titreşimlerine uç akımının etkileri
AYTEKİN DURANAY
Doktora
İngilizce
2022
Gemi Mühendisliğiİstanbul Teknik ÜniversitesiGemi ve Deniz Teknolojisi Mühendisliği Ana Bilim Dalı
DOÇ. DR. ÖMER KEMAL KINACI
- İyileştirilmiş dizi kararlı heterojen araç katarları için dağıtılmış oluşum kontrol algoritması geliştirilmesi
Distributed formation control algorithm development for improved string stability in heterogen vehicle platoons
HAKAN SERT
Yüksek Lisans
Türkçe
2018
Ulaşımİstanbul Teknik ÜniversitesiKontrol ve Otomasyon Mühendisliği Ana Bilim Dalı
DOÇ. DR. SERHAT İKİZOĞLU
- Bundling shape memory alloy wires to improve frequency response and payload lifting capability
Frekans cevabının iyileştirilmesi ve taşınabilecek yükün artırılması için şekil hafızalı alaşımların demet olarak kullanılması
SANİYE DİNDAR
Yüksek Lisans
İngilizce
2015
Bilim ve Teknolojiİstanbul Teknik ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
PROF. DR. ŞENİZ ERTUĞRUL