| Abstract | Postupci rasporedivanja programa na sklopovlje vazan su mehanizam ucinkovitog koristenja novih sklopovskih
tehnologija u podrucju racunarstva visokih performansi (HPC). Postoje mnoge vrste takvih
postupaka, no najrasireniji i najbolji su postupci rangiranja jedinica programa te (meta)heuristicki postupci
vecinom zasnovani na vodenom lokalnom pretrazivanju. Medutim, prate ih nestrukturiranost i
nemogucnost da u punoj mjeri koriste raznorodnu prirodu sklopovlja, posebice komunikacijske mreze
medu obradbenim jedinicama. Problem stvara i rastuca potreba za pracenjem visestrukih pokazatelja
kvalitete (vrijeme izvrsavanja, energija, troskovi itd.), kao i manjak podrske za davanjem vaznosti
pojedinim pokazateljima kvalitete. U ovom radu predstavljamo LOSECO modularni programski okvir
za optimalno dodjeljivanje programa na raznorodne raspodijeljene racunalne sustave. U sklopu tog
okvira predstavljamo i skup modela s posebnim naglaskom na modelu programa u obliku mijesanoga
aciklickoga grafa koji omogucuje istovremeni prikaz vremenskog slijeda medu jedinicama programa i
njihove sinkrone komunikacije te okvir za univerzalni model rasporedivanja pomocu vise korisnicki nagla
senih kriterija (pokazatelja kvalitete). Uz to smo razvili i unaprijedeni postupak rasporedivanja u dva
koraka, RaPPaMaG, koji koristi navedene modele kako bi omogucio particioniranje programa na vremenski
neovisne faze izvrsavanja, a zatim i optimalno rasporedivanje dobivenih particija. Pokazali smo da
postupak RaPPaMaG, osim na programe u obliku mijesanoga grafa, mozemo primijeniti i na postojece
programe iz repozitorija Pegasus te alata za njihovo stvaranje TGFF. S druge strane razvili smo jos
jedan unaprijedeni postupak rasporedivanja, RaNDKiP, zasnovan na rangiranju jedinica programa, koji
omogucuje iskoristavanje raznorodnosti mreze medu obradbenim jedinicama kako bi unaprijedio dobiveni
raspored u odnosu na postojece postupke HEFT i LDCP. Osim skracivanja vremena izvrsavanja programa,
postupak RaNDKiP omogucuje smanjivanje utroska energije labavljenjem nekriticnih vremenskih
isjecaka u rasporedu tzv. postupkom LVI. Postupak LVI omogucuje smanjenje utroska energije od 14%
do 20% u prosjecnom slucaju ovisno o tipu prethodno upotrijebljenog postupka rasporedivanja. |
| Parallel abstract (English) | In high performance computing (HPC) scheduling methods are one of the most important mechanisms
that ensure the ecient use of the emergent hardware technologies. Amongst dierent types of scheduling,
list scheduling methods and various guided local search-based (meta)heuristics are considered as the best,
and therefore they are widely used. However, these methods lack structured approach as well as the
ability to fully exploit the heterogeneous nature of the existing hardware, mostly the heterogeneity of
its network. Another problem is the growing number of dierent quality attributes, such as execution
time, energy consumption, costs, etc., their simultaneous use, and their prioritization. In this thesis we
introduce LOSECO framework, a modular structure of the comprehensive scheduling system. Within this
framework we present a set of models, with one of them being the novel mixed acyclic graph software
model that allows simultaneous description of the time dependency between software units and their
synchronous communication and the other being the multiple-criteria scheduling model which allows
the use of the multiple user prioritized criteria (quality attributes). Furthermore, we have developed
RaPPaMaG, an improved scheduling method that comprises two steps: partitioning, which exploits new
structure of the software model in order to split the program into the time independent execution phases,
and the allocation step which allows their optimal allocation. We have shown that RaPPaMaG can be
applied to the mixed acyclic graph software model, as well as the directed acyclic graph representation
of the existing workloads from Pegasus and ones generated by TGFF. Additionally, we have developed a
second improved, list-based, scheduling method called RaNDKiP, which exploits network heterogeneity,
enabling shorter schedule lengths in heterogeneous systems when compared to the ones obtained by
existing HEFT and LDCP. In addition to reducing the schedule length, RaNDKiP also enables lowering
of the power consumption by slacking the non-critical time slots via LVI procedure. Our experimental
analysis has shown that in the average case LVI reduces energy consumption by 14% to 20%, depending
on the previously used scheduling method. |
