Combinatorial reductions between graph partitioning by vertex separator and hypergraph partitioning problems for parallel and scientific computing applications
Paralel ve bilimsel hesaplama uygulamaları için hiperçizge bölümleme ve düğüm ayıracı ile çizge bölümleme problemlerinin birbirine kombinatoriyal dönüştürümü
- Tez No: 246620
- Danışmanlar: PROF. DR. CEVDET AYKANAT
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2009
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Bölümü
- Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Sayfa Sayısı: 105
Özet
Hiperçizge Bölümleme (HB) ve Düğüm Ayıracı ile Çizge Bölümleme (DACB) problemleriliteratürde gayet bilinen, koşut ve bilimsel hesaplamalarda etkin biçimde kullanılan problemlerdir. Koşut hesaplamalarda tipik bir problem, verilerin ve görevlerin değişik sayıda işlemciye öyle şekilde dağıtılmasıdır ki hesaplamanın çalışma performansı zaman ve yer gereksinimleri açısından hızlı ve verimli olsun. Bunun yanında, DACB problemi seyrek doğrusal sistemlerin verimli çözülebilmesi için doluluk azaltan sıralama yapmak için etkin biçimde kullanılmaktadır. Bu da bilimsel hesaplamanın konu sahası içine girmektedir. Bu tez çalışmasında, HB ve DACB problemleri arasındaki ilişki incelenmektedir. Bu bağlamda, iki kombinatoriyal dönüştürüm açığa çıkarılmıştır. Birinci dönüştürme, HB probleminden DACB problemine, ikincisi ise DACB probleminden HB probleminedir. HB probleminden DACB problemine dönüştürmede girdi dönüşümü kolay olmamaktadır. Girdi dönüşümünden kasıt, verilen bir çizgeyi, problem dönüştürümü uygun olacak şekilde bir hiğerçizgeye dönüştürmektir. DACB probleminden HB problemine dönüştürümde ise çıktı dönüşümü kolay olmamaktadır. Burada da kasıt, verilen bir çizge bölümlemeyi asıl problemimiz olan hiperçizge bölümlemeye dönüştürmektir. Bu kısımda önemli ve faydalı imkansizlık sonuçları türetilmiştir. Bu kolay olmayan kısımlar derinliğince incelenmiş, etkili ve verimli çözümler ve yöntemler önerilmiştir.Bu çalışma çerçevesinde, bir HB tabanlı doluluk azaltan sıralama aracı olan oPaToH, gelişmiş girdi dönüşümleri ile genişletilmiştir. Bunun yanında, başka bir doluluk azaltan sıralama aracı olan onmetıs kullanılarak DACB tabanlı bir HB aracı olan ?hpmetis? üretilmiştir. Ayrıca, yine onmetis kullanılarak bir Dantzig-Wolfe ayrıştırma aracı olan ?dwmetis? üretilmiştir. Dantzig-Wolfe ayrıştırma ise doğrusal problemlerin etkin koşutlanmasında kullanılmaktadır. Deneysel sonuçlarımız gösterdi ki, genişletilen oPaToH, seyrek doğrusal sistem çözümünde hali hazırdaki iyi yöntemlere göre %20'lere varan iyileşme göstermiştir. Üretilen Dantzig-Wolfe ayrıştırma aracı dwmetis ise hali hazırda kullanılan HB tabanlı yöntemlere göre makul kalıte farklılıklarında 5 kata kadar hızlı sonuç üretebilmiştir. Bu sonuç da gayet değerlidir, çünkü toplam performans ölçülürken önçalışma zamanı da değer taşımaktadır. Sonuç olarak, bu çalışmada gösterildi ki koşut ve bilimsel hesaplama işlemlerinin, HB ve DACB problemlerini birbirlerine dönüştürümü kullanılarak daha hızlı çalışmaları sağlanabilmektedir.
Özet (Çeviri)
Hypergraph Partitioning (HP) and Graph Partitioning by Vertex Separator (GPVS)problems are very well known problems which are used in scienti ? c and parallel com-puting effectively. A typical problem in parallel computing is to partition the data/tasksinto several processors such that the overall performance of the computation gets morequali ? ed in terms of time and/or memory. Besides, GPVS is generally used for ? ll-reducing ordering of sparse matrices for solving sparse linear systems ef ? ciently whichlies in the area of scienti ? c computing. In this thesis, the relation between these twoproblems, HP and GPVS problems, are investigated. Two combinatorial reductions,from HP Problem to GPVS Problem and from GPVS Problem to HP Problem are dis-closed along with their theoretical bases. In practice, the nontrivial part of HP Problemto GPVS Problem reduction is the input transformation, that is, converting a graph toa hypergraph such that the reduction holds. The nontrivial part of the reduction fromGPVS Problem to HP Problem is the output transformation, that is, decoding a vertexseparator of the corresponding graph to a partition for the hypergraph. In this part,some useful impossibility results are derived. These nontrivial parts are investigateddeeply and effective and ef ? cient algorithms and methods are proposed.Furthermore, ?oPaToH?, an HP-based ? ll-reducing ordering tool based on PaToH,is enhanced along with implementation of input transformations. Besides, based on? ll-reducing ordering tool onmetis, a GPVS-based HP tool ?hpmetis? is derived anda Dantzig-Wolfe decomposition tool for ef ? cient parallelizm of linear programmingproblem solutions is constructed, which is called as ?dwmetis?. The ? ll-reducing or-dering results obtained with enhanced oPaToH produced more quali ? ed ordering re-sults such as up to %20 improvements for operation count compared to state-of-theart ordering tools such as onmetis. Note that decreasing operation count relates toperforming sparse linear equation solutions faster. The Dantzig-Wolfe decompositionresults with dwmetis produced results around 5 times faster than the state-of-the arthypergraph partitioning tool PaToH with comparable quality for net balancing. Thisis also valuable because the preprocessing overhead is also considered inside the totalexecution time, generally. As a result, in this work it is showed that parallel and sci-enti ? c computing applications can be performed faster by exploiting the combinatorialreductions between HP problem and GPVS problem.
Benzer Tezler
- Hücresel imalat sistemlerinde maliyet ve sinir ağları tabanlı iki evreli bir kümelendirme yaklaşımı
Artificial neurat network x operation costs based twostage GT clusterning procedure
AFFAN NOMAK
Yüksek Lisans
Türkçe
1995
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiDOÇ.DR. BÜLENT DURMUŞOĞLU
- Elektrik dağıtım sistemlerinde kayıp azaltımı için fider düzenlemesi
Distribution feeder reconfiguration for loss reduction
DİLEK DİNÇER
Yüksek Lisans
Türkçe
1997
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik Mühendisliği Ana Bilim Dalı
DOÇ. DR. ADNAN KAYPMAZ
- Metal yüklü grafen yapılarının akciğer kanserinin ön tanısı için biyosensör olarak kullanılabilirliğine yönelik DFT çalışması
DFT study on the feasibility of using metal doped graphene structures as biosensors for the preliminary diagnosis of lung cancer
ŞEYMA KORUCU
Yüksek Lisans
Türkçe
2024
BiyoteknolojiBursa Teknik ÜniversitesiKimya Mühendisliği Ana Bilim Dalı
PROF. DR. MEHMET FERDİ FELLAH
- GAP (grup, algoritma ve programlama)ve monoid polinomları ile ilgili uygulamalar
GAP (group, algorithm and programming) and applications related to monoid polynomials
SEVİLAY İLGİN
Yüksek Lisans
Türkçe
2022
MatematikKaramanoğlu Mehmetbey ÜniversitesiMatematik Ana Bilim Dalı
PROF. DR. EYLEM GÜZEL KARPUZ
- Importance of ASC expression for melanoma tumorigenesis in vivo and a role for inflammasome activation in apoptosis induction
ASC anlatımının canlı içinde melanoma tümorogenezi üzerindeki etkisi ve apoptoz indüklemesinde inflamazom aktivasyonunun rolü
METEHAN ÇİFDALÖZ
Yüksek Lisans
İngilizce
2010
BiyolojiBoğaziçi ÜniversitesiMoleküler Biyoloji ve Genetik Ana Bilim Dalı
DOÇ. DR. NESRİN ÖZÖREN