Abstract-Använda djup-första sökning, vi utveckla och analysera prestandan av en routing system för hypercube multidatorer i närvaro av ett godtyckligt antal felaktiga komponenter. Vi härleder ett exakt uttryck för sannolikheten för routing meddelanden via optimala vägar (av längd lika med Hamming avstånd mellan motsvarande par av noder) från källan nod till en blockerad nod. Den blockerade noden definieras som den första noden som möter meddelandet som inte hittar någon optimal väg till destinationsnoden. Även gränser för denna sannolikhet härleds i sluten form. Observera att sannolikheten för att routing meddelanden via en optimal väg mellan två noder är ett specialfall av våra resultat, och kan erhållas genom att ersätta den Obstructed noden med destination noden. Numeriska exempel ges också för att illustrera våra resultat, och visar att i närvaro av komponentfel djup-första sökning routing kan dirigera ett meddelande via en optimal väg till sin destination med en mycket hög sannolikhet. Index Terms-Coordinate sekvenser, djup-första sökning, feltolerant routing, hypercube multidatorer, inversioner. WING till deras strukturella regelbundenhet och hög potential 0 för parallellt utförande av olika algoritmer, hypercube multidatorer har dragit avsevärd uppmärksamhet under de senaste åren från både akademiska och industriella samhällen [ 11-[ 101. De topologiska egenskaperna hos hyperkuber undersöktes i [13]. System för tilldelning av uppgifter och delkuber föreslogs för att utnyttja parallellismen inom en multidator för hyperkub [2]– [4]. Många tillämpningar på hypercube multidators undersöktes [5]- [7], och flera forskning och kommersiella hypercube maskiner byggdes [8]-[ 101. Effektiv meddelande routing är en nyckel till prestanda för distribuerade minnesmultidatorer, såsom hyperkuber [ll]. För att göra hypercube-multidatorer användbara för tillförlitlighetskritiska tillämpningar har betydande forskningsinsatser gjorts för att utforma feltoleranta routingsystem för dem [ 121–[20]. En ansluten hyperkub med felaktiga komponenter kallas en skadad hyperkub. För att göra det möjligt för icke-feliga noder i en skadad hyperkub att kommunicera med varandra, måste tillräckligt med nätverksinformation antingen hållas vid varje nod eller läggas Manuscript mottagen 15 maj 1989; reviderad 11 december 1989. Detta arbete stöddes delvis av byrån för marin forskning inom ramen för kontrakt N00014-85-K-0122 och NASA inom ramen för Grant NAG-1-296. M. till meddelandet som ska ledas. För den första metoden har flera algoritmer föreslagits i [12]-[15], som i allmänhet kräver att varje hypercube nod behåller en viss mängd global information för sina routing beslut. Detta gör det dock nödvändigt att sprida uppdaterad nätinformation när nätets tillstånd ändras. Vissa radio- och TV-program i skadade hyperkuber finns också i [15] [17]. För den andra metoden, där varje nod endast måste känna till tillståndet (fel eller inte) hos dess angränsande komponenter (länkar eller noder), har flera routingsystem som bygger på begreppet djup-först sökning och dess variation föreslagits [ 181–[20]. Under en djup-första sökning routing schema, varje meddelande åtföljs av en stack som håller reda på historien om vägen rest, och försöker undvika att besöka en nod mer än en gång om inte en backtracking är påtvingad. Även om begreppet djup-först sökning är väl förstått och verkar kunna utnyttja de rikliga kopplingarna i hyperkuben och därmed uppnå en hög grad av feltolerans, varken formell presentation eller rigorös prestandaanalys av detta system har rapporterats i litteraturen. Utveckling och analys av ett feltolerant routingsystem med hjälp av djup-först sökning efter hypercube multidatorer är därför ämnet för detta dokument. Vi kommer först att utveckla ett routingsystem med hjälp av djup-först sökning, där varje nod bara behöver känna till tillståndet hos dess angränsande komponenter. Den väg som ett meddelande har korsat hålls under uppsikt av meddelandet då det leds mot sin destination. Prestanda av denna routing algoritm kommer att analyseras noggrant. En optimal väg mellan ett par noder är en väg av längd lika med Hamming avstånd mellan de två noderna. Enligt detta routingsystem kallas den första noden i meddelandets rutt som är medveten om att det inte finns någon optimal väg från sig själv till destinationen den blockerade noden. Vid den blockerade noden måste meddelandet ta en omväg. I detta dokument tar vi fram exakta uttryck för sannolikheten för optimal ruttning från källnoden till en given blockerad nod i närvaro av både länk- och nodfel. Gränser för dessa sannolikheter härleds också i sluten form, vilket kommer att visas för att nära approxima de exakta uttrycken. Observera att bestämning av sannolikheten för optimal ruttning mellan två noder är ett speciellt fall av våra resultat eftersom destination noden kan ses som en blockerad nod som är 0 hoppa bort från destination noden. Numeriska exempel ges också för att illustrera våra resultat. Det kan ses att i närvaro av komponentfel, djup-första sökning routing kan dirigera ett meddelande via 1045-9219/90/0400-0152$01.00 @ 1990 IEEE en optimal väg till sin destination med en mycket hög sannolikhet. Det är värt att nämna att begreppet djup-först sökning inte bara är användbart för feltoleranta routing i hyperkuber, utan också tillämpligt på feltoleranta och multipat routing i andra multidatorsystem såsom fyrkantiga maskor och sexkantiga maskor [21], [22]. Observera dock att djup först sökning routing måste styras för att fullt ut utnyttja anslutningar i varje multidatorsystem, och därmed, metoden för att styra djup-första sökningen beror nära på systemtopologi. Detta dokument är organiserat enligt följande. Nödvändig notation och definitioner införs i avsnitt 11. Ett feltolerant routing system med djup-först sökning efter hyperkub multidatorer presenteras i avsnitt 111. Utförandet av detta routingsystem analyseras noggrant i avsnitt IV där belysande exempel också ges. Dokumentet avslutas med avsnitt V. En n-dimensionell hyperkub definieras rekursivt som Qn = K2 x Qn-1 där K2 är den fullständiga grafen med två noder, Qo är en trivial graf med en nod och x är produktoperationen på två grafer [23]. En Qn innehåller 2" noder och n2"-" länkar eftersom graden av varje nod i en Qn är n. Låt C vara den ternära symbolen som (0, 1, * } där * är en bryr sig inte symbol. Varje subcube i en Qn kan sedan unikt behandlas av en sträng av symboler i.E. Den högra koordinaten för adressen till en subcube kommer att kallas dimension 1, och den andra till den högra koordinaten som dimension 2, och så vidare. För varje hypercube nod, kommunikationslänken i dimension jag kallas ith länk av noden. För notationell enkelhet, varje länk representeras av en binär sträng med en "-" symbol i sin motsvarande dimension. Till exempel är länken mellan noder oo00 och 0010 representeras av 0-0. Definition I: Hamming avstånd mellan två hyperkub noder med adresser U = UnUn-1.... u1 och w = wnwn-l "'w1 i en Qn definieras som n H(U, w) = x h ( u i, wi) whereh(ui, wi) Dessutom är det nödvändigt att införa den exklusiva verksamheten mellan två binära strängar, och begreppet relativ adress mellan två hyperkub noder. Definition 2: Den exklusiva driften av två binära strängar q = qnqn-l.... q l och m = m,mn-l...ml, betecknar med q e m = r n r n V l ".rl definieras som ri = 0 om qi = mi och ri = 1 i f q i =-för 1 < i i n. Vi använder @ fz1 för att beteckna k sekventiell exklusiv verksamhet. Den relativa adressen till en nod U med avseende på en annan nod w, betecknad av u /~, kan sedan bestämmas av ulw = U w. Låta ek = enenPl. . el där e k = 1 och ej = O V j # k. där var två på varandra följande noder fysiskt gränsar till varandra. Således kan en sökväg i en Qn ses som en sekvens av binära tal av n bitar sådan att varje två på varandra följande binära tal skiljer sig med exakt en bit. Antalet länkar på en stig kallas sökvägens längd. En optimal väg är en stig vars längd är lika med hammingavståndet mellan källan och destinationsnoder. Vi kommer att kalla routing via en optimal väg den optimala vägen routing. Dessutom sägs en länk av nod U vara mot en annan nod w om länken tillhör en av de optimala sökvägarna från U till w. Observera att på grund av den speciella strukturen hos en hyperkub, när källnoden för en väg av längd k i en Qn ges, kan sökvägen beskrivas med en koordinatsekvens koordinatsekvens är en sekvens av ordnade dimensioner i vilka motsvarande två angränsande noder i banan skiljer sig [24]. En koordinatsekvens sägs vara enkel om någon dimension inte inträffar mer än en gång i den sekvensen. Det är lätt att se att en väg är optimal om och endast om dess koordinatsekvens är enkel. Som visas i bild. 1 I detta avsnitt presenterar vi en adaptiv routing algoritm baserad på djup-första sökning, vilket kräver att varje nod att veta endast villkor (fel eller inte) av sina egna länkar. Fallet att en nod är felaktig behandlas som att alla länkar till noden är felaktiga. Denna algoritm kan framgångsrikt dirigera meddelanden mellan ett par anslutna, nonfaulty noder. När den otillräckliga kunskapen om felaktiga komponenter gör att ett meddelande skickas till en mellanliggande nod från vilken ingen optimal väg till destinationsnoden finns, kommer en alternativ väg att väljas på ett sådant sätt att anslutningen av en hyperkub utnyttjas fullt ut. Innan du presenterar routing algoritmen, är det nödvändigt att införa följande förslag som bestämmer, från koordinatsekvensen av en väg, de relativa adresserna för dessa noder korsas. Förslag I: Låt [c 1, c 2,. .., ck] vara koordinatsekvensen av en given väg i en Q n som börjar från nod U, och wui = w,wn-l.... w 1 betecknar den relativa adressen till nod w med avseende på U där k = H ( u, w). Därefter, den väg som anges av [cl, c 2,. ..,ck] slutar vid w om och endast om @fzl Bevis: Ett meddelande traversal längs ith dimension är samma som att invertera biten i ith koordinat av den relativa adressen till sin destination. Att färdas längs en viss dimension ett jämnt antal gånger har därför samma effekt som att inte färdas längs den dimensionen över huvud taget. Detta förslag följer således. Q.E. för j := 1, n börjar långt registreras i en uppsättning TD i samma ordning om du besöker, och kommer att levereras tillsammans med meddelandet till nästa nod. Observera att med hjälp av TDR kan varje mellanliggande nod bestämma adresserna för de noder som besökts innan TDR är backningen av TD enligt definitionen i avsnitt 11. Det är tydligt att det är mycket billigare att skicka TD tillsammans med meddelandet än att skicka adresserna till alla noder som besöks. När källkodsnoden börjar routa ett meddelande, är TD inställd till den tomma uppsättningen 4. Därför, den information som ska fasas på till nästa nod kan representeras som ( d, meddelande, TD) där d är den relativa adressen till destination noden med avseende på en mellanliggande nod, och uppdateras som meddelandet dirigeras mot destinationen. Ett meddelande når sin destination när d blir 0". När en nod får ett meddelande kontrollerar den värdet på d för att se om destinationen nås. Om inte, kommer den mellanliggande noden att försöka skicka meddelandet längs en optimal väg till destinationen. Men om alla optimala vägar blockeras av felaktiga komponenter och de noder som besökts tidigare, kommer noden att dirigera meddelandet via en alternativ sökväg med hjälp av begreppet djup-först sökning. När det inte finns någon alternativ väg tillgänglig, är backtracking påtvingad. Mer formellt, detta routing schema kan beskrivas i en algoritmisk form enligt följande. Algoritm G: Djup-första sökning routing algoritm. om ( För att ange ett meddelandes destination, skickas destinationsnodens relativa adress tillsammans med meddelandet.) Den djup-första sök routing algoritmen kommer att försöka undvika att besöka samma nod mer än en gång utom när backtracking tvingas. Således, de dimensioner som ett meddelande passerade så Observera att en mellanliggande nod kan avgöra om dess ith länk är ansluten till en nod som besöktes tidigare genom att kontrollera om ei tillhör S(T@). När backtracking tvingas måste meddelandet returneras till den nod från vilken detta meddelande ursprungligen togs emot. Detta förklarar hur vi bestämmer värdet g i segmentet kommenteras av /* Backtracking * / i ovanstående algoritm. När g = \S(TD)), CHEN OCH SHIN: RÖST I HYPERCUBE MULTICOMPUTERS vet vi att backtracking tillämpas vid källan noden, och 1111 kan därför dra slutsatsen att källan och destination noderna kopplas bort. Observera att det finns en oundviklig overhead krävs för att uppnå feltolerant routing. För att skicka ett meddelande till sin destination i en skadad hyperkub måste de noder som passerats tidigare av meddelandet göras kända för de mellanliggande noderna för att undvika meddelandelooping. Detta är själva anledningen till att under G varje mellanliggande nod måste foga till meddelandet en tagg TD, från vilken adresser noder korsas tidigare kan återvinnas i ljuset av topologin för en hyperkub. Djup-först sökning säkerställs på så sätt till priset av att bära TD med varje meddelande. Värdena för g och h i G kan enkelt bestämmas från TD. Det kan verifieras att komplexiteten i att bestämma g och h är O( ITDO. Observera att när sannolikheten för förekomst av en felaktig komponent är låg, kan ovanstående schema ändras för att minska den operativa overhead på ett sådant sätt att taggen TD bifogas meddelandet först efter felaktiga komponenter stöts på av meddelandet. Men när sannolikheten för förekomsten av en felaktig komponent är hög, är det värt att använda taggen TD från början för att fullt ut utnyttja olika vägar och noder där backtracking kan förekomma under G. Dessa noder kommer att bilda ett sökträd med 2" -k noder och 2" -k -1 länkar. Eftersom varje länk i sökträdet korsas två gånger, kommer meddelandet att passera 2.2" -k -1) hoppar i sökträdet och k hoppar på sin optimala väg till destinationen. Q.E.D. - Vad är det med dig? undvika att skicka meddelandet tillbaka till en nod som fått meddelandet tidigare. Det finns några andra tekniker som är möjliga att genomföra djup-första sökning routing för hyperkuber. Istället för att hålla hela vägen reste i TD, kan sökningen också genomföras genom att använda en stack. I ett sådant fall förenklas den åtgärd som krävs för backtracking, men ytterligare bestämmelser behövs för att säkerställa att en nod inte kommer att besökas mer än en gång. Betrakta en skadad Q 4 i bild. 2............................................................... Antag att ett meddelande f m leds från U = 0110 till w = 1001. Det ursprungliga meddelandet vid U = 01 10 är (1 11 1, f m, 4). Efter genomförandet av G, nod 01 10 skickar (1 110, f m, [l]) till nod 01 11 som sedan skickar (1 100, f m, [1, 2] ) till nod 0101. Eftersom den tredje dimensionslänken på 0101 är felaktig kommer nod 0101 att skicka (0100, f m, [1, 2, 4]) till 1101. Eftersom den tredje dimensionens länk av 1101 är felaktig kommer nod 1101 att välja en alternativ väg, och skicka (0101, f m, [1,2,4.1]) till 1100, som i sin tur kommer att skicka (0001, f m, [1, 2, 4, 1, 3]) till 1OOO. Sedan, eftersom länkar av lo00 i dimensionerna 1, 2 och 4 är felaktiga, är backtracking påtvingad och meddelandet skickas tillbaka till 1100. Det kan verifieras att meddelandet därefter skickas till sin destination via 11 10, 11 11, 101 1 och sedan 1001. Följande förslag följer direkt av det faktum att djup-första sökning är en allmän graf sökning algoritm och kan starta från någon nod i en graf [26]. Proposition 2: Algoritm G skickar ett meddelande till sin destination så länge destinationen är tillgänglig. Algoritm G är en generaliserad version av algoritmen som presenteras i [18] där antalet fel antas vara mindre än n. Dessutom, från det faktum att dessa länkar korsas inte kommer att bilda en cykel, har vi följande förslag. Noderna och länkarna genomkorsade under G bildar ett träd. Proposition 3 i sin tur leder till ett annat förslag. Det värsta fallet av G använder H ( u, w ) +2 (2" -H ( U, w ) -1) hoppar för att skicka ett meddelande från nod U till nod w för ett par anslutna noder U och w. Bevis: Låt H ( u, w ) = k, sedan finns det högst 2" -k För att illustrera prestanda djup-första sökning routing, låt oss överväga en skadad hyperkub med ett visst antal felaktiga komponenter. Alla möjliga fördelningar av felaktiga komponenter antas vara lika sannolika. Antalet felaktiga noder som krävs för att en enkel koordinatsekvens C ska vara den väg som finns vid djup-först sökning är lika med antalet inversioner i C [191. Detta faktum kan formellt anges på följande sätt. Proposition 5: Antag att H ( u, w ) = n i en Q n. Sedan, under G det minsta antalet felaktiga noder som krävs för den enkla koordinatsekvensen C = [c1, c2. .., c,] att vara den väg som bestäms av G från U till w är V ( C ). Till exempel, låt 0000 och 11 11 vara källan och destination noder, respektive. Därefter, den uppsättning noder vars fel kommer att göra G välja koordinatsekvensen [3,4,1,2] är (0001, 0010, 0101, Ollo}. Mot bakgrund av det faktum att adresser till hyperkub noder bildar en partiell ordning uppsättning, effekterna av en felaktig nod, säger x, är samma som de av en felaktig länk via vilken en mellanliggande nod försöker skicka meddelandet mot x. För ovanstående exempel, den uppsättning länkar vars fel kommer att tvinga G att välja koordinatsekvensen [3,4,1,2] är {WO-, 0-0, 010-, 01-O}. Proposition 5 kan därför förlängas och generaliseras enligt följande. Lemma 1: Låt U och w vara två noder i en skadad Qn med f-feliga länkar och g-feliga noder där H ( u, w) = n. är den väg som valts av G från U till w. Därefter f + g 2 V ( C). Kom ihåg att den blockerade noden är den första noden på en stig som är medveten om att det inte finns någon optimal väg till destinationsnoden och en omväg (dvs. icke-optimal väg) måste tas. För att underlätta vår presentation, definiera vikten av en uppsättning dimensioner för att vara deras summering, dvs, W(c1, c2,. .., c,) = ELl c, Sedan kan vi härleda följande teorem som kännetecknar prestanda G. Bevis: Det finns CT = m(m -1)/2 olika sätt att välja par (Ci, C j), i < j, från (~1, C~,. .., C, ).......................................................................................... Eftersom C är en enkel koordinatsekvens, antingen ci > c, eller ci < c j, vilket innebär att varje urval (ci, c,) kommer att räknas för antingen därmed bevisa lemma. Bevis på Theorem I: Enligt verksamheten för djup-första sökning routing, den lägsta dimensionen bland de dimensioner som inte korsas innan kommer att väljas först. Eftersom H ( u, w ) = n, valet av dimension c1 till det första humlet innebär att c1 -1 felaktiga komponenter har påträffats. Dessutom, valet av dimension c2 till det andra humlet betyder a) det finns en annan c2 -1 felaktiga komponenter påträffas om c2 < c 1, eller b) det finns en annan c2 -2 felaktiga komponenter påträffas om c2 > c1. Enligt samma resonemang vet vi att upp till den blockerade noden (dvs. den första m humle), (1,3), (2,3)}. Tydligt, IS(n, m)l = C: är antalet kombinationer av m objekt av n olika objekt. Låt Z, (k) betecknar antalet permutationer av n nummer med exakt k inversioner. Observera att värdet av Z,(k) kan erhållas från dess genereringsfunktion som anges i (1) senare [25]. Sedan, från Theorem 1 har vi följande viktiga teorem. Teorem 2: Antag att det finns f felaktiga länkar i en Q n, och ett meddelande dirigeras av G från nod U till nod w där H ( u, w ) = n. Låt hL vara Hamming avstånd mellan den blockerade noden och destination noden. Sedan där P ( E ) är sannolikheten för händelse E, L = n2"-' och m + j = n. Bevis: Eftersom fel kan uppstå vid alla f länkar i Q n, Det finns C t olika konfigurationer av felaktiga länkar. Problemet med att få P(hL = j ) minskas sedan till att räkna antalet konfigurationer som leder till fallet h~ = j. Observera att meddelandet passerar m = n-j humle innan det når den blockerade noden, vilket innebär att det finns IS(n, m) 1 möjliga platser för den blockerade noden. Utan förlust av allmängiltighet kan man anta att 0" är källnoden och 1" är destinationsnoden. Sedan finns det en en-till-ett-korrespondens mellan varje element i S(n, m) och varje möjlig plats för den blockerade noden. Överväg en blockerad nod plats x som bestäms av ett element U E S ( n, m). Låt C vara koordinatsekvensen från nod U till x. Från Theorem 1 vet vi att meddelandet har stött på V ( C ) + W ( U ) -m(m + 1)/2 felaktiga länkar innan man når x. Således kan antalet olika vägar från U till x, medan de passerar dimensionerna i U och möter k felaktiga länkar uttryckas som Z,(k -W ( U ) +m(m + 1)/2) där Z,(q) är antalet permutationer av m nummer med q exakt inversioner. För varje given koordinatsekvens till x bestäms platserna för dessa k-feliga länkar som man stöter på innan man når x. Dessutom finns det ytterligare j felaktiga länkar i anslutning till x. Observera också att m-länkar i sökvägen från U till x inte är felaktiga. Därför är antalet olika konfigurationer för en given koordinatsekvens eller sökväg till en viss blockerad nodplats x C;I:It-m = Ci:;:. Därför följer detta teorem. Q.E.D. Det är värt att nämna att fastställandet av sannolikheten för en optimal vägdragning kan ses som ett specialfall av Theorem 2 genom att ställa in den blockerade noden till destinationsnoden, dvs. fastställandet av P(hL = 0). Mer formellt har vi följande följdfråga. Corollary 2.1: Under Algoritm G, sannolikheten för att ett meddelande ska dirigeras i en skadad Qn med f-feliga länkar via en optimal väg till en destination nod som är n humle bort kan uttryckas som "bevis: Eftersom destination noden betraktas som den blockerade noden som är 0 hoppa bort från destination noden, kan man ersätta j = 0 och m = n i uttrycket i Theorem 2. Observera att det enda elementet i S (n, n) är (1, 2,..., n ) och W ( 1, 2,....,n) = n(n + 1)/2, vilket leder till denna följd. Som tidigare nämnts kan värdet av Z,(k) erhållas från sin generationsfunktion [25], eftersom Z,(k) = l/k!dkG,(0)/dzk. Det kan ses att CHEN OCH SHIN: RÖST I HYPERCUBE MULTICOMPUTERS ; =I Numeriska exempel för (2) ges i tabell 11 -B. Från tabell 11 -A och B kan det observeras att (2) mycket nära motsvarar det exakta uttrycket i korrollary 2.1. Sim- Värdena för Zn(k), för 3 5 n 5 6 och 0 5 k 5 n(n -1)/2, beräknas i tabell I. De exakta värdena för P (~L = j) kan alltså bestämmas av Theorem 2, och sannolikheten för en optimal väg routing mellan två noder kan erhållas genom Corollary 2.1. Från Corollary 2.1 och data i tabell I, Vi får tabell 11 -A som visar sannolikheterna för optimal väg routing mellan två noder n hoppar bort från varandra i en Qn med f felaktiga länkar. Det kan ses att Algorithm G i närvaro av länkfel kan skicka ett meddelande till destinationen via en optimal väg med mycket hög sannolikhet. Observera dock att när n är stort kan fastställandet av Zn(k), även om det är genomförbart, kräva en alltför stor beräkning. För att få mer insikter i G prestanda samt minska den beräkning som krävs för att erhålla P (~L = j ), en övre gräns för P (~L = j ) kan härledas i sluten form enligt följande. Lemma 3: Antag att det finns f felaktiga länkar i en skadad Q n, och ett meddelande dirigeras av G från node U till w, där H ( u, w ) = n. Därefter P( hL = j ) ICFI; / C$ om 0 5 j 5 min { n, f } där L = n2 "-" är antalet länkar i en Q n. Bevis: Som nämnts tidigare, problemet med att erhålla P( hL = j ) är att räkna antalet konfigurationer som leder till fallet med hL = j. När h~ = j, alla j länkar mot w av den blockerade noden, säger x, måste vara felaktiga. Enligt djup-först sökning, platsen för den blockerade noden bestäms av de felaktiga länkar som inte finns inom SQ(x, w ) där SQ(x, w ) är den minsta subkuben som innehåller både x och w Eftersom j länkar av nod x inom SQ(x, w ) är felaktiga, det finns CFI; olika distributioner av de andra f-j felaktiga länkar. När dessa f-j felaktiga länkar orsakar nod y, istället för x, att vara den blockerade noden, byter vi länkarna (inklusive felaktiga länkar) i S Q ( y, w ) med de i SQ(x, w), och få en konfiguration som leder till fallet när den blockerade noden är y och h~ = j. Notera att vissa av förstainstansrätten; olika distributioner av felaktiga länkar kan leda till fallet hL > j, vilket innebär att antalet konfirmationer som leder till fallet Q.E.D. h~ = j är mindre än eller lika med C f -i. P(hL = j ) = 1, en lägre gräns för sannolikheten P (~L = 0) kan härledas i sluten form enligt nedan. I ljuset av Lemma 3 och det faktum att ilarly till fallet av felaktiga länkar, prestandan av G kan analyseras med avseende på felaktiga noder som anges i följande teorem. Teorem 3: Antag att det finns g felaktiga noder i en skadad sv, och ett meddelande styrs av G från nod U till nod w där H ( u, w ) = n. Låt hN vara Hamming avstånd mellan den blockerade noden och destination noden. Sedan, för 2 5 j 5 min {g, n}, vi har, där m + j = n. Kom ihåg att källan och destination noder antas vara nonfaulty. Vi anser därför att endast Cr-' olika distributioner av g felaktiga noder. Observera också att när ett meddelande når en blockerad nod som är j hoppar bort från destinationen, måste meddelandet ha korsat n -j = m nonfaulty noder (exklusive källnoden), och blockeras av minst j felaktiga noder vid den blockerade noden. Förhållandena (fel eller inte) för dessa m + j + 2 = n + 2 (inklusive käll- och destinationsnoder) bestäms sedan från en given koordinatsekvens till den blockerade noden. Detta teorem följer således av samma resonemang som det i beviset för Theorem 2. Q.E.D. Sannolikheten för en optimal vägdragning i närvaro av g-feliga noder, dvs. P(hN = 0), kan erhållas genom Corollary 3.1 nedan. Corollary 3.I: Under Algoritm G, sannolikheten för att ett meddelande ska dirigeras i en Qn med g felaktiga noder via en optimal väg till en destination nod belägen n humle bort är k = O Proofi Observera att i detta fall är destination noden betraktas som en blockerad nod som är 0 hoppa bort från destination noden. Från en given koordinatsekvens av en optimal väg, platser n + 1 nonfaulty noder (inklusive 158 källan och destination noder) i sökvägen är kända. Denna följd kommer alltså från Theorem 3. Q.E.D. Med hjälp av tabell I och Corollary 3.1 kan vi få tabell 111-A som ger sannolikheten för optimal vägdragning mellan två noder n hoppar bort från varandra i en Q n med g felaktiga noder. Det kan ses att P(hN = 0) är större än P (~L = 0) när antalet felaktiga komponenter g = f är relativt liten jämfört med antalet noder i en hyperkub. Detta beror på att en felaktig nod betraktas som alla länkar som är knutna till noden är felaktiga, och därför kan meddelandet hitta en felaktig nod tidigare än en felaktig länk. Detta i sin tur innebär att en omväg kommer att tas tidigare i närvaro av felaktiga noder än i närvaro av felaktiga länkar. Detta är anledningen till att P (~N = 0) är större än P (~L = 0) när g = f är liten. Men när antalet felaktiga komponenter g = f är stort är P (~L = 0) större än P (~N = 0). Detta stämmer också med vår intuition eftersom det finns mycket mer länkar än noder i en hyperkub. På samma sätt som fallet med felaktiga länkar, de associerade gränserna i fallet med felaktiga noder kan erhållas från följande lemma. Lemma 4: Antag att det finns g felaktiga noder i en skadad Q n och meddelanden ska dirigeras från en godtycklig nod U till en annan nod w där H ( u, w ) = n. Därefter P (~N = j ) 5 CrJ2-i/Cf-2 om 2 5 j 5 min { n, g}, och P (~N = j ) = 0 om j = 1 där N = 2" är det totala antalet noder i en Q,. Från Lemma 4 och resonemanget som används för att bestämma den nedre gränsen av P (~L = 0), kan vi få en lägre gräns för sannolikheten P (~N = 0) i sluten form som: Numeriska exempel för (3) ges i tabell 111 -B. Det framgår av tabellerna 111-A och B att (3) nära motsvarar det uttryck som ges i Corollary 3.1, och även att Algorithm G skickar ett meddelande till destinationen via en optimal väg med en ganska hög sannolikhet i närvaro av felaktiga noder. I detta dokument presenterade vi ett routingsystem baserat på djup-först sökning. Kunskapen om antalet inversioner av en given permutation används för att analysera resultatet av detta routingschema. Antalet felaktiga linkshoder som krävs för att en koordinatsekvens ska bli koordinatsekvensen för en väg mot en given blockerad nod bestäms. Sannolikheter för routing meddelanden via optimal sökväg till givna blockerade nod platser bestäms, och deras tillhörande gränser härleds i sluten form. Genom att ställa in den blockerade noden till destination noden, sannolikheten för den optimala vägen routing mellan två noder kan erhållas som ett specialfall av våra resultat. Det visas också att detta routing system kan skicka ett meddelande till sin destination via en optimal väg med mycket stor sannolikhet. Författarna vill tacka J.-C. J. Chen på IBM för hennes hjälp med att få fram data för tabellerna I1 och 111 maj 1980, s. Det är 23-30. T. C. Lee och J. P. Hayes, "Routing och sändning i felaktiga hyperkub datorer", i Proc. Tredje konf. Hypercube Concurrent Appl., januari 19-20, 1988, s. 346-354 januari 19-20, 1988, s. Denna förordning träder i kraft den tjugonde dagen efter det att den har offentliggjorts i Europeiska unionens officiella tidning. 1. Vad är det för fel på dig? M. Gordon och Q. F. Stout, "Hypercube meddelande routing i närvaro av fel," i Proc. Tredje konf. Hypercube Comput. Ansökan, jan 19-20, s. - Jag vet inte vad jag ska göra. - 318-327. 19-20, 1988
Varje meddelande som väntar på en kanal i V IN 1 ansluten till en felaktig/osäker nod kan sedan dirigeras via motsvarande omväg i V IN REF.
Depth-first search approach for fault-tolerant routing in hypercube multicomputers
{'venue': 'IEEE Trans. Parallel Distrib. Syst.', 'journal': 'IEEE Trans. Parallel Distrib. Syst.', 'mag_field_of_study': ['Computer Science']}