ѧ
JOURNAL OF SOFTWARE
2000Vol.11No.2P.256-259



k-ɫ⼰˻㷨
쿡־
ժҪ˻𷽷ȿԿһµģ,ֿΪǶģ˻شĽ.İѾԼĶͨСתΪ߹㷺k-ɫ,k-ɫľ˻㷨.㷨߶ཻͼģ͵Ļ,ھͽȸ,ûλ,ӳΪӦ,ٹ˸.еĿΥԼĳͷΥԼĳͷԪһ֤ܹ⵽һϷ.ʵ,һЧ㷨.
ؼʣͨС,k-ɫ,˻𷽷.
ţTP18
A Mean Field Annealing-Based Algorithm for k-Colorable Problem
HU Wei-mingXU Jun-hua
(National Key Laboratory of Text Processing Technology Institute of Computer Science and Technology Beijing University,Beijing,100871)
HE Zhi-jun
(Department of Computer Science and Engineering Zhejiang University,Hangzhou,310027)
AbstractThe mean field annealing approach is a new neural network model,which improves the simulated annealing approach greatly.In the paper,the via minimization problem in multi-layer routing with adjacent constraints is translated to a k-colorable problem which has more general meanings,and a mean field annealing algorithm for the k-colorable problem is proposed.On the basis of the segment-crossing graph model,the adjacent matrix and the crossing matrix are introduced.A permute matrix of binary variables is used to map the problem to the neural network,and then the energy function is presented.The object item,crossing constrained item and adjacency constrained item in the energy function,and the normalization of neurons prove that the effective result can be gotten.The experimental results show that it is an effective method.
Key wordsVia minimization in multi-layer routing,k-colorable problem,mean field annealing approach.
ڳģɵ·(VLSI),ͨһʵ.,ͨСоֻ˫㲼ϣ1.㲼ֺ߳,㲼ߵͨСҲõо25.VLSIķչ,ϵĲ߼Ѿ𽥳,Ŀǰѷչ߲㲼.߲Ǽɵ·շչҪ־֮һ.ɵ·յķչCADµҪ.ĽͨСתΪ߹㷺k-ɫ,һ־˻㷨,ȡ˽ϺõЧ.йk-ɫо,ޱ.
1ͼģk-ɫ
1.1ཻͼģ
һͨСǰĶ㲼ͼһ߶ཻͼ6.߶ཻͼG(V,EVEC)ʾ,Vʾͼе߶,ͼıͨױ(EV)ͽ(EC).ֱͬһ߶,EVоһͨױӱʾ߶εĶ.EC,һ,ζʾ߶ཻص.
1.2ھͽ
ھAʾɸ߶ε,ýCʾͬ߶εĽ.(i,j)EVʱ,AԪaijڡ1,ڡ0.(i,j)ECʱ,CԪCijڡ1,ڡ0.
1.3Լ
Լֻͨ߶.
1.4k-ɫ
ÿһһɫʾ,ԽkͨСΪk-ɫ.ཻͼkɫÿɫ,һ߽ӵ㲻ͬһɫ,,ͬ߶νͬһཻص;ԼҪͨױӵֻͬɫڵɫ;EVӵ㾡ͬɫ.
2˻𷽷
˻𷽷ȿԿһµģ,ֿΪǶģ˻شĽ.˻ֻҪĳؼ¶ȸʵʩ˻,Դﵽĳƽ״̬,ͿԵõһŽϺõĴŽ.,ʱΪ,ͬʱ־ģ˻Ƶŵ.˻𷽷ԪһķԼ.˻𷽷3̱ʾ:,VеNά״̬ʸ,iΪ,gԪI/OԺ,T¶ȿƲ.
3񾭼
3.1ӳ䷽
n㡢kɫɫnk׻λvixnkʾ:дҪɫĶ,дɫ.λһֵΪ01ľ.һλӦһֿеɫ.ҪnkԪ.Ԫ(i,x)vix=1ʾiӦɫx;vix=0ʾiɫx.
3.2
Ϊ


еĵ1ΪŻĿ,Сͨ.(i,j)EVҶiͶjŲͬɫ (ͨ),,
еĵ2Ϊͷ,ɽ㲻ͬɫ.ɽͬɫ,Ϊ0.Ҳ˵,ʽcijvixcjxʾ(i,j)ECʱ(cij0),iͶjͬɫ,vixvjxͬʱΪ1.
еĵ3ΪΥԼĳͷ.ҽͨױͬɫɫʱ,Ϊ0.ɫ1ɫֻɫ2,ɫkɫֻɫk-1,ɫx(2xk-1)ɫɫx-1ɫx+1.ABֿ.
ͦȡϴֵ,ܽϿһн,һ;ͦȡСֵ,øõĽ,ҪøļʱΪ.ݾ,ͦȡ2.4Ǻʵ.˻綼ÿн.
Evixһƫþ

