可编程逻辑阵列分段递进优化布局算法研究

崔秀海; 杨海钢; 龚萧; 黄娟; 谭宜涛

doi:10.3724/SP.J.1146.2008.01689

可编程逻辑阵列分段递进优化布局算法研究

doi: 10.3724/SP.J.1146.2008.01689

崔秀海^{①;杨海钢},
杨海钢,
龚萧,
黄娟,
谭宜涛

计量
- 文章访问数: 3511
- HTML全文浏览量: 91
- PDF下载量: 591
- 被引次数: 0
出版历程
- 收稿日期: 2008-12-12
- 修回日期: 2010-04-20
- 刊出日期: 2010-06-19

A Research on Subsection Progressive Optimization Placement Algorithm of FPGA

摘要

摘要: 为了提高FPGA(Field Programmable Gate Array)的布通率并优化电路的连线长度，在模拟退火算法的基础上，该文提出一种新的FPGA布局算法。该算法在不同的温度区间采用不同的评价函数，高温阶段采用半周长法进行快速优化布局，低温阶段在评价函数中加入变量因子并进行适度的回火处理，以此来优化布局。实验表明，该算法提高了布通率，优化了连线长度，与最具代表性的VPR(Versatile Place and Route)布局算法相比布线通道宽度提高了近6%，电路总的连线长度降低了4~23%。
- FPGA; 布局; 评价函数; 布通率; 模拟退火; VPR (Versatile Place and Route)
Abstract: A novel FPGA simulated annealing placement algorithm is proposed to improve the routability and optimize the length of wires. Different cost functions are applied to different temperature range. In high temperature stage, the half perimeter method is utilized to fast optimize the placement; while in low temperature stage, a variable factor is added into the cost function and the reasonable temper process is also used to improve the quality of placement. Experiment results demonstrate that, compared with the VPR, the proposed method requires 6% fewer routing tracks and the length of wire is 4~23% shorter.

HTML全文

参考文献(1)

Siva Nageswara Rao Borra. Annamalai Muthukaruppan, Suresh S. A novel approach to the placement and routing problems for field programmable gate arrays. Applied Soft Computing, 2007, 7(1): 455-470.[2]Edmund Lee, Guy Lemieux, and Shariar Mirabbasi. Interconnect driver design for long wires in field- programmable Gate Arrays[J].Journal of Signal Processing Systems.2008, 51(1):57-76[3]Xu Wenyao.[J].Xu Kejun, and Xu Xinxin. A novel placement algorithm for symmetrical FPGA. ASICON 07. 7th International Conference on ASIC, Guilin, Oct.2007,:-[4]Marconi Ye Lo.[J].Gaydadjiev T, and Bertels G. An efficient algorithm for free resources management on the FPGA. Design, Automation and Test in Europe, Date08, Munich, Mar.2008,:-[5]Lin Y, Hutton M, and He L. Statistical placement for FPGAs considering process variation[J].IET Computers Digital Techniques.2007, 1(4):267-275[6]Betz V and Rose J. VPR: A new packing, placement and routing tool for FPGA research. Seventh International Workshop on Field-Programmable Logic and applications, London, UK, 1997: 213-222.[7]Marquardt A, Betz V, and Rose J. Timing-driven placement for FPGAs. ACM/SIGDA Int. Symp. on FPGAs, Monterey, CA USA, 2000: 203-213.[8]Hu Bo. Timing-driven placement for heterogeneous field programmable gate array. International Conference on Computer Aided Design Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, CA, Santa Clara, 2006: 383-388.[9]Chen G and Cong J. Simultaneous timing driven and duplication. Proc. 13th FPGA, Monterey, CA,USA, 2005: 51-59.[10]Yang M. Hybrid genetic algorithm for Xilinx-style FPGA placement. Proc. of the First Intl. Conf. on CAD/ECAD, Durham University, UK, 2004: 95-100.[11]Maidee P, Ababei C, and Bazargan K. Timing-driven partitioning-based placement for island style FPGAs[J].?IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems.2005, 24(3):395-406[12]Ahmed E and Rose J. The effect of LUT and cluster size on deep-submicron FPGA performance and density. Proceedings of the 8th ACM/SIGDA International Symposium on Field Programmable Gate Arrays, Monterey, 2000: 3-12.[13]Yang S. Logic synthesis and optimization benchmarks. Version 3.0, Tech. Report, Microelectronics Centre of North Carolina. 1991.[14]Singh D P and Manohararajah V. Incremental retiming for FPGA physical synthesis. Annual ACM IEEE Design Automation Conference, California, USA, 2005: 433-438.[15]Lin Joey Y, Chen Deming, and Cong Jason. Optimal simultaneous mapping and clustering for FPGA delay optimization. Annual ACM IEEE Design Automation Conference Proceedings of the 43rd annual conference on Design automation, San Francisco, CA, USA, 2006: 472-477.

施引文献

资源附件(0)

访问统计