集成电路EDA 课件6.2 第6章 布局布线理论

集成电路EDA物理设计——布局布线学习目标认识什么布局布线了解布局布线的重要性了解布局布线算法的分类1集成电路布局布线简介

PhysicalDesignviaPlace-and-Route:RTLtoGDS通过物理设计布局布线：从RTL

到GDSVLSI设计流程VLSI设计StylesCommondigitalcells常见的数字单元VLSI设计Styles标准单元版图（Standardcelllayout）带有馈通单元（feedthroughcell）标准单元版图使用over-the-cell（OTC）布线VLSI设计Styles使用宏单元格的布局（Layoutwithmacrocells）VLSI设计Styles具有外部连接的反向器单元的版图层。版图（Layout）层与设计规则（DesignRules）设计规则的类别:尺寸规则、

分隔规则、

重叠规则。版图（Layout）层与设计规则（DesignRules）物理设计优化约束类型•技术约束：允许为特定技术节点进行制造，并且源自技术限制。•电气约束：可确保设计所需的电气行为。•几何（设计方法）约束：降低总体设计过程的复杂性。算法和复杂性其中许多问题是NP-hard（NP：non-deterministicpolynomialtime）——没有已知的算法可以确保以省时的方式实现全局最优解。⇒启发式算法用于查找近乎最优的解决方案。启发式算法确定性：算法做出的所有决定都是可重复的，即不是随机的。确定性启发式的一个例子就是Dijkstra的最短路径算法。随机：算法的某些决定是随机做出的。就结构而言，启发式算法可以是：——构造性：启发式算法从一个初始的、不完整的（部分）解决方案开始，然后添加组件，直到得到一个完整的解决方案。——迭代式：启发式算法以一个完整的解决方案为起点，反复改进当前解决方案，直到达到预设的终止条件。常见EDA术语NetlistPin-OrientedNetlistNet-OrientedNetlistConnectivitygraph常见EDA术语Connectivitymatrix常见EDA术语常见EDA术语RTL回顾（物理设计前需要完成）代表寄存器传输级。数字电路的抽象，包括：组合逻辑、寄存器、模块（分层和“黑盒”——如模拟宏、SRAM宏等）和端口/网络。用硬件描述语言(HDL)描述。硬件描述语言（HDL）HDL是一种使用RTL抽象描述电路的语言。通用HDL：Verilog、VHDL。研究型HDL：FIRRTL、CoreIR。moduleadd_one:inputclock:Clockinputreset:UIntoutputio:{flipin:UInt,out:UInt}io.out<=tail(add(io.in,UInt("h01")),1)RTLinAction(FIRRTL)circuitHelperDelayedAdd2:moduleHelperDelayedAdd2:inputclock:Clockinputreset:UIntoutputio:{flipin:UInt,out:UInt}Module/portdescriptionregmy_reg:UInt,clockmy_reg<=tail(add(io.in,UInt("h01")),1)io.out<=tail(add(my_reg,UInt("h01")),1)Registers/state(Combinational)logicRTLinAction(Verilog)moduleHelperDelayedAdd2(inputclock,inputreset,input[3:0]in,output[3:0]out);reg[3:0]my_reg;always@(posedgeclock)beginmy_reg<=in+4’h1;endassignout=my_reg+4’h1;endmoduleRegisters/state(Combinational)logicModule/portdescriptionRTL设计只是一部分是什么导致创建硬件困难重重？是什么让设计周期变得漫长而昂贵？架构设计空间探索。RTL开发。物理设计与实现。验证——是否正确？验证——要解决的问题正确吗？编译器和生成器。拥有可靠、可重复使用且功能强大的工具是重中之重。BAG、Chisel等。物理设计为何重要自动P&R并非完全自动!?你是想告诉我先进工艺节点有些EDA软件支持先进工艺节点，但是工艺进步增加物理设计自动化的难度。物理设计很难——CAD工具不是自动的敏捷RTL受非敏捷物理设计的拖累（AgileRTLisslowedbynon-AgilePhysicalDesign）题外话：为什么要进行敏捷物理设计？1.模拟/混合信号(AMS)系统。2.提高可用性，实现更快的设计空间探索。3.技术可移植性。4.分层设计。BigPicture概述（简化）RTL、原理图、时序和Layout视图之间的交互综合Synthesis●将RTL（Verilog）映射到综合后网表（结构Verilog）。●标准cells具有不同的尺寸和驱动强度。●综合工具使用前面提到的约束来适当地选择标准单元。●Synthesis还将执行优化以简化RTL。moduleadder(input[1:0]a,input[1:0]b,output[1:0]c);assignc=a+b;endmodule综合的例子平面规划Floorplanning●回想一下：RTL说要放什么（logic、state、macros），但没有说放在哪里。●Floorplanning是指定放置约束的艺术。●放置约束的主要类型：○芯片大小——告诉布局布线工具芯片有多大以及有多少填充。○模块放置——告诉布局布线工具将来自某个模块的单元放在某个边界内。○宏放置——告诉布局布线工具将宏放置在哪里（例如模拟模块、SRAM等）。●数字布局通常使用标准单元格。●标准单元是CMOS逻辑门的晶体管级实现。●标准cell的典型结构包括电源/接地轨和引脚。标准单元版图（StandardCellLayout）●通过将标准单元格彼此相邻放置，将它们组合到轨道中的布局中。●信号在标准单元上方的层中路由。●电源通过电源计划（例如电网和过孔）路由到电源轨（vdd和gnd）。●每一行通常是镜像的（vdd->gnd、gnd->vdd等）。●重叠轨道，而不是相邻轨道。标准单元版图（StandardCellLayout）布局规划的其他方面●电源规划Powerplanning——定义芯片的电源策略。例如，芯片的电源计划可能涉及在每一层为VDD和GND创建网格。●分接单元Tapcells——技术要求衬底/体“分接”到已知电压。存在执行此实体敲击的标准单元。一些stdcell架构带有内置tap。●填充单元Fillercells——为了满足密度要求，必须填充未使用的空间，通常使用decap。平面图可视化（Visualization）

