
Computer Engineering
1999ꡡ259ڡVol.25 No.9  1999



άmeshϵӦݴ·㷨

ժҪڹϿģ˶άmeshϵӦݴ·㷨㷨Ϊ磮ϢԴĿĽڵλжϽһ磮ϢûϹʱ··ɣ㷨ݴǻڹϻ͹ĸ󣬽㷨һάmeshϵݴ·㷨f-cube2ܱȽϣ
ؼʣϿģͣϻ磬Ӧݴ·
Adaptive Fault-tolerant Routing Algorithm for Two-dimension Mesh
Li Jieliang Sun Suolin
(Dept. of Computer Science, National University of Defense Technology, Changsha 410073)
AbstractWe present an adaptive deadlock-free fault-tolerant routing algorithm in two-dimersion mesh, which is based block fault model. The algorithm decomposes the network into two virtual networks, VIN0 and Vin1. According to the relative position of source and destination mode. it determines which virtual network the message is routed into. Messages are routed minimally when not blocked by fault. The fault-tolerant techniques are departent on the concept of fault ring and fault chain. At last, we compare the algorithm with f-cube2, which is another fault-tolerant routing algorithm in two-dimension mesh.
Key wordsFault block model; Fault-ring; Fault chain; Virtual network; Adaptive fault fouting
ѧѸͷչԼѧµսҪһϵͳ󡢸ӳ̶ȸߵ⡣ɴ˴ʹϵṹ߶ȲлչдѳΪѧͼϵṹеһоȵ㡣
ģдϵͳ(MPP)û罫ڵÿڵиԵĴͱ档ڵ֮䲢йͬһ񣬴Ӷṩ˺ܸߵĲԡڵ֮ͨ罻ݺͽͬ˻ӰMPPϵͳܵҪ֮һ
MPPϵͳйϿɷڴ桢I/OϵͳԼ硣ֻǽڵϺ·ϡ
1о
MPPϵͳе·㷨
DallySeitzͨо·㷨ͨǷʱʹõ·ڽڵΪÿͨһСͨͨͼеĻӶϢݹб֤
GlassNinάmeshk-ary n-cubeͨĲӦ·㷨˶άάmeshϿֵܳȻֹеĳЩתԷֹȻҪ··ɣһԴĿĽڵԼ佫ֻһ·Խ֮ΪӦ·ɡǻͨĽתģ㷨ʹ֮nάmeshеn-1ϣȻάάmeshֻۣȷԻд֤ʵ
BoppanaChalasani˹Ͽ顢ϻ͹ĸԷݴ·㷨ơڴ˻˶άmeshϽͨݴ·㷨f-cube2ǵ㷨ȷԵģԲߡĽǵĻģάmesh ϵӦݴ·㷨㷨ֻͬͨ
2ģ
㷨ǶάmeshϵӦݴ·㷨㷨¼ٶ(1) ԴڵSĿĽڵD޹ϵģ(2) ÿ·˫ģ(3) ÿǹϽڵ֪Χڵ·״̬
2.1 ģ
ϼFָǹϽڵ͹·ļϡΪ˷·㷨ǽBoppanaChalasaniĹϿ(f-region)ĸָǣ(1)ı߽ϽзǹϽڵ·(2)ڲйϽڵ·FеÿϽұضһϿ顣ϿĲ˶άmeshĹϼϡ
Ͽͬб߽б߽磬ʹָΪ֣迼ǡ
2.2 ϻ͹γ
ÿڵ֮·״̬ڵxϣھӽڵƶϳ·ԼڵxϡڹϿģУÿڵֻһάй·ڵxڶά϶й·֮ΪϽڵ㣬ֹͣ״̬źŸھӽڵ㡣ù̷ûµĽڵ·Ϊϡ
ӻƹ޹ϲ(ڵ·)Ϊջγɹϻγɹϻ״ΪΡϻϵĽڵϽڵ(hop)
3Ӧݴ㷨
Ƚ绮ֳVIN0VIN1VIN0VIN1еͨÿ·ĴVIN0VIN1иһֱͨΪc0c1
ĿĽڵԴڵʱϢѡVIN1ĿĽڵԴڵ㶫ʱϢѡVIN0޹£ϢõȫӦ··㷨
㷨ǰȸи
Դڵ S(s1,s0)
ĿĽڵ D(d1,d0)
·ɱ־ R(r1,r0)=(d1-s1,d0-s0)
ͨ cdim,dir,numdimʾάdirʾnumʾ
޹͹ϻغµݴ㷨ϢڽͨǰȸRжϽһ硣׼£
if (r0>0) VIN0
if(r0<0)VIN1
if(r0=0)ѡһ
㷨1 άƽVIN0ϵӦݴ·㷨tf
(1) ޸R
if (RǼС&&r030) misroute=0
else misroute=1 /*RǼСļr0r1ǼС*/
(2) if(R==0) Ϣͷ΢ƬĿĽڵ㲢
(3) if(ĿĽڵ·޹ϵ&&misroute==0){
direction = null;
ͷ΢ƬѡһĿĽڵ··}
(4) if(direction == null) {
if(r0>0&&c0,+,0)
then if (r1>0) direction =ʱ
if (r1<0) direction =˳ʱ
if (r1=0) directionѡ
if(r1>0&&c1,+,0) direction =˳ʱ
if(r1<0&&c1,-,0) direction =ʱ}
(5) ͷ΢Ƭdirectionָķ·
VIN1ϵ·㷨VIN0ϵ㷨ơڴ˲
Tf㷨֤
1 Tf㷨ڿģ޻
֤ΪVIN0еϢVIN1У֮Ȼ漰ܷVIN0VIN1СǼϢVIN0УVIN1е֮ͬ
û£Ϣֻڵ0ά͵һά·ɣԲֻܳȴҲͲܳ
ϢϹϻʱϢƹϻ3֣(1)ϢӹϻƵߡʱϢܽеתΪϵϡ(2)ϢӹϻıƵϱߣϢܽеתΪϡϵϣ(3)ϢӹϻϱƵߣϢܽеתΪһκ޹ʱƣϢֻ򶫡ڶƣϢֻڹϻϡ߽ϡڹϻϱ߽£Ϣֻܽϡϵͱ5תǣγһڹϻߵ֮ơϢ·ɵ·Լܵתǣͼ1ʾϢһάϲתһάҲ
tf㷨޹͹ϻغʱġ
⣬ΪϢûʱõ··ɡϢ뿪һϻҲصԭĹϻеĹϻĿ޵ģϢսĿĽڵ㣬tf㷨޻ġ

