FPGA软件平台中电路划分算法的介绍

FPGA软件平台中电路划分算法的介绍丁贤庆1目录一、FPGA简介 二、 电路划分的实例三、FPGA中的Kernighan-Lin(KL)算法四、FPGA中的Fiduccia-Mattheyses(FM)算法2目录一、FPGA简介

二、 电路划分的实例三、FPGA中的Kernighan-Lin(KL)算法四、FPGA中的Fiduccia-Mattheyses(FM)算法3FPGA结构45可编程的交叉开关(SwitchBox，SB)是行信号与列信号的交汇点，信号在这里可以转变方向。信号可以通过连接块和交叉开关从一个逻辑块传递到另一个逻辑块。从图中可以看出，在可重构逻辑器件中，交叉开关所对应的路由资源通路会影响信号线的布通率。SBCHCHSBWirecapacities6目录一、FPGA简介 二、 电路划分的实例三、FPGA中的Kernighan-Lin(KL)算法四、FPGA中的Fiduccia-Mattheyses(FM)算法7几个术语的解释Partitioning划分Floorplanning

规划Placement布局Routing布线--Regularnetsrouting规则化--Clockrouting时钟--Powerrouting电源Compaction压缩/优化8实例1电路FPGA结构9实例210实例211实例312Circuit:Cutca:fourexternalconnections124536785648723156487231CutcaCutcbBlockABlockBBlockABlockBCutcb:twoexternalconnections实例413目录一、FPGA简介 二、 电路划分的实例三、

FPGA中的Kernighan-Lin(KL)算法四、FPGA中的Fiduccia-Mattheyses(FM)算法14564213324561GraphG2:Nodes1,2,6.GraphG1:Nodes3,4,5.Collectionofcut

edges

Cutset:(1,3),(2,3),(5,6),Block(Partition)Cells建模思想（电路图）15划分效果的评价目标：1、Numberofconnectionsbetweenpartitionsisminimized2、Eachpartitionmeetsalldesignconstraints(size,numberofexternalconnections..)3、Balanceeverypartitionaswellaspossible16划分效果的评价目标16Given:Agraphwith2nnodeswhereeachnodehasthesameweight.Goal:Apartition(division)ofthegraphintotwodisjointsubsetsAandBwithminimumcutcostand|A|=|B|=n.25631478Example:n=4Block

ABlockB划分算法：Kernighan-Lin(KL)Algorithm具体介绍17Cost

D(v)ofmovinganode

vD(v)=|Ec(v)|–|Enc(v)|,where

Ec(v)isthesetofv’sincidentedgesthatarecutbythecutline,andEnc(v)isthesetofv’sincidentedgesthatarenotcutbythecutline.Highcosts(D>0)indicatethatthenodeshouldmove,whilelowcosts(D<0)indicatethatthenodeshouldstaywithinthesamepartition.25631478Node3:D(3)=3-1=2Node7:D(7)=2-1=1划分算法：Kernighan-Lin(KL)Algorithm具体介绍18Gainofswappingapairofnodes

a

and

b

g=D(a)+D(b)-2*

c(a,b),where

D(a),

D(b)are

the

respective

costsofnodes

a,b

c(a,b)istheconnectionweightbetweenaandb:Ifanedgeexistsbetweenaandb,

thenc(a,b)

=edgeweight(here1),otherwise,c(a,b)

=0.

The

gain

gindicateshowusefultheswapbetweentwonodeswillbe

Thelarger

g,themorethetotalcutcostwillbereduced25631478划分算法：Kernighan-Lin(KL)Algorithm具体介绍19Gainofswappingapairofnodes

aundb

g=D(a)+D(b)-2*

c(a,b),where

D(a),

D(b)are

the

respective

costsofnodes

a,b

c(a,b)istheconnectionweightbetweenaandb:Ifanedgeexistsbetweenaandb,

thenc(a,b)

=edgeweight(here1),otherwise,c(a,b)

=0.

25631478Node3:D(3)=3-1=2Node7:D(7)=2-1=1

g(3,7)=D(3)+D(7)-2*

c(a,b)=2+1–2=1=>Swapping

nodes3and7would

