Independent task assignment for heterogeneous systems

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.