о뷢չ
JOURNAL OF COMPUTER RESEARCH
AND DEVELOPMENT
1999 36 12 Vol.36 No.12 1999



AgentĲвϵͳ
ׯġڡԡʰ
ժҪϸVLSI·Ƶһ裬ҪΪغвߺͨߣNPȫ.ʹJavaԣAgentļһܹԴĲпغвϵͳPSR.ʵϵͳԱ㷨͵ʱ临ӶȡýϺõĲ߽ҾкܸߵĿ.
ؼʡAgent,غвߣϵͳȺϵͳJava
ͼšTN41.4TN-052
AN PARALLEL ROUTING SYSTEM BASED
ON AGENT ORIENTED TECHNIQUE
ZHUANG Chang-Wen, FAN Ming-Yu, LI Chun-Hui, and YU Jue-Bang
(Department of Opto-Electronic Technology, University of Electronic Science and Technology of China, Chengdu 610054)
AbstractDetailed routing is the last step of VLSI circuit's physical design. Routing can be classified into switchbox routing and channel routing, both of which are NP-complete. By using agent-oriented technique, a parallel switchbox router (PSR) is developed based on computer network using Java. This system can make full use of available computing resources in a local network. The experiment results show that this router has low complexity and high scalability.
Key wordsagent, switchbox routing, parallel system, ant colony system, Java
1
AgentչǳѸ٣ѾеõӦã13.ĿǰAgentͳһĶ壬ڲͬӦŲͬĺ.вY.ShohamAgentĶ壬һʵ(belief)(capability)(decision)ͳŵ(commitment or obligation)Ⱦ״̬ʱʵAgent4.
ϸVLSI·Ƶһ裬ҪΪغвߺͨߣ5,6.VLSI·΢׹շչԲ㷨µܣʱӡġšҪ󣬲ߵѶҲ.µĲϵͳҪԴ͸Ƚʵּ˲мͼܷӦҲҪ.
֪InternetķչΪṩ˺嫵ϢԴҲΪṩǿļԴü磬ǿʵָٵĲмϵͳ7,8.
Ĳвϵͳͨ磬Agent.ϵͳȽȺ㷨911ǿ֮Ӧ⿪غв.ϵͳеAgentΪ3ֱ࣬ΪAgentغAgent͵Agent.Agentͨڴ滥ͨţЭͬѧϰγǿȺΪЧؽӵĿغв⣬ԴClient/Serverģʽ˲вϵͳPSRиǿļͺܸߵĿ.
2غв
غSBһMQݺ.SBNαΪ1,2kN-1,N.ÿţŰҪֲڴϡ¡ҷ.غ˫㲼ߵҪ:˳SBMQߣγɶӦڸһͨNΣTkkĸΪ䶥㼯Vk.ε֧ɷֲSBϡ㣬ɽ(vias)ͨڱ֤ͨǰ£ܳȺ͹ӦС.ͼ1һغм䲼߽غй6ıϵĺڷʾһţ12ţ23.ڿغвNPȫ⣬ģıʱ佫ָ˱ĽüܷAgent˷.

ͼ1غSB䲼߽

3ϵṹ
вϵͳһЭͬѧϰAgentɣЩAgentΪ3ֱ࣬ΪAgentغAgent͵Agent.ͼ2ʾ3AgentֱڲͬĲϣͨвϵͳֻһAgentһ̨ϣغAgentnnв벼ߵļֱ̨еn̨Уÿ̨ſغAgentļ϶NAgentNضغĸǲ.ֱ3AgentĹ.

