Tez No	İndirme	Tez Künye	Durumu
335604		Independent task assignment for heterogeneous systems / Heterojen sistemler için bağımsız iş atama Yazar:ERTUĞRUL KARTAL TABAK Danışman: PROF. DR. CEVDET AYKANAT Yer Bilgisi: İhsan Doğramacı Bilkent Üniversitesi / Mühendislik ve Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Bölümü Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:	Onaylandı Doktora İngilizce 2013 187 s.
Bu tezde, heterojen sistemler için büyüklüğü farklılık gösteren işlerin işlemcilere dağıtılması problemleri üzerinde çalıştık. Bu bağlamda iki ayrı problemi inceledik. İlk olarak farklı işlem büyüklüğüne sahip iş katarlarının heterojen işlemcilere bir boyutlu dağıtılması problemi üzerinde durduk. İkinci olarak ise, farklı işlem büyüklüğüne sahip bağımsız işlerin heterojen sistemlerde atanması problemi üzerinde çalıştık. Farklı büyüklükteki iş katarlarının bir boyutlu parçalanması probleminde iki alt problem üzerinde çalıştık. Birincisi, zincir-zincir parçalama (ZZP) olarak bilinen bir boyutlu sıralı iş zincirinin bir boyutlu sıralı işlemci zinciri üzerine parçalama problemi, ikincisi ise zincir parçalama (ZP) olarak tanımladığımız, bir boyutlu iş zincirinin sıra önemli olmadan işlemcilere parçalama problemi. ZZP problemi için heterojen sistemlerde polinom zamanda optimal çözüm sunan algoritmalar sunduk. ZP probleminin ise NP-tam olduğunu ispatladık. Yaptığımız çalışmalar sonucunda ZZP probleminde sunduğumuz optimal çözümlerin sezgisel yöntemlerden çok daha iyi sonuçları karşılaştırılabilir sürelerde bulabildiğini ortaya koyduk. Bağımsız iş atama probleminde, bilinen ve çok kullanılan yapıcı sezgisel algoritmalardan MinMin, MaxMin ve Sufferage algoritmalarının iyileştirilmesi üzerinde çalıştık. BU sezgisel metotların N işi K işlemciye dağıtırken O(KN2) zamanda çalıştığı biliniyordu. Bu tezde, MinMin algoritmasında, çözümünü ve çözüm kalitesini değiştirmeden, çalışma zamanını O(KN log N) zamana dönüştürecek algoritmik iyileştirmeler yaptık. Ayrıca, Minmin algoritması ile MaxMin ve Sufferage algoritmalarını birleştirerek, iki adet daha hibrit algoritma elde ettik. MaxMin ile MinMin hibritlemesi, MaxMin algoritmasının özellikle kuvvet kanunu gibi özellikleri taşıyan dağılımlardaki dezavantajlarını gidermenin yanında, MaxMin algoritmasının çalışma hızını da iyileştirdi. Sufferage ile MinMin hibritlemesi ise Sufferage algoritmasının çözüm kalitesini düşürmeden çözüm hızını iyileştirdi. Algoritmalar için verdiğimiz detaylı akışlar sunduğumuz algoritmaların kolay gerçekleştirilebilir olduğunu göstermektedir. Gerçek hayattan alınan çok sayıdaki örnek veri üzerinde yaptığımız deneyler sunduğumuz MinMin ve hibrit algoritmaların klasik versiyonlarından ve diğer çok kullanılan sezgisel algoritmalardan çok daha iyi çalıştığını gösterdi. Deneylerde kullandığımız büyük ölçekli veriler için, MinMin, MaxMin ve Sufferage algoritmaları ve diğer çok kullanılan sezgisel algoritmalar günler, haftalar hatta aylar mertebesinde çalışırken, sunduğumuz algoritmalar sonuçları iki-üç dakika içinde hesaplayabildiler. Bağımsız iş atama probleminde ayrıca, graf ve hipergraf parçalama gibi uygulamalarda başarıyla kullanılmış çok katmanlı mimari yöntemlerin probleme adaptasyonu üzerinde çalıştık. Çok katmanlı mimarinin katlama aşamasında kullanılmak üzere etkili, çoğu zaman O(KN) sürede çalışan bir algoritma tasarladık. Çok katmanlı mimarinin açma kısmında kullanılmak üzere, iki adet iyileştirme algoritması tasarladık: O(KN) sürede çalışan kaydırma temelli iyileştirme algoritması ve O(K2N) sürede çalışan değiştirme temelli iyileştirme algoritması. Yaptığımız çalışmalar çok katmanlı yaklaşımların, özellikle büyük örnek veriler için hem iş atama kalitesini hem de çalışma süresi performansını ciddi olarak iyileştirdiğini ortaya koymaktadır. Bağımsız iş atama probleminin gerçekçi vir dağıtık uygulamasını göstermek üzere, iş atama eşleştirme problemini inceledik. Bu problem, Internet üzerindeki çok sayıda web sitesinin birden fazla yerde konuşlanmış dağıtık indirici sistemleri vasıtası ile en az sürede tarama işleminin gerçekleştirilmesini hedeflemektedir. Bu problemin bağımsız iş atama problemi olarak modellemesini gerçekleştirdik. Günümüzde kullanılan bağımsız iş atama algoritmalarını sunduğumuz iyileştirilmiş algoritmaları ve çok katmanlı algoritmamızı problem üzerinde deneyerek karşılaştırdık. Karşılaştırmalarımızda gerçek hayattan alınan çok büyük örnek kümeler kullandık. Sonuçlarımız, kolay gerçekleştirilebilen sezgisel yöntemler yerine, bağımsız iş atama yaklaşımının dağıtık indirici sistemlerin verimliliğini ciddi olarak arttırdığını gösterdi.
We study the problem of assigning nonuniform tasks onto heterogeneous systems. We investigate two distinct problems in this context. The first problem is the one-dimensional partitioning of nonuniform workload arrays with optimal load balancing. The second problem is the assignment of nonuniform independent tasks onto heterogeneous systems. For one-dimensional partitioning of nonuniform workload arrays, we investigate two cases: chain-on-chain partitioning (CCP), where the order of the processors is specified, and chain partitioning (CP), where processor permutation is allowed. We present polynomial time algorithms to solve the CCP problem optimally, while we prove that the CP problem is NP complete. Our empirical studies show that our proposed exact algorithms for the CCP problem produce substantially better results than the state-of-the-art heuristics while the solution times remain comparable. For the independent task assignment problem, we investigate improving the performance of the well-known and widely used constructive heuristics MinMin, MaxMin and Sufferage. All three heuristics are known to run in O(KN2) time in assigning N tasks to K processors. In this thesis, we present our work on an algorithmic improvement that asymptotically decreases the running time complexity of MinMin to O(KN logN) without affecting its solution quality. Furthermore, we combine the newly proposed MinMin algorithm with MaxMin as well as Sufferage, obtaining two hybrid algorithms. The motivation behind the former hybrid algorithm is to address the drawback of MaxMin in solving problem instances with highly skewed cost distributions while also improving the running time performance of MaxMin. The latter hybrid algorithm improves the running time performance of Sufferage without degrading its solution quality. The proposed algorithms are easy to implement and we illustrate them through detailed pseudocodes. The experimental results over a large number of real-life datasets show that the proposed fast MinMin algorithm and the proposed hybrid algorithms perform signicantly better than their traditional counterparts as well as more recent state-of-the-art assignment heuristics. For the large datasets used in the experiments, MinMin, MaxMin, and Sufferage, as well as recent state-of-the-art heuristics, require days, weeks, or even months to produce a solution, whereas all of the proposed algorithms produce solutions within only two or three minutes. For the independent task assignment problem, we also investigate adopting the multi-level framework which was successfully utilized in several applications including graph and hypergraph partitioning. For the coarsening phase of the multi-level framework, we present an efficient matching algorithm which runs in O(KN) time in most cases. For the uncoarsening phase, we present two refinement algorithms: an efficient O(KN)-time move-based refinement and an effcient O(K2N logN)-time swap-based refinement. Our results indicate that multi-level approach improves the quality of task assignments, while also improving the running time performance, especially for large datasets. As a realistic distributed application of the independent task assignment problem, we introduce the site-to-crawler assignment problem, where a large number of geographically distributed web servers are crawled by a multi-site distributed crawling system and the objective is to minimize the duration of the crawl. We show that this problem can be modeled as an independent task assignment problem. As a solution to the problem, we evaluate a large number of state-of-the-art task assignment heuristics selected from the literature as well as the improved versions and the newly developed multi-level task assignment algorithm. We compare the performance of different approaches through simulations on very large, real-life web datasets. Our results indicate that multi-site web crawling effciency can be considerably improved using the independent task assignment approach, when compared to relatively easy-to-implement, yet naive baselines.