Master Thesis MSTR-2019-84

BibliographySchnack, Stefan: Analysis of Parallel Processing Processes by Task Graph Reduction.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Master Thesis No. 84 (2019).
117 pages, english.
Abstract

Abstract: To handle the increasing load modern systems are experiencing, their processing power or network bandwidth is increased by higher parallelization. Such parallel systems are for example multicore processors or communication networks that use parallel paths for redundancy to lower transmission times. In the parallel execution of tasks belonging to a job, where completion depends on the completion of all tasks, Fork-Join(FJ) problems are occuring during their processing. This type of problems lead to the need for an efficient way of performance analysis for these parallel systems. So far only boundary methods like Network Calculus are used for this, that only allow generating approximate results. This thesis presents a method for the exact performance analysis of general parallel systems. Two different model structures with parallel paths are represented as queuing models and their processes are described with stochastic distribution functions. The task structure of the resulting queuing models are represented by task graphs based on directed acyclic graphs(DAGs). These task graphs are then reduced by the aggregation of parallel tasks to get a basic queuing model structure with one statistically equivalent single task. This allows for the exact calculation of the queuing models when corresponding analysis methods exist. In any other cases first and second-order moment approximations are used together with tabled results for standard queuing models. Due to the high complexity of the analytical calculations for more than two parallel tasks, a numerical solution, programmed in Matlab, is implemented. It consists of multiple scripts to calculate FJ queuing models of both applied model structures by task graph reduction and is used to generate results for single and multi-server FJ queuing models. Whenever possible, the results are verified by analytical calculations and by comparing them to tabled results.

Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems
Superviser(s)Kühn, Prof. Paul J.; Rothermel, Prof. Kurt
Entry dateMarch 24, 2020
   Publ. Computer Science