Bulut görev çizelgelemesi için benzetilmiş tavlama tabanlı bir optimizasyon yaklaşımı

Abstract

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.

The technology advancing with each passing day brings a huge data along the way that grows very rapidly and cannot be processed with traditional algorithms/hardware. Storing, processing and analyzing these data in a reasonable amount of time require distributed data clusters. Such data clusters are frequently encountered in infrastructures that provide cloud services. Task scheduling is the name of the task-server mapping process that will allow all of the tasks to be used to analyze this data to be run on those cluster nodes (servers) as soon as possible. In other words, scheduling is an optimization problem categorized as NP-hard and seeking global minimum. Therefore, there is a need for metaheuristic approaches to solve this problem in such a way that it can produce near-optimum (if possible optimal) values at reasonable times.In this thesis, a simulated annealing based metaheuristic approach was developed for task scheduling and serial and parallel versions of this approach were transformed into a computer program using C ++ programming language. For the parallel version, the OpenMP library was also used. The metaheuristic called simulated annealing takes its inspiration from metallurgical science. Metals heated up to high temperatures are converted into a liquid state and, if properly cooled slowly, have a regular crystal structure. The simulated annealing method, inspired by this observation, aims at bringing a first initial solution to a desired global solution, starting at high temperatures and gradually decreasing this temperature at every step.The effectiveness of the proposed approach has been tested by twelve famous benchmarks, which are formed by the Braun model to compare the performance of task scheduling algorithms. Both the serial and the parallel version of the proposed approach were able to produce better results for all benchmarks than the best latency values reported in the literature within the time constraint of 90 seconds. In order to decrease the execution time of the developed computer program and to improve the quality of the solutions produced, different random number generation and perturbation techniques, data structures, early termination conditions, exploration-exploitation rates and compiler effect required by simulated annealing were also analyzed in detail within the scope of this thesis.