о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999Vol.36No.6P.685-689



ĵ·

ժҪпһߴСΪĿġʱΪԼġֿ뻮ֿ֮ȷ˹ϵĵ·,һ·ֵľ˻㷨.㷨ͨλӳΪ,˰ŻĿԼʱԼ,þ˻𷽳̵.ÿԪֻܷ䵽һֿԼԪһķ.㷨Visual C++Աʵ,ʵһЧķ.,л˻ϵĵ·.
ؼʣ磬˻·
ţTP18
A NEURAL NETWORK APPROACH FOR PERFORMANCE-DRIVEN
CIRCUIT PARTITIONING
HU Wei-Ming
(National Key Laboratory of Text Processing Technology,Institute of Computer Science and Technology,
Peking University,Beijing 100871)
AbstractHere proposed is a mean field annealing approach to the performance\|driven circuit partitioning, in which the object is to minimize the total routing cost between cells, the constraints are timing and area, and the partitions have intrinsic topological relationships. In the algorithm, a permute matrix is used to map the problem to neural network,and the energy function including object item, area constrained item,and the timing constrained item is presented, and then iteration procedure is put into practice with the mean annealing equation. Normalization of neurons proves that one cell only can be assigned to one partition. The algorithm is programmed with Visual C++, and experimental result shows that it is an effective method. In addition, the human and machine combined partitioning conception is also discussed.
Key wordsneural network, mean field annealing, performance-driven, circuit partitioning
1
ָһϵͳָϵͳ,ʹÿϵͳ̫,Ӷʵ.Χƻ,˴ʽ㷨,ǶиԵŵ,ҲиԵȱ.˹жصĽṹͶصĴϢ,ܹһЩͳ㼼, Ҳ˳·:ף1ӦHopfieldƽԼĿٵĶ(bipartitioning),ȡõЧ;ף2ӦBoltzmannף1ݻͬ,̽˲Boltzmann·Ŀ;ף3ݰģ۵ķ֯,һ·ֵģ㷨,Ƕ黮(multi-way partitioning).Ŀһ֮ȷ˹ϵĵ·(FPGATCM͵Ļ),һ·ֵ㷨.
2͵Ԫ鲢
ĵ·Ϊ:һʵ,:MԪɵĵ·ԪI,siǵԪi;aijǴӵԪiԪj;cijǴӵԪiԪjźŲʱ;NֿɵĻֿ鼯X,txΪx;bxyǴӿxyĲߴ;dxyǴӿxyĲʱ,ҪѰһ:IX,ʹС,:Լ:,ʱԼ:d((i),(j))c(i,j)i,jI.
˵:bxyģͻʽĲߴ.:x=y,bxy=0,bxy=1ʱ,ŻĿӦĳһ׵Ŀ;bxyΪxyManhattan,ȼڿߵManhattanܳ,ԸҪbxyֵ.bxydxy໥йϵ,аֹϵ䡱,ʹⶨһ.Լָ䵽ͬһֿĵԪܺͲܴڸûֿ.ʱԼϵͳʱ,ҿͨʱӷ̺ϵ·ԪڲʱƵóԪʱӣ4.ÿԵԪʵʱҪС֮ʱ.
ڽ񾭼֮ǰ,ԸʱԼ,ԵԪй鲢,ԼٵԪ,ӶСĹģ,ʵʩ˻ļʱ.鲢ķΪ:Ԫij,c(i,j)<(d(x,y)),鲢Ԫi͵ԪjΪԪk.
3 񾭼
3.1 ģ
˻𷽷Ҫص:پ˻ֻҪĳؼ¶ȸʵʩ˻,Դﵽĳƽ״̬,ͿȡýϺõЧ;ھ˻ȿɿһµģ,ֿΪǶģ˻شĽ.ۿԪһķԼ.
˻3̱ʾ:Vе״̬ʸ,iΪ,gԪI/OԺ,T¶ȿƲ.
3.2ӳ䷽
MԪN黮ӳΪ,ҪûλvixMNʾ:дԪ,дĻֿ.λһֵΪ01ľ,ӦһֿеĻ.(i)=x,ԪiӦڻֿx,Ԫ(i,x)vix=1,vix=0.ҪMNԪ.
3.3 
ӳΪӦ,Ϊ:

