Author_Institution :
Synopsys Inc., Mountain View, CA, USA
Abstract :
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 SRPU and a computational task represented by an acyclic data flow graph G=(V, E). Computations with logic area requirements that exceed SRPU 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 SRPU in its logic requirement. Scheduling assigns an execution order to the partitioned segments so as to ensure proper execution. Thus, for each segment in {s1,s2,...,s k}, scheduling assigns a unique ordering Si-j,1⩽i⩽k,1⩽j⩽k, such that the computation would execute in proper sequential order as defined by the flow graph G=(V, E)
Keywords :
data flow graphs; field programmable gate arrays; logic partitioning; reconfigurable architectures; configurable computing unit; data flow graphs scheduling; emulation systems; functional verification; hardware costs; k-way partitioning; logic area requirements; performance; reconfigurable computers; spatially interconnected subtasks; supercomputers; temporal partitioning; Costs; Data flow computing; Emulation; Field programmable gate arrays; Flow graphs; Hardware; Partitioning algorithms; Processor scheduling; Reconfigurable logic; Supercomputers;