Please use this identifier to cite or link to this item: https://hdl.handle.net/10593/1003
Title: Szeregowanie zadań jednorodnie podzielnych w heterogenicznych systemach rozproszonych
Other Titles: Scheduling divisible loads in heterogeneous distributed systems
Authors: Berlińska, Joanna
Advisor: Drozdowski, Maciej. Promotor
Keywords: przetwarzanie równoległe
parallel processing
szeregowanie zadań
scheduling
zadania jednorodnie podzielne
divisible loads
MapReduce
ocena efektywności
performance evaluation
Issue Date: 5-May-2011
Abstract: Celem rozprawy jest analiza pewnych zagadnień szeregowania zadań jednorodnie podzielnych w heterogenicznych systemach rozproszonych i konstrukcja algorytmów rozwiązujących te problemy. Jako pierwszy rozważany był problem jednoetapowego szeregowania zadań jednorodnie podzielnych w topologii gwiazdy. Zaproponowano w pełni wielomianowe schematy aproksymacji i algorytmy aproksymacyjne dla tego problemu. Następnie rozważany był problem wieloetapowego szeregowania zadań jednorodnie podzielnych. Przeprowadzono analizę eksperymentalną własności problemu. Na podstawie otrzymanych wyników skonstruowano algorytmy heurystyczne. Zostały one ocenione i porównane eksperymentalnie. Teoria zadań jednorodnie podzielnych została także zastosowana do modelowania, analizy i szeregowania aplikacji MapReduce. Skonstruowano model matematyczny i algorytmy szeregowania takich obliczeń. Przeprowadzono ocenę efektywności MapReduce. Model został następnie uogólniony na aplikacje wielowarstwowe. Podano algorytmy szeregowania takich aplikacji i przeanalizowano wpływ parametrów systemu na strukturę uszeregowania.
The main goal of this work is the analysis of several divisible load scheduling problems in heterogeneous distributed systems and the construction of algorithms solving these problems. First, single-round divisible load scheduling in star networks is analyzed. Fully polynomial time approximation schemes and approximation algorithms are proposed for this problem. Then, multi-round divisible load scheduling with memory limits is investigated. An extensive computational study of the features of the problem is provided. These results are used to construct heuristic algorithms solving the problem. The algorithms are evaluated and compared based on the experimental results. The divisible load theory is also applied to model, analyze and schedule computations in the MapReduce framework. A mathematical model of such computations is constructed and scheduling algorithms are proposed. Performance limits of the proposed organization of computations are investigated. Afterwards, the model is generalized to handle multilayer applications. Scheduling algorithms for multilayer applications are given and the influence of the system parameters on the schedule structure is studied.
Description: Wydział Matematyki i Informatyki: Zakład Algorytmiki i Programowania
URI: http://hdl.handle.net/10593/1003
Appears in Collections:Doktoraty (WMiI)
Doktoraty 2010-2021 /dostęp otwarty/

Files in This Item:
File Description SizeFormat 
Joanna Berlinska - PhD.pdf2.74 MBAdobe PDFView/Open
Show full item record



Items in AMUR are protected by copyright, with all rights reserved, unless otherwise indicated.