Mobile Pipelines: Parallelizing Left-Looking Algorithms Using Navigational Programming
- Resource Type
- Authors
- Lei Pan; Michael B. Dillencourt; Ming Kin Lai; Lubomir Bic
- Source
- Lecture Notes in Computer Science ISBN: 9783540309369
HiPC
- Subject
- Pipeline transport
Software development process
Class (computer programming)
Matrix (mathematics)
Distributed shared memory
Computer science
Parallelism (grammar)
Parallel computing
Algorithm
Pipeline (software)
Sequential algorithm
Cholesky decomposition
- Language
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.