Adaptive Load Balancing Based On Duty-Cycle of Thread Calculation Time in Parallel Simulations

Krzysztof Szymiczek

Abstract


Parallelization and load balancing is crucial for performance of simulation software executed on modern computer systems. Adaptive approach for load balancing is presented. Duty-cycle measure of parallel threads calculation time is used as a basis. The solution scales from multi-core processor up to cluster systems and virtualized environments.

Keywords


parallel; load balancing; duty-cycle; multithreading

Full Text:

PDF

References


Yang J. et al.: Making parallel programs reliable with stable multithreading. Communications of the ACM 57.3, 2014, p.: 58-69.

Marowka A.: Back to thin-core massively parallel processors. Computer, vol.44.12, p.: 49-54.

Saifullah A. et al.: Multi-core real-time scheduling for generalized parallel task models. Real-Time Systems 49.4, 2013, p.:404-435.

Gruca A, et al. (eds.), Szymiczek K. et al.: CCES – Cancer Clonal Evolution Simulation Program, Man-Machine Interactions 5, Proceeding os 5th ICMMI, 2017, p.:172-181

Wang K. et al.: Optimizing load balancing and data-locality with data-aware scheduling. Big Data, 2014 IEEE International Conference on. IEEE, 2014.

Mandal A. et al.: An Empirical Study and Analysis of the Dynamic Load Balancing Techniques Used in Parallel Computing Systems. CoRR, vol. abs/1109.1650, 2011.

Nogueira L. et al.: Supporting Parallelism in Server-based Multiprocessor Systems. CoRR, Vol. abs/1106.2766, 2011.

Page A.J. et al.: Multi-heuristic dynamic task allocation using genetic algorithms in a heterogeneous distributed system. Journal of Parallel and Distributed Computing, Vol.70, 2010, p.:758-766.

Y.-K. Kwok, I. Ahmad, Dynamic critical-path scheduling: an effective technique for allocating task graphs to multiprocessors, IEEE Transactions on Parallel and Distributed Systems 7 (5), 1996, p.: 506-521.

Braun T.D. et al.: A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems, Journal of Parallel Distributed Computing 61 (6), 2001, p.: 810-837.

Ibarra O. et al.: Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors, Journal of the ACM, vol. 77, 1997, p.: 280-289.

Eager D.L. et al.: Adaptive Load Sharing in Homogenous Distributed Systems, IEEE Transactions on Parallel and Distributed Systems SE-12 (5), 1986, p.: 662 - 675.

Krueger P. et al.: An adaptive load balancing algorithm for a multicomputer, Dep. Comput. Sci., Univ. Wisconsin, Madison, Tech. Rep. 539, 1984

Hummel S. F. et al.: Load-sharing in heterogeneous systems via weighted factoring. Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, ACM, 1996.