Job scheduling for heterogeneous supercomputers
Heterojen süperbilgisayarlar için iş çizelgeleme
- Tez No: 433929
- Danışmanlar: PROF. DR. CAN ÖZTURAN
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2016
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 140
Özet
Bu tez, GPGPU veya ekişlemci gibi hızlandırıcıların kullanıldığı heterojen süperbilgisayarlardaki iş çizelgeleme problemini ele almaktadır. Homojen süperbilgisayarlarda, mevcut kaynaklara kullanıcı işlerinin çizelgelenmesi problemi NP-zor sınıfındadır. Heterojen sistemler iş çizelgeleme problemini birleşimsel olarak daha zor yapmaktadırlar. Bu tezde amaçlarımız (i) son teknoloji heterojen süperbilgisayarlar için yeni tür iş çizelgeleme algoritmaları tasarlamak, (ii) bu algoritmaları kullanılmaya hazır açık kaynak kodlu yazılım ekleri olarak gerçekleştirmek ve (iii) bu algoritmaların etkinliğini gerçcek hayat kullanımını öykünerek göstermektir. Heterojen süperbilgisayarlardaki iş çizelgeleme problemini çözmek için dört farklı model önerilmiştir. İlk modelde, topolojiyi dikkate almayan basit bir beraber tahsis etme problemi formülleştirilmiştir. İkinci modelde, problemi bir müzayede problemi olarak ele alıp ve bir boyutlu bir sistem topolojisi varsayarak her iş için otomatik olarak birden fazla teklif yaratılmıştır. Üçüncü modelde, sayı aralıkları kullanarak kaynak istekleri yapabilen şekillendirilebilir işler desteklenmiştir. Dördüncü ve son modelimizde, hiyerarşik şekilde bağlanmış şişman-ağaç topolojisi de dikkate alınmıştır. Tüm bu modeller tam sayı programlama problemi olarak formüle edilip, her çizelgeleme adımında periyodik olarak çözülmektedir. Çizelgeleme algoritmalarının başarımlarını test etmek için daha önceden tanımlanmış olan iş yüklerine ek olarak, heterojen sistemler için daha gerçekçi iş yükleri yaratacak olan kendi iş yükü üreticimiz de geliştirilmiştir. Yapılan testler algoritmalarımızın geleneksel geri dolgulama algoritmalarından sistem kullanımı, ortalama iş bekleme süresi ve/veya iş parçalanması açılarından bakınca daha iyi performans ortaya koyduğunu göstermektedir.
Özet (Çeviri)
This thesis addresses the job scheduling problem for heterogeneous supercomputers where accelerators such as GPGPUs or co-processors are employed. On homogeneous supercomputers, the problem of scheduling user jobs to the available resources is NP-hard. Heterogeneous systems make the scheduling problem combinatorially more difficult. In this thesis, we aim to (i) design a new class of scheduling algorithms for state-of-the-art heterogeneous supercomputers, (ii) implement these scheduling algorithms as ready to use open source plugin software (iii) demonstrate the effectiveness of these algorithms by emulating real life usages. We propose four different models to solve the scheduling problem on heterogeneous supercomputers. In the first model, we formulate a simple co-allocation problem that does not take topology into consideration. In the second model, we implement the problem as an auction problem and automatically generate multiple bids for each job by assuming a one dimensional system topology. In the third model, we support moldable jobs that may request a range of resources. In our fourth model, we also consider topologically aware scheduling for hierarchical fat tree interconnection architectures. All of these models are formulated as integer programming problems and are solved periodically at each scheduling step. We use existing workloads to test the performance of our scheduling algorithms and also develop our own workload generator that generates realistic workloads for heterogeneous systems. The tests carried out show that our algorithms perform better than the traditional backfiilling algorithm in terms of system utilization, average job waiting time and/or job fragmentation.
Benzer Tezler
- Job scheduling heuristics for grid
Grid için kaynak tahsis modelleri
M. ÖZGÜR ERBAŞ
Yüksek Lisans
İngilizce
2007
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. CAN ÖZTURAN
- Paralel bilgisayarlar için dağıtık dinamik yük dengeleme
Distributed dynamic load balancing for parallel computers
MUAMMER AKÇAY
Doktora
Türkçe
2008
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEskişehir Osmangazi ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. NİHAT ADAR
- Deterministic and stochastic models for practical scheduling problems
Uygulamalı çizelgeleme problemleri için deterministik ve stokastik modeller
ELVİN ÇOBAN GÖKTÜRK
Doktora
İngilizce
2012
Endüstri ve Endüstri MühendisliğiCarnegie Mellon Universityİşletme Yönetimi Ana Bilim Dalı
PROF. DR. ALAN SCHELLER-WOLF
- Bütünleşik üretim ve dağıtım çizelgeleme problemleri için çözüm yaklaşımları
Solution approaches for integrated production and distribution scheduling problems
ECE ÇETİN YAĞMUR
Doktora
Türkçe
2021
Endüstri ve Endüstri MühendisliğiKonya Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. SAADETTİN ERHAN KESEN
- Deep Q-Learning approaches for stochastic dynamic optimization problems
Stokastik dinamik optimizasyon problemleri için Derin Q-Öğrenme yaklaşımları
TUĞÇE YAVUZ
Doktora
İngilizce
2024
Endüstri ve Endüstri MühendisliğiEskişehir Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. ONUR KAYA