reduce

the

cut

size

by125631478划分算法：Kernighan-Lin(KL)Algorithm具体介绍20Gainofswappingapairofnodes

aundb

g=D(a)+D(b)-2*

c(a,b),where

D(a),

D(b)are

the

respective

costsofnodes

a,b

c(a,b)istheconnectionweightbetweenaandb:Ifanedgeexistsbetweenaandb,

thenc(a,b)

=edgeweight(here1),otherwise,c(a,b)

=0.

25631478Node3:D(3)=3-1=2Node5:D(5)=2-1=1

g(3,5)=D(3)+D(5)-2*

c(a,b)=2+1–0=3=>Swapping

nodes3and5would

reduce

the

cut

size

by325631478划分算法：Kernighan-Lin(KL)Algorithm具体介绍21Gainofswappingapairofnodes

aundbThegoalistofindapairofnodesaandbtoexchangesuchthat

gismaximizedandswapthem.划分算法：Kernighan-Lin(KL)Algorithm具体介绍22Maximumpositivegain

Gm

ofapassThemaximumpositivegain

Gmcorrespondstothebestprefixofmswapswithintheswapsequenceofagivenpass.

Thesemswapsleadtothepartitionwiththeminimumcutcostencounteredduringthepass.

GmiscomputedasthesumofΔgvaluesoverthefirstmswapsofthepass,withmchosensuchthatGmismaximized.划分算法：Kernighan-Lin(KL)Algorithm具体介绍23划分算法：Kernighan-Lin(KL)Algorithm具体介绍2425631478Cutcost:9Notfixed:

1,2,3,4,5,6,7,8划分算法：Kernighan-Lin(KL)Algorithm应用实例2525631478Cutcost:9Notfixed:

1,2,3,4,5,6,7,8

D(1)=1 D(5)=1

D(2)=1 D(6)=2

D(3)=2 D(7)=1

D(4)=1 D(8)=1

Costs

D(v)ofeach

node:Nodes

that

leadtomaximum

gain划分算法：Kernighan-Lin(KL)Algorithm应用实例2625631478Cutcost:9Notfixed:

1,2,3,4,5,6,7,8

D(1)=1 D(5)=1

D(2)=1 D(6)=2

D(3)=2

D(7)=1

D(4)=1 D(8)=1

g1=2+1-0=3

Swap(3,5)

G1=

g1=3Nodes

that

leadtomaximum

gainGaininthe

currentpassCosts

D(v)ofeach

node:Gain

after

node

swapping划分算法：Kernighan-Lin(KL)Algorithm应用实例27Cutcost:9Notfixed:

1,2,3,4,5,6,7,825631478

D(1)=1 D(5)=1

D(2)=1 D(6)=2

D(3)=2

D(7)=1

D(4)=1 D(8)=1

g1=2+1-0=3

Swap(3,5)

G1=

g1=3Nodes

that

leadtomaximum

gainGaininthe

currentpassGain

after

node

swapping25631478划分算法：Kernighan-Lin(KL)Algorithm应用实例28Cutcost:9Notfixed:

1,2,3,4,5,6,7,8Cutcost:6Notfixed:

1,2,4,6,7,8

D(1)=1 D(5)=1

D(2)=1 D(6)=2

D(3)=2

D(7)=1

D(4)=1 D(8)=1

g1=2+1-0=3

Swap(3,5)

G1=

g1=32563147825631478划分算法：Kernighan-Lin(KL)Algorithm应用实例29Cutcost:9Notfixed:

1,2,3,4,5,6,7,8Cutcost:6Notfixed:

1,2,4,6,7,8

D(1)=1 D(5)=1

D(2)=1 D(6)=2

D(3)=2

D(7)=1

D(4)=1 D(8)=1

g1=2+1-0=3

Swap(3,5)

G1=

g1=3

D(1)=-1 D(6)=2

D(2)=-1 D(7)=-1

D(4)=3

D(8)=-1

2563147825631478划分算法：Kernighan-Lin(KL)Algorithm应用实例30Cutcost:9Notfixed:

1,2,3,4,5,6,7,8Cutcost:6Notfixed:

