Bulut görev çizelgelemesi için benzetilmiş tavlama tabanlı bir optimizasyon yaklaşımı
A simulated annealing-based optimization approach for cloud task scheduling
- Tez No: 529910
- Danışmanlar: DR. ÖĞR. ÜYESİ DENİZ DAL
- 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: 2018
- Dil: Türkçe
- Üniversite: Atatürk Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 145
Ö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.
Özet (Çeviri)
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.
Benzer Tezler
- Bulut bilişimde metasezgisel görev çizelgelemesi
Metaheuristic task scheduling in cloud computing
MERVE NUR AKTAN
Yüksek Lisans
Türkçe
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. HASAN BULUT
- Bulut sistemlerde görev çizelgeleme problemlerine metasezgisel bir çözüm modelinin geliştirilmesi
Developing a metaheuristic solution model to task scheduling problems in cloud systems
MÜCAHİT BÜRKÜK
Yüksek Lisans
Türkçe
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolFırat ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ GÜNGÖR YILDIRIM
- Novel data partitioning and scheduling schemes for dynamic federated vehicular cloud
Dinamik federe araç bulutu için yeni bir görev yükü paylaşımı ve iş planlaması şemaları
WISEBORN MANFE DANQUAH
Doktora
İngilizce
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. DENİZ TURGAY ALTILAR
- Multi-objective task scheduling in heterogeneous fog environments
Heterojen sis ortamlarında çok amaçlı görev zamanlaması
LOKMAN ALTIN
Doktora
İngilizce
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. SADIK FİKRET GÜRGEN
PROF. DR. HALUK RAHMİ TOPCUOĞLU
- Dynamic multi-objective workflow scheduling in cloud computing
Bulut hesaplama için dinamik çok-amaçlı iş akışı çizelgelenmesi
GOSHGAR ISMAYILOV
Yüksek Lisans
İngilizce
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. HALUK RAHMİ TOPCUOĞLU