例子MacroCompiler（宏编译器）SRAM宏实现Flip-flop实现默认情况下，这些memory会编译成标准的cellflip-flops，与SRAM宏相比，这对于实现memos来说非常低效。例：放置和布线(PlaceandRoute)●给定综合后网表和布局规划/物理设计约束，通过在芯片上放置标准单元并创建在不同单元之间布线的导线来创建物理布局。●执行标准单元放置和布线，同时遵守布局规划/物理设计约束和到宏（例如模拟宏、SRAMs）的布线。●最终结果是可以发送到晶圆厂的GDS文件。设计规则检查DRC●设计规则检查（DRC）是检查GDS文件中的几何图形是否遵循晶圆厂给出的规则的过程。●数字标准单元布局仍必须遵守设计规则。●当设计/布局集成在一起时，经常会发生错误。●先进技术中的DRC规则极其复杂且令人困惑。布局与原理图（LVS）●布局与原理图（LVS）是检查几何图形/布局是否与原理图/网表匹配的过程。●EDA工具可以导出用于数字设计的网表。●当模块集成在一起时，经常会出现LVS错误。●他们令人困惑，因为短网(shortednet)可能会弄乱整个检查！验证Verification●可以在post-synthesis和post-place与routenetlist（RTL）上运行仿真，以检查系统是否仍然按预期运行。●在工业中使用时序注释来运行这些检查，以便不会违反建立和保持时间。VLSI物理设计：从图形分区到时序收敛

•IC布局必须满足几何约束和时序约束。

•芯片设计人员必须完成时序收敛。VLSI物理设计：从图形分区到时序收敛介绍时序收敛：

•时序驱动布局（Timingdrivenplacement）最大限度地减少信号延迟：将位置指定给电路元素时。

•时序驱动布线（Timingdrivenrouting）最大限度地减少信号延迟：选择路由拓扑和特定路由时。

•物理综合（Physicalsynthesis）通过更改netlist来改进时序。−晶体管或门的尺寸：增加晶体管的宽长比，减少Delay或增加Gate的驱动强度。−将缓冲区插入网络以减少传播延迟。−沿关键路径重构电路。

•性能驱动（Performancedriven）的物理设计流程。

时序优化（Timingoptimization）engines必须快速准确地估计电路延迟改进电路时序。

时序优化器通过电路组件调整传播延迟，主要目标是满足时序约束，包括：−设置（长路径）约束，用于指定数据输入信号的时间量在每个存储元件的clockedge之前应该是stable(steady)。−Holdtime（shortpath）约束，用于指定数据输入的时间量信号在每个存储元件的clockedge之后应该是稳定stable。介绍•Timingclosure：满足时序约束的过程通过布局优化和网表修改。•行业术语：“设计具有闭合时序”（thedesignhasclosedtiming）。介绍时序分析（TimingAnalysis）和

性能约束（PerformanceConstraint）时序电路，在时间上“展开”。

