Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18] [ 19] [ 20] [ 21] [ 22] [ 23] [ 24]

¡@

Journal of Information Science and Engineering, Vol. 26 No. 2, pp. 565-583 (March 2010)

Reduced Communication Costs via Network Flow and Scheduling for Partitions of Dynamically Reconfigurable FPGAs*

YUNG-CHUAN JIANG AND JHING-FA WANG
 Department of Electrical Engineering
National Cheng Kung University
Tainan, 701 Taiwan

This paper presents a dynamically reconfigurable FPGA partitioning algorithm for netlist-level circuits. The proposed algorithm combines traditional max-flow min-cut computing with a scheduling mechanism to improve maximum communication costs. Application of our previously published scheduling mechanism [19] to partitioning of sequential circuits can induce problems regarding the crossing of cuts, so in this paper we introduce an additional labeling mechanism to guarantee the removal of any crossed cuts. Experimental results on a number of standard benchmark circuits show the proposed algorithm achieves superior maximum communication costs compared to the published FBP-m, PAT and Hierarchical algorithms. Compared to the published ILP algorithm, which uses a very different methodology, our algorithm consistently produces superior runtime but approximately equal maximum communication costs.

Keywords: FPGA, dynamically reconfigurable computing, circuit partitioning, temporal partitioning, graph theory

Full Text (¥þ¤åÀÉ) Retrieve PDF document (201003_14.pdf)

Received March 19, 2008; revised December 3, 2008 & April 14, 2009; accepted April 30, 2009.
Communicated by Yao-Wen Chang.
* This research was supported by the National Science Council of Taiwan, R.O.C., under grants No. NSC 98- 2218-E-006-003.