层次式fpga快速布局算法

《层次式fpga快速布局算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、万方数据第22卷第9期计算机辅助设计与图形学学报V01．22No．92010年9月JournalofComputer—AidedDesign＆．ComputerGraphicsSep．2010层次式FPGA快速布局算法戴晖¨，周强”，边计年"，曾祥智2’1’(清华大学计算机科学与技术系北京100084)2’(北京联发科技有限公司北京100080)(daih05@mails．tsinghua．edu．cn)摘要：随着现代FPGA规模与结构迅速发展，对FPGA物理设计的要求越来越高，为此，对商业化层次式FPGA提出一种快速布局算法．以基于划分的布局方

2、法作为基本算法框架，针对层次式FPGA的结构制定计划分粒度控制、空间分配和线网权重分配等优化策略，对电路划分过程(整体布局过程)和详细布局过程进行优化．实验结果表明，该算法在实现快速布局的同时，嵌入的优化策略平均将总线长缩短29％；与基于结群的层次式FPGA布局算法相比，平均线长仅为基于结群算法的60％，同时平均运行速度快4倍多．关键词：层次式FPGA；划分算法；快速布局中图法分类号：TP302．1；TN47FastPlacementAlgorithmforHierarchicalFPGAsDaiHui”，ZhouQiang"，BianJinia

3、n¨，andZengXiangzhi2’”(DepartmentofComputerScienceandTechnology，TsinghuaUniversity。Beijing100084)”(MediaTek(Beijing)Inc。Beijing100080)Abstract：AsthecapacitiesoftheFPGAdevicescontinuetogrow，andmorecomplexarchitecturesareembeddedintomodernFPGAs，itbringsgreatchallengestoFPGAphysi

4、caldesigntools．Inthispaper，afastplacementalgorithmisproposedtonewcommercialhierarchicalFPGAs．Thealgorithmisbasedonpartitionframework，andembeddedwithsomeoptimizationstrategiesaimingatglobalplacementprocessanddetailedplacementprocessonhierarchicalFPGAs．Experimentalresultsshowth

5、attheembeddedoptimizationstrategiesenableouralgorithmagreatimprovementtothetotalwirelengthofcircuit，whichachieves29％onaverage．Whilecomparedwithclustering—basedalgorithm，otiralgorithmspeedsmountuptoover4timesinruntimewithnearly40％reductiononwirelength．Keywords：hierarchicalFPGA

6、；partitionalgorithm；fastplacement随着半导体生产工艺的进步，FPGA得到了迅速的发展，但FPGA的功能增大给FPGA物理设计提出了更高的要求．FPGA布局是FPGA物理设计的关键环节，布局质量的好坏将直接影响FPGA的性能．由于FPGA布线资源的预置性和有限性，不良的布局结果甚至可能导致无法顺利完成布线‘11．现有主流FPGA布局研究中，文献[2]在孤岛结构FPGA基础上提出了一种基于模拟退火的布局收稿日期：200909—11；修回日期：2010-03—25．基金项目：国家自然科学基金(60876026，60833

7、004)．藏晖(1983一)，男，博士．主要研究方向为FPGA物理设计；周强(1966～一)。男．博士，副教授，CCF高级会员，主要研究方向为VLSI高层次综合、布图规划．FPGA物理设计等；边计年(1945一)，男，博士，教授。博士生导师，CCF高级会员。主要研究方向为面向系统芯片(SoC)的系统设计方法学，包括系统描述、软硬件划分与通信综合、与布图绪合的高层次综合、系统协同验证等；曾祥智(1985一)，男，硕士，主要研究方向为FPGA布局算法．万方数据计算机辅助设计与图形学学报第22卷算法，其速度和效果上都是当年学术界的最优秀算法之一，但它只

8、能对问题规模不大以及芯片结构简单的情况进行有效处理；其他一些FPGA快速布局算法【35]主要是针对启发式算法的改进，无法有效地在处理大规