一种减少重复搜索的FPGA快速布线算法-论文.pdf

《一种减少重复搜索的FPGA快速布线算法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第26卷第6期计算机辅助设计与图形学学报V01．26No．62014年6月JournalofComputer—AidedDesign&ComputerGraphicsJune2014一种减少重复搜索的FPGA快速布线算法刘洋h，杨海钢”，黄志洪，刘峰”，罗杨””(中国科学院电子学研究所可编程芯片与系统研究室北京100190)(中国科学院大学北京100049)(yanghg@mail．ie．ac，cn)摘要：为了提高FPGA布线的运行速度，提出一种减少重复搜索的快速布线算法，该算法分为布通驱动布线算法和时序驱动布线算法．在布通驱动布线算法中，通过把线网的布线

2、路径转换成连接的布线路径来判断每条连接的路径中是否存在拥塞节点，如果存在，保留其布线路径，否则重新进行搜索；时序驱动布线算法采用临界度判定机制来平衡运行速度和时序性能之间的比重．实验结果表明，与公认的VPR布线算法相比，布通驱动布线算法和时序驱动布线算法的运行时间分别平均减少了95．19和28．98％，且时序驱动布线算法的关键路径延时减少了4．8O．关键词：可编程门阵列；布线；重复搜索；拥塞节点；临界度判定中图法分类号：TP302．1AFastFPGARoutingAlgorithmBasedonRepeatedSearchAvoidanceLiuYang

3、’，YangHaigang¨，HuangZhihong，，LiuFeng”，andLuoYang(SystemonProgrammableChipResearchDepartment，InstituteofElectronics，ChineseAcademyofSciences，Beijing100190)(UniversityofChineseAcademyofSciences，Beijing100049)Abstract：ThispaperpresentsafastFPGAroutingalgorithmthatreducesrepeatedsearc

4、hinordertoimprovethespeedofFPGArouting．Thealgorithmdividesintoroutability—drivenalgorithmandtiming—drivenalgorithm．Bytransformingtheroutedpathofeachnetintoroutedpathsofconnections，routability—drivenalgorithmjudgeswhetherthepathofeveryconnectioncontainscongestednodesornot．Ifthepath

5、ofoneconnectioncontainscongestednodes，itwillberipped—upandrerouted；otherwise，thepathwillbereserved．Criticalitydeterminantstrategyisemployedtotrade—offrunningspeedandtimingperformanceintiming—drivenalgorithm．Experimentalresultsdemonstratedthat，theproposedroutability—drivenalgorithm

6、andtiming—drivenalgorithmdecrease95．19and28．98ofruntimerespectively，andcriticalpathdelayoftiming—drivenalgorithmcanbereducedby4．80onaverage，comparedwithVPR．Keywords：fieldprogrammablegatearray；routing；repeatedsearch；congestednodes；criticalitydeterminant可编程门阵列(fieldprogrammablegatea

7、rray，时用户电路的规模也越来越大，对FPGA应用软件FPGA)由于设计周期短、成本低等优点，已被广泛的运行速度提出了更高的挑战．布线被认为是应用于航天、通信等许多领域．随着FPGA的快速FPGACAD流程中最耗时的一个过程Ⅲ，提高发展和工艺水平的不断提高，芯片规模越来越大，同FPGA布线算法的运行速度，对于减少FPGA应用收稿日期：2013—04—22；修回El期：2013一o't一25．基金项目：国家“八六三”高技术研究发展计划(2012AA012301)；中国科学院、国家外国专家局创新团队国际合作伙伴计划．刘洋(1983一)，男，博士研究生，主要研

8、究方向为大规模集成电路设计自动化；杨海钢(196O一)，男，博士，