1,2,4,6,7,825631478

D(1)=1 D(5)=1

D(2)=1 D(6)=2

D(3)=2

D(7)=1

D(4)=1 D(8)=1

g1=2+1-0=3

Swap(3,5)

G1=

g1=3

D(1)=-1 D(6)=2

D(2)=-1 D(7)=-1

D(4)=3

D(8)=-1

g2=3+2-0=5

Swap(4,6)

G2=G1+

g2

=8Nodes

that

leadtomaximum

gainGaininthe

currentpassGain

after

node

swapping2563147825631478划分算法：Kernighan-Lin(KL)Algorithm应用实例31Cutcost:9Notfixed:

1,2,3,4,5,6,7,8Cutcost:6Notfixed:

1,2,4,6,7,8Cutcost:1Notfixed:

1,2,7,825631478Cutcost:7Notfixed:

2,8

D(1)=1 D(5)=1

D(2)=1 D(6)=2

D(3)=2

D(7)=1

D(4)=1 D(8)=1

g1=2+1-0=3

Swap(3,5)

G1=

g1=3

D(1)=-1 D(6)=2

D(2)=-1 D(7)=-1

D(4)=3

D(8)=-1

g2=3+2-0=5

Swap(4,6)

G2=G1+

g2

=8

D(1)=-3

D(7)=-3

D(2)=-3 D(8)=-3

g3=-3-3-0=-6

Swap(1,7)

G3=G2

+

g3

=2Gaininthe

currentpassNodes

that

leadtomaximum

gainGain

after

node

swapping256314782563147825631478划分算法：Kernighan-Lin(KL)Algorithm应用实例32Cutcost:9Notfixed:

1,2,3,4,5,6,7,825631478Cutcost:9Notfixed:

–Cutcost:6Notfixed:

1,2,4,6,7,8Cutcost:1Notfixed:

1,2,7,8Cutcost:7Notfixed:

2,8

D(1)=1 D(5)=1

D(2)=1 D(6)=2

D(3)=2

D(7)=1

D(4)=1 D(8)=1

g1=2+1-0=3

Swap(3,5)

G1=

g1=3

D(1)=-1 D(6)=2

D(2)=-1 D(7)=-1

D(4)=3

D(8)=-1

g2=3+2-0=5

Swap(4,6)

G2=G1+

g2

=8

D(1)=-3

D(7)=-3

D(2)=-3 D(8)=-3

g3=-3-3-0=-6

Swap(1,7)

G3=G2

+

g3

=2

D(2)=-1

D(8)=-1

g4=-1-1-0=-2

Swap(2,8)

G4=G3

+

g4=0

25631478256314782563147825631478划分算法：Kernighan-Lin(KL)Algorithm应用实例33MaximumpositivegainGm=8withm=2.

D(1)=1 D(5)=1

D(2)=1 D(6)=2

D(3)=2

D(7)=1

D(4)=1 D(8)=1

g1=2+1-0=3

Swap(3,5)

G1=

g1=3

D(1)=-1 D(6)=2

D(2)=-1 D(7)=-1

D(4)=3

D(8)=-1

g2=3+2-0=5

Swap(4,6)

G2=G1+

g2

=8

D(1)=-3

D(7)=-3

D(2)=-3 D(8)=-3

g3=-3-3-0=-6

Swap(1,7)

G3=G2

+

g3

=2

D(2)=-1

D(8)=-1

g4=-1-1-0=-2

Swap(2,8)

G4=G3

+

g4=0

划分算法：Kernighan-Lin(KL)Algorithm应用实例34

D(1)=1 D(5)=1

D(2)=1 D(6)=2

D(3)=2

D(7)=1

D(4)=1 D(8)=1

g1=2+1-0=3

Swap(3,5)

G1=

g1=3

D(1)=-1 D(6)=2

D(2)=-1 D(7)=-1

D(4)=3

D(8)=-1

g2=3+2-0=5

Swap(4,6)

G2=G1+

g2

=8

D(1)=-3

D(7)=-3

D(2)=-3 D(8)=-3

g3=-3-3-0=-6

Swap(1,7)

G3=G2

+

g3

=2

D(2)=-1