EvixһƫΪ:
(1)
ĵ1ΪĿ,СԪߴ.
ĵ2ΪԼ,ʾ,ֻеֿеԪʱȡСֵ,ƽͼƽĹϵʾ˸ֿеԪʹʱȡСԼϵ.
ĵ3ΪʱԼ.ʱԼ͵ĲʽԼֱӼ뵽,Ҳ˵,粻ֱӴʱԼ,Ϊ,ǶһDelay(i:1M,j:1M,x:1N,y:1N),ʱԼתò.c(i,j)d(x,y),Delay(i,j,x
,y)=1,Ԫi͵ԪjܹͬʱֱڿxͿy; c(i,j)<d(x,y),Delay(i,j,x,y)=0,Ԫi͵Ԫjͬʱֱ䵽xͿy.Delay,ͿԶʱԼ,

Delay(i,j,x,y)=0ʱ,vix,vjyͬʱΪ1,Ϊ0(ʱԼ);Ϊ0(ʱԼ).
ֵע,DelayĶֻΪ˵ķ,ʵϲޱҪO(M2)(NM)Ĵ洢ռȥ洢Delay.ʱ,ͨ߼ķDelayֵ.,E3ķΪ:if c(i,j)<d(x,y) E3=E3+0.5vixviy;
ͦ¶ԽкܴӰ.ͦȡϴֵ,ܽϿһн,һ;ͦȡСֵ,øõĽ,ҪøļʱΪ.ݾ,ͦȡ3.5Ǻʵ.Hopfield粻ͬ,˻綼ÿн,ٶҪHopfield.
3.4 Ԫһ
Լ,λÿһеԪֻ1ԪΪ1,Hopfieldͨмӳͷķ.ְ취ɶ,µĶӦнľֲС,Ӷǰ.ھ˻,ԲùһķԼ.
Ԫ״̬ʸvixɿ:ԪƽŶ,Ԫi䵽xĸ,Boltzmannֲ,
vix=exp(-ix/T)(2)
,ix Խ,λռиvixԽС,Ԫiܷڿx.Ϊ˻ʵʸ,Ԫvixйһ:
(3)
֤ÿԪֻܷһֿ,ӶҲԼ.ڸµ,Ԫ䵽ֿĸʳʾȷֲ;ڵʱ,ԪнСֵĻֿ,ʹĿ꺯С.еԼʱԼ͹һ֤ܹϷ.
3.5 ٽ¶
ٽ¶Tc,ΪʱÿԪԸֿռиΪ1/N,ÿһԪ(i,x),0ix=ix(vix=1/N),Ϊv0ix=exp(-0ix/T0ix),T0ix=0ix/lnv0ix)=0ix/ln(N).ѡ,x{T0ix}Ϊϵͳٽ¶,ڴӸ¶ȿʼʵʩ˻.
4 㷨ʱ临Ӷ
ݾ˻𷽳,Խϵͳֵľ˻:
1.еԪĹ鲢.
2.ѡȡvix(i=1,2,Mx=1,2,,N)ֵ,йһ,T=TcֵE,E1.
3.ѡһԪi,´:(1)ʽix(i=1,2,N)ֵ;(2)ʽvix(x=1,2,N)ֵ;(3)ʽԪһ;Eֵ,E2.
4.E2E1ĲE;EƵ0,,E2E1,ٷز3.
˵3:  EEĲ.ΪEʱ临,·E:

