Scientific Computing Seminar

Date:
Friday, November 5, 2004
Time:
1:00pm-2:00pm
Location:
50A-5132
Seminar Speaker:
Peter Gottschling
Title:
Parallel Graph Algorithms and Libraries
Abstract:
Graph algorithms gain particular importance these days, for instance to improve the robustness of the power grid or investigate gene regulatory networks. The parallelizability of graph algorithms is extremely different: some of them can reach nearly perfect scalability by computing almost independently on replicated graphs and others are nearly impossible to parallelize. Several algorithms will be presented and different ways to implement will be shown introducing new libraries. For example, it will be demonstrated how a maximum-flow calculation can be realized by means of breadth-first search (using ParGraph) and using matrix vector products (with Janus). In both versions, the concept of generic programming is crucial. Another case study comes from the Jacobian accumulation on partial derivatives in automatic differentiation (using Angel). Since it is impossible to cover the complete range of graph algorithms and to give all technical details of graph-related libraries where I was involved in the development, the talk will focus on parallel aspects of some representative graph algorithms and conceptions of its parallel implementation. The development of parallel graph software will provide many intellectual challenges in algorithmic theory and software engineering, as realizing different concepts of parallelization to mention only one aspect, and will open high performance computing to new areas like the power grid design.
Sponsor of Seminar:
Ali Pinar
Scientific Computing

Contact Esmond G. Ng EGNg@lbl.gov