CYCLIC: A Locality-Preserving Load-Balancing Algorithm for PDES on Shared Memory Multiprocessors

Authors

  • Antonio García-Dopico Department of Computer System Architecture and Technology, Technical University of Madrid, Facultad de Informática, Madrid
  • Antonio Pérez Department of Computer System Architecture and Technology, Technical University of Madrid, Facultad de Informática, Madrid
  • Santiago Rodríguez Department of Computer System Architecture and Technology, Technical University of Madrid, Facultad de Informática, Madrid
  • Maria Isabel García Department of Computer System Architecture and Technology, Technical University of Madrid, Facultad de Informática, Madrid

Keywords:

Parallel algorithms, shared memory systems, load balancing, locality of references, multicore, VHDL, PDES

Abstract

This paper presents a new load-balancing algorithm for shared memory multiprocessors that is currently being applied to the parallel simulation of logic circuits, specifically VHDL simulations. The main idea of this load-balancing algorithm is based on the exploitation of the usual characteristics of these simulations, that is, cyclicity and predictability, to obtain a good load balance while preserving the locality of references. This algorithm is useful not only in the area of logic circuit simulation but also in systems presenting a cyclic execution pattern, that is, repetition over time, making the future behavior of the tasks predictable. An example of this is Parallel Discrete Event Simulation (PDES), where several tasks are repeatedly executed in response to certain events. A comparison between the proposed algorithm and other load-balancing algorithms found in the literature reveals consistently better execution times with improvements in both load-balancing and locality of references that can be of help on current multicore desktop computers.

Downloads

Download data is not yet available.

Downloads

Published

2013-01-24

How to Cite

García-Dopico, A., Pérez, A., Rodríguez, S., & García, M. I. (2013). CYCLIC: A Locality-Preserving Load-Balancing Algorithm for PDES on Shared Memory Multiprocessors. Computing and Informatics, 31(6), 1255–1278. Retrieved from https://www.cai.sk/ojs/index.php/cai/article/view/1307

Most read articles by the same author(s)