Paper Info
Title
Studying the impact of synchronization frequency on scheduling tasks with dependencies in heterogeneous systems
Abstract
In this work, we develop and evaluate a theoretical model, which we then use to study the impact of the synchronization frequency on the performance of dynamic self-scheduling algorithms. These algorithms are used to parallelize loops with data dependencies on heterogeneous systems. The proposed model uses a formula to estimate the parallel time as a function of the synchronization frequency. Inter-node communication has been proven to be the dominant factor for the performance degradation of applications containing loops with data dependencies. The synchronization mechanism therefore requires careful fine-tuning in order to give the best possible performance. The proposed model determines the optimal synchronization frequency that results in the minimum parallel time. We use this model to study the impact of the synchronization frequency on the parallel execution of a computational kernel from image processing. For this kernel, the synchronization frequency giving the minimum parallel time predicted by our theoretical model was very close to the synchronization frequency giving the least parallel time in practice. We validate our model by extensive comparisons of the theoretically predicted parallel time and synchronization frequency against those obtained from practical experiments. The comparisons show that the proposed model is highly accurate, its predictions for the optimal synchronization frequency being within 0.0250% of the experimentally optimal synchronization frequency in the best case, and within 0.1750% of the experimentally optimal synchronization frequency in the worst case. Finally, the comparisons show that the proposed model improves on a previously existing model in heterogeneous systems, whereas it gives similar results in homogeneous systems.
Year
DOI
Venue
2010
10.1016/j.peva.2010.08.020
Perform. Eval.
Keywords
Field
DocType
self-scheduling algorithms,performance evaluation,theoretical model,data dependency,minimum parallel time,dynamic load balancing,synchronization frequency,synchronization mechanism,parallel execution,loops with dependencies,heterogeneous system,inter-processor communication,optimal synchronization frequency,heterogeneous systems,parallel time,scheduling algorithm,image processing
Kernel (linear algebra),Synchronization,Computer science,Homogeneous,Scheduling (computing),Image processing,Real-time computing,Dynamic load balancing,Distributed computing
Journal
Volume
Issue
ISSN
67
12
Performance Evaluation
Citations 
PageRank 
References 
3
0.39
21
Authors
5
Name
Order
Citations
PageRank
Theodore Andronikos110515.07
Ciorba Florina M.212522.96
Ioannis Riakiotakis3422.88
George Papakonstantinou413414.52
Anthony T. Chronopoulos552350.61