fpga布局布线算法研究

《fpga布局布线算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学位论文版权使用授权书IIIIfllllllllllllMIIIIIIIIIfY2428512本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。(保密的学位论文在解密后适用本授权说明)学位论文作者签名：本星格签字日期：2。f弓年3月27日翩虢务允签字日期：多p／乡年弓月刁日中图分类号：TP312UDC：004学校代码：10004密级：

2、公开北京交通大学作者姓名：杜星格导师姓名：袁小龙硕士学位论文FPGA布局布线算法的研究论文英文题目学号：10120026职称：副教授学位类别：工学学位级别：硕士学科专业：微电子学与固体电子学研究方向：EDA技术北京交通大学2013年3月致谢本论文的工作是在我的导师袁小龙副教授的悉心指导下完成的，袁小龙教授严谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢三年来袁小龙老师对我的关心和指导。袁老师悉心指导我们完成了实验室的科研工作，在学习上和生活上都给予了我很大的关,L3禾H帮助，在此向袁小龙老师表示衷心的谢意。袁

3、老师对于我的科研工作和论文都提出了许多的宝贵意见，在此表示衷心的感谢。在实验室工作及撰写论文期间，师兄师姐以及余明、章涛、丁艳和韩小月等同学对我的论文研究工作给予了热情帮助，在此向他们表达我的感激之情。另外也感谢我的家人，他们的理解和支持使我能够在学校专心完成学业。虫塞摘要中文摘要摘要：现场可编程门阵列(FPGA)自1984年问世以来发展迅速，目前已经成为数字集成电路设计领域的一种最为普遍的实现途径。其特有的可编程性大大简化了传统数字电路的设计过程，可以毫不夸张的说通过适当的编程可以实现任何数字器件的功能，上至高性能的CPU，

4、下至简单的74电路。FPGA的设计需要有配套的EDA软件工具为支撑，随着电路规模不断增大，对软件算法的要求也越来越高。通用布局布线工具(VPR)是JonathanRose等人联合开发的，被广泛应用于学术界研究不同架构FPGA的布局布线过程。VPR安装方便并且具有图形化操作界面，但是对于一个大规模电路来说布局布线速度显得很慢，如何提高速度是本文研究的重点。本文以VPR为研究对象与实验平台，介绍了布局布线所需要的FPGA结构描述文件、布线资源图以及如何自动化生成参数化结构。通过深入研究VPR布局布线算法，对原有算法做了以下四项改进

5、：第一，对布局准备阶段中用于确定FPGA尺寸的二分查找法进行改进，主要是消除开始与结尾部分的重复查找来减少查找次数提高速率。实验结果表明，改进后的算法节省了三分之一的查找次数；第二，VPR布局算法以经典的模拟退火算法为基础，本文在原有模拟退火算法的基础上加入了回火算法，即在退火降温过程中加入回火升温过程，试图寻找可能被遗漏的最优解。文中共进行了五组实验，实验结果表明，加入回火算法后大大减少了布局消耗的时间，并且仍然能够保证良好的布局质量，五组实验中全程回火0．1最优；第三，VPR布线器使用路径搜索算法，该算法具有很强的顺序性，

6、不同的布线顺序导致不同的布线结果。文中在原算法的基础上加入线网扇出排序算法，即将各线网按照扇出进行排序，布线顺序分别按照扇出数递增和递减两种排序方式进行实验，实验结果表明，使用递减序列节省了四分之一的布线时间，而使用递增序列布线时间有所增加，这与预期结果相吻合，同时证明了递减序列的优越性；第四，布线以布局为前提，布局以布线为目的，两者紧密联系，所以文章最后将布局与布线两方面的改进(之前的改进是单独进行的)结合起来，实验结果表明，全程回火0．1与线网降序排列法最佳。上述四种改进使FPGA布局布线速度得到了一定程度的改善。关键词：

7、FPGA；VPR；布局布线算法；模拟退火算法；迷宫布线；Dijkstra算法分类号：TP312一一△旦墨至黔￡!一—————————————————————————————————————————————————————_————————————————————一——一ABSTRACTABSTRACT：Filedprogrammablegatearray(FPGA)hasbeendevelopingrapidlysince1984．andithasbecometooneofthemostcommonwaysusedindigi

8、talinte薄atedcircuitdesign．ItsuniqueprogrammabilitygreatlysimplifiestheprocessoftraditionaldigitalcffcuRdesign．Itisnotexaggeratetosaythatth