Partitioning data flow programs

The authors describe the Quac data flow compiler and its partitioning mechanism. During translation of data flow programs the compiler determines the size of each function and statically assesses the amount of communication between pairs of functions. It then creates a graph in which each node represents a program function with each node weighted by the function sizes. Nodes are joined if there is non-zero communication between the functions they represent, with the edges weighted to reflect the amount of communication. The amount of communication is estimated heuristically. An algorithm of Widjaja is used to produce a partition of this graph, which is used to allocate function code to a set of homogeneous loosely coupled processors to minimise interprocessor communication costs subject to memory size constraints.