Allocation and Scheduling of Dataflow Graphs on Hybrid Dataflow/von Neumann Architectures

Hybrid dataflow/von Neumann processors expose their processing units and datapaths to the compiler to exploit the instruction-level parallelism of sequential programs. Generating code from dataflow graphs for such processors that use FIFO-buffered datapaths requires (1) an allocation that maps the nodes of the dataflow graph to the processing units (PUs) of the processor, and (2) a schedule for firing the nodes on the PUs that does not violate the FIFO behavior of the buffers. In previous work, we have encoded the constraints required to ensure the FIFO behavior for the code generation as a SAT problem. In this paper, we consider PU allocation and node scheduling in isolation, inspired by the traditional compilers, which also treat register allocation and instruction scheduling as separate problems. If a schedule is given, we reduce the PU allocation problem to a graph coloring problem so that heuristics can solve it efficiently. We also perform interference analysis, similar to register interference analysis to reveal special properties of the PU allocation graph. If a PU allocation is given, the scheduling problem is almost reduced to a 2SAT problem so that it can also be solved efficiently.