Matrix product on heterogeneous master-worker platforms

ABSTRACT

This paper is focused on designing efficient parallel matrix-product algorithms for heterogeneous master-worker platforms. While matrix-product is well-understood for homogeneous 2D-arrays of processors (e.g., Cannon algorithm and ScaLAPACK outer product algorithm), there are three key hypotheses that render our work original and innovative:

- Centralized data. We assume that all matrix files originate from, and must be returned to, the master. The master distributes data and computations to the workers while in ScaLAPACK, input and output matrices are supposed to be equally distributed among participating resources beforehand). Typically, our approach is useful in the context of speeding up MATLAB or SCILAB clients running on a server (which acts as the master and initial repository of files).

- Heterogeneous star-shaped platforms. We target fully heterogeneous platforms, where computational resources have different computing powers. Also, the workers are connected to the master by links of different capacities. This framework is realistic when deploying the application from the server, which is responsible for enrolling authorized resources.

- Limited memory. As we investigate the parallelization of large problems, we cannot assume that full matrix column blocks can be stored in the worker memories and be re-used for subsequent updates (as in ScaLAPACK).

We have devised efficient algorithms for resource selection (deciding which workers to enroll) and communication ordering (both for input and result messages), and we report a set of numerical experiments on a platform at our site. The experiments show that our matrix-product algorithm has smaller execution times than existing ones, while it also uses fewer resources.

REFERENCES

• 1: Cyril Banino , Olivier Beaumont , Larry Carter , Jeanne Ferrante , Arnaud Legrand , Yves Robert, Scheduling Strategies for Master-Slave Tasking on Heterogeneous Processor Platforms, IEEE Transactions on Parallel and Distributed Systems, v.15 n.4, p.319-330, April 2004 [doi>10.1109/TPDS.2004.1271181]
• 2: Olivier Beaumont , Vincent Boudet , Antoine Petitet, A Proposal for a Heterogeneous Cluster ScaLAPACK (Dense Linear Solvers), IEEE Transactions on Computers, v.50 n.10, p.1052-1070, October 2001 [doi>10.1109/12.956091]
• 3: Olivier Beaumont , Vincent Boudet , Fabrice Rastello , Yves Robert, Matrix Multiplication on Heterogeneous Platforms, IEEE Transactions on Parallel and Distributed Systems, v.12 n.10, p.1033-1051, October 2001 [doi>10.1109/71.963416]
• 4: Prashanth B. Bhat , C. S. Raghavendra , Viktor K. Prasanna, Efficient collective communication in distributed heterogeneous systems, Journal of Parallel and Distributed Computing, v.63 n.3, p.251-263, March 2003 [doi>10.1016/S0743-7315(03)00008-X]
• 5: Jack J. Dongarra , L. S. Blackford , J. Choi , A. Cleary , E. D'Azeuedo , J. Demmel , I. Dhillon , S. Hammarling , G. Henry , A. Petitet , K. Stanley , D. Walker , R. C. Whaley, ScaLAPACK user's guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
• 6: Lynn Elliot Cannon, A cellular computer to implement the kalman filter algorithm, Montana State University, Bozeman, MT, 1969
• 7: R. Clint Whaley, A. Petitet, and J. J. Dongarra. Automated empirical optimizations of software and the atlas project. Parallel Computing, 27(1-2):3--35, Jan. 2001.
• 8: Jack J. Dongarra , Sven Hammarling , David W. Walker, Key concepts for parallel out-of-core LU factorization, Parallel Computing, v.23 n.1-2, p.49-70, April 1997 [doi>10.1016/S0167-8191(96)00096-8]
• 9: Hong Jia-Wei , H. T. Kung, I/O complexity: The red-blue pebble game, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.326-333, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802486]
• 10: Dror Irony , Sivan Toledo , Alexander Tiskin, Communication lower bounds for distributed-memory matrix multiplication, Journal of Parallel and Distributed Computing, v.64 n.9, p.1017-1026, September 2004 [doi>10.1016/j.jpdc.2004.03.021]
• 11: Alexey Kalinov , Alexey Lastovetsky, Heterogeneous distribution of computations solving linear algebra problems on networks of heterogeneous computers, Journal of Parallel and Distributed Computing, v.61 n.4, p.520-535, April 2001 [doi>10.1006/jpdc.2000.1686]
• 12: Kequin Li , Victor Y. Pan, Parallel Matrix Multiplication on a Linear Array with a Reconfigurable Pipelined Bus System, IEEE Transactions on Computers, v.50 n.5, p.519-525, May 2001 [doi>10.1109/12.926164]
• 13: Muthucumaru Maheswaran , Shoukat Ali , Howard Jay Siegel , Debra Hensgen , Richard F. Freund, Dynamic Matching and Scheduling of a Class of Independent Tasks onto Heterogeneous Computing Systems, Proceedings of the Eighth Heterogeneous Computing Workshop, p.30, April 12-12, 1999
• 14: J.-F. Pineau, Y. Robert, F. Vivien, Z. Shi, and J. Dongarra. Revisiting matrix product on master-worker platforms. Research Report 2006-39, LIP, ENS Lyon, France, Nov. 2006.
• 15: J.-F. Pineau, Y. Robert, F. Vivien, Z. Shi, and J. Dongarra. Revisiting matrix product on master-worker platforms. IEEE Advances in Parallel and Distributed Computational Models, 2007.
• 16: T. Saif and M. Parashar. Understanding the behavior and performance of non-blocking communications in MPI. In Proceedings of Euro-Par 2004: Parallel Processing, LNCS 3149, pages 173--182, 2004.
• 17: Sivan Toledo, A survey of out-of-core algorithms in numerical linear algebra, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 18: Ling Zhuo , Viktor K. Prasanna, Scalable and Modular Algorithms for Floating-Point Matrix Multiplication on Reconfigurable Computing Systems, IEEE Transactions on Parallel and Distributed Systems, v.18 n.4, p.433-448, April 2007 [doi>10.1109/TPDS.2007.1001]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Experimentation, Theory

Keywords:
communication, limited memory, matrix product