A framework for SPMD applications with load balancing
Resumo
This work describes SAMBA, a framework for the development of a parallel SPMD applications with load balancing. SAMBA contains the structure common to different SPMD applications and a library of load-balancing algorithms. This structure allows the developer to concentrate on the specific problem at hand. The load-balancing library make easier the identification of the mot appropriate strategy for a given application. Experiments conducted with SAMBA on threee different parallel applications are described, illustrating the ease of use of the proposed framework and the relevance of load balancing.
Palavras-chave:
SPMD, load balancing, framework, data parallelism, parallel programs
Referências
J.N.C. Árabe and C.D. Murta, "Auto-balanceamento de carga em programas paralelos". Proc. of the VIII Brazilian Symposium on Computer Architecture and High Performance Processing, 1996, p.65–73.
A.C.B. de Andrade Filho, Optimizing hydrocarbon field development using a genetic algorithm based approach. PhD Dissertation, Dept. of Petroleum Eng., Stanford University, 1997.
G. Booch, Object-Oriented Analysis and Design with Applications. Benjamin/Cummings, 1994.
G. Booch and J. Rumbaugh, Unified Method. Rational Software Corporation, 1996.
S. Crivelli and E.R. Jessup, "The PMESC programming environment for distributed-memory MIMD computers". Journal of Parallel and Distributed Computing 57 (1999), 295–321.
T. Decker, "Virtual Data Space – A universal load balancing scheme". LNCS 1253 (1997), 159–166.
E. Dijkstra, W. Seijen, and A. Gasteren, "Derivation of a termination detection algorithm for a distributed computation". Information Processing Letters 16 (1983), 217–219.
M.A. Franklin and V. Govindan, "A general matrix model for dynamic load balancing". Parallel Computing 22 (1996), 969–989.
C. Fonlupt, P. Marquet, and J. Dekeyser, "Data-parallel load balancing strategies". Parallel Computing 24 (1998), 1665–1684.
M. Furuichi, K. Taki, and N. Ichiyoshi, "A multi-level load balancing scheme for or-parallel exhaustive search programs on multi-psi". Proc. of the Second ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 1990, 50–59.
E. Gamma, R. Helm, R. Johnson, and J. Vlissides, Design Patterns – Elements of Reusable Object-Oriented Software. Addison-Wesley, 1994.
I. Jacobson, M. Christerson, P. Jonsson, and G. Overgaard, Object-Oriented Software Engineering – A Use Case Driven Approach. Addison-Wesley, 1992.
S. Lifschitz, A. Plastino, and C.C. Ribeiro, "Exploring load balancing in parallel processing of recursive queries". LNCS 1300 (1997), 1125–1129.
T.G. Mattson, "Scientific computation", in Parallel and Distributed Computing Handbook (A.Y. Zomaya, editor), p.981–1002. McGraw-Hill, 1996.
Message Passing Interface Forum, "MPI: A message passing interface". Proceedings of Supercomputing '93 (A.Y. Zomaya, editor), 878–883. IEEE Computer Society, 1993.
W. Pree, Design Patterns for Object-Oriented Software Development. Addison-Wesley, 1995.
W. Pree, Framework Patterns. SIGS Management Briefings, SIG Books & Multimedia, 1996.
A. Plastino, Balanceamento de carga de aplicações paralelas SPMD. Doctorate thesis, Department of Computing, Catholic University of Rio de Janeiro, 2000.
A. Plastino, C.C. Ribeiro, and N. Rodriguez, "Uma taxonomia de algoritmos de balanceamento de carga para aplicações SPMD". Technical Report PUC-RioInf.MCC49/98, Department of Computing, Catholic University of Rio de Janeiro, 1998.
A. Plastino, C.C. Ribeiro, and N. Rodriguez, "A tool for SPMD application development with support for load balancing". Proc. of the ParCo Parallel Computing Conf., Delft, 1999, to appear.
M.J. Quinn, Parallel Computing: Theory and Practice. McGraw-Hill, 1994.
J. Rumbaugh, M. Blaha, W. Premerlani, F. Eddy, and W. Lorensen, Object-Oriented Modeling and Design. Prentice Hall, 1991.
J.B. Weissman, "Prophet: Automated scheduling of SPMD programs in workstation networks". Concurrency: Practice and Experience 11 (1999), 301–321.
M.A. Willebeek-LeMair and A.P. Reeves, "Strategies for dynamic load balancing on highly parallel computers". IEEE Trans. on Parallel and Distributed Systems 4 (1993), 979–993.
M.J. Zaki, W. Li, and S. Parthasarathy, "Customized dynamic load balancing for a network of workstations". Journal of Parallel and Distributed Computing 43 (1997), 156–162.
A.C.B. de Andrade Filho, Optimizing hydrocarbon field development using a genetic algorithm based approach. PhD Dissertation, Dept. of Petroleum Eng., Stanford University, 1997.
G. Booch, Object-Oriented Analysis and Design with Applications. Benjamin/Cummings, 1994.
G. Booch and J. Rumbaugh, Unified Method. Rational Software Corporation, 1996.
S. Crivelli and E.R. Jessup, "The PMESC programming environment for distributed-memory MIMD computers". Journal of Parallel and Distributed Computing 57 (1999), 295–321.
T. Decker, "Virtual Data Space – A universal load balancing scheme". LNCS 1253 (1997), 159–166.
E. Dijkstra, W. Seijen, and A. Gasteren, "Derivation of a termination detection algorithm for a distributed computation". Information Processing Letters 16 (1983), 217–219.
M.A. Franklin and V. Govindan, "A general matrix model for dynamic load balancing". Parallel Computing 22 (1996), 969–989.
C. Fonlupt, P. Marquet, and J. Dekeyser, "Data-parallel load balancing strategies". Parallel Computing 24 (1998), 1665–1684.
M. Furuichi, K. Taki, and N. Ichiyoshi, "A multi-level load balancing scheme for or-parallel exhaustive search programs on multi-psi". Proc. of the Second ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 1990, 50–59.
E. Gamma, R. Helm, R. Johnson, and J. Vlissides, Design Patterns – Elements of Reusable Object-Oriented Software. Addison-Wesley, 1994.
I. Jacobson, M. Christerson, P. Jonsson, and G. Overgaard, Object-Oriented Software Engineering – A Use Case Driven Approach. Addison-Wesley, 1992.
S. Lifschitz, A. Plastino, and C.C. Ribeiro, "Exploring load balancing in parallel processing of recursive queries". LNCS 1300 (1997), 1125–1129.
T.G. Mattson, "Scientific computation", in Parallel and Distributed Computing Handbook (A.Y. Zomaya, editor), p.981–1002. McGraw-Hill, 1996.
Message Passing Interface Forum, "MPI: A message passing interface". Proceedings of Supercomputing '93 (A.Y. Zomaya, editor), 878–883. IEEE Computer Society, 1993.
W. Pree, Design Patterns for Object-Oriented Software Development. Addison-Wesley, 1995.
W. Pree, Framework Patterns. SIGS Management Briefings, SIG Books & Multimedia, 1996.
A. Plastino, Balanceamento de carga de aplicações paralelas SPMD. Doctorate thesis, Department of Computing, Catholic University of Rio de Janeiro, 2000.
A. Plastino, C.C. Ribeiro, and N. Rodriguez, "Uma taxonomia de algoritmos de balanceamento de carga para aplicações SPMD". Technical Report PUC-RioInf.MCC49/98, Department of Computing, Catholic University of Rio de Janeiro, 1998.
A. Plastino, C.C. Ribeiro, and N. Rodriguez, "A tool for SPMD application development with support for load balancing". Proc. of the ParCo Parallel Computing Conf., Delft, 1999, to appear.
M.J. Quinn, Parallel Computing: Theory and Practice. McGraw-Hill, 1994.
J. Rumbaugh, M. Blaha, W. Premerlani, F. Eddy, and W. Lorensen, Object-Oriented Modeling and Design. Prentice Hall, 1991.
J.B. Weissman, "Prophet: Automated scheduling of SPMD programs in workstation networks". Concurrency: Practice and Experience 11 (1999), 301–321.
M.A. Willebeek-LeMair and A.P. Reeves, "Strategies for dynamic load balancing on highly parallel computers". IEEE Trans. on Parallel and Distributed Systems 4 (1993), 979–993.
M.J. Zaki, W. Li, and S. Parthasarathy, "Customized dynamic load balancing for a network of workstations". Journal of Parallel and Distributed Computing 43 (1997), 156–162.
Publicado
24/10/2000
Como Citar
PLASTINO, Alexandre; RIBEIRO, Celso C.; RODRIGUEZ, Noemi.
A framework for SPMD applications with load balancing. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 12. , 2000, São Pedro/SP.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2000
.
p. 245-252.
DOI: https://doi.org/10.5753/sbac-pad.2000.41222.
