Navigational programming: Toward structured distributed parallel programming

2005 2005

Other formats: Order a copy

Abstract (summary)

As distributed-memory cluster computers become less expensive and increasingly available, our ability to program this new generation of supercomputers is lagging behind demand. Achieving scalability and ease of programming simultaneously is a grand challenge. The state of the art for implementing large-scale high-performance scientific and engineering applications has been message passing (MP), despite the fact that MP is widely considered hard to use. Studies reveal that the two operations at the heart of MP---Send() and Recv ()--change the code similar to the goto statements, thus making structured programming problematic. This is reminiscent of the software crisis of the 1960s that led to Dijkstra's recommendation that goto statements be abolished.

This dissertation introduces a new methodology, called Navigational Programming (NavP), that is based on the use of self-migrating computations. NavP is philosophically different from message passing because it describes the quantity of interest---a distributed computation---following the movement of its locus. In contrast, all other approaches use the SPMD (Single Program Multiple Data) view to describe computations at stationary locations. Program transformations in NavP involves the insertion of migration statements ( hop()), which, unlike the Send() and Recv(), does not change code structure. NavP puts an end to the use of "goto " statements and it enables scalable structured distributed parallel programming. This dissertation develops the NavP methodology with steps for its programmers to follow. Case studies using real-world examples demonstrate how efficient, scalable, and elegant NavP programs can be developed in an incremental fashion using the NavP methodology. We show how the NavP methodology yields parallel implementations of algorithms that are difficult to parallelize, and that on the surface appear unparallelizable, using MP. Performance data shows that for several important and non-trivial real-world applications, NavP programs are as fast as or faster than the corresponding MPI programs. NavP exploits both fine-grained parallelism using shared variables and multithreading, and coarse-grained parallelism using pipelined tasks in a uniform fashion. NavP holds the promise of allowing scientists and engineers to use the most advanced computers without being overwhelmed by the complexity of rewriting their codes with each new generation of architectures.

Indexing (details)

Computer science
0984: Computer science
Identifier / keyword
Applied sciences; Cluster computing; Distributed computing; Navigational programming; Parallel programming
Navigational programming: Toward structured distributed parallel programming
Pan, Lei
Number of pages
Publication year
Degree date
School code
DAI-B 67/03, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
9780542578502, 0542578506
Bic, Lubomir F.; Dillencourt, Michael B.
University of California, Irvine
University location
United States -- California
Source type
Dissertations & Theses
Document type
Dissertation/thesis number
ProQuest document ID
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.