- 期刊
- OpenAccess
Reduced Communication Costs via Network Flow and Scheduling for Partitions of Dynamically Reconfigurable FPGAs
並列摘要
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.
延伸閱讀
- 蔡志偉（2009）。A Task Dependent Scheduling Algorithm for Dynamically Reconfigurable FPGA Systems〔碩士論文，國立臺北科技大學〕。華藝線上圖書館。https://doi.org/10.6841/NTUT.2009.00300
- 游杰易（2008）。An Efficient Scheduling Algorithm for Partial Dynamic Reconfigurable FPGA Systems〔碩士論文，國立臺北科技大學〕。華藝線上圖書館。https://doi.org/10.6841/NTUT.2008.00425
- Mehta, D. P., Shetters, C., & Bouldin, D. W. (2013). Meta-Algorithms for Scheduling a Chain of Coarse-Grained Tasks on an Array of Reconfigurable FPGAs. VLSI Design, 2013(), 58-70. https://doi.org/10.1155/2013/249592
- Lin, C. H. (2007). Design and Implementation of Asynchronous Reconfigurable FPGAs [master's thesis, Tatung University]. Airiti Library. https://www.airitilibrary.com/Article/Detail?DocID=U0081-0607200917242764
- Li, C. F. (2007). Leakage-Aware Task Scheduling for Partially Dynamic Reconfigurable FPGAs [master's thesis, National Taiwan University]. Airiti Library. https://doi.org/10.6342/NTU.2007.01429