Architecture-Dependent Partitioning of Dependence Graphs

Performance tuning of non-blocking threads is based on graph partitioning algorithms that create serial code blocks from dependence graphs. Previously existing algorithms are directed toward deadlock-avoidance and maximization of run-length. The latter criterion often generates a high synchronization overhead. This paper presents a partitioning algorithm for dependence graphs that uses a heuristic to determine a costefficient solution based on an architecture-dependent cost function. We present empirical results based on benchmark programs that were compiled with MIT's Id compiler, extended by our architecture-dependent partitioning algorithm. The results demonstrate a reduction in software overhead with our architecturedependent partitioning algorithm, compared with previously existing partitioning methods. The execution of the sample programs on an emulator for the Monsoon dataflow architecture shows a reduced number of processor cycles. 1 Introduction Programs that were designed t..