EDA全局布局中线长估计算法研究

摘要

随着定制化芯片的需求越来越大，对与之配套的电子设计自动化(Electronic Design Automation，EDA)软件的要求也就越来越高，尤其是在某些特定芯片需要特定功能的EDA软件支持的情况下。然而，主流EDA软件基本上被国外少数公司所垄断，价格昂贵且不易获得特殊支持，所以研究并开发具有特定需求的EDA软件成为当务之急。 EDA软件主要包括逻辑综合，布局和布线等功能，其中布局和布线是EDA软件的重要组成部分。布局布线的效果直接反映EDA软件的质量，为了衡量布局布线的效果，用于对布局布线进行评估的线长估计函数就显得十分重要。 论文分析了不同目标芯片类型的布局线长估计函数的特点，在全部线长、执行效率、关键路径延迟、拥塞控制等方面，对线长估计函数及布局算法进行了改进，提高了布局算法的执行效率和布局结果的精度。通过分析标准单元和FPGA在布局结构、布局特点和布局目标上的异同，总结出两种类型的线长代价函数的优化目标。在标准单元布局线长估计函数方面，首先实现了最小线长、最小关键延迟、最小拥塞三种运行模式，并且通过使用带查找表和高度电路启发式分割的斯坦纳改进线长估计函数，代替了原有半周长线长估计，大大提高了布局精度；针对FPGA布局线长估计函数的特点，通过引入拥塞和Switch延迟改善了布局的拥塞和延迟控制。 论文设计和实现了基于标准单元的最小分割布局原型系统，并实现了不同线长估计函数，获得较好的布局结果。对当前主流FPGA布局布线VPR算法作了针对性的改进，实现了6输入LUT结构，在线长估计函数中加入拥塞、Switch延迟等优化目标，且在布局阶段尝试使用布线算法(pathfinder)取代线长估计函数。

目录

文摘

英文文摘

声明

第一章绪论

1.1研究背景

1.2基本概念

1.3布局算法及其线长估计函数研究现状

1.3.1基于标准单元的布局算法研究现状

1.3.2基于FPGA的布局算法研究现状

1.3.3布局线长估计函数研究热点

1.4主要研究内容

1.5论文组织结构

第二章标准单元布局及其线长估计函数

2.1基于标准单元的布局算法

2.1.1模拟退火布局算法

2.1.2最小分割布局算法

2.1.3基于行的布局算法

2.2标准单元布局的线长估计函数

2.2.1半周长线长估计函数

2.2.2二次线长估计函数

2.2.3一次线长估计函数

2.2.4线性最小生成树(RMST)线长估计函数

2.2.5线性斯坦纳树(RSMT)线长估计函数

2.2.6采用查找表(Look-up table)的斯坦纳线长估计函数

2.3 小结

第三章标准单元布局原型实现及其线长估计函数改进

3.1基于超图分割的标准单元布局系统原型实现

3.1.1数据结构

3.1.2输入文件格式

3.1.3最小分割(Min-Cut)策略

3.1.4最小分割(Min-Cut)函数框架

3.1.5四路分割

3.1.6超图分割hMetis算法参数设置

3.2线长估计函数实现与改进

3.2.1线长估计函数实现

3.2.2斯坦纳树线长估计函数改进

3.3相关实验及结果分析

3.3.1改进后斯坦纳树线长估计函数实验

3.3.2线长估计函数集成实验及结果分析

3.3.3布局原型系统运行结果

3.4 小结

第四章FPGA布局算法及其线长估计函数

4.1 FPGA器件特点

4.2 FPGA布局与标准单元布局的区别

4.3主流FPGA布局及其线长估计函数

4.3.1时序分析

4.3.2延迟模型

4.3.3代价函数的计算

4.4小结

第五章FPGA布局算法及其线长估计函数改进

5.1基于FPGA布局线长估计函数改进思路及方法

5.2针对6-LUT结构的改进

5.3布局线长估计函数改进

5.3.1拥塞(congestion)控制算法

5.3.2对齐(terminal alignment）代价函数

5.4全局布局中集成pathfinder布线算法

5.5改进实验及结果分析

5.6 小结

第六章总结和展望

6.1论文工作总结

6.2进一步的展望

致谢

参考文献

发表论文