•时序电路中的主要延迟问题：−门延迟（Gatedelays）是由于门转换造成的。−线路延迟（Wiredelays）是由于信号沿线路传播造成的。−时钟偏移（Clockskew）是由于顺序元素激活的时间差异。•需要快速估计时序电路时序：−执行静态时序分析（statictiminganalysis，STA）。−假设clockskew可以忽略不计，推迟到clocknetwork综合之后。时序分析（TimingAnalysis）和

性能约束（PerformanceConstraint）STA：假设每个门转换的最坏情况。

•给定组合电路，表示为有向无环图（DAG）。−每条边（节点）都有权重

=线（门）延迟。

•计算每个节点的slack

=RAT–AAT。−RAT为需要的到达时间，最晚信号可以转换时间。−AAT为实际到达时间，最晚可能的过渡时间。−按照惯例，AAT在每个节点的输出端定义。⇒任何输出的负slack都意味着电路不符合时序要求。⇒所有输出均具有正slack，这意味着电路满足时序要求。静态时序分析组合电路作为DAG。静态时序分析计算每个节点的AATs：其中FI(v)是faninnodes，t(u,v)是u和v之间的延迟（AATsofinputsaregiven）。静态时序分析计算每个节点的RAT：静态时序分析其中FO(v)是fanoutnodes，t(u,v)是u和v之间的延迟(RATsofoutputsaregiven)。在每个节点计算slacks:静态时序分析使用Zero-Slack算法延迟预算

•建立网络的时序预算。−在时序驱动版图设计期间，必须优化Gate和Wire延迟。−Wire延迟取决于线长。−在放置和布线后才知道导线长度。

•使用zero-slack算法延迟预算。−设vi

为逻辑门。−设ei

