MigPF: Towards on self-organizing process rescheduling of Bulk-Synchronous Parallel applications

da Rosa Righi R, de Quadros Gomes R, Facco Rodrigues V, Andre da Costa C, Marcos Alberti A, Lima Pilla L, Olivier Alexandre Navaux P (2018)


Publication Status: Published

Publication Type: Journal article

Publication year: 2018

Journal

Publisher: ELSEVIER SCIENCE BV

Book Volume: 78

Pages Range: 272-286

DOI: 10.1016/j.future.2016.05.004

Abstract

Migration is a known technique to offer process rescheduling, being especially pertinent for Bulk Synchronous Parallel (BSP) programs. Such programs are organized in a set of supersteps, in which the slowest process always determines the synchronization time. This approach motivated us to develop a first model called MigBSP, which combines computation, communication, and migration costs metrics for process rescheduling decisions. In this paper, a new model named MigPF enhances our previous work in three aspects: (i) a different algorithm for detecting imbalance situations, which considers the performance of each processor, including its enclosed processes, instead of individual times of each process; (ii) an improvement on the rescheduling reactivity through shortening the interval for the next migration call when imbalance situations arise; (iii) a new algorithm for self-organizing the migratable processes and their destinations. Particularly, this third item represents our main scientific contribution, not only in terms of the MigBSP context, but also in a broader one that covers the entire BSP landscape. The algorithm assembles n possible rescheduling plans (where n is the number of processes) and provides a prediction function (pf) that chooses the most profitable rescheduling plan when compared to the current mapping. We developed a MigPF prototype with the Adaptive MPI (AMPI) library, which offers a standard framework for implementing migration-based load balancing policies. We tested this prototype against other built-in AMPI rescheduling policies with two scientific applications: shear sorting and fractal image compression. The results revealed performance gains up to 41% and an overhead limited to 5% when migrations do not take place. (C) 2016 Elsevier B.V. All rights reserved.

Authors with CRIS profile

Additional Organisation(s)

How to cite

APA:

da Rosa Righi, R., de Quadros Gomes, R., Facco Rodrigues, V., Andre da Costa, C., Marcos Alberti, A., Lima Pilla, L., & Olivier Alexandre Navaux, P. (2018). MigPF: Towards on self-organizing process rescheduling of Bulk-Synchronous Parallel applications. Future Generation Computer Systems-The International Journal of Grid Computing Theory Methods and Applications, 78, 272-286. https://dx.doi.org/10.1016/j.future.2016.05.004

MLA:

da Rosa Righi, Rodrigo, et al. "MigPF: Towards on self-organizing process rescheduling of Bulk-Synchronous Parallel applications." Future Generation Computer Systems-The International Journal of Grid Computing Theory Methods and Applications 78 (2018): 272-286.

BibTeX: Download