On-The-fly topological sort-A basis for interactive debugging and live visualization of parallel programs

Abstract

This paper presents an optimal technique for on-The-fly ordering and matching of event data records that are being produced by a number of distinct processors. This is essential for effective interactive debugging and live visualization of parallel programs. The technique involves on-The-fly construction of the causality graph of the execution of the program. A sliding window over the graph is maintained by discarding portions of the graph as soon as they are no longer required for ensuring correct order of subsequent program events. The sort places an event record into the causality graph when it is received, places it into the output stream as soon as possible-As soon as fill of its predecessors in the causal order have been placed into the output, and discards the event record as soon as possible-As soon as all of its successors in the causal order notice that it has been output. This technique is optimal in terms of the amount of space required for the sort, and in terms of the amount of additional delay incurred prior to delivery of an event record to its ultimate destination. We describe the algorithm in detail, show its optimality, and present results from experiments on a Meiko system running with PICL and ParaGraph.