可布性驱动的层次式FPGA布局算法研究

论文摘要

在超深亚微米技术工艺下,布局成为超大规模集成电路物理设计中至关重要的一步。由于现场可编程门阵列(Field Programable Gate Array,FPGA)布线资源的预先确定性,使得FPGA的布局更为重要。本文以建立高性能、低拥挤的布局为目标,从FPGA芯片结构和布局算法两方面进行了深入研究。论文提出了一种通用的层次式FPGA(HFPGA)结构模型及布局模型,并且给出了该模型的数学计算公式;提出将元件之间的层次距离转化为线长的方法,实现了基于线网模型的高精度布局算法;提出利用矩形的对角线元件之间层次来代替线长,从而达到优化线长的同时提高布通率的快速布局算法。实验结果表明,两种算法均在北卡罗来纳微电子中心(MCNC)学术芯片测试案例上取得了较理想的布局实验效果,为下一步的布线工作建立了良好的基础接口,并且完成了初始布线的工作。本FPGA结构模型的提出和布局算法的实现也都为工业界提供了借鉴价值。

论文目录

• 摘要
• ABSTRACT
• 第一章 引言
• 1.1 课题的背景、意义和目标
• 1.1.1 集成电路技术与EDA 工具的发展
• 1.1.2 FPGA 的发展现状及趋势
• 1.2 FPGA 的物理设计
• 1.3 本文的研究内容及贡献
• 1.4 论文的组织结构
• 第二章 通用的HFPGA 结构及布局模型
• 2.1 目前常见的FPGA 结构及布局模式
• 2.1.1 对称型FPGA
• 2.1.2 行排列FPGA
• 2.1.3 门海式FPGA
• 2.1.4 布局模式
• 2.2 层次式FPGA 结构
• 2.3 通用层次式FPGA 结构及布局模型
• 2.3.1 通用层次式FPGA 的结构特点
• 2.3.2 层次式FPGA 布局模型
• 2.3.3 HFPGA 布局数学拓扑关系
• 2.4 本章小结
• 第三章 拥挤度驱动布局算法研究
• 3.1 经典布局算法在本课题中的存在形式
• 3.1.1 基于划分的布局算法
• 3.1.2 遗传算法
• 3.1.3 模拟退火布局算法
• 3.2 拥挤度驱动布局算法
• 3.2.1 拥挤度的定义
• 3.2.2 拥挤度的建模
• 3.2.3 降低拥挤度的策略
• 3.3 本章小结
• 第四章 高精度拥挤度驱动布局算法VPH
• 4.1 布局中的拥挤度分析
• 4.1.1 研究布局中拥挤问题的必要性
• 4.1.2 拥挤度的理论模型－星型模型
• 4.2 通用层次式布局算法VPH 的实现
• 4.2.1 拥挤度的数据模型——树型结构
• 4.2.2 拥挤度的数据结构－四叉树
• 4.2.3 拥挤度算法实现
• 4.3 实验结果及分析
• 4.4 本章小结
• VPH'>第五章 快速拥挤度驱动布局算法W_VPH
• 5.1 布局中拥挤度与线长的关系
• VPH 布局模型—对角线模型'>5.2 W_VPH 布局模型—对角线模型
• 5.2.1 布局中的线长
• 5.2.2 对角线模型
• VPH 的实现'>5.3 布局W_VPH 的实现
• 5.3.1 Cost 花费代价函数
• VPH 布局策略'>5.3.2 W_VPH 布局策略
• 5.4 实验结果及分析
• 第六章 总结和展望
• 6.1 总结
• 6.2 未来的工作展望
• 参考文献
• 致谢
• 在学期间发表的学术论文和参加科研情况