Incremental Parallelization Using Navigational Programming: A Case Study
- Resource Type
- Authors
- Wendy Y. Zhang; Arthur U. Asuncion; Lubomir Bic; Lei Pan; Michael B. Dillencourt; Ming Kin Lai
- Source
- ICPP
- Subject
- Theoretical computer science
Programming language
Computer science
Computation
Cannon's algorithm
Concurrent computing
Program transformation
Context (language use)
Parallel computing
computer.software_genre
Computer-aided software engineering
computer
Matrix multiplication
- Language
We show how a series of transformations can be applied to incrementally parallelize sequential programs. Our navigational programming (NavP) methodology is based on the principle of self-migrating computations and is truly incremental, in that each step represents a functioning program and every intermediate program is an improvement over its predecessor. The transformations are mechanical and straightforward to apply. We illustrate our methodology in the context of matrix multiplication. Our final stage is similar to the classical Gentleman's algorithm. The NavP methodology is conducive to new ways of thinking that lead to ease of programming and high performance.