Yeni nesil dizelemede optimal iş akışı çizelgeleme
Optimal workflow scheduling in next generation sequencing
- Tez No: 827808
- Danışmanlar: PROF. DR. FATİH ERDOĞAN SEVİLGEN
- 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: 2023
- Dil: Türkçe
- Üniversite: Gebze Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 93
Ö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.
Özet (Çeviri)
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.
Benzer Tezler
- Recombinant production and characterization of serine protease enzyme from Virgibacillus sp. AGTR strain
Virgibacillus sp. AGTR suşundan izole edilen serin proteaz enziminin rekombinant üretimi ve karakterizasyonu
BEGÜM ÖZDEN
Yüksek Lisans
İngilizce
2019
Biyoteknolojiİstanbul Teknik ÜniversitesiMoleküler Biyoloji-Genetik ve Biyoteknoloji Ana Bilim Dalı
PROF. DR. NEVİN GÜL KARAGÜLER
- Yeni nesil dizileme sisteminin tanıda uygulanması ve sonuçların biyoinformatik yöntemlerle değerlendirilmesi
Application of new generation sequencing system to diagnosis and approach of bioinformatic tools
NARMIN AHMADOVA
Yüksek Lisans
Türkçe
2019
Bilim ve TeknolojiEge ÜniversitesiBiyomedikal Teknolojiler Ana Bilim Dalı
PROF. DR. AFİG BERDELİ
- Nörofibromatozis tip1 olgularında NF1 gen mutasyonlarının yeni nesil dizileme teknolojisi ile araştırılması
Investigation of NF1 gene mutations with next generation sequencing technology in neurofibromatosis type1 cases
SHAHRASHOUB SHARIFI
- Nanopore dizileme teknolojisi ile SNP panelinin geliştirilmesi
Development of SNP panel with nanopore sequencing technology
VEYSEL SAPAN
Yüksek Lisans
Türkçe
2022
Adli Tıpİstanbul Üniversitesi-CerrahpaşaFen Bilimleri Ana Bilim Dalı
DOÇ. ÖZLEM BÜLBÜL ERCAN
- Illumına ve DNB sekanslama teknolojileri ile elde edilen özel gen dizileme verilerinin karşılaştırılması
Comparison of in house gene sequencing data obtained by illumina and DNB sequence technologies
TUĞÇE ACAR
Yüksek Lisans
Türkçe
2023
GenetikYıldız Teknik ÜniversitesiMoleküler Biyokimya ve Genetik Ana Bilim Dalı
PROF. DR. MUHAMMED HAMZA MÜSLÜMANOĞLU