D(8)=-1

g4=-1-1-0=-2

Swap(2,8)

G4=G3

+

g4=0

SinceGm

>0,

thefirstm=2swaps

(3,5)and(4,6)areexecuted.25631478SinceGm

>0,morepassesareneededuntil

Gm

0.MaximumpositivegainGm=8withm=2.划分算法：Kernighan-Lin(KL)Algorithm应用实例35目录一、FPGA简介 二、 电路划分的实例三、FPGA中的Kernighan-Lin(KL)算法四、FPGA中的Fiduccia-Mattheyses(FM)算法36Singlecellsaremovedindependentlyinsteadofswappingpairsofcells.Thus,thisalgorithmisapplicabletopartitionsofunequalsizeorthepresenceofinitiallyfixedcells.

Cutcostsareextendedtoincludehypergraphs,i.e.,netswithtwoormorepins.WhiletheKLalgorithmaimstominimizecutcostsbasedonedges,theFMalgorithmminimizescutcostsbasedonnets.

Theareaofeachindividualcellistakenintoaccount.Nodesandsubgraphsarereferredtoascellsandblocks,respectively.划分算法：Fiduccia-Mattheyses(FM)Algorithm37Given:agraphG(V,E)withnodesandweightededgesGoal:toassignallnodestodisjointpartitions,soastominimizethetotalcost(weight)ofallcutnetswhilesatisfyingpartitionsizeconstraints划分算法：Fiduccia-Mattheyses(FM)Algorithm38Gain

g(c)forcellc

g(c)=FS(c)–TE(c),wherethe“movingforce“

FS(c)isthenumberofnetsconnectedtocbutnotconnectedtoanyothercellswithinc’spartition,i.e.,cutnetsthatconnectonlytoc,andthe“retentionforce“

TE(c)isthenumberofuncutnetsconnectedtoc.Thehigherthegain

g(c),thehigheristheprioritytomovethecellctotheotherpartition.Cell2:FS(2)=0 TE(2)=1

g(2)=-113425abcde划分算法：Fiduccia-Mattheyses(FM)Algorithm39Gain

g(c)forcellc

g(c)=FS(c)–TE(c),wherethe“movingforce“

FS(c)isthenumberofnetsconnectedtocbutnotconnectedtoanyothercellswithinc’spartition,i.e.,cutnetsthatconnectonlytoc,andthe“retentionforce“

TE(c)isthenumberofuncutnetsconnectedtoc.Cell1:FS(1)=2 TE(1)=1

g(1)=1Cell2:FS(2)=0 TE(2)=1

g(2)=-1Cell3:FS(3)=1 TE(3)=1

g(3)=0Cell4:FS(4)=1 TE(4)=1

g(4)=0Cell5:FS(5)=1 TE(5)=0

g(5)=113425abcde13425abcde划分算法：Fiduccia-Mattheyses(FM)Algorithm40Maximumpositivegain

Gm

ofapassThemaximumpositivegainGmisthecumulativecellgainofmmovesthatproduceaminimumcutcost.Gm

isdeterminedbythemaximumsumofcellgainsgoveraprefixofmmovesinapass划分算法：Fiduccia-Mattheyses(FM)Algorithm41RatiofactorTheratiofactoristherelativebalancebetweenthetwopartitionswithrespecttocellarea.

Itisusedtopreventallcellsfromclusteringintoonepartition.

Theratiofactorrisdefinedas

wherearea(A)andarea(B)arethetotalrespectiveareasofpartitionsAandB

划分算法：Fiduccia-Mattheyses(FM)Algorithm42BalancecriterionThebalancecriterion

enforcestheratiofactor.

Toensurefeasibility,themaximumcellareaareamax(V)mustbetakenintoaccount.

ApartitioningofVintotwopartitionsAandBissaidtobebalancedif

[r∙area(V)–areamax(V)]≤area(A)≤[r∙area(V)+areamax(V)]划分算法：Fiduccia-Mattheyses(FM)Algorithm43BasecellAbasecellisacellcthathasmaximumcellgaing(c)amongallfreecells,andwhosemovedoesnotviolatethebalancecriterion.Cell1:FS(1)=2 TE(1)=1

