Replicated hypergraph partitioning
Çoklamalı hiperçizge bölümleme
- Tez No: 275102
- 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: 2010
- 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ı: 68
Özet
Hiperçizge bölümleme son zamanlarda dağıtık veri erişimi ve uzamsal veri tabanlarında iletişim ve disk erişim maliyetlerini doğru bir sekilde yakalamak için kullanılmıştır. Bu alanlardaki hiperçizge modellerinde, hiperçizge bölümleme kullanılarak elde edilen bölümlerin kalitesi hedeflenen problemin objektifi için çok önemli olabilir. Çoklama, dağıtık veri erişimi ve veri tabanı sistemlerinde çeşitli performans meselelerini ele almak için yaygın olarak kullanılan bir terminolojidir. Çoklamanın arkasındaki ana motivasyon, hedeflenen konunun performansını daha fazla alan kullanma pahasına geliştirmektir.Bu çalışmada, hiperçizge bölümlemenin kalitesini düğüm çoklamasıyla geliştiren hiperçizge bölümleme şemalarının üstüne odaklanıyoruz. Bu aşamada, çoklama ve bölümlemenin bir arada yapıldığı bir çoklamalı hiperçizge bölümleme şeması öneriyoruz. Yaklaşımımız, hiperçizge bölümlemesi için başarılı çok seviyeli ve özyinelemeli ikiye bölümleme yöntemlerini kullanmaktadır. Çoklama, çok seviyeli yöntemin açılma safhasında verimli Fiduccia-Mattheyses (FM) yinelemeli geliştirme sezgiselini genişleterek elde edilmektedir. Bu genişletilmiş versiyona çoklamalı FM (rFM) diyoruz. Önerilen rFM sezgiseli yeni algoritmalar ve köşe durumları öne sürerek taşıma, çoklama ve azlama işlemlerini desteklemektedir. Önerilen çoklama şemasını çok seviyeli hiperçizge bölümleme aracı PaToH'a entegre edip çeşitli gerçekçi veri takımları üstünde test ediyoruz.
Özet (Çeviri)
Hypergraph partitioning is recently used in distributed information retrieval (IR)and spatial databases to correctly capture the communication and disk accesscosts. In the hypergraph models for these areas, the quality of the partitionsobtained using hypergraph partitioning can be crucial for the objective of thetargeted problem. Replication is a widely used terminology to address differentperformance issues in distributed IR and database systems. The main motivationbehind replication is to improve the performance of the targeted issue at the costof using more space.In this work, we focus on replicated hypergraph partitioning schemes that im-prove the quality of hypergraph partitioning by vertex replication. To this end,we propose a replicated partitioning scheme where replication and partitioningare performed in conjunction. Our approach utilizes successful multilevel andrecursive bipartitioning methodologies for hypergraph partitioning. The repli-cation is achieved in the uncoarsening phase of the multilevel methodology byextending the efficient Fiduccia-Mattheyses (FM) iterative improvement heuris-tic. We call this extended heuristic replicated FM (rFM). The proposed rFMheuristic supports move, replication and unreplication operations on the verticesby introducing new algorithms and vertex states. We show rFM has the samecomplexity as FM and integrate the proposed replication scheme into the mul-tilevel hypergraph partitioning tool PaToH. We test the proposed replicationscheme on realistic datasets and obtain promising results.
Benzer Tezler
- Exploiting replicated data for communication load balancing in image-space parallel direct volume rendering of unstructured grids
Düzensiz ızgaralarda görüntü-uzayı paralel hacim görüntüleme için iletişim yükü eşitlemede kopyalanmış veriden faydalanma
ERKAN OKUYAN
Yüksek Lisans
İngilizce
2009
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Bölümü
PROF. DR. CEVDET AYKANAT
- Fast and efficient model parallelism for deep convolutional neural networks
Derin konvolüsyonel sinir ağları için hızlı ve verimli model paralelleştirmesi
BURAK ESEROL
Yüksek Lisans
İngilizce
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. MUHAMMET MUSTAFA ÖZDAL
PROF. DR. CEVDET AYKANAT
- Data distribution and performance optimization models for parallel data mining
Koşut veri madenciliği için veri dağıtımı ve başarım optimizasyon modelleri
ERAY ÖZKURAL
Doktora
İngilizce
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT
- Dual layer scale free network topology synthesis
Başlık çevirisi yok
MEHMET BURAK AKGÜN
Doktora
İngilizce
2014
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolUniversity of Nevada-RenoDr. MEHMET HADİ GÜNEŞ
- Serbest düşme filikalarında yolcu güvenliği
Occupant safety in free fall lifeboats
MEHMET BURAK KOÇAK
Yüksek Lisans
Türkçe
2017
Gemi Mühendisliğiİstanbul Teknik ÜniversitesiGemi İnşaatı ve Gemi Makineleri Mühendisliği Ana Bilim Dalı
PROF. DR. AHMET ERGİN