FPGA軟件平臺中電路劃分算法的介紹

FPGA軟件平臺中電路劃分算法的介紹丁賢慶1目錄一、FPGA簡介 二、 電路劃分的實例三、FPGA中的Kernighan-Lin(KL)算法四、FPGA中的Fiduccia-Mattheyses(FM)算法2目錄一、FPGA簡介

二、 電路劃分的實例三、FPGA中的Kernighan-Lin(KL)算法四、FPGA中的Fiduccia-Mattheyses(FM)算法3FPGA結(jié)構(gòu)45可編程的交叉開關(guān)(SwitchBox，SB)是行信號與列信號的交匯點，信號在這里可以轉(zhuǎn)變方向。信號可以通過連接塊和交叉開關(guān)從一個邏輯塊傳遞到另一個邏輯塊。從圖中可以看出，在可重構(gòu)邏輯器件中，交叉開關(guān)所對應(yīng)的路由資源通路會影響信號線的布通率。SBCHCHSBWirecapacities6目錄一、FPGA簡介 二、 電路劃分的實例三、FPGA中的Kernighan-Lin(KL)算法四、FPGA中的Fiduccia-Mattheyses(FM)算法7幾個術(shù)語的解釋Partitioning劃分Floorplanning

規(guī)劃Placement布局Routing布線--Regularnetsrouting規(guī)則化--Clockrouting時鐘--Powerrouting電源Compaction壓縮/優(yōu)化8實例1電路FPGA結(jié)構(gòu)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劃分效果的評價目標(biāo)：1、Numberofconnectionsbetweenpartitionsisminimized2、Eachpartitionmeetsalldesignconstraints(size,numberofexternalconnections..)3、Balanceeverypartitionaswellaspossible16劃分效果的評價目標(biāo)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應(yīng)用實例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應(yīng)用實例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應(yīng)用實例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應(yīng)用實例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應(yīng)用實例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應(yīng)用實例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應(yīng)用實例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應(yīng)用實例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應(yīng)用實例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應(yīng)用實例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應(yīng)用實例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