g(1)=1Cell2:FS(2)=0 TE(2)=1

g(2)=-1Cell3:FS(3)=1 TE(3)=1

g(3)=0Cell4:FS(4)=1 TE(4)=1

g(4)=0Basecell划分算法：Fiduccia-Mattheyses(FM)Algorithm44划分算法：Fiduccia-Mattheyses(FM)Algorithm4513425ABabcdeStep0:

Compute

the

balance

criterion

[r∙area(V)–areamax(V)]≤area(A)≤[r∙area(V)+areamax(V)]

0,375*16–5=1

area(A)

11=0,375*16+5.Given:

Ratiofactorr=0,375area(Cell_1)=2

area(Cell_2)=4

area(Cell_3)=1

area(Cell_4)=4

area(Cell_5)=5.

划分算法：Fiduccia-Mattheyses(FM)Algorithm实例4613425ABabcdeStep1:

Compute

the

gainsofeach

cell

Cell1:FS(Cell_1)=2 TE(Cell_1)=1

g(Cell_1)=1Cell2:FS(Cell_2)=0 TE(Cell_2)=1

g(Cell_2)=-1Cell3:FS(Cell_3)=1 TE(Cell_3)=1 g(Cell_3)=0Cell4:FS(Cell_4)=1 TE(Cell_4)=1

g(Cell_4)=0Cell5:FS(Cell_5)=1 TE(Cell_5)=0

g(Cell_5)=1划分算法：Fiduccia-Mattheyses(FM)Algorithm实例4713425ABabcdeCell1:FS(Cell_1)=2TE(Cell_1)=1

g(Cell_1)=1Cell2:FS(Cell_2)=0TE(Cell_2)=1

g(Cell_2)=-1Cell3:FS(Cell_3)=1TE(Cell_3)=1 g(Cell_3)=0Cell4:FS(Cell_4)=1TE(Cell_4)=1

g(Cell_4)=0Cell5:FS(Cell_5)=1TE(Cell_5)=0

g(Cell_5)=1Step2:

SelectthebasecellPossiblebasecellsareCell1andCell5BalancecriterionaftermovingCell1:area(A)=area(Cell_2)=4BalancecriterionaftermovingCell5:area(A)=area(Cell_1)+area(Cell_2)+area(Cell_5)=11Bothmovesrespectthebalancecriterion,butCell1isselected,moved,andfixedasaresultofthetie-breakingcriterion.划分算法：Fiduccia-Mattheyses(FM)Algorithm实例4813425ABabcdeStep3:Fixbasecell,update

gvaluesCell2:FS(Cell_2)=2 TE(Cell_2)=0

g(Cell_2)=2Cell3:FS(Cell_3)=0 TE(Cell_3)=1

g(Cell_3)=-1Cell4:FS(Cell_4)=0 TE(Cell_4)=2

g(Cell_4)=-2Cell5:FS(Cell_5)=0 TE(Cell_5)=1

g(Cell_5)=-1

AfterIterationi=1:

PartitionA1=2

,PartitionB1=1,3,4,5

,with

fixed

cell

1

.划分算法：Fiduccia-Mattheyses(FM)Algorithm实例4913425ABabcdeCell2:FS(Cell_2)=2TE(Cell_2)=0

g(Cell_2)=2Cell3:FS(Cell_3)=0TE(Cell_3)=1

g(Cell_3)=-1Cell4:FS(Cell_4)=0TE(Cell_4)=2

g(Cell_4)=-2Cell5:FS(Cell_5)=0TE(Cell_5)=1

g(Cell_5)=-1Iterationi=2

Cell2hasmaximumgain

g2=2,area(A)=0,balancecriterionisviolated.Cell3hasnextmaximumgaing2=-1,area(A)=5,balancecriterionismet.Cell5hasnextmaximumgaing2=-1,area(A)=9,balancecriterionismet.

Movecell3,updatedpartitions:A2={2,3},B2={1,4,5},withfixedcells{1,3}Iterationi=1划分算法：Fiduccia-Mattheyses(FM)Algorithm实例50Cell2:

g(Cell_2)=1