Temporal partitioning and scheduling data flow graphs for reconfigurable computers

作     者：Purna, KMG Bhatia, D 

作者机构：Synopsys Inc Mountain View CA 94043 USA Univ Cincinnati Elect & Comp Engn & Comp Sci Dept Design Automat Lab Cincinnati OH 45521 USA 

出 版 物：《IEEE TRANSACTIONS ON COMPUTERS》 (IEEE Trans Comput)

年 卷 期：1999年第48卷第6期

页      面：579-590页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：This research is partially suported by the U.S. Air Force Laboratory at Wright Patterson Air Force Base under contract number F33615-96-C1912.Dinesh Bhatia is an associate professor in the Department of Electrical and Computer Engi-neering and Computer Science at the University of Cincinnati. He also directs the Design Auto-mation Laboratory. His research interests in-clude all aspects of architecture and CAD for field programmable gate arrays  reconfigurable and adaptive computing  physical design automation of VLSI systems  and algorithms. His research is actively supported by the U.S 

主　　题：configurable computing field programmable gate arrays spatial partitioning temporal partitioning scheduling data flow graphs reconfigurable computers high performance computing 

摘      要：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 comp