Abstract
We consider the class of “left-looking” sequential matrix algorithms: consumer-driven algorithms that are characterized by “lazy” propagation of data. Left-looking algorithms are difficult to parallelize using the message-passing or distributed shared memory models because they only possess pipeline parallelism. We show that these algorithms can be directly parallelized using mobile pipelines provided by the Navigational Programming methodology. We present performance data demonstrating the effectiveness of our approach.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Dongarra, J.J., Duff, I.S., Sorensen, D.C., van der Vorst, H.A.: Solving Linear Systems on Vector and Shared Memory Computers. Society for Industrial and Applied Mathematics, Philadelphia (1991)
Menon, V., Pingali, K.: Look left, look right, look left again: An application of fractal symbolic analysis to linear algebra code restructuring. International Journal of Parallel Programming 32, 501–523 (2004)
Pan, L., Bic, L.F., Dillencourt, M.B.: Distributed sequential computing using mobile code: Moving computation to data. In: Ni, L.M., Valero, M. (eds.) Proceedings of the 2001 International Conference on Parallel Processing (ICPP 2001), pp. 77–84. IEEE Computer Society, Los Alamitos (2001)
Pan, L., Lai, M.K., Dillencourt, M.B., Bic, L.F.: Mobile pipelines: Parallelizing left-looking algorithms using navigational programming. School of Information & Computer Sciences Technical Report TR# 05-12, University of California, Irvine, Irvine, Calif. (2005)
Pan, L., Bic, L.F., Dillencourt, M.B., Lai, M.K.: NavP versus SPMD: Two views of distributed computation. In: Gonzalez, T. (ed.) Proceedings of the Fifteenth IASTED International Conference on Parallel and Distributed Computing and Systems, Anaheim, Calif., vol. 2, pp. 666–673. ACTA Press (2003)
Department of Computer Science, University of California, Irvine Irvine, Calif.: MESSENGERS User’s Manual, Version 1.2.04 (2005), http://www.ics.uci.edu/~messengr/messengersC/messman1_2_04.ps
Wicke, C., Bic, L.F., Dillencourt, M.B., Fukuda, M.: Automatic state capture of self-migrating computations in messengers. In: Rothermel, K., Hohl, F. (eds.) MA 1998. LNCS, vol. 1477, pp. 68–79. Springer, Heidelberg (1998)
Pan, L., Lai, M.K., Noguchi, K., Huseynov, J.J., Bic, L.F., Dillencourt, M.B.: Distributed parallel computing using navigational programming. International Journal of Parallel Programming 32, 1–37 (2004)
Xue, J.: Loop Tiling for Parallelism. Kluwer Academic Publishers, Boston (2000)
Hughes, T.J.R.: The Finite Element Method: Linear Static and Dynamic Finite Element Analysis. Prentice Hall, Englewood Cliffs (1987)
Blackford, L.S., Choi, J., Cleary, A., D’Azevedo, E., Demmel, J., Dhillon, I., Dongarra, J., Hammarling, S., Henry, G., Petitet, A., Stanley, K., Walker, D., Whaley, R.C.: ScaLAPACK Users’ Guide. Society for Industrial and Applied Mathematics, Philadelphia (1997)
Wilkinson, B., Allen, M.: Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers, 2nd edn. Pearson Prentice Hall, Upper Saddle River (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pan, L., Lai, M.K., Dillencourt, M.B., Bic, L.F. (2005). Mobile Pipelines: Parallelizing Left-Looking Algorithms Using Navigational Programming. In: Bader, D.A., Parashar, M., Sridhar, V., Prasanna, V.K. (eds) High Performance Computing – HiPC 2005. HiPC 2005. Lecture Notes in Computer Science, vol 3769. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11602569_24
Download citation
DOI: https://doi.org/10.1007/11602569_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30936-9
Online ISBN: 978-3-540-32427-0
eBook Packages: Computer ScienceComputer Science (R0)