为网。−设DELAY(v）和DELAY(e)分别为门和网的延迟。−定义门控的时序预算TB(v)

=DELAY(v)+DELAY(e)。使用Zero-Slack算法延迟预算使用Zero-Slack算法延迟预算使用Zero-Slack算法延迟预算时序驱动放置（Timing-DrivenPlacement）时序驱动布局优化电路延迟。•设T是所有计时端点的集合。•电路延迟由最差负裕量（worstnegativeslack，WNS）

•或总负slack（totalnegativeslack，TNS）•分类：net-based、path-based、integrated。Net-Based技术Netweights被加到每一个net–placer优化weightedwirelength。

Staticnetweights:placement之前计算

（不改变）。−Discretenetweights:−Continuousnetweights:−BasedonnetsensitivitytoTNSandslack其中t是最长路径延迟，α是临界指数。其中Dynamicnetweights:在放置（placement）期间（重新）计算。−估计每次迭代的slack时间：其中L是线长的变化。−更新净临界度（netcriticality）：IF在关键网络排名前3%−更新净权重（netweight）：变化包括每j次迭代更新一次、不同的关系临界度和净权重之间。Net-Based技术

将STA嵌入到线性规划中以进行放置(Placement)•构造一组用于时序驱动放置的约束。−物理约束定义单元的位置。−TimingConstraints定义slack要求。

•优化需要优化的目标。−改善最差负slack（WNS）。−改善总负slack（TNS）。−改进WNS和TNS的组合。对于物理约束，设：

和

为单元V的中心v∈V。

是连接到网络e的单元集e∈E。

left(e)、right(e)、bottom(e)

和top(e)

分别为e的边界框的左、右、下和上边界的坐标。

和

是连接到e的V引脚相对于和

的引脚偏移量。

将STA嵌入到线性规划中以进行放置(Placement)定义e的半周长线长（Halfperimeterwirelength，HPWL）：然后，对于所有v∈Ve：

将STA嵌入到线性规划中以进行放置(Placement)•对于时序约束，设：−为单元v从输入引脚vi到输出引脚vo

的门延迟。−

为净e从单元U的输出引脚uo

到单元V的输入引脚vi

的延迟。−

是单元格v的引脚j的到达时间。

将STA嵌入到线性规划中以进行放置(Placement)对于单元v的每个输入引脚vi：

将STA嵌入到线性规划中以进行放置(Placement)对于单元v的每个输出引脚vo：对于顺序单元τ中的每个引脚τp：确保每个slack（τp）≤0针对总负slack进行优化：

将STA嵌入到线性规划中以进行放置(Placement)针对最差的负slack进行优化：针对TNS和WNS进行优化：时序驱动布线(Timing-DrivenRouting)•时序驱动布线力求最小化：−最大sink延迟：从源极到网络中任何sink的延迟。−总线长：网络的布线长度。

•对于信号网络，设：−s0

为源（source）节点。−sinks={s1，...，sn}是sinks−G=（V，E）为相应的加权图（weightedgraph），其中：−V={v0，v1，...，vn}表示net的source和sink节点，−边的权重e（vi，vj）∈E表示vi

和vj之间的布线成本。•对于超过G的任何生成树(spanningtree)T，设：−radius(T）为最长source-sink路径的长度，单位为T。−cost(T）为T的总边权重（weigh）。

•在“shallow”树和“light”树之间进行权衡。

•“shallow”树具有最小半径。−Shortest-paths树。−由Dijkstra算法构建。

•“light”树的成本最低。−最小生成树（Minimumspanningtree，MST）。−由Prim算法构造。时序驱动布线(Timing-DrivenRouting)时序驱动布线(Timing-DrivenRouting)Bounded-Radius，Bounded-Cost算法•通过设置两者的上限来权衡半径和成本。•在bounded-radius中，bounded-cost（BRBC）算法中，让：−TS

成为最短路径树。−TM成为最小生成树。•TBRBC是使用满足以下条件的参数ε构建的树：•当ε=0时，TBRBC具有最小半径。•当ε=∞时，TBRBC的成本最低。Prim-Dijkstra权衡（Tradeoff）基于Prim算法和Dijkstra算法的Prim-Dijkstra权衡。•从汇集sinksS中，根据不同的成本函数迭代添加sinks。−Prim算法成本函数：−Dijkstra算法成本函数：

−Prim-Dijkstra权衡成本函数：•γ是介于0和1之间的常数。Prim-Dijkstra权衡（Tradeoff）将Source-to-Sink延迟降至最低•通过添加sinks迭代形成树，并针对关键sink(s)进行优化。•在关键sink路由树（criticalsinkroutingtree,CSRT）问题中，最小化：其中α(i)是接收器si的接收器关键性，t(s0,si

)是从s0到si的延迟。•在criticalsinkSteiner树问题中，构造一个除最关键的sinksc

之外的所有sinks的最低成本SteinertreeT。•通过以下方式添加关键的sink：−H0：从sc

到s0

的单线。

−H1：可以将sc

连接到T的最短导线，只要路径从s0

到sc

是尽可能短的总长度。−HBest：尝试从sc

到T中的edges，从sc

到s0

的所有最短连接。对这些树中的每一个执行时序分析，然后选择SC

延迟最低的一个。将Source-to-Sink延迟降至最低PhysicalsynthesisPhysicalsynthesis是一组timingoptimization，用于修复负slack。•包括创建时序预算和执行时序校正。

•时间预算包括：−沿路径或网络分配目标延迟。−通常在布局和布线阶段。−也可以在时序校正操作期间进行。

•时序校正包括：−门尺寸。−缓冲器插入。−网表重构。门尺寸设一个门v有3个尺寸A、B、C，其中：

•栅极尺寸较大，输出电阻较低。

•负载电容较大时：

•栅极尺寸越小，输出电阻越高。

•负载电容较小时：门尺寸门尺寸缓冲器Buffering缓冲器：两个串联反相器。•减少延迟（Improvedelays），通过：−加快电路速度或用作延迟元件。−转换时间的变化。−屏蔽电容负载。•缺点：−增加面积usage。−功耗增加。缓冲器Buffering网表重构（NetlistRestructuring）•网表重构仅更改现有门，不改变功能。

•更改包括：−克隆：复制门。−重新设计fanin或fanout树：改变门的拓扑结构。−交换通信引脚：更改连接。−门分解：例如，将AND-OR更改为NAND-NAND。−布尔重构：例如，应用布尔定律来改变电路门。

•还可以对上述内容进行反向转换，例如缩小大小、合并。网表重构（NetlistRestructuring）网表重构（NetlistRestructuring）网表重构（NetlistRestructuring）网表重构（NetlistRestructuring）网表重构（NetlistRestructuring）网表重构（NetlistRestructuring）性能驱动（Performance-Driven）的设计流程基准物理设计流程：1.布局规划、I/O布局、电源规划。2.逻辑综合和技术映射。3.全局布局和顺序元素合法化。4.时钟网络综合。5.全局路由和层分配。6.拥塞驱动的详细布局和合法化。7.详细布线。8.制造、电气验证和掩模生成。性能驱动（Performance-Driven）的设计流程性能驱动（Performance-Driven）的设计流程性能驱动（Performance-Driven）的设计流程性能驱动（Performance-Driven）的设计流程性能驱动（Performance-Driven）的设计流程性能驱动（Performance-Driven）的设计流程性能驱动（Performance-Driven）的设计流程性能驱动（Performance-Driven）的设计流程性能驱动（Performance-Driven）的设计流程时序约束与时序分析小结

TimingConstraintsandTimingAnalysis

•电路延迟是在信号路径上测量的。−从初级输入到sequential元件;从sequentials输出到主输出。−从sequentials到sequentials。

•路径延迟的组成部分。−门延迟：高估每个门的最坏情况转换（以确保快速的StaticTimingAnalysis）。−导线延迟：取决于导线长度和（对于具有>2个引脚的网络）拓扑结构。

时序约束与时序分析小结

TimingConstraintsandTimingAnalysis•时序约束−sequentials主输入和输出引脚的实际到达时间（Actualarrivaltimes，AAT）。−sequentials主输出和输入引脚所需的到达时间（Requiredarrivaltimes，RAT）。

•静态时序分析−两个线性时间遍历计算每个门（和网）的AAT和RAT。−在每个时间点：slack=RATAAT。−负裕量（slack）=时序违规；关键网络/门是具有负裕量的网络/门。

•时间预算：将规定的电路延迟划分为净延迟范围。时序驱动布局（Timing-DrivenPlacement）小结•门/单元位置会影响导线长度，从而影响网络延迟。

•时序驱动布局优化门/单元位置以改善时序。−与时序分析交互以识别关键网络，然后biases

placementopt。−总线长也必须保持较低，否则布线将失败。−时序优化可能会增加routing拥塞。

•按净加权布局。−时序驱动布局的Theleastinvasivetechnique（侵入性最小的技术）

。−执行tentativeplacement，然后根据timinganalysis更改netweight。

•按净预算布局−为每个网络分配延迟边界；将延迟边界转换为长度边界。−根据单个网络的长度约束执行布局。

•基于线性规划的布局。−布局被cast为方程组和不等式。−时序分析和优化使用额外的不等式进行合并。时序驱动布局（Timing-DrivenPlacement）小结定时驱动有几个方面

-单个网络：将较长的导线换成较短的source到sink路径。-耦合电容和信号完整性：平行导线充当电容器会减慢/加快信号转换速度。全网表优化：优先优化应首先优化的网。

单个网络优化

-一个极端：独立路由每个源-汇（source到sink）路径（高线长）。

-另一个极端：使用最小生成树（低线长、高延迟）。

-可调整的权衡：Prim算法和Dijkstra算法的混合算法。

时序驱动布线（Routing）小结耦合电容和信号完整性

-并行导线只有在同时转换时才值得关注。

-识别关键网络，将相邻导线推远以限制串扰。全网表优化

-运行试验路由，然后运行时序分析以确定关键网络。

-然后进行相应调整，重复操作直至收敛。时序驱动布线（Routing）小结物理综合（PhysicalSynthesis）小结•传统上，在已知网表后执行布局与布线

，然而，尽早修复门尺寸和网络拓扑并不能考虑布局感知时序分析。−门位置和网络路由不可用。•物理综合使用来自试验布局的信息来修改网表。•网络缓冲：将网络分成更小（大约相等长度）的段-长网络具有高电容，驱动器可能太弱。•门/缓冲器尺寸大小：增加缓冲器器强度和门的物理大小。−大门具有较高的输入引脚电容，但较小的驱动器电阻-较大的门可以驱动更大的扇出、更长的网络;更快的传输−大门需要更多空间，更大的上游驱动器•门克隆：分割大扇出−克隆的门可以单独放置，这与单个较大的门不同。VLSI布局布线是一项复杂而重要的任务，通常需要使用专业的EDA工具来辅助完成，它直接决定了芯片的性能和可靠性。首先进行布局。布局是指在一定尺寸的芯片上安排各种元件的位置。布局的目标是最小化电路的面积，并提供良好的信号传输和电源供应。接下来是布线。布线则是将各个元件连接起来，形成完整的电路系统。布线的目标是最小化信号延迟和功耗，并确保信号传输的可靠性和稳定性。集成电路布局布线简介学习布局布线的必要性VLSI布局布线的设计与优化在集成电路芯片设计过程中必不可少，并且随着半导体工艺尺寸不断缩小，物理优化越来越突出，用于VLSI的EDA工具也必须随之不断更新。EDA软件用户需要在使用布局布线工具的时候深入理解相关的数学模型和方法。布线工具ICC布线工具ICCII大规模集成电路布局布线的关键技术和方法1.自动化布局布线工具这些工具通常会利用算法和人工智能技术，自动寻找最佳的布局方案和布线路径。2.信号完整性分析为了保证电路的稳定性和可靠性，需要对信号传输过程中的完整性进行分析。3.高密度互连技术随着集成电路的规模越来越大，高密度互连技术变得越来越重要。这种技术可以大大提高集成电路的性能。芯片设计总流程及物理设计主要步骤大规模集成电路布局布线的基本步骤

1．布局首先，需要确定每个元件在芯片上的位置。这需要考虑到元件的大小、形状、互连性等因素，并尽可能地减小它们之间的距离，以便减少信号传输延迟。2．划分网格然后，需要将芯片划分为多个网格，每个网格都有固定的宽度和高度。这样可以使布局更有序，方便后续的布线操作。3．绘制时序图接着，需要绘制出元件之间的时序关系图，以确保信号能够按照预定的时间顺序进行传输。4．连接元件最后，需要使用导线将各个元件连接起来，形成完整的电路系统。在这个过程中，需要注意避免导线交叉和过长等问题，以保证电路的可靠性和稳定性。自顶向下基于划分的布局过程示例布线一般分为总体布线和详细布线两个流程。物理设计时，一般会先将整个电路划分为多个子模块（划分），对子模块的设计称为布图规划，此后人们将子模块具体分配到整个电路板的具体位置上，这一步为布局，布局后便是布线，一般先进行总体布线（GlobalRouting,GR），将布线资源分配到各模块，后进行详细布线（DetailedRouting,DR），将互连线分配到具体的金属层和位置。物理设计过程是EDA（电子设计自动化）的主要处理对象，是人工最易出错的部分。大规模集成电路布局布线的基本步骤全局布线线段（虚线）与iroute（实线）2顺序与并行路由模型

由于路由的复杂性，路由分两步进行：全局路由和详细路由。在全局路由阶段，网的拓扑结构和他们的相应位置相对于作为路由障碍的对象被确定。详细布线的复杂程度取决于几个因素，如引脚位置，布线区域的形状，和它的能力进行改进，以适应布线。顺序与并行路由模型简介2.1优化的标准

所有路由的首要目标是达到100%布线，满足所有的设计规则。1.面积：对于标准单元格和自定义布局，主要目标是最大限度地减少所需的整体布局面积。2.总线长：信号延迟与线长成正比。3.可路由性：这里的目标是在整个芯片上均匀地分布网，以确保最大的可路由性。4.过孔成本：每一层的变化都与一个过孔的成本相关联。5.串扰：这表示相邻导线之间不必要的耦合效应。6.偏斜最小化：这对于类似时钟的高扇出高速信号是必要的。不幸的是，这些因素中有许多是相互直接冲突的。2.2基于布线约束的布线模型

路由器也可以根据使用的层数和这些层上允许的布线方向来区分（图1）：1.平面模型2.曼哈顿模型3.敲膝模型4.无网格模型5.多层模型图1常用路由模型示意图（a）平面模型（b）曼哈顿模式（两层）（c）膝关节模型（d）无网络模型（具有可变宽度导线和不均匀间距规则）（e）多层模型（三层无限制

重叠模型）撞膝588751.基于图的路由器

；2.基于人工智能的方法；3.整数规划方法；4.组合优化技术5.计算几何启发技术。2.3算法模型3分块（Partitioning）的介绍

分块介绍一个大规模电路，在进行布局布线之前，往往需要对有些部分进行分块，将电路分成更小的模块可以有效的降低设计的复杂度。为什么要分块？答:1)这样能简化设计，让各个模块各自设计。2)受到芯片大小的限制。比如某个小元件上只能布置8个门电路，那么就要把网络分块成大小不大于8的小块。2.分块的目标?答：在块大小，引脚数等限制条件下尽量使块和块之间连接减少。因为太多的连接意味着更长的延时和更高的出错的可能性。分块的例子如果有两块小芯片各自可以刻录4个逻辑门电路，那么第一种设计方案就优于第二种，因为第一种两个模块之间只用连两条线，第二种需要四条。名词术语1.Cell即元胞。如图2中的圆形a-f。2.Partition即划分。如图2中的A与B。3.多元k-way-partition即k路划分。4.对于一个图G(V,E)area(v)指相应模块面积，W(e)指的是边e的优先级。图2割线5.Disjoint指的是一个图已经应分尽分了，每个点都属于且仅属于一个子集。6.如果一个边e的两端分属于两个子集，则称之为cut。7.超图（hypergraph）指图中某些线进行了合并，即一个"net"能连接三个以上的Cell。图3是一个简单例子。8.3.1名词术语图3超图例子Multigraph（多重图）3.1名词术语Hypergraph（超图）Graph（图）Directedgraphswithcycles带循环的有向图Directedacyclicgraph有向无环图3.1名词术语Undirectedgraphwithmaximumnodedegree3最大节点阶数为3的无向图Directedtree有向树8.3.1名词术语Rectilinearminimumspanningtree(RMST)RectilinearSteinerminimumtree(RSMT)3.1名词术语KL(Kernighan-Lin)算法

分块算法是一个难题，没法直接在多项式时间内获得最优解。KL算法是通过迭代改进进行划分，用于求解所有节点都有相同权重的二分图。KL算法的核心思想是交换。先把所要研究的元胞分成两组，在两组中各自找一个节点，把这一对节点进行交换，交换前后比较一下是不是能减少割线权重。【例1】如图2，若要把e从B集合移动到A集合，割线数目怎么变化？解：(e,f)不再是割线，但是(d,e),(g,e)和(c,e)成了割线，所以割线数目增加了两条。

交换一对分属于两个子集的a,b两点的增益定义为△g(a,b)，即该节点交换前后所引起割边代价的变化。如果这两个点的换集合的过程不独立的话（a与b之间存在一条边），a与b之间连线的权重显然被多算了两次，要减掉。

△g(a,b)=D(a)+D(b)-2c(a,b)

交换完的两个点先固定，这样重复多次直到全部点被固定。前m步每次交换的增益加起来就是前m步的总增益。最大增益Gm为给定轮次中，进行m次交换的最好结果。需要注意的是，交换过程中△g不一定每一步都一直为正，在某个轮次为负，但是由于其他移动增益可以对其进行补偿，因此整个轮次是完整的。【例2】KL算法

条件：如图节点a-h的初始化分。任务：执行KL算法。解：初始割边代价=9。计算所有自由节点a-h的代价D(v)。D(a)=1，D(b)=1，D(c)=2，D(d)=1，D(e)=1，D(f)=2，D(g)=1，D(h)=1△g1=D(c)+D(e)-2c(c,e)=2+1-0=3交换并锁定节点c和e。acebdfghaecbdfgh更新所有连接到最新交换节点c和e的自由节点(a,b,c,d,e,f,g,h)的代价D(v)。D(a)=-1，D(b)=-1，D(d)=3，D(f)=2，D(g)=-1，D(h)=-1△g2=D(d)+D(f)-2c(d,f)=3+2-0=5交换并锁定节点d和f。以此类推，交换并锁定节点a和g。△g3=-6交换并锁定节点b和h。△g4=-2当m=2，时，Gm=8。KL算法并不是总能得到最优解。【例2】KL算法

aecbfdghKL(Kernighan-Lin)算法的伪码与例子：3.3

FM算法的移动选择和KL很类似，目标是将割代价最小化。但是一次只需要挪动一个点。需要注意的是，FM需要引入一个比例因子来对两个划分进行平衡，防止所有的元胞挪到一个部分。FM(Fiduccia-Mattheyses)算法不同于KL算法，FM算法的增益算的是单个点。每次移动节点前要计算所有节点的增益，取增益最大的节点进行挪动，挪到所有节点都固定为止。和KL算法一样，FM算法也是计算从1到最后一步每一步的Gm，即增益累加值，取Gm值最大的步数进行交换。FM算法可以得到解的质量和运行时间很好的折中。它的技术速度较快，但是当一个超图中“net”(即hyper-graph中连了多个点的边)连接了不只数百个节点时，FM可能会较低效。为了提高划分网表的可拓展性，FM算法被嵌入到一个多级架构中。对于具有成千上万门电路，可以先将节点结群以减少点数，应用FM算法，再拆点，再使用FM算法往复循环。FM(Fiduccia-Mattheyses)算法FM算法例子FM算法例子（续）FM(Fiduccia-Mattheyses)算法为了构建一个粗粒度网表，连接紧密的节点被结群，如图所示。多极划分技术从粗粒度阶段开始，初始原图被粗粒度化几个等级，粗粒度化后，在最粗粒度图中找到一种启发式划分，找到的划分会分到下一级粗粒度图上并细化。转换和细化会持续到原始图的划分分解被找到。4芯片的规划

芯片的分块（也叫分区）与芯片规划这两部分非常重要，将会极大地影响后续的设计。芯片规划主要包括三个阶段①布局规划②引脚分配③电源规划布局规划输入为已经初步确定大小或形状的各个模块，模块的来源可能来自于门级或RTL级网表的自动划分，或者从层次化设计中提取。引脚分配(I/Oplacement)能布置输入输出引脚的位置(inputandoutputpads)。电源规划旨在给每个模块连接到电源网（包括地线网）络上。芯片规划4.1布局规划的目标

1.边界框的面积和形状：布局规划的全局边界框包括所有模块的最小的矩形。2.总的布线长度：过长的布线长度会影响信号延时、能量损耗以及制造成本。3.面积与线长的混合优化：对于面积和线长都要考虑的情况下，可以用加权平均的方式生成优化目标。4.信号延迟：目前，延迟的时间主要集中在模块之间的互连上。4.2布局规划的划分

1.矩形划分(rectangulardissection)：将芯片面积划分为一组块或非重叠矩形的集合。2.切割式平面规划(slicingfloorplan)：通过反复切割矩形而得一种矩形分割方案。3.切割树/切割式平面规划树(slicingtreeorslicingfloorplantree)：这个树的每个叶节点代表一个模块。标准表示法用H和V表示横切(horizontal)和纵切(vertical)。图6切割式平面规划与一种切割树4.2布局规划的划分

4.非切割式平面规划(non-slicingfloorplan):不能通过对模块的横切纵切来形成的平面规划。一个最小的没有空间浪费的非二分布图规划是个轮形，又称作“轮(wheel)”。5.平面规划树(floorplantree):用于表达层次式平面规划的树。每个叶节点表示块区，每一个内部节点代表一个横切，纵切或者轮。图7一个层次式平面规划与对应的切割树8.4.2布局规划的划分

6.约束图对(constraint-graphpair)。一对用于表示一个平面规划的有向图，即纵向约束图和横向约束图，这两个图用于表示块区位置之间的关系。对应图7的平面规划图，约束图对如图8所示。图8对应图7中平面规划图的约束图对约束图中若两点之间有连线代表两点之间相邻。横向约束图为VCG，纵向约束图为HCG。在VCG中，最长路径代表着整个模块的宽度。HCG中最长路径代表着整个模块的高度。需要注意图中上下左右的相对顺序要与平面规划图保持一致。规划表示方式之间的转换包括：把一个布局规划换成约束图对；把一个布局规划换成序列对；把序列对转换成布局规划。4.2布局规划的划分

【例2】abcde4.2布局规划的划分abcde解：尺寸：W=12×H=9坐标：a(0,5)b(8,6)c(0,0)d=(4,0)e(8,0)5布局布线

5.1全局布线现代VLSI芯片非常密集，而且往往体积太大，无法通过网格算法的一次通过来整体求解。因此，由于其高度的复杂性，大多数VLSI路由算法都是以两个阶段的方式工作：首先，形成一个全局或松散路由，确定网络的拓扑及其相对于作为路由障碍的对象的相对位置。随后是一个详细的路由阶段，确定模块终端之间在层、通过和轨道分配方面的最终互连规范。因此，全局路由的主要任务是将一个更大、更复杂的问题分解成几个更易于处理的较小问题。直线最小斯坦纳树（左）与汉南网格（右）的例子。5.1全局布线全局路由分解为两个子问题1.全局路由图构造：大多数全局路由器根据从给定布局和路由区域定义中提取的全局路由图执行路由（图9）。2.布线区域内的网，以满足所需的优化准则。计算特定网络的全局路由，如图9（b）所示，在适当的位置添加表示终端的顶点。图9一个小宏单元问题的全局路由（a）全局路由图（b）终端的扩充图10基于网格的全局图基于网格的全局图这一阶段相当依赖于特定的布局风格。1.门阵列:

布线区域自动定义为门阵列的行和列的单元之间的布线通道的形式。2.标准单元格布局:对于标准单元设计，布线区域以相邻单元行之间的通道的形式被清楚地定义。3.宏单元布局:在宏单元布局中，更多地涉及到路由区域定义。5.2全局路由图和区域排序直线邻接图模型：图11（a）显示了小型宏单元布局的全局路由图。

极坐标图模型：这些如图11（b）和（c）所示。5.2全局路由图和区域排序padscellscriticalregionsrectilinearadjacencygraphabcdef“+”jn“T”jn（a）fdeabcSourceSinkfdeabcSourceSink（b）（c）图11对于6个单元的宏单元布局（a）直线邻接图（b）水平极坐标图（c）垂直极坐标图

3)混合图模型（图12）。

5.2全局路由图和区域排序（a）（b）（c）（d）图12导出混合（a）吉哈尔图（b）在孤块修改后（c）经过10次修改后（d）外部通道修改后在全局图中，边（通道）可以相交形成“T”或“+”连接。图13所示。abcdeabcde（a）（b）（c）图13两种可能的+到T的转换4.区域排列5.目标函数

全局路由器可用于解决一系列目标。这些也是部分由所使用的技术决定。对于SOG、GA和PCB类型的布线，由于布线空间是有限的，可布线性是全局布线器的主要目标。可路由性的目标是分配路由，使没有过度拥挤的区域。对于标准单元和宏单元