Research Seminar - August 13, 1999

Abstract

Many parallel programs employ regular topological structures to support their computation. This topological information is exploitable in the debugging process. Communications not normally part of a topology, ones that are either missing or unexpected, are immediately recognisable. Furthermore, animations used to assist the debugging, may be enhanced by arranging representations of the executing tasks with reference to the program's topology.

However, direct topology support is lacking in many environments,including workstation clusters, where popular language extensions such as the Parallel Virtual Machine (PVM) and the Message Passing Interface (MPI) are common. Programmers are required to implement topology support themselves. Moreover, debugger support that exploits topological information is lacking; without explicit knowledge, determining a program's topology is difficult.

In this seminar, a methodology is presented to identify program topologies with little or no prior knowledge. This methodology uses the concept of distance between graphs. Unfortunately, for the purpose of debugging, topologies are likely to be corrupted; for degenerate cases, the problem is NP-hard. However, several generic algorithms were implemented and tested on five common parallel processing topologies, with results demonstrating the feasibility of identifying topologies of unknown programs.