ParPaToH: A 2D parallel hypergraph partitioning tool
ParPaToH: Bir 2-boyutlu paralel hiperçizge bölümleme aracı
- Tez No: 180671
- Danışmanlar: PROF. DR. CEVDET AYKANAT
- Tez Türü: Yüksek Lisans
- Konular: Mühendislik Bilimleri, Engineering Sciences
- Anahtar Kelimeler: Multilevel hypergraph partitioning, parallel computing.iii
- Yıl: 2006
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 59
Özet
Hiperşizge bülü mleme, hacim boyama, bilgi getirme ve VLSI devre tasarımı gibi,c oudeğişik alanlardaki en iyileme sorunlarını cozmek işin kullanılan bir işlemdir.gs şü c sVarolan bülü mleme yüntemleri bell irli bir boya kadar olan hiperşigeler işinou o c ccalışıyor olsa da, bu boyu aşan hiperşizgeler işin yetersiz kalmaktadır.şs s c cBu tezde, iletişim yü kü nü azaltmak işin 2-boyutlu bir veri bülü mlemesi kul-s uuu c oulanan ve kabul gürmüş cok-dü zeyli bülü mleme paradigmasını parallel işlemeye uy-o us ş u ou sgun hale getirmiş bir p-yün parallel hiperşizge bülü mleme aracı olan ParPaToH'us o c outakdim ediyoruz. Bü yü k olşekli iletişime izin veren yeni hiperşizge bülü mlemeu u üc s c oukavramlarını aşıkladıktan sonra, aracın yapısını detaylı bir şekilde anlatıp, etk-c sililiğini güzler onü ne seren deney sonuşlarını sunuyoruz.g o üu cAnahtar süzcükler : Cok-dü zeyli hiper cizge bülü mleme, paralel işleme.ou ş u ş ou siv
Özet (Çeviri)
Hypergraph partitioning is a process that is being used to ï¬nd solutions foroptimization problems in various areas, including parallel volume rendering, par-allel information retrieval and VLSI circuit design. While the current partitioningmethods are adequate for hypergraphs up to certain size, these methods start tofail once the problem size exceeds this threshold.In this thesis we introduce ParPaToH, a parallel p-way hypergraph partition-ing tool that makes use of a 2-D decomposition to reduce the communicationoverhead and implements a parallel-computing friendly version of the acceptedmulti-level partitioning paradigm to generate its partitioning. We present newconcepts in hypergraph partitioning that lead to a coarse-grain parallel solution.Finally, we discuss the implementation of the tool in detail and present experi-mental results to demonstrate its eï¬ectiveness.