反熔丝FPGA布局算法

魏 岩

（中国电子科技集团公司第四十七研究所，沈阳110032）

反熔丝FPGA布局算法

魏 岩

（中国电子科技集团公司第四十七研究所，沈阳110032）

布局是大规模集成电路设计中非常重要的环节。在现场可编程门阵列（Field Programmable Gate Array，FPGA）的应用中，由于布线资源已经确定，所以FPGA的布局算法更加重要。针对反熔丝FPGA的布局应用，在目前最流行的布局算法上进行改进和优化很有必要。以建立高性能、低拥挤的布局为目标，从反熔丝FPGA芯片结构和布局算法两方面进行了深入研究。根据更精确的代价值计算，以及代价框模型和移动上限的改善，得到更有效的布局结果。反熔丝FPGA的布局算法需要新的代价值计算方法和计算公式。通过实验验证，改进后的反熔丝FPGA布局算法的布局结果更为合理，为下一步的布线工作展开建立了良好接口。

布局算法；反熔丝；现场可编程门阵列；模拟退火算法；行排列FPGA；代价值

1 引 言

目前，市场上有三种基本的FPGA编程技术：SRAM、Flash、反熔丝。其中反熔丝具有高抗干扰性和低功耗的优点，适用于要求高可靠性、高保密性的定型产品。学术界大都是针对孤岛型结构的SRAM的FPGA布局算法进行研究，对行排列的反熔丝FPGA的研究较为匮乏［1］。传统的布局算法应用在反熔丝FPGA时效率低、布局结果差，对布线造成较大压力。所以，需要在反熔丝FPGA的结构上，有针对性的对布局算法进行改进和优化。

2 反熔丝FPGA布局算法的设计和实现

2.1 基本布局算法模型

布局问题属于NP难题，想要找到较好的布局结果非常困难。目前典型的布局算法模型有：基于划分的布局算法、遗传算法、模拟退火布局算法等。其中，模拟退火算法［2-3］计算过程简单、通用，在增加新的优化目标或者约束方面方便得多。

2.2 反熔丝FPGA结构简介及传统布局算法面临的问题

有别于其它结构的FPGA，反熔丝FPGA的逻辑单元都是N输入、1输出的逻辑结构，而且反熔丝FPGA的结构是行排列的FPGA结构［4］。如图1所示。

由于这种特殊的结构，传统布局算法如果直接应用在反熔丝FPGA上则会造成水平线网资源浪费以及对多扇出线网预估不足的问题。

例如，在传统布局算法下，一根5扇出的线网在布局布线后可能会得到图2的结果。

图2 传统布局算法下1根5扇出的线网所占用的资源

可以看到，由于传统布局算法对反熔丝结构的预估不足，在这根5扇出的线网上使用了4根水平线和2根垂直线。对于反熔丝FPGA的结构来说，这样的布局结果在布线后会造成很大的线网资源浪费。

2.3 针对反熔丝FPGA布局算法的改进

布局算法在衡量布局结果是否合理时需要预估线网对布线资源产生的压力和代价。而在布局器预估代价值的大小时，建立了一个半周长线长模型［5］。半周长模型包含线网所有顶点的一个最小矩形称为边界框［6］。在反熔丝布局中，为了精确计算线网的代价值，分别计算水平方向和垂直方向的边界框线长：

普通模拟退火算法的代价函数计算公式抽象为：

其中，q（i）是补偿因子。这是因为当线网端点数目超过3时，边界框线长模型低估了所需要的连线［7］。bbx和bby分别代表水平、垂直方向代价框的值。

由于反熔丝和Flash系列的FPGA结构多为N输入、单输出的逻辑单元。在结构上鼓励由一个输出驱动的多个逻辑单元布局在同一水平排列上，并励电路尽量利用横向的布线资源。所以，修改代价函数计算公式如下：

其中，βx和βy分别是根据FPGA的水平、垂直方向的线网资源得到的针对水平方向和垂直方向的相对代价成本。fanout（i）是根据当前线网neti的扇出数做出的代价重视增益。也就是说在网表的代价计算时要更多的为多扇出的线网考虑，并降低横向布局成本，提高纵向布局成本。所述线网neti的代价值与fanout（i）成正比，与βx和βy成反比。

每次充分迭代后，根据新的布局代价评估重新计算温度、交换限制。交换限制的计算公式为：

