Yeni nesil dizelemede optimal iş akışı çizelgeleme
Optimal workflow scheduling in next generation sequencing
Yazar: GÜLÇİN YILDIZ
Danışman: PROF. DR. FATİH ERDOĞAN SEVİLGEN
Gebze Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2023
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Dinamik çizelgeleme = Dynamic scheduling

Özet:
Çizelgeleme, işlemci kaynağı üzerinde bir veya birden fazla uygulamanın maksimum tamamlanma süresini etkileyen önemli bir unsurdur. Çok sayıda araştırma, uygulamaların veri bağımlılığı olan işlemlerini yönlü döngüsüz çizge (DAG) ile modelleyerek çizelgeleme problemini ele almıştır. Uygulamanın bir işlemi, birden fazla işlemci üzerinde yürütülebiliyorsa veri paralel ismini alır. DAG ile modellenen ve veri paralel işlemler içeren uygulamaların çizelgelemesi problemi için birçok çalışmada veri paralel işlemlere tahsis edilecek işlemci sayısının belirlenmesi (işlemci tahsisi) ve yürütme sırasının belirlenmesi ile işlemlerin uygun işlemcilere atanması (çizelgeleme) prosedürleri için çözüm geliştirilir. Bu tez çalışmasında da veri paralel işlemler içeren DAG ile modellenen uygulamaların homojen işlemci kaynağında statik ve dinamik çizelgeleme problemi ele alınmıştır.
Statik çizelgeleme problemi için geliştirilmiş CPA, MCPA, MCPA2, IAES gibi açgözlü algoritmalar vardır. Tez çalışmasında işlemci tahsisi prosedürü için açgözlü algoritmaların işlemci tahsisi sezgisellerini kullanan hiper-sezgisel bir yöntem geliştirilmiştir. Hiper-sezgisel yöntem ile açgözlü algoritmaların işlemci tahsisindeki güçlü yönlerinden faydalanılmıştır. 
Dinamik çizelgeleme problemi için literatürde az sayıda çalışma olduğu gözlemlenmiştir. Dinamik çizelgeleme probleminde iş akışlarının sisteme varış zamanı bilinemez. Tez çalışması kapsamında, iş akışlarının sisteme varış zamanında işlemci tahsisi ve çizelgelemeyi tekrar tetiklemesi ile çözüme ulaşılır. İşlemci tahsisinde geliştirilen hiper-sezgisel yöntem kullanılmıştır.  Çizelgeleme prosedürü için de genetik algoritma (meta-sezgisel yöntem) ile çözüm geliştirilmiştir. 
Deneysel çalışmalarda statik çizelgelemede önerilen algoritma CPA algoritmasına göre ortalama %14, MCPA algoritmasına göre %7, MCPA2 algoritmasına göre %9, IAES algoritmasına göre %5 daha başarılı sonuç vermiştir. Dinamik çizelgelemede ise önerilen algoritma ile hiper-sezgisel işlemci tahsisi CPA ile işlemci tahsisine göre %16, IAES ile işlemci tahsisine göre %14, MOWS algoritmasına göre %20 daha başarılı sonuç vermiştir.

Abstract:
Scheduling is an important factor affecting the maximum completion time of one or more applications on the processor resource. In many studies, the scheduling problem has been expressed by modeling the data dependencies of applications with a directed acyclic graph (DAG). If a task of the application can be executed on more than one processor, it is called data parallel. In the scheduling problem of the application represented by DAG and containing data parallel tasks, the stages of determining the number of processors to be allocated to the data parallel tasks (processor allocation) and determining the execution order (scheduling) are considered. In this thesis, the problem of static and dynamic scheduling of applications including data parallel tasks and modeled by DAG on homogeneous processor resource is solved.
In the static scheduling problem, there are greedy algorithms such as CPA, MCPA, MCPA2, IAES. In this thesis, a hyper-heuristic method using heuristics of greedy algorithms is developed for the processor allocation. The hyper-heuristic method takes advantage of the processor allocation strengths of heuristics.
It has been observed that there are few studies in the literature for workflows in the dynamic scheduling problem. In the dynamic scheduling problem, the arrival time of the workflows in the system are not known. In the thesis study, a genetic algorithm (meta-heuristic method) solution has been developed for the scheduling procedure of the dynamic scheduling problem. For the processor allocation, the developed hyper-heuristic method is used.
In experimental studies, the algorithm recommended for static scheduling has yielded an average of 14% better results compared to the CPA algorithm, 7% better results compared to the MCPA algorithm, 9% better results compared to the MCPA2 algorithm, and 5% better results compared to the IAES algorithm. In dynamic scheduling, the proposed algorithm has resulted in 16% better processor allocation compared to processor allocation with CPA, 14% better processor allocation compared to IAES, and 20% better results compared to the MOWS algorithm.