ͼ2Agentķ༰
(1)Agent
ڲϵͳÿ̨϶NAgentУÿAgentͨغеһNAgentͨԼʱغв߾ͳɹ.Agent˷ǿȺ㷨IACS(intensified ant colony system)㷨M.DorigoȺϵͳ9,10ݵĻϣǿõģ11.һAgentԿΪһȺȺĿǰ״̬иŵ˽ṹԼǰ򣬲ʵʱǲһѸǰĳţ϶һϣžͻ.AgentΪֱӰ쿪غвʵϣAgentϵͳĺģԴǽڵ3һ.ÿAgentͨԼ޷ʱֹͣߣȻԼڻϵĿغAgent沼߽.ڿغеĲٽԴAgentͬ.
(2)غAgent
ڼ֮غAgentAgentעԼпмϣ벢вϵͳпغв.Agentյж֮ͬ⿪غAgent󣬲ضغеϢͨ緢͸ӦĿغAgent.ǵ͵Client/Serverģʽģʽʹϵͳи߿.
غиĲɸAgentɵģغAgentɸAgentҽյAgentָʾڲʵĳʼڸAgentγɶݵȼ.յAgentĲ߽֮󣬽ЩϴAgent֮ȴAgentķָʾԽһεֹͣ߹.
(3)Agent
AgentλAgentϲ㣬ԸغAgentע󣬲йͨ紫͸غAgent.ҪǽԸغAgentĲ߽ȻͳơԱ´εȡøõĽ.ЩѲͨûвͨؼ߳ǷҪ.Agent֮󣬾еֹͣ۴͸ϵĿغAgentָʾǼֹͣ.ֹͣԺ󣬵AgentĲ߽͵ָļ.
4Agent
ϽAgentǲвϵͳĺģͨAgentЭͬγǿȺΪŽ˿غв.3AgentУAgentߣԼǰ£غͬһĸŻ.ΪʵAgentM.DorigoȺϵͳ.
M.Dorigo1992һַ㷨ϵϵͳ(ASAnt System)9ݣL.M.Gambardellaֽ䷢չΪȺϵͳant colony systemACS֮ӦTSP⣬˽Ŵ㷨(GA)ģ˻㷨(SA)ݻ滮㷨(EP)ŵĽ10.
ȺϵͳAgentƵĻƣǾɼ򵥵ĸΪӵȺΪ.ף11ȲǿȺϵͳIACSϸߣڱǽIACSĻ˼븳AgentAgentԣȺһڿغУ֮㲼һߣһ֮㲼ͨ.Agentн£
1.Ŀ·.ڲ߹УAgentһµλúѼĿ·ϢѡнԵ.ЩϢ:
ǰޱ;
ǰǰڱţУжٸ;
Agentǰλ뱾ĳ൱ʱҪĿĿɵԼ⣬·.
ͼ3ʾAgentӱ£λAǰp൱ΪĿ꣬AgentǲеO㣻ˣAgentμABOACOAA1B1OAA2B2O·ǷͨǷȺЩͨ·.

ͼ3ױŵĿɵԼ
2.ֱﴦ.ͨ٣ǰ//ҲڱŻͨɵԼֱۣAgentΪڽĳţֻʣһͨ·ЩAgentͲȴڵǰ㵽֮䲼Ͻߣͨ.
3.ͣȻǰ.Agentнʱֱﴦһһ༴Ųһ񣬵λãҪѼϢ١ڡ.⣬ǵֻиAgentͨ˸غеĲɣˣÿAgentнʱֻܵԹԵȥɱȺĲҲҪչ˵AgentȥǸԵҲЭͬķʽͬ.ֿǣµĻЭͬԭͣȻƣĳAgentһλú󣬽ǰǷһδEûAgentһǰAgentͨӦʾǷͣȴһʱwԸAgentͨEĻᣬEĳ·.Ϊˣ㷨һʴСͣW0W0ȡ0.9,Ǿ˵ͣȵĸΪ90ǰĸΪ10.ͣȻƺ󣬿ЧرⲻͬAgentòĳͻ.
4..ÿAgent붨Ŀ()ԱĴС.Ŀǰǵ㷨ֱAgentࡢҲࡢǰǰ4ϵҶԼ㵥pΪ

(1)
УG1һĳ|cp.x-p.x|=1or|cp.y-p.y|=1AgentpĺΪ1AgentпͬһϹΥ߹.
5.ѡн.Agentֻǰһ(Խ)нܺ.ɹʽ1͵õ4ĴСAgentۺϿǺ󣬽ǣ³ɼǰķн.ͼ3ʾAgentӱ£λAҲǰһţֱΪtp(ͼ3).֮ϵΪ1Ϊ0.ȻAgent䣨򶫣߳ϻǰ߳Agentɱ£߽ӹĿ.ԣʱAgent鿴ܷ񾭹A1ܣѡϷΪǰܾA1Agentٲ鿴ܷǰȵ.
ᣬAgentֹͣߣ򿪹غAgent沼߽ת1.
AgentнпԿAgentѾ൱ܣȫܹԼݺ;ԼΪԼԤ.֮Agent֮ЭͬAgentϵ·ĳţͨţΪAgent¸Ŀѡ·ټͣȻƣǼǿAgent˸ӵȺΪ.
5ʵ
ǸԲAgenṭʵ˲вϵͳPSRΪJavaϵͳΪWindows95AgentǻJavaĶ̻߳ʵֵ.JavaԵƽ̨޹ԣʹвϵͳ칹УͬϵAgent֮׽ӿڽͨţϵͳƽֲTCP/IPЭInternetϣԳϵĿмԴ.ȻڸAgent߳ʵ֣ϵͳҲһ̨Уֻʱʧȥϲе.
ϣһغв⣬ļǹ̶ģҪ㷨ĵ3AgentsܺͿغⱾȷ.WܼWs㷨дмWpǲмȻǵ㷨мϵͳn̨һضĿغвߣ㸺طֲn̨ϣٱSΪ

