接触fpga布线是从复位杯的比赛开始。但是比赛的问题和数据已经将布线问题高度抽象化为了一个数学问题。所以个人认为无法实际支撑fpga布线的研究，因为在读相关文献的时候常常有看不懂的地方。所以从现在起阅读并翻译《MAPPING AND FPGA GLOBAL ROUTING USING MEAN FIELD ANNEALING》第三章的内容。
有些部分因怕翻译有误所以也copy了原文。
 |
 |
|---|---|
FPGAs & Global Routing
- 介绍FPGA以及其物理设计的简要步骤
- 路由架构，global routing problem 以及 经典解决方案
- 对global routing problem 进行建模
1.Introduction to Field Programmable Gate Arrays
Field Programmable gate arrays (FPGAs)是新的电子可编程集成电路，具有高集成性和高速的周转时间。在VLSI设计自动化中，制造时间是一个比较重要的问题，为了减少制造互连的时间而引入可编程器件。
FPGA是ASIC设计市场中非常流行的可编程器件。FPGA可以减少制造周转时间和成本。在其最简单的形式中，FPGA由一个可编程逻辑块阵列和路由网络组成，以实现逻辑块的互连。可编程逻辑块可以由用户编程来实现一个小的逻辑功能。FPGA的一个重要特性是通过使用电子可编程的switches进行重新编程。商业的FPGA在 使用何种编程技术类型、 逻辑块的结构 和 路由结构 这几个方面有所不同。FPGA的逻辑块可以像晶体管一样简单，也可以像微处理器一样复杂。它通常能够实现许多不同的组合和顺序逻辑功能。FPGA的逻辑块可以分为晶体管对、基本的小门（如两个输入的NAND）、多路复用器和查找表。
1.1 Logic Blocks
FPGA的不同逻辑块在尺寸和能力上有很大的不同。两个晶体管逻辑块只能实现一个反相器，但尺寸非常小，而Xilinx FPGA中使用的查找表逻辑块(look-up table，LUT)可以实现任何五个输入的逻辑功能，但它们的尺寸明显较大。
逻辑块可以按照粒度进行分类。粒度可以用各种方式定义，例如，逻辑块可以实现的布尔函数的数量，相当于两个输入NAND门的数量，晶体管的总数，输入和输出的数量。但一般来说，商业逻辑块可以分为两类：细粒度和粗粒度。使用细粒度逻辑块的主要优点是可使用的块被充分利用，主要缺点是需要较多的线段和可编程switch。
1.2 Programming Technologies
FPGA是使用电子可编程开关进行编程的。根据这些可编程开关的特性，如导通电阻和电容，编程技术可分为三个主要类型。这三种类型是SRAM、antifuse 和 EPROM。
- SRAM编程技术使用静态的RAM cells去控制门和多路复用器。在SRAM中，switch是一个由一个SRAM位的状态来控制的导通的晶体管，故SRAM是易失性的。因此FPGA必须在芯片电源启动时及时加载和配置，它需要外部辅助的永久性存储提供编程位，比如PROM or EPROM. SRAM的优点是可快速重编程，最大的缺点就是占用面积大（实现个SRAM单元需要至少5个晶体管。）
- antifuse是一种具有非编程状态的，两端之间具有极高的电阻。当在端之间施加一个极高的电压，两端就会被打通产生低电阻连接，这种连接是持久性的。编程antifuse需要额外的电路来提供可编程的高电压和高电流。使得antifuse本身的体积很小但是，加上额外的电路就不那么小了。
- 浮动门编程技术使用一种特殊技术，该技术在紫外线可擦EPROM和电可擦EEPROM中被发现。EPROM的主要优点是快速可编程性。另外，他也不需要额外的持久性存储在芯片通电时对其进行编程。然而，这种技术的加工步骤更为复杂且需要更多的高祖晶体管。
1.3 路由结构
FPGA路由结构是对可编程switch和wiring segment的放置，以实现内部的编程性的逻辑互连。图3.1展示了一个典型的路由结构的模型。
一个wire segment是一条由可编程switch连接的线路，一条wire segment中可能会包含一个或多个switch。每个wire segment的末端都会附着一个switch。
- 一个 track 是形成一条线段的一条或多条wire segment的序列；
- 一个 routing channel 是一组平行的track。
图3.1中还包含着两种基础的结构：switch block和connection block。
- 一个switch block 提供水平和垂直线段之间的互连，当然也可以是水平与水平。
- 一个connection block在channel中提供逻辑块的输入和输出和wire segment的连接。
如图3.2所示，FPGA普遍拥有的两个重要的内部互连块。这些块内部的switch的数量对可路由性来说至关重要。switch数量越多路由选择就越多，但会影响路由质量和体积。
这些switch的数量及分布叫做FPGA的灵活性。switch block的灵活性记为$F_s$,connection block的灵活性记为$F_c$。$F_s$可以被定义为switch block提供给每个进入的wire segment的可以连接的总数。$F_c$可以被定义为channel中每个逻辑块可以连接的wire数。接下来展示两个商业FPGA的路由架构，它们分别来自Xilinx和Actel。
The Xilinx Routing Architecture
逻辑块通过connection_block与channel连接。由于使用的是SRAM编程技术所以连接点体积比较大，在 Xilinx 3000的$F_c$为2~3（有5条track通过block）。逻辑块的四个边上都有connection block，它们将不同的总共11个pin连接到wire segment。当pin被连接到水平或垂直的wire segment上之后，每个sire可以连接另一侧的15个可能的wire segment中的5~6个。Xilinx 3000的architecture提供了4种wire segment：
- General-purpose interconnect由通过switch block的wire segment组成。
- Direct interconnect 由逻辑块直接与相邻最近的邻居逻辑块之间的互连。
- Long lines，跨越芯片级的长度，提供high-fanout 均匀延迟连接。
- Clock line，是跨越整个芯片的单个线网，由高驱动缓冲器驱动。（没理解）。
The Actel Routing Architecture
Actel的路由结构是非对称式的，水平方向要比垂直方向有更多的track。Actel FPGA的输入和输出引脚的连接性是不同的。对于输入引脚，每个引脚可以连接对应这一侧的channel种的所有track，。而输出引脚横跨逻辑块上面2个channel和下面2个channel，它可以连接它跨过的这四个channel中包含的所有channel。在Actel中没有独立可分离的switch block。相对应的起到该功能的东西分布在整个水平的channel中。所有的垂直的track都可以与入射的水平track相连接。每个水平的channel由22个track组成，每个track可划分成不同长度的segment。垂直的segment共有3种类型：输入段，输出端，和通过整个芯片高度或者重要部分的freeway。这允许比输出端允许的垂直距离更长。
2 Physical Design Automation of FPGAs
FPGA的物理设计流程包含三个主要步骤：partitioning,placement and routing.
2.1 Partitioning
Partitioning is the separation of the logic into Logic blocks. Partitioning has both a logical and physical component. The connections within a logic blocks are constrained by the limited routing architecture and limited number of blocks outputs. However, the quality of the resulting partitioning depends on how well the placement can be done. The logical component has been investigated in the context of technology mapping in logic optimization.
Partitioning 就是将逻辑划分成逻辑块。分区同时拥有着逻辑组件和物理组件。逻辑块内的连接受到路由结构的限制和块输出的数量。但是最终分区质量取决于分区的好坏。逻辑组件在逻辑优化的技术优化背景下应运而生。
2.2 Placement
Placement starts with logic blocks and input-output blocks in partitioned netlist and decides which corresponding blocks on the chip should contain them. The FPGA placement problem is very similar to traditional standard cell and gate array placement problems. Many of existing algorithm placement algorithms are applicable, such as simulated annealing,force directed relaxation and min-cut.
Placement从逻辑块和位于分区线网表中的输入-输出块开始进行，并决定了他们应该对应在哪个芯片哪个的块上。FPGA placement问题与传统的单元和门阵列的布局问题相似。现有的很多布局算法，如模拟退火算法、强定向松弛算法、最小裁剪。
2.3 Routing
In general such a global router divides the multipoint nets into two terminal nets and routes them with minimumdistance path.
解决好所有电路的placement后，所有线网的每一个pin都必须连接。不同的FPGA结构有着不同的路由算法。FPGA的路由问题和standard cell和门阵列的设计一样复杂。FPGA路由可以分成：global routing and detailed routing。
The global route defines route for each connection by assigning it a sequence of channel segments. After the paths are defined in terms of channel between two-pin connection detailed router chose specific wiring segments to implement the channel segment assigned during global routing.
主流的Global router会把多端线网花分为一组双端线网，然后使用最短路径算法。同时也要考虑平衡channel的密度。全局路由从粗粒度层面通过给出一条channel segment 序列来为每一条连接大致规划出一条路径。在这条路径以channel的形式确定下来后，由详细路由选择具体的wire segment 来实现global routing阶段设计出的路径。
3. Global Routing Problem in Design Automation of FPGAs
全局路由为每个线网选择channel然后将具体的选择哪条wire segment 和 switch这种工作留给detailed router。全局路由为每个net决定哪些pin是真正需要被连接的。全局路由的最终目标是最小化channel密度之和。在许多研究中，FPGA中的路由问题都直接分配segment，而忽略了全局路由阶段。有一个独特的FPGA全局路由器：PGAroute.该路由器类似于standard cell的全局路由器，使用LocusRoute算法。
LocusRoute算法中，对每个多端线网执行以下三个步骤。
1) net的划分：用最小生成树算法将一个多端线网划分为一组双端线网。
2) Route Generation and Evaluation:在这一步中考虑每一对pin之间的可能路径，并根据cost来选择最低的那条。
选择路径的方法是基于那些有2个转弯或者更少的路径.Locus评估两个物理pin之间所有两个弯道路径的cost，选择最低的那条。cost函数由channel的密度来定义。每个wire segment和switch block 被表示为cost array中的元素。
每一个cost array $H_{i,j}$中的元素,包含着通过wire segment(i,j)的路径数量.
The cost of path(P) is calculated as:
3) Reconstruction：这一步将所有的双端网重新连接在一起，然后performs assigns unique numbers to distinct segments of some nets in each channel. 在每个channel中，执行分配唯一的数字在某些网的不同段。
Locus route利用迭代策略，即在第一次所有线网被路由之后，每个线网再依次被撕裂和重新路由。迭代减少了顺序依赖，提高路由质量。
4.Model of FPGA for Global Routing
商用的FPGA由以下部分组成：一个可编程逻辑块组成的规则的二维阵列（LB），一个可编程路由网络，switch boxes(SB)[3,1,2]. Logic blocks 被用来实现电路的功能；路由网络用来实现逻辑块和输入输出之间的连接。FPGA的路由网络包括wiring segment和connection blocks。基于FPGA的商业SRAM中，wiring segment可以分为三种类型（路由资源）：channel segments, long lines and direct-interconnection.水平(垂直)的channel segment 由若干平行wire segment组成，它们连接水平(垂直)channel中的两个连续的SB。SB允许这些channel segments彼此可编程互连。direct-interconnection是相邻LB之间的连接。long lines水平或竖直地穿过FPGA路由区域。connection block提供从LB的输入输出引脚到相应channel segments的wire segment的连接。每个引脚可以连接到一个通道中有限数量的wire segment上，这被称为connection block的灵活度。在本工作中，假设每个LB引脚可以连接到各自通道中的所有wire segment，把它作为我们的FPGA 模型的连接块。
direct-interconnections可以提供邻居LB之间的最小延迟的连接，long line在需要长距离传递信号是被使用（比如全局的时钟信号），这些路由资源在global routing中都没有被考虑到。因此我们关于的FPGA全局路由的模型只有可编程逻辑块（LB）,交换盒（SB）， channel segments。一个FPGA可以被建模为，二维的 由连接在水平和竖直channel segments中的LB组成的二维阵列，而SB则负责将水平和竖直的channel segments 连接在一起。
在本工作中我们使用最小生成树算法将多端线网划分为一组双端线网。故在此之后，文中提到的线网都指的是双端网。考虑一条双端曼哈顿距离为$dh+d_v$的线网，其中$d_h$和$d_v$分别代表水平距离和垂直距离。该线网的路由区域被限制在大小为$(d_h+1)×(d_v+1)$的LB网格，如下图a所示
然后该线网的最短距离可以被分解为三个独立的子网。该线网的每一个pin在最佳的路由区域只有一个邻居SB。所以，每一个pin都可以通过水平的或竖直的channel segment与他的相邻的SB相连接，就如上图所示。同时，这两个pin连接的SB之间的连接的最佳路由区域就限制在$(d_h+1)×(d_v+1)$的大小的网格中。基于这个事实，我们进一步将每个线网细分为三个双端子网，及LS,SS,SL(如上图b所示)。这里，LS和SL子网代表着 LB-to-SB和SB-to-LB的连接，SS子网代表着特定网络的SB-to-SB连接。因此我们只LS和SL这两种子网考虑2条可能的路径，为SS子网考虑吧$d_h+d_v-2$条可能的包含1个或2个转弯的路径。
我们定义一个FPGA图(L,S,C),它是一个P×Q的二维网格，L,S,C分别代表着LB,SB,channel segments.这里P和Q代表着FPGA中水平和垂直的通道数量。每个顶点$s{p,q}$代表着水平通道p和竖直通道q处的SB。网格中的每一个矩形单元$L{p,q}$代表着四面相邻着$s{p,q}$，$s{p,q+1}$，$s{p+1,q}$，$s{p+1,q+1}$的LB。边被标记为$c^{h}{pq}$($c^{v}{pq}$),对应夹在$s{p,q}$和$s{p,q+1}$($s{p+1,q}$)中间的channel segment。如下图所示：
全局路由问题为 寻找这些子网的路由的均匀分布 减少了搜索空间。路由的均匀分布有利于提高后续详细路由阶段寻找到可行路由的可能性。所以我们需要定义一个目标函数奖励balanced路由。因为我们前面讲到我们要避免区域性密度过高。将权重与边相关连以简化对给定路由结果的balance质量的计算。$w^{h}{pq}$($w^{v}{pq}$)代表$c^{h}{pq}$($c^{v}{pq}$)上的权重，意义是channel segment. 上的权重。通过这种模型，我们可以通过下面的公式来表示给定一条路由结果的balance质量：
公式中，每个channel segment将其密度的平方贡献给目标函数，从而惩罚不平衡的路由分布。因此全局路由问题就是最小化上式。
MFA SOLUTION FOR GLOBAL ROUTING IN FPGA
待续。。。。。。