Geri Dön

Replicated hypergraph partitioning

Çoklamalı hiperçizge bölümleme

PDF İndir

  1. Tez No: 275102
  2. Yazar: REHA OĞUZ SELVİTOPİ
  3. Danışmanlar: PROF. DR. CEVDET AYKANAT
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2010
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. Tez No

    246588

    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

    İngilizce

    2009

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Bilgisayar Mühendisliği Bölümü

    PROF. DR. CEVDET AYKANAT

  2. Tez No

    575184

    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

    İngilizce

    2019

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. MUHAMMET MUSTAFA ÖZDAL

    PROF. DR. CEVDET AYKANAT

  3. Tez No

    336855

    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

    İngilizce

    2013

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. CEVDET AYKANAT

  4. Tez No

    403453

    Dual layer scale free network topology synthesis

    Başlık çevirisi yok

    MEHMET BURAK AKGÜN

    Doktora

    İngilizce

    İngilizce

    2014

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolUniversity of Nevada-Reno

    Dr. MEHMET HADİ GÜNEŞ

  5. Tez No

    485187

    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

    Türkçe

    2017

    Gemi Mühendisliğiİstanbul Teknik Üniversitesi

    Gemi İnşaatı ve Gemi Makineleri Mühendisliği Ana Bilim Dalı

    PROF. DR. AHMET ERGİN

Geri Dön