Temporal partitioning and scheduling data flow graphs for reconfigurable computers

FPGA-based configurable computing machines are evolving rapidly. They offer the ability to deliver very high performance at a fraction of the cost when compared to supercomputers. The first generation of configurable computers (those with multiple FPGAs connected using a specific interconnect) used statically reconfigurable FPGAs. On these configurable computers, computations are performed by partitioning an entire task into spatially interconnected subtasks. Such configurable computers are used in logic emulation systems and for functional verification of hardware. In general, configurable computers provide the ability to reconfigure rapidly to any desired custom form. Hence, the available resources can be reused effectively to cut down the hardware costs and also improve the performance. In this paper, we introduce the concept of temporal partitioning to partition a task into temporally interconnected subtasks. Specifically, we present algorithms for temporal partitioning and scheduling data flow graphs for configurable computers. We are given a configurable computing unit (RPU) with a logic capacity of S-RPU and a computational task represented by an acyclic data now graph G = (V, E). Computations with logic area requirements that exceed S-RPU cannot be completely mapped on a configurable computer (using traditional spatial mapping techniques). However, a temporal partitioning of the data flow graph followed by proper scheduling can facilitate the configurable computer based execution. Temporal partitioning of the data flow graph is a k-way partitioning of G = (V, E) such that each partitioned segment will not exceed S-RPU in its logic requirement. Scheduling assigns an execution order to the partitioned segments so as to ensure proper execution. Thus, for each segment in {s(1), s(2), ..., s(k)}, scheduling assigns a unique ordering s(i) --> j, 1 less than or equal to i less than or equal to k, 1 less than or equal to j less than or equal to k, such that the computation would execute in proper sequential order as defined by the flow graph G = (V, E).