Multiobjective Scheduling of Hybrid Synchronization Messages

• Ricardo Parizotto UFRGS
• Braulio Mello UFFS

DOI: https://doi.org/10.5753/semish.2022.222591

Resumo

One of the essential aspects of distributed simulations is to order events according to a causal consistency model. However, traditional approaches are costly in terms of processing to ensure causality. A promising approach to order events is using a hybrid synchronization approach, where processes can alter dynamically between optimistic and conservative approaches. Unfortunately, synchronizing processes running a hybrid synchronization is a complex problem. In this work, we discuss a multi-objective scheduling of hybrid synchronization messages problem. Beyond that, we propose using a scheduling algorithm and describe how to integrate the algorithm in an existing distributed simulator. Finally, we propose a preliminary analysis of our algorithm regarding work done and the number of messages.

Palavras-chave: Distributed simulation, Hybrid sinchronization, Simulation message scheduling

Referências

Brown, R. (1988). Calendar queues: a fast 0 (1) priority queue implementation for the simulation event set problem. Communications of the ACM, 31(10):1220–1227.

Eker, A., Arafa, Y., Badawy, A.-H. A., Santhi, N., Eidenbenz, S., and Ponomarev, D. (2021). Load-aware dynamic time synchronization in parallel discrete event simulation. pages 95–105.

Jefferson, D. R. and Barnes, P. D. (2017). Virtual time iii: unification of conservative and optimistic synchronization in parallel discrete event simulation. In 2017 Winter Simulation Conference (WSC), pages 786–797. IEEE.

Junior, E. M., Terra, A., Parizotto, R., and Mello, B. (2020). Closing the gap between lookahead and checkpointing to provide hybrid synchronization. In Anais do XLVII Seminário Integrado de Software e Hardware, pages 104–115, Porto Alegre, RS, Brasil. SBC.

Kolen, A. W., Lenstra, J. K., Papadimitriou, C. H., and Spieksma, F. C. (2007). Interval scheduling: A survey. Naval Research Logistics (NRL), 54(5):530–543.

Mello, B. A. and Wagner, F. R. (2002). A standardized co-simulation backbone. In SoC Design Methodologies, pages 181–192. Springer.

Perumalla, K. S. /spl mu/sik-a micro-kernel for parallel/distributed simulation systems. In Workshop on Principles of Advanced and Distributed Simulation (PADS’05), pages 59–68. IEEE.

Santoro, T. and Quaglia, F. (2010). A low-overhead constant-time ltf scheduler for optimistic simulation systems. In The IEEE symposium on Computers and Communications, pages 948–953. IEEE.

Som, T. K. and Sargent, R. G. (1998). A probabilistic event scheduling policy for optimistic parallel discrete event simulation. In Proceedings of the Twelfth Workshop on Parallel and Distributed Simulation, PADS ’98, page 56–63, USA. IEEE Computer Society.

Taylor, S. J. (2019). Distributed simulation: state-of-the-art and potential for operational research. European Journal of Operational Research, 273(1):1–19.