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 maximisation of run-length. The latter criterion often generates a high synchronisation overhead. This paper presents a partitioning algorithm for dependence graphs that uses a heuristic to determine a cost-efficient 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 architecture-dependent 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 ..