可布性驱动的FPGA总体布局优化算法

张晓珂　高文超　周强 钱旭 贾泽宇

摘要 自从FPGA问世以来，FPGA布局研究一直是设计自动化研究领域的热点，传统FPGA布局一般要求芯片连线总长最短、芯片面積最小。随着 IC工艺技术的飞速发展，可布性研究越来越受到关注。而拥挤度是衡量可布性的重要指标，布线中拥挤的出现往往来源于布局不合理，因此需要在布局阶段就考虑可布性。提出了一种考虑水平和垂直溢出的可布性驱动的线长模型，将其与解析式布局的目标函数相结合，以优化布线拥挤和线长，减少运算的复杂度。实验证明，相比FPGA解析式布局算法，线长和拥挤度都有了很大改进。

关键词 FPGA；可布性；拥挤度；总体布局

DOI DOI： 10.11907/rjdk.162490

中图分类号： TP312

文献标识码： A 文章编号 文章编号： 16727800（2017）002004803

0 引言

随着时代的发展，专用集成电路（ASIC）已远远不能满足用户需求，因而更多的研究者将目光转向了半定制设计模式的器件，成为近期用途最广泛的一种可编程逻辑器件。FPGA（现场可编程门阵列）凭借着灵活性、高集成度、低功耗等特点备受设计人员的瞩目。FPGA通常包含3类可编程资源：二维的可编程逻辑模块（Configuration logic blocks，CLB）、外围的输入输出模块（I/O Blocks，IOB）和可编程互联线资源（Interconnection Resource，IR）。

近年来，FPGA的结构也层出不穷，下列是几种用途比较广泛的结构：对称式、基于行结构、门海式及层次式等。对称型结构，又称为孤岛型结构，是用途最广泛的一种结构。岛型 FPGA 包含了行排和列排的逻辑单元 CLB，水平和垂直的布线通道包含不同长度的布线段。逻辑单元的引脚通过连接盒（Connection Box）连接到水平盒垂直布线通道中的线段上，这些线段再通过开关盒（Switch Box）以一定的方式互相连接。

在FPGA整体设计过程中，布局和布线是非常重要的两大部分，在布线阶段不能实现100%的布通率，需要返回去重新布局，直到完全可布，往返的过程会大大增加设计时间。因此，在布局阶段关注可布性，能够极大提高FPGA的设计效率。本文研究的重点就是在FPGA布局过程中让可布性问题得到更好的解决。

1 布局器介绍

本文的可布性优化策略均在解析式布局器[1]的基础上进行实验。使用最小线长目标，同时尽量减少模块间的重叠。问题表达为：

其中，HPWL（x，y）是所有模块总的半周长，Db（x，y）是密度公式，Mb是期望得到的每个网格里的平均密度。线长和密度公式都不可微，因此首先要对这两个函数进行平滑转换。

使用log-sum-exp方法来近似式（1）中非线性半周长线长。

采用钟形公式[3]来模拟密度部分：

用惩罚函数方法将线长目标和密度约束连接起来，这样，有限制的最优化问题就转化成为一个无约束的优化问题：

最后采用共轭梯度法进行求解。

2 基于线长模型的可布性优化算法

可布性驱动的FPGA布局算法有3方面的核心技术[2]：可布性评价标准、可布性预测和可布性优化。

2.1 可布性评价标准

可布性评价就是当布局完成后进行总体布线，然后根据总体布线结果评价布局结果的可布性。目前最常用的方法就是结合总线长和总体布线的拥挤度作为可布性的评价标准。

在岛型结构上实现布局算法，就是对CLBs进行放置以后，为了能够将电路芯片进行合理的连接运行，这需要了解开关盒资源的利用情况，因此拥挤度的研究将集中在开关盒（Switch Box）上。布线资源Se是一个固定值，根据芯片的技术参数如可用的布线层数、每一层的走线方向以及开关盒的尺寸来进行计算。布线需求De是穿过边开关盒线网的总数。当且仅当De大于Se时 ，即开关盒的布线资源使用量超出布线资源拥有量时，就出现布线拥挤的情况，此时布线溢出量（Overflow）大于零。对于一块FPGA芯片而言，总的布线溢出量可以用来评价一个已知布局的拥挤度情况。

2.2 可布性预测

可布性预测采用布线估计模型设计，布线估算模型主要分为两类：脱离线网拓扑结构模型（Topology-Free Modeling）和基于线网拓扑结构模型（Topology-Based Modeling）。

基于拓扑结构的布线模型一般采用斯坦纳树（Steiner Tree）结构对每个线网进行布线需求建模。但是在布线过程中，对网表中所有的线网建立ST树是一个较为复杂的过程。同时，每次布局更新操作中，布线路径都会发生变化，因此需要重新进行ST树的建立，这样将会引发大量的计算，因此该模型时间代价较高。先对部分网格预先计算好斯坦纳树，然后在布局过程中利用这些数据，这种方法可降低计算的复杂度。对于多端线网而言，增量式的A*tree算法，可以建立一个线性的斯坦纳树分支来支持增量更新，这样也可降低算法的计算量。脱离拓扑结构的布线模型在布局阶段不进行实际布线，只是根据某种策略估算布线需求，因此计算量小、速度快，但其精确性依赖于FPGA具体结构和估算策略。

2.3 可布性优化

可布性优化采用布线拥挤度方案选取的方法进行，布线模型完成后，在全局布线网格上可以得到一个布线拥挤度图（Congestion Map）。到目前为止，已研究出多种可布性的优化算法，如图1所示。

