Bulut Görev Çizelgelemesi için Benzetilmiş Tavlama Tabanlı Bir Optimizasyon Yaklaşımı
Tezin Türü: Yüksek Lisans
Tezin Yürütüldüğü Kurum: Atatürk Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği, Türkiye
Tezin Onay Tarihi: 2018
Tezin Dili: Türkçe
Öğrenci: Esra ÇELİK
Danışman: Deniz Dal
Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu
Özet:Her geçen gün ilerleyen teknoloji, kapasitesi hızla artan ve geleneksel algoritmalar/donanımlar ile işlenemeyen büyük veriyi beraberinde getirmektedir. Bu verinin depolanması, makul sürelerde işlenebilmesi ve analiz edilmesi için de dağıtık büyük veri kümelerine ihtiyaç duyulmaktadır. Bu tür veri kümelerine ise bulut bilişim hizmeti veren altyapılarda sıklıkla rastlanmaktadır. Görev çizelgeleme, bu veriyi analiz etmek için kullanılacak görevlerin tamamının söz konusu küme düğümleri (sunucuları) üzerinde en kısa sürede işletilmesine imkân verecek görev-sunucu eşleştirmesi işleminin adıdır. Başka bir deyişle çizelgeleme, NP-hard olarak da kategorize edilen ve global minimum arayan bir optimizasyon problemidir. Dolayısıyla bu problemin optimuma yakın (eğer mümkünse optimum) değerleri makul sürelerde üretebilecek şekilde çözüme kavuşturulması için metasezgisel yaklaşımların yardımına ihtiyaç duyulmaktadır. Bu tez kapsamında görev çizelgeleme için benzetilmiş tavlama tabanlı bir metasezgisel yaklaşım geliştirilmiştir ve bu yaklaşımın seri ve paralel versiyonları C++ programlama dili kullanılarak bir bilgisayar programına dönüştürülmüştür. Paralel versiyon için aynı zamanda OpenMP kütüphanesinden faydalanılmıştır. Benzetilmiş tavlama isimli metasezgisel, esin kaynağını metalurji biliminden almaktadır. Yüksek sıcaklıklara kadar ısıtılan metaller rastgele sıvı hale dönüşmekte ve uygun bir şekilde yavaşça soğutulduklarında düzenli bir kristal yapıya kavuşmaktadır. Bu gözlemden esinlenen benzetilmiş tavlama yöntemi de eldeki problemi temsil eden rastgele bir ilk çözümü yüksek sıcaklıklardan başlayarak ve bu sıcaklığı her adımda yavaşça azaltarak arzulanan global çözüme yaklaştırmayı hedeflemektedir. Geliştirilen yaklaşımın yetkinliği görev çizelgeleme algoritmalarının performanslarını karşılaştırmak için kullanılan ve Braun modeliyle oluşturulmuş on iki meşhur benchmark ile test edilmiştir. Önerilen yaklaşımın hem seri hem de paralel versiyonu, tüm benchmarklar için, literatürde şu ana kadar bir sezgisel veya metasezgisel kullanılarak rapor edilen en iyi gecikme değerlerinden daha iyi sonuçları 90 saniye kısıtı içerisinde üretebilmiştir. Geliştirilen bilgisayar programının çalışma süresinin azaltılması ve üretilen çözümlerin kalitesinin arttırılması için, benzetilmiş tavlamanın ihtiyaç duyduğu farklı rastgele sayı üretme ve pertürbasyon teknikleri, veri yapıları, döngü sonlandırma koşulları, keşif-sömürme oranları ve derleyici etkisi yine bu tez kapsamında detaylı olarak analiz edilmiştir.