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
- Dokuma kumaşlarda örgü tipinin ham kumaşın boyutları ve geometrik özellikleri üzerindeki etkilerinin araştırılması
Başlık çevirisi yok
EMEL ÖNDER
- İki katlı pamuk ipliklerinden dokunan kumaşlarda örgüye bağlı olarak maksimum atkı sıklığının değişimi üzerinde bir araştırma
Başlık çevirisi yok
MELTEM ASLI NARTER
- A Decision support system for planning standby garbage collection trucks
Yedek çöp toplama kamyonlarının planlanması için bir karar destek sistemi
GÜLSER HACISALİHOĞLU
Yüksek Lisans
İngilizce
1987
Orta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
Yükleniyor...
- 1981 Türkiye tarımsal yapısının önemli bileşenleri ve tarımsal bölgelerin elde edilmesi
Principle components of Turkey's agricultural structure and to determine agricultural rigions in 1981
İHSAN KARABULUT
