Job scheduling for heterogeneous supercomputers
- Global styles
- Apa
- Bibtex
- Chicago Fullnote
- Help
Abstract
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ğinigerç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 şekillendirilebiliriş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. This thesis addresses the job scheduling problem for heterogeneous supercomputerswhere accelerators such as GPGPUs or co-processors are employed. On homogeneoussupercomputers, the problem of scheduling user jobs to the available resources isNP-hard. Heterogeneous systems make the scheduling problem combinatorially moredifficult. In this thesis, we aim to (i) design a new class of scheduling algorithms forstate-of-the-art heterogeneous supercomputers, (ii) implement these scheduling algorithmsas ready to use open source plugin software (iii) demonstrate the effectivenessof these algorithms by emulating real life usages. We propose four different modelsto 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 andautomatically generate multiple bids for each job by assuming a one dimensional systemtopology. In the third model, we support moldable jobs that may request a rangeof resources. In our fourth model, we also consider topologically aware scheduling forhierarchical fat tree interconnection architectures. All of these models are formulatedas integer programming problems and are solved periodically at each scheduling step.We use existing workloads to test the performance of our scheduling algorithms andalso develop our own workload generator that generates realistic workloads for heterogeneoussystems. The tests carried out show that our algorithms perform better thanthe traditional backfiilling algorithm in terms of system utilization, average job waitingtime and/or job fragmentation.
Collections