percsucc是上一个温度下移动接受的百分比，根据实验得出：percsucc＝0.44是最佳移动接受率［8］，所以公式使用（1-0.44＋percsucc）可以找到最合适的交换限制。Cx和Cy代表水平和垂直方向的平均布线通道宽度，由于水平布线资源比垂直布线资源丰富，所以布局算法可以通过Cx和Cy来限制垂直方向的对交换，提高水平方向的调整速率。

通过上述有针对性的改进，在图2所示的同样的5扇出线网会有如图3中所示的改善：

图3 改进后的布局算法下1根5扇出的线网所占用的资源

如图3所示，同样的线网在布局算法改进之后只占用了2根水平线和1根垂直线，线网资源的利用率得到了明显改善。

2.4 测试与验证

为了对改进的布局算法进行验证，在基于反熔丝结构的FPGA芯片上（规模为100×30个逻辑单元）进行了测试。在布线器不做调整的前提下，测试不同的布局算法得到布局结果对布线器的影响。节选测试结果如表1所示。通过表1可以看到，基于改进的布局算法得到的布局结果对布线的压力明显减少。布线器能够更快的找到布线路径，也就是说改进的布局算法得到的布局结果更为合理。

表1 布局算法改进前后布局模块耗时对比

3 结束语

针对反熔丝FPGA的结构特点，对传统的FPGA布局算法进行改进。改进的布局算法通过测试表明，这些改进可以大幅提高布局质量，减少布线器的压力。

［1］ PEDRAM M，NOBANDEGANI B S，PREAS B T.Design and analysis of segmented routing channels for rowbased FPGA＇s［J］.IEEE Trans Computer-Aided Design Integr Circ＆Syst，1994，13（12）：1470-1479.

［2］ SHARMA A，HAUCK S，EBELING C.Architecture adaptive routability-driven placement for FPGAs［C］.//Int Conf Field Program Logic＆Appl，2005：427-432.

［3］ Sechen C.The Timber Wolf placement and routing package［J］.Solid-State Circuits，1985，21：510-522.

［4］ S Brown，R Francis，J Rose.Filed Programmable Gate Arrays［M］.Boston，Kluwer Academic Publishers，1992.

［5］ 洪先龙，严晓浪，乔长阁.超大规模集成电路布图理论与算法［M］.北京：科学出版社，1998.

Hong Xian long，Yan Xiao lang，Qiao Chang ge.Placement algorithm for Grand scale ic［M］.Beijing：Scientific Publishers，1998.

［6］ 王燕华.可布性驱动的层次式FPGA布局算法研究［D］.北京：华北电力大学，2008.

Wang Yan hua.Research of the Placement algorithm for Hierarchical FPGA［D］.Beijing：North China Electric Power University，2008.

［7］ KIRKPATRICK S，GELATT C D，VBCCHIM P.Optimization by simulated annealing［J］.Science，1983，220（4598）：671-678.

［8］ LAM J，DELOSME JM.Pedonmnce of a new anneling schedule［C］.//Proc 25th ACM/IEEE Des Autom Conf，1988：306-311.

Placement Algorithm s for Antifuse FPGA

Wei Yan
（The 47th Research Institute of China Electronics Technology Group Corporation，Shenyang 110032，China）

Placement is a very important part of Large Scale Integration Design.It＇s especially important on the application of Field Programmable GateWay（FPGA）as a result of the routing resource is fixed.It＇s necessary to improve algorithm to adapt for antifuse FPGA based on the most popular placement algorithm.Aiming at the higher performance and lower congestion，this article mainly focuses on the antifuse FPGA architecturemodel and related placement algorithm.The better placement result is found according to the exact cost and the improved bounding box and move limit.The placement algorithms of antifuse FPGA needs a new way to compute the cost and the corresponding mathematical model.The experimental results show that the improved algorithm ismore reasonable for antifuse FPGA and provides the better interface for the routing.

Placement algorithm；Antifuse；FPGA；Simulate Annealing algorithm；Row-style FPGA；Cost

10.3969/j.issn.1002-2279.2015.03.002

TN4

A

1002-2279（2015）03-0004-03

魏岩（1986-），男，辽宁省盘锦市人，助理工程师，主研方向：集成电路设计。

2015-01-15