ͼ1Ϣϻʱ·ɵķ
(ߴֵܳת)
4ģ
ǲһ¼ķtf㷨f-cube2㷨ģ⡣·ϵͨʱָõķҽϢͨʱƬתͨռھӽڵ䣬һʱڴһ΢Ƭģ1616meshҼÿϢΪ20΢ƬϢʹƽģʽģУʹƽƽӳΪܱȽϵı׼ȱȽ޹£f-cube2tf㷨ܡͼ2űȽ㷨ͬͬĿµܣͼ3

ͼ2޹tff-cube216x16meshе

ͼ3 tff-cube2ڹµ
ͨͼ2ͼ3֪޹ϣtf㷨ܶf-cube2ҪáΪtf㷨õӦ㷨˵ѡ··ɣԱܿ͹ϵĸԸ
5
ĻڹϿģ˶άmeshϵӦݴ·㷨tfǵ㷨ͻģڳֶϿʱԿȷ޹Ͻڵ·Ϣ㷨ӵۺ͸еġڵھӽڵ·״̬ݴγɹϻ㷨಻֮ڶάmeshϻ͹Ǿο飬ҪһЩڵΪϽڵ㣬˷ϵͳԴ״ĹϻݴΪݴоȵ㡣
߼飺(1975)УоҪMPPϵͳͨо
ߵλѧѧϵɳ410073
ο
1 Boppana RV,Chalasani S.Fault-tolerant Wormhole Routing Algorithms for Mesh Networks.IEEE Trans.Computer,1995,44
2 Dally WJ,Seitz CL.Deadlock-free Message Routing in Multiprocessor Interconnection Network.IEEE Trans.Computer, 1987,36
3 Glass CJ,Ni LM.The Turn Model for Adaptive Routing. Proc. 1992 Int'l Symp.Computer Architecture,1992:278-287
ոڣ1998-11-30
