一种新的快速FPGA布局算法课件

1、论 文 报 告一种新的快速FPGA布局算法报告人：陈凡 导 师：梁华国 教授2022/9/18 研究背景1 模拟退火算法2 快速FPGA布局算法3总结与展望 4TSV数目敏感的三维电路划分2022/9/182VLSI设计流程（回顾）封装和测试设计验证制造物理设计电路设计功能设计逻辑设计系统规范说明图1-1 VLSI设计流程详细布线布图规划和布局总体布线物理设计划分芯片制造电路设计图1-2 物理设计过程2022/9/183研究背景1 什么是布局问题？2 集成电路的布局问题怎样描述？2022/9/184布局就是把元件或模块安置在芯片或印制电路板的适当位置上，并使其满足一定的目标要求。布局阶段的输入

2、是一组模块、模块上的引线段信息和网表。通常所说的“布局问题”是指待安置的模块均是硬模块。当模块中包含有软模块时，此时的布局问题称为布图规划（Floorplanning）问题。布局问题2022/9/185集成电路的布局问题描述为：设B1，B2，.Bn是需要放置在芯片上的单元，每一个Bi(1in)对应的高度和宽度分别为Hi和Wi。N=N1,N2,.,Nm表示连接不同单元的线网的集合，Q=Q1,Q2,.,Qk表示单元间用于布线的空区域，Li(1im)表示估计的线网Ni的长度。布局问题就是为每个单元寻求一个矩形区域R=(R1,R2,.,Rn)使其满足下列条件：每个单元都能放置与它相对应的矩形区域，也就

3、是说，Ri的高度和宽度分别为Hi和Wi任意两个矩形不重叠。即布局是可布的。即 所有 和 面积之和最小。所有线网总线长最小，即 最小。2022/9/187宏模块的意义及作用随着电路规模的增大，FPGA规划(FPGAFloorplanning)问题 被引入到FPGA宏模块布局里。 首先，对于一些有特殊功能的宏模块，如加法器、乘法器等宏模块单元，由于对时序有特定要求，故可由用户指定宏模块，在布局时不将其打散而作为硬软模块进行操作；另外，随着电路规模的增大，电路单元越来越多，直接对大量的逻辑单元等较小单元进行布局布线非常耗时，在这种情况下，将单元以宏模块的方式进行布局有助于节省大量时间。2022/9/

4、188模拟退火算法阐述模拟退火模仿逐渐冷却熔化金属以制造高质量金属材料的退火过程。首次将模拟退火算法用在布局中的是Jepsen和Gelatt。基于模拟退火算法的布局器的伪代码2022/9/1810 研究背景1 模拟退火算法2 快速FPGA布局算法3总结与展望 4一种快速FPGA布局算法2022/9/1811摘要在模拟退火算法的基础上,提出了一种快速FPGA布局算法.该算法先用解析模型快速确定所有宏模块及单个逻辑模块的“理想”位置,然后通过局部扩散消除模块之间的重叠, 得到一个较好的初始布局方案,最后再用低温的模拟退火进一步优化, 确定各模块的最终位置.实验数据表明, 以目前在学术界普遍采用的平

5、方线网总长度为目标函数,与经典的VPR算法相比,新算法大大降低了布局所耗费的时间,而不影响最终布局方案的质量.关键词: 快速布局; 二次规划法; 局部扩散; 模拟退火2022/9/1812新的布局算法 2022/9/1814算法伪代码2022/9/18152种转换方法二次规划的目标函数为：2022/9/1817初始布局（续）(1)式中的x、y是电路中各模块在芯片上的位置坐标。Wij 是连接第i个节点(xi,yi)和第j个节点(xj,yj)边的权重。(2)将等号右边展开可以发现F(x,y)表示的是所有模块间的线网长度的平方和. 由于平方线网长度和真正的线网总长度是正相关的，而且便于计算，因此被学

6、术界普遍采用作为布局优化的目标。(1)式可以用矩阵的形式改写为:其中x、y分别是所有节点的横、纵坐标组成的向量, Q是一个对称矩阵, dx 和dy 来自于固定的输入输出节点, c是一个常量。由于(2) 式是一个二次的函数, 因此该问题是二次规划问题, 属于非线性规划的一种. 当 时, F(x,y)取最小值, 即需要满足2022/9/1818调整初始布局方案1 在FPGA中只有特定的位置才可以放置逻辑模块,且一个位置只能容纳一个模块。2 由于在解方程组时并没有考虑这些限制条件, 所以求得的模块坐标可能不在基本位置上, 或者多个模块占据了同一个基本位置而导致重叠。这里提出一种启发式(heurist

7、ic)的局部扩散算法来调整初始布局方案。2022/9/1819调整初始布局方案(续)2022/9/1820调整初始布局方案(续)1 决定逻辑模块的位置时, 首先将其二维坐标设定为二次规划得到的果，如果是小数则必须先取整。对于宏模块则将坐标赋给处于其几何中心的基本位置。2 当宏模块的长度或宽度不是偶数时, 其几何中心没有基本位置, 这种情况需要在离中心最近的基本位置中取二维坐标值最大者作为中心。然后检查各模块的位置是否“合法”具体来说，不“合法”的情况有3种:1，该模块的坐标在整个芯片区域之外；2，该模块的坐标所在位置的逻辑资源类型与该模块的类型不符；3，该位置已放置了其他模块。2022/9/1

8、821低温退火一、该算法的效果取决于一套退火方案, 即一系列参数的设定：布局的初始温度、每个温度下执行多少次交换、选择交换对象的范围、如何改变温度以及退火终止的条件。二、设定初始温度的原则是: 一个导致现有布局方案质量下降0.1%的交换仍有0.1%的可能被接受。由于导致布局质量变差的交换被接受的概率是 所以初始温度为：其中C是当前布局方案下目标函数的值。2022/9/1822实验结果2022/9/1824实验结果(续)2022/9/1825 研究背景1 模拟退火算法2 快速FPGA布局算法3总结与展望 4TSV数目敏感的三维电路划分2022/9/1827总结与展望1）从以上数据可以发现, 以学术界普遍采用的平方线网总长度为评价指标, 对于大多数例子, 本文提出的算法在布局质量上与VPR相仿, 而与此同时其所耗费的时间相较于VPR而言大大减少. 当电路规模特别小时, 本文提出的算法在速度上的优势并不