图1（a）代表了初始的预估布线拓扑结构。假设每个布线边缘的布线容量为1，那么它有3个水平边缘的溢出。假设每个pin点都在网格的中央，得到线网的总线长为11。图1（b）代表了单元膨胀的可布性优化算法。单元膨胀是将每个标准单元按固定比例的大小进行放大，等到下一次迭代过程，标准单元所占布局区域的比例就会更大，将标准单元体积缩小到正常大小时，它与其它标准单元之间的间隔就会增大。经过单元膨胀，水平边缘的溢出数量减少为2个，线长维持不变为11。单元膨胀策略被广泛应用于很多布局算法中，例如Ripple、SimPLR[3]、CRISP[4]等。CROP[5]布局算法介绍了一种基于权重的线长模型，能够有效减少线网边界框的大小，以此来控制布线拥挤。如图1（c）所示，它最终发生了两个水平边缘的溢出，线长的大小减少为6。TimberWolf布局算法提出了另一种基于权重的线长模型。为了更加全面地缓解布线拥挤，Jiang et al.[6]和 Chuang et al.[7]通过在全局布局中引入了一个拥挤度近似模型来移除线网边界框之间的重叠。如图1（d）所示，只有将线网边界框的重叠移除，才能有效地最小化布线拥挤。相比之下，Tsota et al.[8]将线长密度应用到解析式布局框架中。Hsu et al.[9]通过引入一个s-型方程减少布线拥挤，它是基于解析式布局的溢出改进算法。Hsu et al.[10]进一步提出了一个线网拥挤优化技术来分散这些线网边界框的密度，使其均匀地分布在整个布局区域来优化可布性。图1（e）最终的结果是0个溢出，单位长度为9。

本文提出了一种同时考虑水平溢出和垂直溢出的可布性驱动的线长模型，将其与解析式布局的目标函数相结合以优化布线拥挤和线长。如图1（f）所示，通过可布性驱动的线长模型，布局完成后的结果为0个溢出和5个单位长度的线长。对线长公式进行改进，可布性驱动线长的非线性公式被定义为：

其中，αe和βe分别代表了线网e的水平和垂直权重。为了准确地模型化水平和垂直布线拥挤的影响，定义水平和垂直的线网权重如下：

θy，e和θx，e分别代表了标准化的垂直和水平溢出。为了同时优化线长和可布性，αe和βe都由相同的可布性因素决定，其中一个增加，另一个则减小。而线网边界框形状的改变都要依靠标准化的水平和垂直溢出，这样可布性驱动的线长不会有明显改变。

这样，可以将log-sum-exp公式转变为如下形式：

然后使用共轭梯度法（CG）来解决这个无约束的最小化问题。

3 实验结果

FPGA全局布局流程程序使用C++编程语言在OA平台上实现，运行在使用Intel Xeon 3.0GHz CPU，6G内存的Linux服务器上。由于FPGA无太多测试用例，因而实验选取ISPD04 benchmarks[13]进行测试。

表1为本文布局器与基础布局器的实验结果对比，第1列为选取的ISPD2014的前12个例子，第2、3列为本文布局器的详细布局线长和占用内存，第4、5列为基础布局器的详细布局线长和占用内存，其中dpWL代表的是详细布局的线长，作为评价总线长的标准，单位为毫米（mm），CPU以时间为标准，单位为分（min）。表1的最后一行为本文布局器和基础布局器12个例子的平均线长，相比基础布局器，本文布局器的平均线长优化了14%，保证了在优化可布性的同时，布局线长也有所优化。

4 结语

本文实现了一个基于线长模型的FPGA可布性优化算法，它以孤岛型FPGA结构为依据，采用解析式布局器作为基础布局器，在优化大多数布局存在可布性问题的同时还能够优化线长。不仅在布线阶段解决了拥挤问题，且与解析式布局算法相比较，有更好的质量结果。实验证明了其结果的有效性和合理性。期望后续研究可以实现：可针对开关模块（Switch Box）提出拥挤度优化策略，根据可布性评价标准，在APlace框架的目标约束中增加可布性约束。

参考文献：

[1] 高文超，周强，吕勇强，等.应用于大规模FPGA的解析式布局算法[J].计算机辅助设计与图形学学报，2011（11）：19441948.

[2] 周全.详细布线可布性驱动的布局算法研究[D].北京：清华大学，2015.

[3] M C KIM，J HU，D J LEE，et al.A simplr method for routabilitydriven placement[C].In Proc.of ICCAD，2011：6773.

[4] J A ROY，N VISWANATHAN，G J NAM，et al.crisp：congestion reduction by iterated spreading during placement[C].In Proc.of ICCAD，2009：357362.

[5] Y ZHANG，C CHU CROP.Fast and effective congestion refinement of placement[C].In Proc.of ICCAD，2009：344350.

[6] Z W JIANG，B Y SU，Y W CHANG.Routabilitydriven analytical placement by net overlapping removal for largescale mixedsize designs[C].In Proc.of DAC，2008：167172.

[7] Y L CHUANG，G J NAM，C J ALPERT，et al.Designhierarchy aware mixedsize placement for routability optimization[C].In Proc.of ICCAD，2010：663668.

[8] K TSOTA，C KOH，V BALAKRISHNAN.Guiding global placement with wire density[C].In Proc.of ICCAD，2008：212217.

[9] M K HSU，S CHOU，T H LIN，et al.Routabilitydriven analytical placement for mixedsize circuit designs[C].In Proc.of ICCAD，2011：8084.

[10] M K HSU，Y F CHEN，C C HUANG，et al.Routabilitydriven placement for hierarchical mixedsize circuit designs[C].In Proc.of DAC，2013：16.

（責任编辑：孙 娟）