FPGA布局算法研究与设计
|
摘要
FPGA(Field Programmable Gate Array),即现场可编程门阵列,具有集成度高、逻辑资源丰富、设计灵活以及使用范围广等特点,因此在数字系统设计中得到了广泛的应用。FPGA设计流程主要包括设计输入、逻辑综合、逻辑优化、技术映射、打包、布局和布线。在FPGA设计中,布局是极为重要的一个环节,它直接影响到后续布线的质量和整个电路的性能。在FPGA芯片逻辑资源中,布线资源占到整个芯片资源的60%以上,因此如何在布局阶段对布线资源进行合理的估算并有效降低布线的拥挤度成为布局算法重要研究方向。
基于布线拥挤度的FPGA布局算法的研究主要分为两个方面：首先是如何使现有的优化算法适应于FPGA结构,即完成现有算法针对特定FPGA结构的建模,同时将布线拥挤度代价函数融于算法结构中,从而达到在布局阶段减少降低布线拥挤度的目的。其次是在布局阶段对布线拥挤度估算模型进行研究。基于FPGA结构对布线资源的使用进行合理的建模,以准确估算布线资源的使用,且在算法中将拥挤度代价作为代价函数的一部分引导算法过程,从而达到减少布线资源使用降低布线拥挤度的目的。
本文针对基于布线拥挤度的FPGA布局算法的两个方面进行了较为深入的研究,所做的主要工作如下：
基于布线拥挤度问题对FPGA设计领域的主要布局优化算法进行了详细的分析,包括基于划分的布局算法,模拟退火算法,遗传算法,蚁群算法等。基于对常见布局优化算法的比较,本文将蚁群算法应用于FPGA布局中,以FPGA著名开源软件VPR为研究平台,将布线拥挤度作为启发因子引导算法,实验表明基于布线拥挤度的蚁群布局算法能够获得较好的结果。
布线拥挤度估算模型是基于布线拥挤度的布局算法的一个重要研究方向。本文对主流拥挤度估算算法的特点进行了分析,提出一种等概率的拥挤度估算模型。该模型基于Bounding Box结构构建,不依靠具体的布线路径来进行布线资源估算,而是将布线资源的估算等概率分配给每个待布局区域,因此不会造成布局时间的显著增加。实验结果表明该模型的估算精确度与Xilinx ISE基本一致,将该模型融于布局算法中在不显著增加FPGA布局时间的情况下降低了布线拥挤度,从而改善了电路的性能。
Since FPGA (Field Programmable Gate Array) has the characteristics of high integration, rich logical resource, flexible design and a widely usage, it has been widely used in the design of digital systems. FPGA design flow includes design entry, logic synthesis, logic optimization, technology mapping, packing, placement and routing. In the flow of FPGA design, the placement is extremely important because it directly affects the quality of routing and the performance of whole circuit. Routing resources account for over 60% of overall resources in FPGA chips, so how to do a reasonable estimation for the routing resource and effectively reduce the routing congestion becomes an important research direction for placement algorithm.
The research of placement algorithm based on routing congestion is divided into two aspects. The first aspects is how to adapt the existing optimization algorithm to FPGA architecture and merge routing congestion function into the algorithm structure, so as to achieve the reduction of routing congestion in the placement.Secondly, the research has been focusing on the routing congestion estimation model. In these algorithms, the routing congestion estimation model can accurately estimate the routing resource utilization.Then the cost of routing congestion as a part of the cost function can guide the placement algorithm for reducing the use of routing resources.
This thesis carried out a detailed analysis on the main placement algorithm based on routing congestion, including partition-based algorithm, simulated annealing algorithm, genetic algorithm and ant colony algorithm. With the comparison of these optimization algorithms, ACO(Ant Colony Optimization) is applied to FPGA placement considering routing congestion. Experiments show that ACO-based placement algorithm can obtain better results than that of VPR.
Routing congestion estimation model is very important for placement algorithm. We proposed a equiprobable-estimation model based on bounding box structure. Experimental results demonstrate that the accuracy of this model is comparable with Xilinx ISE. This model which was integrated into placement algorithm can improve the circuit performance without a significant increasing of run time of placement.
基于布线拥挤度的FPGA布局算法的研究主要分为两个方面：首先是如何使现有的优化算法适应于FPGA结构,即完成现有算法针对特定FPGA结构的建模,同时将布线拥挤度代价函数融于算法结构中,从而达到在布局阶段减少降低布线拥挤度的目的。其次是在布局阶段对布线拥挤度估算模型进行研究。基于FPGA结构对布线资源的使用进行合理的建模,以准确估算布线资源的使用,且在算法中将拥挤度代价作为代价函数的一部分引导算法过程,从而达到减少布线资源使用降低布线拥挤度的目的。
本文针对基于布线拥挤度的FPGA布局算法的两个方面进行了较为深入的研究,所做的主要工作如下：
基于布线拥挤度问题对FPGA设计领域的主要布局优化算法进行了详细的分析,包括基于划分的布局算法,模拟退火算法,遗传算法,蚁群算法等。基于对常见布局优化算法的比较,本文将蚁群算法应用于FPGA布局中,以FPGA著名开源软件VPR为研究平台,将布线拥挤度作为启发因子引导算法,实验表明基于布线拥挤度的蚁群布局算法能够获得较好的结果。
布线拥挤度估算模型是基于布线拥挤度的布局算法的一个重要研究方向。本文对主流拥挤度估算算法的特点进行了分析,提出一种等概率的拥挤度估算模型。该模型基于Bounding Box结构构建,不依靠具体的布线路径来进行布线资源估算,而是将布线资源的估算等概率分配给每个待布局区域,因此不会造成布局时间的显著增加。实验结果表明该模型的估算精确度与Xilinx ISE基本一致,将该模型融于布局算法中在不显著增加FPGA布局时间的情况下降低了布线拥挤度,从而改善了电路的性能。
Since FPGA (Field Programmable Gate Array) has the characteristics of high integration, rich logical resource, flexible design and a widely usage, it has been widely used in the design of digital systems. FPGA design flow includes design entry, logic synthesis, logic optimization, technology mapping, packing, placement and routing. In the flow of FPGA design, the placement is extremely important because it directly affects the quality of routing and the performance of whole circuit. Routing resources account for over 60% of overall resources in FPGA chips, so how to do a reasonable estimation for the routing resource and effectively reduce the routing congestion becomes an important research direction for placement algorithm.
The research of placement algorithm based on routing congestion is divided into two aspects. The first aspects is how to adapt the existing optimization algorithm to FPGA architecture and merge routing congestion function into the algorithm structure, so as to achieve the reduction of routing congestion in the placement.Secondly, the research has been focusing on the routing congestion estimation model. In these algorithms, the routing congestion estimation model can accurately estimate the routing resource utilization.Then the cost of routing congestion as a part of the cost function can guide the placement algorithm for reducing the use of routing resources.
This thesis carried out a detailed analysis on the main placement algorithm based on routing congestion, including partition-based algorithm, simulated annealing algorithm, genetic algorithm and ant colony algorithm. With the comparison of these optimization algorithms, ACO(Ant Colony Optimization) is applied to FPGA placement considering routing congestion. Experiments show that ACO-based placement algorithm can obtain better results than that of VPR.
Routing congestion estimation model is very important for placement algorithm. We proposed a equiprobable-estimation model based on bounding box structure. Experimental results demonstrate that the accuracy of this model is comparable with Xilinx ISE. This model which was integrated into placement algorithm can improve the circuit performance without a significant increasing of run time of placement.
引文
[1]V. Betz and J. Rose, "VPR:A New Packing, Placement and Routing Tool for FPGA Research, " Int'1 Workshop on FPL,1997, pp.213-222.
[2]W. Swartz and C. Sechen, "Timing Driven Placement for Large Standard Cell Circuits, " DAC,1995, pp.211-215.
[3]B. Riess and G. Ettelt, "SPEED:Fast and Efficient Timing Driven Placement, " IEEE International Symposium on Circuits and Systems,1995, pp.377-380.
[4]A. Marquardt, V. Betz and J. Rose, "Timing-Driven Placement for FPGAs", in Proc. ACM/SIGDA FPGA Conference, FPGAOO, pp 203-213,2000.
[5]S. K. Nag and R. A. Rutenbar, "Performance-Driven Simultaneous Placement and Routing for FPGAs". IEEE Trans. On CAD for Integrated Circuits and Systems, Vol. 17, No.6, pp.499-518, June 1998.
[6]M. Wang and M. Sarrafzadeh, "Behavior of congestion minimization during placement, " in Proc. Int. Symp. Physical Design, Apr.1999, pp.145-150.
[7]P. N. Parakh, R. B. Brown, and K. A. Sakallah, "Congestion driven quadratic placement," in Proc. Design Automation Conf., June 1998, pp.275-278.
[8]M. Wang, X. Yang, K. Eguro, and M. Sarrafzadeh, "Multi-center congestion estimation and minimization during placement, " in Proc. Int. Symp. Physical Design, Apr.2000, pp.147-152.
[9]M. Wang, X. Yang, and M. Sarrafzadeh, "Dragon2000:Fast standard-cell placement for large circuits, " in Proc. Int. Conf. Computer-Aided Design, Nov.2000, pp. 260-263.
[10]A. E. Dunlop, B. W. Kernighan. A Procedure for Placement of Standard Cell VLSI Circuits. IEEE Transactions on Computer-Aided Design,1985,4(1):92-98
[11]A. E. Caldwell, A. B. Kahng, I. L. Markov. Can Recursive Bisection Alone Produce Routable Placements. in:Proceedings of International Design and Automation Conference,2000.477-482
[12]M. Wang, X. Yang, M. Sarrafzadeh. Standard-cell Placement Tool for Large Industry Circuits. Proceedings of International Conference on Computer-Aided Design, pp.260-264,2000
[13]Sechen. C. The Timber Wolf placement and routing package. Solid-State Circuits, 1985:510-522
[14]M.Yang and A.E.A. Almaini. Hybrid Genetic Algorithm for Xilinx-style FPGA Placement. Proc. Of the First Intl. Conf. on CAD/ECAD, Durham University, UK,2004, pp.95-100.
[15]Schnecke V and Vornberger 0. Hybrid genetic algorithms for constrained placement problems. IEEE Transactions on Evolutionary Computation, vol.1, no.4, pp.266-277, Nov 1997.
[16]M. Yang, A. E. A. Almaini. An Evolutionary Approach for Symmetrical FPGA Placement.. Assignment Problem Intellectics Group. Department of Computer Science Darmstadt University of Technology, Germany, Tech. Rep. AIDA-99-03,2001.
[17]A. Marquardt, V. Betz and J. Rose, "Timing-Driven Placement for FPGAs", in Proc. ACM/SIGDA FPGA Conference, FPGAOO, pp 203-213,2000.
[18]S.K. Nag and R. A. Rutenbar, "Performance-Driven Simultaneous Placement and Routing for FPGAs". IEEE Trans. On CAD for Integrated Circuits and Systems, Vol. 17, No.6, pp.499-518, June 1998
[19]Vittorio Maniezzo, Alberto Colorni. The Ant System Applied to the Quadratic Assignment Problem. IEEE Transactions on Knowledge and Data engineering, vol.11, no.5, September/October 1999.
[20]Stauffer A, Sipper M, Perez-Uribe A. Some Applications of FPGAs in Bio-Inspired Hardware. FPGAs for Custom Computing Machines, PP.278-279, Apr.1998
[21]S.Mayrhofer and U. Lauther. Congestion-driven placement using a new multi-partitioning heuristic. Proc Computer-Aided Design Conference[C].1990, pp.332-335
[22]C. Chang, J Cong,D.Pan and X. Yuan.Multilevel global placement with congestion control. IEEE Transaction On Computer-Aided Design of Integrated Circuits and Systems,22(4):395-409, April 2003.
[23]Cheng C E. RISA:Accurate and efficient placement routability modeling. Proc Computer-Aided Design Conference[C].San Jose:IEEE,1994:690-695.
[24]J. Lou, S. Thakur, S. Krishnamoorthy, and H. Sheng. Estimating routing congestion using probabilistic analysis. IEEE Transaction. On Computer-Aided Design of Integrated Circuits and Systems,21(1):32-42, January 2002.
[25]X, Yang, R. Kastner and M. Sarrafzadeh. Congestion estimation during top-down placement. IEEE Trans. On Computer-Aided Design of Integrated Circuits and Systems,21(1):72-80, January 2002.
[26]U. Brenner and A. Rohe. An effective congestion-driven placement framework. IEEE Trans. On Computer-Aided Design of Integrated Circuits and System,22(4):387-394, April 2003
[27]B. Hu,M. Marek-Sadowska. Congestion Minimization during placement without estimation. Proc Computer-Aided Design Conference[C].2002, pp.739-745
[28]U. Brenner and A. Rohe. An effective congestion-driven placement framework. IEEE Trans. On Computer-Aided Design of Integrated Circuits and System,22(4):387-394, April 2003
[29]Parakh P N, Brown R B, Sakallah K A. Congestion driven quadratic placement. Proc Computer-Aided Design Conference[C]. San Francisco:IEEE,1998:275-278.
[30]X. Yang, B. K. Choi, and M. Sarrafzadeh. Routability-driven white space allocation for fixed-die standard-cell placement. IEEE Transaction On Computer-Aided Design of Integrated Circuits and Systems,22 (4):410-419, April 2003.
[31]M. Dorigo, V. Maniezzo, A. Colorni. The Ant System:Optimization by a colony of coorperating agents. IEEE Transaction On Systems, Man, and Cybernetics-Part B, 1996,26(1):pp.29-41.
[32]/[26]Dorigo M, Luca Maria Gamberdella. Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem. TR, IRIDIA,1996.
[33]http://www. eecg. toronto. edu/. vaughn/challenge/challenge. html
[34]陆重阳,卢东华.PGA技术及其发展趋势[J].微电子技术,2003,31(1)：5-7.
[35]段海滨.蚁群算法原理及其应用.北京,科学出版社,2005.
[36]K. Shahookar, P. Mazumder. VLSI cell placement techniques. ACM Computing Surveys(CSUR), vol.23, n.2, pp.143-220, June.1991.
[37]Dehon A. Balancing interconnect and computation in a reconfigurable computing array. ACM/SIGDA Int. Symp. On FPGAs,1999, pp.69-78.
[38]Deming Chen, Jason Cong and Peichen Pan. FPGA Design Automation:A Survey Foundations and Trends in Electronic Design Automation Vol.1, No 3 (November 2006) 195-330
[39]Cong J, Kong T, Shinnerl J R, et al. Large-scale circuit placement:Gap and promise[A]. Proc Computer-Aided Design Conference[C].San Jose:IEEE,2003:883-890.
[40]Y. Zhuo, H. Li, and S. P. Mohanty. A congestion driven placement algorithm for FPGA synthesis. Proceedings of the International Conference on Field Programmable Logic and Applications,2006, pp.683-686.
[41]S. Brown, R. J. Francis and J. Rose, Field Programmable Gate Arrays, Kluwer Academic Publishers,1992.
[42]W. E. Donath. Placement and average interconnection lengths of computer logic. IEEE Transaction On Computer-Aided Design of Integrated Circuits and Systems, pp.272-277, April 1979.
[2]W. Swartz and C. Sechen, "Timing Driven Placement for Large Standard Cell Circuits, " DAC,1995, pp.211-215.
[3]B. Riess and G. Ettelt, "SPEED:Fast and Efficient Timing Driven Placement, " IEEE International Symposium on Circuits and Systems,1995, pp.377-380.
[4]A. Marquardt, V. Betz and J. Rose, "Timing-Driven Placement for FPGAs", in Proc. ACM/SIGDA FPGA Conference, FPGAOO, pp 203-213,2000.
[5]S. K. Nag and R. A. Rutenbar, "Performance-Driven Simultaneous Placement and Routing for FPGAs". IEEE Trans. On CAD for Integrated Circuits and Systems, Vol. 17, No.6, pp.499-518, June 1998.
[6]M. Wang and M. Sarrafzadeh, "Behavior of congestion minimization during placement, " in Proc. Int. Symp. Physical Design, Apr.1999, pp.145-150.
[7]P. N. Parakh, R. B. Brown, and K. A. Sakallah, "Congestion driven quadratic placement," in Proc. Design Automation Conf., June 1998, pp.275-278.
[8]M. Wang, X. Yang, K. Eguro, and M. Sarrafzadeh, "Multi-center congestion estimation and minimization during placement, " in Proc. Int. Symp. Physical Design, Apr.2000, pp.147-152.
[9]M. Wang, X. Yang, and M. Sarrafzadeh, "Dragon2000:Fast standard-cell placement for large circuits, " in Proc. Int. Conf. Computer-Aided Design, Nov.2000, pp. 260-263.
[10]A. E. Dunlop, B. W. Kernighan. A Procedure for Placement of Standard Cell VLSI Circuits. IEEE Transactions on Computer-Aided Design,1985,4(1):92-98
[11]A. E. Caldwell, A. B. Kahng, I. L. Markov. Can Recursive Bisection Alone Produce Routable Placements. in:Proceedings of International Design and Automation Conference,2000.477-482
[12]M. Wang, X. Yang, M. Sarrafzadeh. Standard-cell Placement Tool for Large Industry Circuits. Proceedings of International Conference on Computer-Aided Design, pp.260-264,2000
[13]Sechen. C. The Timber Wolf placement and routing package. Solid-State Circuits, 1985:510-522
[14]M.Yang and A.E.A. Almaini. Hybrid Genetic Algorithm for Xilinx-style FPGA Placement. Proc. Of the First Intl. Conf. on CAD/ECAD, Durham University, UK,2004, pp.95-100.
[15]Schnecke V and Vornberger 0. Hybrid genetic algorithms for constrained placement problems. IEEE Transactions on Evolutionary Computation, vol.1, no.4, pp.266-277, Nov 1997.
[16]M. Yang, A. E. A. Almaini. An Evolutionary Approach for Symmetrical FPGA Placement.. Assignment Problem Intellectics Group. Department of Computer Science Darmstadt University of Technology, Germany, Tech. Rep. AIDA-99-03,2001.
[17]A. Marquardt, V. Betz and J. Rose, "Timing-Driven Placement for FPGAs", in Proc. ACM/SIGDA FPGA Conference, FPGAOO, pp 203-213,2000.
[18]S.K. Nag and R. A. Rutenbar, "Performance-Driven Simultaneous Placement and Routing for FPGAs". IEEE Trans. On CAD for Integrated Circuits and Systems, Vol. 17, No.6, pp.499-518, June 1998
[19]Vittorio Maniezzo, Alberto Colorni. The Ant System Applied to the Quadratic Assignment Problem. IEEE Transactions on Knowledge and Data engineering, vol.11, no.5, September/October 1999.
[20]Stauffer A, Sipper M, Perez-Uribe A. Some Applications of FPGAs in Bio-Inspired Hardware. FPGAs for Custom Computing Machines, PP.278-279, Apr.1998
[21]S.Mayrhofer and U. Lauther. Congestion-driven placement using a new multi-partitioning heuristic. Proc Computer-Aided Design Conference[C].1990, pp.332-335
[22]C. Chang, J Cong,D.Pan and X. Yuan.Multilevel global placement with congestion control. IEEE Transaction On Computer-Aided Design of Integrated Circuits and Systems,22(4):395-409, April 2003.
[23]Cheng C E. RISA:Accurate and efficient placement routability modeling. Proc Computer-Aided Design Conference[C].San Jose:IEEE,1994:690-695.
[24]J. Lou, S. Thakur, S. Krishnamoorthy, and H. Sheng. Estimating routing congestion using probabilistic analysis. IEEE Transaction. On Computer-Aided Design of Integrated Circuits and Systems,21(1):32-42, January 2002.
[25]X, Yang, R. Kastner and M. Sarrafzadeh. Congestion estimation during top-down placement. IEEE Trans. On Computer-Aided Design of Integrated Circuits and Systems,21(1):72-80, January 2002.
[26]U. Brenner and A. Rohe. An effective congestion-driven placement framework. IEEE Trans. On Computer-Aided Design of Integrated Circuits and System,22(4):387-394, April 2003
[27]B. Hu,M. Marek-Sadowska. Congestion Minimization during placement without estimation. Proc Computer-Aided Design Conference[C].2002, pp.739-745
[28]U. Brenner and A. Rohe. An effective congestion-driven placement framework. IEEE Trans. On Computer-Aided Design of Integrated Circuits and System,22(4):387-394, April 2003
[29]Parakh P N, Brown R B, Sakallah K A. Congestion driven quadratic placement. Proc Computer-Aided Design Conference[C]. San Francisco:IEEE,1998:275-278.
[30]X. Yang, B. K. Choi, and M. Sarrafzadeh. Routability-driven white space allocation for fixed-die standard-cell placement. IEEE Transaction On Computer-Aided Design of Integrated Circuits and Systems,22 (4):410-419, April 2003.
[31]M. Dorigo, V. Maniezzo, A. Colorni. The Ant System:Optimization by a colony of coorperating agents. IEEE Transaction On Systems, Man, and Cybernetics-Part B, 1996,26(1):pp.29-41.
[32]/[26]Dorigo M, Luca Maria Gamberdella. Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem. TR, IRIDIA,1996.
[33]http://www. eecg. toronto. edu/. vaughn/challenge/challenge. html
[34]陆重阳,卢东华.PGA技术及其发展趋势[J].微电子技术,2003,31(1)：5-7.
[35]段海滨.蚁群算法原理及其应用.北京,科学出版社,2005.
[36]K. Shahookar, P. Mazumder. VLSI cell placement techniques. ACM Computing Surveys(CSUR), vol.23, n.2, pp.143-220, June.1991.
[37]Dehon A. Balancing interconnect and computation in a reconfigurable computing array. ACM/SIGDA Int. Symp. On FPGAs,1999, pp.69-78.
[38]Deming Chen, Jason Cong and Peichen Pan. FPGA Design Automation:A Survey Foundations and Trends in Electronic Design Automation Vol.1, No 3 (November 2006) 195-330
[39]Cong J, Kong T, Shinnerl J R, et al. Large-scale circuit placement:Gap and promise[A]. Proc Computer-Aided Design Conference[C].San Jose:IEEE,2003:883-890.
[40]Y. Zhuo, H. Li, and S. P. Mohanty. A congestion driven placement algorithm for FPGA synthesis. Proceedings of the International Conference on Field Programmable Logic and Applications,2006, pp.683-686.
[41]S. Brown, R. J. Francis and J. Rose, Field Programmable Gate Arrays, Kluwer Academic Publishers,1992.
[42]W. E. Donath. Placement and average interconnection lengths of computer logic. IEEE Transaction On Computer-Aided Design of Integrated Circuits and Systems, pp.272-277, April 1979.