3.3Ԫһ
ÿֻһɫ,ԻλÿеԪֻһΪ1,ΪԼ.ھ˻,ԲԪһķԼ.Ԫ״̬ʸvixԿǵiƽŶɫxĸ,Boltzmannֲ,vixexp(-ix/T).Ϊ˻ʵʸ,Ԫvixйһ,.֤ÿֻһɫ,ӶҲԼ.
3.4㷨
,˻̵Ҫ:
ѡȡvixֵ;йһ,;
repeat {
ѡһi; Total=0
for x=1 to k {

Total=Total+exp(-ix/T);
}
for x=1 to k vix=exp(-ix/T)/Total;
}untill (E)
ЦEEĲ;E=0ƽ,ԽСõĽԽ,ʱҲԽ.
3.5ʱ临
k<<n,ھ˻,ÿεʱ临ΪO(n).Ϊʹﵽƽ״̬,ҪO(n)ε,Ծ˻̵ʱ临ΪO(n2).
4ɫԼ
ʵӦ,ʱ涨ĳЩֻĳЩضɫ,ΪɫԼ.ԿֶɫԼʽ.1:ĳһضĶֻĳһضɫ,綥n1ֻɫk1;n2ֻɫk2.һɫPʾֹϵ:бʾ,бʾɫ,iɫxʱ,p(i,x)=1,Ϊp(i,x)=0.2:ضĶضmɫ(k1,k2,...,km)(mk,k-ɫ)еκһ.,߶ཻͼ.߶ཻͼϼk-mƶ,ƶֱk-mضĶŵɫ,Щƶý,ٽƶŵɫӵɫ.ڶɫԼ,Լ:.ҽڻλ붨ɫΪ1ԪλӦԪضΪ1ʱ,Ϊ0.ԼʹĳЩܹضɫ.
5ʵ
㷨Visual C++5.0,Founder 5166ʵ.һЩѷ׵Ĳ֤k-ɫ㷨.1г˼ʵִн.㲼ߵʵ(3-ɫ),㷨ĽҪף3ݺף5ݵʽͨС㷨.һף8ݵ㲼ͼ(5-ɫ)ҲΪ,.
Table 1Experimental results for multi-layer constrained layer assignment
1ͨСʵ

Number
of
examplesNumber
of
layersNumber
of
netsNumber
of
original viasNumber of vias required fromRun
time(s)Source of
examples
Algorithm in
Ref.3ݢAlgorithm in
Ref.5ݢOur
algorithm (s)
1321573640344.71Fig.9 in
Ref.7
234710783787513.96Fig.11 in
Ref.7
3363150105949360.90Fig.14 in
Ref.7
454762--5031.04Fig.1 in
Ref.8

,ڲ,,ԭͨ,ͨ,ף3е㷨,ף5е㷨,౾㷨,ʱ,Դ,ף7еͼ9,ף7еͼ11,ף7еͼ14,ף8еͼ1. 
,ĽԼĶͨСתΪһk-ɫ,Ӧþ˻𷽷.߶ཻͼĻϽھ󡢽,ݴ˽.еĿ궥ΥԼĳͷΥԼĳͷԪһ֤ܹ⵽һϷ.㷨нϿٶȺͽϸߵ.
ĿоõȻѧ(No.69576009)йʿѧ.
߼飺,1968,ʿ,ʦ,ҪоΪIC-CAD,˹,GIS.
쿡,Ů,1968,ʦ,ҪоΪ˹.
־,1923,,ʿʦ,ҪоΪ˹,
,CAD.
ߵλ(ѧѧоϢصʵҡ100871)
쿡(ѧѧоϢصʵҡ100871)
־(㽭ѧѧ빤ѧϵݡ310027)
οף
1He Jiang-an,Hong Xian-long.An efficient two-layer router based on unconstrained via minimization.Journal of Software,1992,3(1):816
(ν,.һԼͨŻĵ˫㲼㷨FOREST.ѧ,1992,3(1):816)
2Chang K C,Du H C.Layer assignment problem for three-layer routing.IEEE Transactions on Computer,1988,C-37(5):625632
3Chang K E,Jyu H F,Feng W S.Constrained via minimization for three-layer routing.Computer Aided Design,1989,21(6):346354
4Fang S C,Chang K E,Feng W S.Via minimization with associated constraints in three-layer routing problem.In: Proceedings of IEEE ISCAS.1990.16321635
5Ahn K,Sahni S.Constrained via minimization.IEEE Transactions on CAD,1993,12(2):273282
6Fang S C,Chang K E,Feng W S et al.Constrained via minimization with practical considerations for multi-layer VLSI/PCB routing problems.In: Proceedings of IEEE 28th DAC.1991.6065
7Chen Y K,Liu M L.Three-Layer channel routing.IEEE Transactions on CAD,1984,CAD-3(2):156163
8Braun D,Burns J,Romeo F et al.Techniques for multi-layer channel routing.IEEE Transactions on CAD,1988,7(6):698712
