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.