2
ʽ2һ

3
Уf=Ws/(Ws+Wp).
ϣnܴʱٱȿԴﵽS=1/f.
⣬ڸĿغУдϢҪΪ߽䴫߳ȷ.߳LΪ600󣬴·ݾҪ2Lֽڣ1200ֽڣԼ1KֽڣǵķʵУ10̨΢ɵ̫ܵĴΪ2L10ֽڣ10Kֽڣھǲӵģ⣬ǵ㷨дзСʽ3֪PSRϵͳܹܸߵļٱ.
ڷʵУPSRһЩ͵Ŀغн˲.ʵøϵͳɻñWEAVERMIGHTYBEAVERGAP׼͵ļ㸴Ӷȣϵͳи߿.ͼ1ͼ4ǲвϵͳɵĲ߽1ͱ2ǵĲвϵͳPSRͬ׼(benchmark)6ݵıȽϽ.


ͼ4Bursteinв߽
1ֲ㷨ԸܶȿغеıȽ

㷨߳ʱ()
GSR36529?
MIGHTY32530?
BEAVER275291
GAP295292281
PSR315292


2ֲ㷨BursteinѿغıȽ

㷨߳ʱ()
WEAVER415311508
BEAVER445471
GAP365381831
PSR425384


Ϊʾϵͳĸ߿ԣBursteinУڴ1̨10̨˲вϵͳͼ5ʾ.ԵʱΪ׼ϵͳٶȣYᣩ̨Xᣩ.ȻͨſӰ죬ԲͬĿغʵϵͳõļٱȻ仯ϵͳȻ. 

ͼ5ϵͳٶȵ
6ۼĹ
ǲAgentʹJavaһʵ˲вϵͳȺϵͳĻ˼븳Agent.ʵʾϵͳԽԣ֤AgentĿ.һǽڶ㲼гԲAgentоAgentĹʵַ.
õйʿĿ.
߼飺ׯģУ19698ʿоҪоΪܡVLSI
ͼ.
ڣŮ19626ʿҪоΪӦáVLSI衡ơͨϵͳ۵.
ԣŮ19713ʿоҪоΪܡVLSI衡ơ.
ʰУ193212ڣҪ·Զϵͳ缰ǡܡɵ·CADо.
ߵλӿƼѧӼϵɶ610054
ο
1Ҧ֣,.๦ܸ֪ϵͳеAgent.ѧ,1996,7(3):163167
(Yao Zheng, Gao Wen, Agent oriented technology in multiple functional perceptive system, Journal of Software(in Chinese), 1996, 7(3): 163167)
2Sandip Sen. Developing an automated distributed meeting scheduler. IEEE Expert Intelligent Systems & Their Applications, 1997, 12(4): 4145
3Kraus S, Sycara K, Evenchik A. Reaching agreement through argumentation: A logical model and implementation. Artificial Intelligence, 1998, 104(1,2): 169
4Shoham Y. Agent-oriented programming. Artificial Intelligence(in Chinese), 1993, 60(1): 5192
5, ǳ. ģɵ·ͼۺ㷨. : ѧ磬1998
(Hong Xianlong, Yan Xiaolang, Qiao Changge. The Theory and Algorithm in VLSI Layout. Beijing: Science Press, 1998)
6Lienig J. A parallel genetic algorithm for performance driven VLSI routing, IEEE Trans Evol Comput, 1997, 1(1): 2939
7ƣׯ. InternetĴڵ绷. 鱨ѧ. 1996, 15(2): 132140
(Jiang Haiyun, Zhuang Changwen. Network environment of Internet node in Sichuan province. Journal of the China Society for Sciencific and Technical Information(in Chinese), 1996, 15(2): 132140)
8ׯģ. ʵֲмȺϵͳ. Ӧ, 1998, 18(6): 1113
(Zhuang Changwen, Lin Xiaodong. Realizing parallel computing in cluster system. Computer Applications, 1998, 18(6): 1113)
9Dorigo M. Optimization, learning and natural algorithmsPh D dissertation. DEI, Politecnico di Milano, Italy, 1992
10Dorigo M, Gambardella L M. Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Trans Evol Comput, 1997, 1(1): 5366
11ׯģڣԣʰ. ЭͬʽһȺϵͳ. 뵼ѧ. 1999, 20(5): 400406
(Zhuang Changwen, Fan Mingyu, Li Chunhui, Yu Juebang. Ant colony switchbox router based on coordination mechanism. Journal of Semiconductor(in Chinese), 1999, 20(5): 400406)
ԭյڣ1999-04-26޸ĸյڣ1999-08-31.
