Peter Gottschling

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. Biography:

Dr. Gottschling studied at Technische Universita"t Dresden, Ecole Normale Supe'rieure de Cachan, and Universite' Paris-Sud Orsay. He then worked at Fraunhofer FIRST (originally an institute of the former GMD: Gesellschaft fu"r Mathematik und Datenverarbeitung), at University of Hertfordshire, at Federal Institute for Materials Research and Testing (BAM), and at Argonne National Laboratory before returning to the Center for High Performance Computing (ZHR) of Technische Universita"t Dresden.