vixvixԪ(i,x)״̬. E=0ƽ,ΪE<.ģ˻𷽷ͬ,˻𷽷ֻҪڹؼ¶Tcʵʩľ˻,ɵõȫŽȫŽ.ȡڵ,ȡԽС,Խ,ʱԽ.
NM,ixͦEʱ临ӶȶΪO(M);ΪʹE0,ҪO(M)ε,Ա㷨ʱ临ӶΪO(M2).
5˻ϵĻ
Щ·Ӧó,رڽϵͳʱ,˵ĸԤȡúܺõЧ.,TCMĸ߲,ʼֿоԱֹܵԪ䵽TCMоƬɣ4,ʼҪ˵ܺ;,мֵ.Ȼ,ڳʼδȷļ,Լ.ΪЩԼ,ҪһЩԪ·䵽ֿ.ƶӦʼСƫ.Ҳ˵,һΥʱԼԼĳʼ,ҪѰһƫʼСԼЧ.
һԪʼڵĿַڵĿ֮ManhattanϸõԪڲʱΪõԪƫ.ԾܲƶнϴڲʱӵĵԪ.һʼinitial:IJÿһԪڲʱdi,Զһ۾P,һMN,pix=diMan_dis(x,initial(i)),ʾԪi䵽ֿxĴ.еԪƫƵܺͱ㹹ϵͳƫ.TCMĻ,ڳʼƫΪŻĿ,E1,һ,ڼ,ܹ˻ϵĵ·˼.
6 ʵ
㷨Visual C++Ա,Compaq586/100ʵ.ѡ·ʵ֤㷨Ч:1Ϊṹĵ·.ͼ1ʾ,ͼбߵĴϸʾԪĿĶ,ͼе߽õ·ָ4,ֱӷָĵԪ(ab)֮ʱӴоƬ(12)Ĳʱ(c(a,b)d(1,2)).ѿ,ͼʾķָǸõ·ֳ4ʱŽ.,,200Ԫֳ4ʱ,Ž,㷨нǿѰ.һɼ,һ.

ͼ1ʵ
1˲õ4·йϢ,12Ϊ1·,34Ϊ2.1гЩ·ֳ4ֿʵ,ҽHNN㷨˱Ƚ.ʵ,㷨ٶȲHNN㷨;,㷨4HNN㷨ʱ,ȡñHNNõöн.,㷨ҲHNN㷨ȶ.
1 ʵ

ŵԪĿManhattanߴܺʱ(s)
㷨HNN㷨㷨HNN㷨
16420816300.980.17
219613668107106.439.7
3575730713111848319.390.2
4104393551906-859.7-

ע:4㷨HNNɢ,δü 
7
һĵ·ֵ㷨.㷨Ӧþ˻𷽷ԼСߴΪĿꡢʱΪԼŻ.ʵ,㷨нǿѰ.
Ŀõйʿѧ͹Ȼѧ(Ŀ69576009).
߼飺У196811ʿҪIC-CAD˹GISС.
ߵλ(ѧѧоϢصʵҡ100871)
οף
1Yih J S,Mazumder P. A neural network design for circuit partitioning. IEEE Trans on CAD of integrated circuits and systems, 1990, 9(12): 12651271
2oenig A,Wehn N,Glesnet M.Partitioning on Boltzmann machines. In: Proc of IEEE Int'l Symp on Circuit and System.San Diego,1992. 324327
3ε. ģ˹緽ڵ·еӦ. ѧ, 1992, 15(9): 641647
(Shen Tao et al . Application of fuzzy neural computing in circuit partitioning. Chinese Journal of Computers (in Chinese), 1992, 15(9): 641647)
4hih M,Kuh E S. Quadratic Boolean programming for performance-driven system partitioning.In: Proc of Design Automation Conf.New Orleans, 1993. 761765
5ohannes F M. Partitioning of VLSI circuits and systems. In: Proc of Design Automation Conf.California. 1996. 8386
6ok C W,Cheng C K,Lin T T Y. General purpose multiple-way partitioning algorithm. IEEE Trans on CAD of integrated circuits and systems, 1994, 13(12): 14801487
7han V C,Lewis D. Hierarchical partitioning for field-programmable systems. In:Proc of IEEE Int'l Conf on Computer Aided Design.California, 1997. 428435 
ոڣ1998-08-19
޸ڣ1999-01-19
