DOI: 10.3724/SP.J.1089.2010.11020

Journal of Computer-Aided Design & Computer Graphics (计算机辅助设计与图形学学报) 2010/22:9 PP.1455-1462

Fast Placement Algorithm for Hierarchical FPGAs

As the capacities of the FPGA devices continue to grow, and more complex architectures are embedded into modern FPGAs, it brings great challenges to FPGA physical design tools. In this paper, a fast placement algorithm is proposed to new commercial hierarchical FPGAs. The algorithm is based on partition framework, and embedded with some optimization strategies aiming at global placement process and detailed placement process on hierarchical FPGAs. Experimental results show that the embedded optimization strategies enable our algorithm a great improvement to the total wirelength of circuit, which achieves 29% on average. While compared with clustering-based algorithm, our algorithm speeds mount up to over 4 times in runtime with nearly 40% reduction on wirelength.

Key words:hierarchical FPGA,partition algorithm,fast placement

ReleaseDate:2014-07-21 15:25:43

[1] Zeng Xiangzhi. Fast placement algorithm for hierarchical FPGAs[D]. Beijing: Tsinghua University. Department of Computer Science & Technology, 2009 (in Chinese) (曾祥智. 层次式FPGA快速布局算法研究[D]. 北京: 清华大学计算机科学与技术系, 2009)

[2] Betz V, Rose J. VPR: a new packing, placement and routing tool for FPGA research[C]// Proceedings of the 7th International Workshop on Field Programmable Logic and Applications. London: Springer, 1997: 213-222

[3] Wrighton M G, DeHon A M. Hardware-assisted simulated annealing with application for fast FPGA placement[C]// Proceedings of the ACM-SIGDA International Symposium on FPGAs. New York: ACM Press, 2003: 33-42

[4] Maidee P, Ababei C, Bazargan K. Fast timing-driven partitioning-based placement for island style FPGAs[C]// Proceedings of the 40th Annual Design Automation Conference. New York: ACM Press, 2003: 598-603

[5] Callahan T J, Chong P, DeHon A,et al. Fast module mapping and placement for datapaths in FPGAs[C]// Proceedings of the 6th ACM-SIGDA International Symposium on FPGAs. New York: ACM Press, 1998: 123-132

[6] Dai H, Zhou Q, Cai Y C,et al. Fast placement for large-scale hierarchical FPGAs[C]// Proceedings of the 11th IEEE International Conference on Computer-Aided Design and Computer Graphics. Yellow Mountain City: IEEE Press, 2009: 190-194

[7] Zeng X Z, Zhou Q, Cai Y C,et al. Wirelength optimization for multilevel hierachical FPGA[C]// Proceedings of World Congress on Software Engineering. Los Alamitos: IEEE Press, 2009, 4: 361-366

[8] Karypis G, Aggarwal R, Kumar V,et al. Multilevel hypergraph partitioning: application in VLSI domain[C]// Proceedings of International Design and Automation Conference. New York: ACM Press, 1997: 526-529

[9] Hong Xianlong, Yan Xiaolang, Qiao Changge. Large-scale VLSI floorplan theory and algorithm[M]. Beijing: Science Press, 1998 (in Chinese) (洪先龙, 严晓浪, 乔长阁. 超大规模集成电路布图理论及算法[M]. 北京: 科学出版社, 1998)

[10] Angelo Family Datasheet[M]. Version 1.0. Agate Logic Inc, 2009