A bipartite graph model for placement, scheduling and replication in data grids
Veri gridlerinde yerleştirme, çizelgeleme ve çoklama için iki-kısımlı çizge modeli
- Tez No: 313518
- 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: 2012
- 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ı: Belirtilmemiş.
- Sayfa Sayısı: 81
Özet
Veri gridleri, büyük veri setleri üreten ve kullanan uygulamalar için coğrafi olarak dağıtılmış kaynaklar sağlar. Halbuki, veri gridlerinde veriye hızlı erişim ve işler için düşük yanıt süresi temin etme durumları, çeşitli sebeplerden dolayı engellenmektedir. Bu sorunları ele almak için, yüksek veri elverişliliği, düşük bant genişliği tüketimi ve indirgenmiş yanıt süresi sağlayan değişik veri çoklama ve iş çizelgeleme stratejileri sunulmuştur. Veri çoklama sayesinde, veri farklı konumlarda çok kopyalı şekilde muhafaza edilmektedir. Ayrıca, grid üzerinde etkili bir şekilde iş çizelgeleme yaparak, sistem verimliliğinin arttırılması amaçlanmıştır. Çoklama stratejileri genelde statik ve dinamik olarak sınıflandırılır. Statik çoklama stratejilerinde, çoklama kararları çoğunlukla grid sistemindeki veri erişim maliyetlerini, bant genişliği özelliklerini ve saklama kısıtlarını kapsayan bir maliyet modeline dayanarak verilir ve çoklama işlemi sistemin tasarlanması sırasında yapılmaktadır. Dinamik çoklama stratejilerinde çoklama işlemi, kullanıcı isteği deseninindeki değişiklikleri sisteme uyarlamak için çalışma zamanında yapılmaktadır. İş çizelgeleme stratejileri, çevrimiçi mod ve toplu mod olmak üzere iki genel kategorinin içinde yer alırlar. Çevrimiçi mod çizelgeleyicisi, bir işi ulaşır ulaşmaz bir makineye atar. Toplu mod yönteminde, bütün grid bilgisini kullanarak, bütün işler aynı anda ele alınır ve çizelgelenir.Biz bu çalışmada, grid sistemindeki işleri ve verileri temsil eden bir“iki kısımlı çizge”modeli önermekteyiz. Veri yerleştirme ve iş çizelgeleme stratejisi elde etmek için bu çizgeyi bölüntülüyoruz. Elde edilen bölüntüler, yerleşkeler arasındaki bant genişliğini ve hoplama bilgisini hesaba katan KL-tabanlı buluşsal bir çizge bölüntüleme yöntemi kullanarak, grid yerleşkelerine atama yapmak için yeniden iyileştirilmektedir. Çoklama, bölüntüleme sürecinden önce seçilen en çok erişilen dosyaların belli bir miktarını kopyalarak gerçekleştirilir. Deneysel sonuçlar göstermektedir ki, bölüntüleme kalitesindeki artış, atama kalitesine olumlu şekilde yansımaktadır. Buna ek olarak, veri çoklama uygulandığında iletişim maliyetinin dikkate değer ölçüde düştüğü gözlemlenmiştir.
Özet (Çeviri)
Data grids provide geographically distributed resources for applications that generate and utilize large data sets. However, there are some issues that hinder to ensure fast access to data and low turnaround time for the jobs in data grids. To address these issues, several data replication and job scheduling strategies have been introduced to offer high data availability, low bandwidth consumption, and reduced turnaround time for grid systems. Multiple copies of existing data are maintained at different locations via data replication. Data replication strategies are broadly categorized as static and dynamic. In static replication strategies, replication is performed during the system design, and replica decisions are generally based on a cost model that includes data access costs, bandwidth characteristics and storage constraints of the grid system. In dynamic replication strategies, the replication operation is managed at runtime so that the system adapts to the changes in user request patterns dynamically. Job scheduling strategies fall under two main categories: online mode and batch mode. The online mode scheduler assigns tasks to sites as soon as they arrive. In the batch mode, the complete set of jobs are taken into account and scheduled at the same time by using all the grid information.In this thesis, we propose a bipartite graph model for tasks and files in the grid system, and then we partition this graph to obtain a data placement and job scheduling strategy. The obtained parts are further refined in order to be assigned to grid sites by using a KL-based heuristic that takes the bandwidth and hop information between sites into account. Replication is achieved by replicating a certain amount of most accessed files chosen prior to the partitioning process. Experimental results indicate that the increase in the partitioning quality reflects positively on the mapping quality. Morever, it is observed that the communication cost is notably decreased when the data replication is applied. Hence, our results show that by replicating a small amount of data files and placing files onto sites using bipartite graph model, we can obtain performance improvement for scheduling jobs compared to no replication.
Benzer Tezler
- Semantik veri modellerinde bellekte kalıcı girişler için indeks seçimi
Selection of indexes to memory-resident entities for data models
EDA SÜRÜCÜ
- Reducing communication volume overhead in large-scale parallel SpGEMM
Büyük ölçekli paralel SyGEMM'de iletişim hacmini düşürme
BAŞAK ÜNSAL
Yüksek Lisans
İngilizce
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT
- Klasik ve ağ kodlamalı OFDMA sistemlerde alt-taşıyıcı atama
Subcarrier allocation in conventional and network coded OFDMA systems
BUĞRA ENGİN
Yüksek Lisans
Türkçe
2015
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. İBRAHİM ALTUNBAŞ
- Automatic synset detection from Turkish dictinary using confidence indexing
Güven endeksi kullanılarak Türkçe sözlükten eş anlam kümelerinin otomatik tespiti
ERHAN TURAN
Doktora
İngilizce
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolÇukurova ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. UMUT ORHAN
- Talep tahmini için model topluluklarının kullanılması
Using ensembles of classifiers for demand forecasting
İREM İŞLEK
Yüksek Lisans
Türkçe
2015
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. ŞULE ÖĞÜDÜCÜ