Analysis of a Heuristic for Code Partitioning

In this paper, we analyze the time complexity and performance of a heuristic for code partitioning for Distributed Memory Multiprocessors (DMMs). The partitioning method is data-flow based where all levels of parallelism are exploited. Given a weighted Directed Acyclic Graph (DAG) representation of the program, our algorithm automatically determines the granularity of parallelism by partitioning the graph into tasks to be scheduled on the DMM. The granularity of parallelism depends only on the program to be executed and on the target machine parameters. The output of our algorithm is passed on as input to the scheduling phase. Finding an optimal solution to this problem is NP-complete. Due to the high cost of graph algorithms, it is nearly impossible to come up with close to optimal solutions that do not have very high cost (higher order polynomial). Our proposed heuristic gives good performance and has relatively low cost.