Performance And Reliability Analysis Of New Fault-Tolerant .
WSEAS TRANSACTIONS on COMPUTERSRita Mahajan and Renu VigPerformance and Reliability Analysis of New Fault-TolerantAdvance Omega NetworkRITA MAHAJAN1, Dr.RENU VIG2,1Department Of Electronics And Electrical Communication,Punjab Engineering College, Chandigarh,INDIA.rita mahajan@rediffmail.com2Department of Electronics,UIET, Panjab University, Chandigarh,INDIA.renuvig@hotmail.comAbstract:- The performance and fault tolerance are two very crucial factors in designinginterconnection networks for a multiprocessor system. A new type of MIN, Fault TolerantAdvanced Omega network, which using 4 4 switches, is proposed on the basis of the idea ofthe Delta network and the Omega network. In this paper, it is proved that 4 4 switches have thebetter performance/cost ratios than 2 2 switches based on the current level of the VLSItechnology. This paper expounds its topological properties and routing algorithm and makesperformance/cost ratios comparisons. The mathematical analysis approach is used here to findthe probability of acceptance and bandwidth with change in traffic. Furthermore reliabilityanalysis of Fault-Tolerant Advanced Omega Network (FTAON) is discussed in detail, It is seenthat FTAON is more reliable and cost effective than other previously proposed MINs of similarclass. It has been also observed that it has fault tolerant and nonblocking capability in complexparallel systems.Keywords:- Interconnection Network, Advanced Omega Network, Fault-Tolerance, Reliability.1favored for processor memory connectionin large-scale shared memory machinebecause of its cost effectiveness [3]. Themodest cost of unique path MINs (a singlepath between any source and ssor systems, but then lack offault tolerance is a major drawback.A major component of these systems is theinterconnection network that enables theprocessorstocommunicateamongthemselves or with memory units. Thefailure of a component in theinterconnection network can frequentlybring down the entire system or cause asevere degradation in performance, unlesssufficient measures are taken to make theIntroductionA myriad of tasks require the computationalpower and speed made possible by es with multiple processors forscientific and commercial applications havebeen described in the literature [1]. Withthe progress of research on parallelprocessing,interconnectionnetworksprovide the communications needed in aparallel processing system betweenprocessors, between processors or memorymodulesbenefits,enhancingtheperformance of the system, requiring lowerhardware overhead. The interconnectionscheme (MIN) banyan network includingOmega networks, Delta networks have beenISSN: 1109-27501280Issue 8, Volume 7, August 2008
WSEAS TRANSACTIONS on COMPUTERSRita Mahajan and Renu VigA crucial quality for MIN servingcommunications needs of large-scalemultiprocessor systems is fault-tolerance.This paper describes the fault-tolerancemethods used in the Advanced Omeganetwork. The Fault-Tolerant AdvancedOmega network consists of an AdvancedOmega network with one additional stage atthe input allow the bypass, when desired, ofthe extra stage or the output stage. Thus, ithas a relatively low incremental cost overthe Advanced Omega network and achievesbetter reliability. The extra stage providessome additional paths from each source toeach destination. It makes the FaultTolerant Advanced Omega network as anon blocking network. Four paths areavailable between each source destinationpair if no fault exists. The distributedcontrol through the use of routing tags isavailable in the fault-tolerant AdvancedOmega network. Therefore, the faulttolerant Advanced Omega network is ananswer to the need for reliablecommunications in parallel/distributedsystems.network tolerant to such failures. Thecentral part of the MPPs, interconnectionnetwork, has three important factors:topology, routing technique and flowcontrol mechanism[13]. In order to reducethe cost of it and to improve itstransmission performance and scalability,many types of interconnection networkhave been proposed. As a large subset,Multistage Interconnection Network (MIN)are well suited to communication amongtightly coupled system components ofUMA, and offer a good balance betweencost and performance, such as Omeganetwork, Generalized Cube network, Deltanetwork , the extra stage network and theClos network [2][15-19] are proposed toimprove the transmission performance.Up to now these Multistage InterconnectionNetworks have been used in many types ofparallel computers and in most cases havebeen realized with 2x2 switches, which isavailable and convenient to research.Among them, Delta network has quite highbandwidths and performance, but itsscalability is inferior. Omega Networks area famous subclass of blocking MultistageInterconnection Networks (MINs). Theyhave been recently identified as an efficientinterconnection network for a switchingfabric of communication structures such asgigabit ethernet switch, terabit router, andATM switch[8]. Omega network has thequalities of simple routing techniques andbetter scalabilities. In section 2 it has beenproved that based on the current level ofthe VLSI technology, 4x4 switches have thebetterperformance/costratiosthan2x2 switches. Thus, this paper, on the basisof the idea of the Delta network and theOmega network, proposes the idea of a newtype of multistage interconnection networkusing 4x4 switches, the Advanced Omeganetwork. It has simple routing technique,can achieve many kinds of permutations,and has superior scalability. The evaluationof its performance shows that the AdvancedOmega network has higher performancethan Delta network, Omega network andCrossbar network.ISSN: 1109-27502 Element size: a factor ofMIN’s performance /cost ratioFrom the prospect of the art of VLSItechnique, the expanding of system scalehas made it difficult to implement manyinterconnection network configurations [5][10]. Systematic assembling is limited bythe pin limitation problem of a LSI chip.This technique in assembling is the finaldecisive factor in the nterconnectionnetwork configuration [13]. Only when thenetwork configuration, under this condition,effectively takes advantage of thesystematic assembling characteristics can itgain high performance. Even using thecurrent art of technology, it is difficult tosolve the pin limitation problem of a LSIchip. Assuring the MIN discussed in thispaper have the property that there is onlyone route between every pair of sourcenode and destination node in the networkand the number of switches of every1281Issue 8, Volume 7, August 2008
WSEAS TRANSACTIONS on COMPUTERSRita Mahajan and Renu Vig switches, but its number of switches stagesis less. That is to say, compared with thesame scale MIN using 2x2 switches, we canimprove the performance of MIN by using4x4 switches without anymore cost in termsof latency. We can say that 4x4 switcheshave the better performance/cost ratios.switches stage in the network is fixed.Then, according with the propertymentioned above, we can know that thenumber of switches needed to construct theMIN has nothing to do with the shuffle wayof the interconnection structure. Supposethe delay has a great effect on thesystematic performance and the crosspoints is a vital factor to measure themanufacture cost. So we can analysis therelationship between the number of crosspoints and the number of switches stages inthe MIN in order to approximately find outwhichswitchhasthebetterperformance/cost ratio. As the twoparameters, the scale of the MIN and that ofthe switch, decided the number of switchesin the MIN, We can use formula showed inequation (1) to calculate the number ofcross point of MIN (we can consider a crosspoint as single channel ) :S m.N. logmN ,(1)Fig. 1: Comparison in the number ofcross points of MIN using differentswitches and crossbar.where S is the number of cross point ofMIN, N is the scale of MIN, m is the scaleof switches and logmN is the number ofswitches stages. In this case, consider m 4,N 4k, k 1,2, 3 . The results are shown inTable1, Figure1 and Figure 2.Table1. Comparison in the number ofcross point of MIN using differentswitches and crossbarFig. 2: Comparison in the number ofswitch stages of MIN using differentswitches.From Figure1 and Figure 2, we can see thatthe number of cross points of MIN using4x4 switches is the same as that using 2x23 ThenetworkISSN: 1109-27501282AdvancedOmegaIssue 8, Volume 7, August 2008
WSEAS TRANSACTIONS on COMPUTERSRita Mahajan and Renu VigThe Omega network has N 2n inputs,termed as sources (S) and N outputs,termed as destinations. There exist log2Nstages and each stage has N/2 switchingelements. There is a unique path betweeneach source-destination pair. The networkcomplexity, defined as the total number ofswitching elements in the MIN is(N/2)*(log2N). In Omega network, therouting of a message from a given source toa given destination is based on thedestination address. This is termed as Selfrouting. Each bit in the destination addresscan be used to route the message throughone stage and if the bit in the destinationaddress controlling the routing in a givenstage is 0, then the message is routed to theupper output of the switch otherwise isrouted to the lower output of the switch.Figure 3 shows 8 x 8 Omega network.Some paths are also shown for destination2, 3 and 5. Routing tags are 010,011,101respectively whatever the source is. Oneproblem associated with the Omeganetwork is the high probability of blocking.Although any input may be connected toany output, it is desirable to be able toconnect other inputs to other outputs.Blocking occurs when the second andsubsequent connections cannot be made.type of MIN, Advanced Omega network,which using 4x4 switches, is proposed.This section expounds its topologicalproperties and routing algorithm and makesperformance/cost ratios comparisons.3.1 Definition ofOmega networktheAdvancedThe Advanced Omega network is a kind ofblockingmultistageinterconnectionnetwork using 4x4 switches. The interiorstructure of every switch is a 4x4 crossbar.The Advanced Omega Networks’ scale is Nx N and N 4k (k 2, 3, 4 ). The physicalnames of the switching components (stage,element and link) are assigned as follows.The stages are labeled in a sequence from 0to (log4 N) 1 with 0 for the leftmost stageand (log4N) 1 for the rightmost stage.Similarly, the levels of links are labeled in asequence from 0 to log4N. In each stage,each switching element is named by acodeword of n (log4N) 1 tetradic digits,pn pn-1 p1 . Each link in each level isnamed by a codeword of n 1 tetradic digitspn pn-1 p0. The first n leftmost digits pnpn-1 p1 ,are the same as the tetradicrepresentation of the switching element towhich the link id connected at one of fourright terminals of the switching element;the last digit, p0 , is equal to 0 if the link isconnected to the uppermost terminal of theswitching element and p0 is equal to 1, 2, 3in a sequence from 1 to 3 if the link isconnected to the below terminals. Thetopology describing rules of the AdvancedOmega network is defined byFor link (pn pn-1 p1p0 of switch (pn pn-1 p1) is connected to link (pn-1 p1p0 pn ) ofswitch (pn-1 p1p0) for each stage.The topology of the Advanced Omeganetwork can be generates in a advancedway. Figure 4 shows 16 x 16 AdvanceOmega network.Fig. 3: 8 x 8 Omega NetworkOn the basis of the idea of the Deltanetwork and the Omega network, a newISSN: 1109-27501283Issue 8, Volume 7, August 2008
WSEAS TRANSACTIONS on COMPUTERSRita Mahajan and Renu Vig4 Analysis in the Advancedomega network performanceWe evaluate the performance of theAdvanced Omega network from threeaspects: network’s pass rate, latency andperformance/cost ratio. In accordance withthe analysis model that has been made [16][22], we can compare the performance ofthe Advanced Omega network with that ofthe existing Crossbar network, Deltanetwork and Omega network.Fig.4: The advanced process toconstruct the Advanced omega Network( N 16)3.2 The Advanced omega network’srouting techniquesThe routing algorithm uses a destinationtag routing method [4], by which theAdvanced omega network can set up anymapping connection from one terminal onone side of the network to another terminalon the other side. Consider switching inputnumberS to output number D. LetD dndn-1 .d1d0 [n (log4N) 1 and 0 di 3,0 si 3] be the destination tag, and let S SnSn-1 .S1S0 be the source tag. TheRouting algorithm assigns c dn-i as therouting control signal of the switchingelement in stage i to control its state. It isset to switch the input to the no. c 1 outputof the switching element It is easy to seethat at any stage i, an input that has beenswitched to position pn pn-1 p1 p0 is thenswitched into position pn pn-1 p1 di by theswitching element, and then goes throughthe shuffle and ends up at pn pn-1 .di pi 1 .P1 . Thus, after n 1 operations, the originalinput must be connected to output dn dn-1 d1 d0. So it will certainly be able to get tothe destination properly. The AdvancedOmega network’s simple destination-tagrouting method makes it efficient and lowercost in routing.ISSN: 1109-2750Fig.5:Comparisonperformance/cost ratioswiththeFigure 5 shows the curves ofperformance/cost ratio. The numbersuggests that when N 16, theperformance/cost ratios of the AdvancedOmega network is obviously superior tothat of Crossbar, Delta network and Omeganetwork[7]. Adopting the Advanced Omeganetwork as the interconnection network ofseveral multiprocessor systems is moreattractive.4.1 Bandwidth AnalysisAdvanced omega networkintheAssume a MIN of size an x bn constructedfrom a x b crossbar switches and having anSources connected to bn destinations. Theanalysis of crossbar is applied to a x bcrossbar switch and then extended to thecomplete MIN. The distinct destinationdigit (in base b) for setting of individual a xb switches controls each stage of MIN.1284Issue 8, Volume 7, August 2008
WSEAS TRANSACTIONS on COMPUTERSRita Mahajan and Renu Vigunder(pi represents the probability of therequest to be at ith stage of links)For omega network (N 16) shown in figure6 has five link stages.Since the destinations are independent anduniformly distributed, so are the destinationdigits. The probabilistic approach is used toanalyze the MINs based on independentrequest assumptions[14]. Given the requestrate p at each of the a inputs of an a x bcrossbar module, the expected the rate ofrequests on any one of the b output linesfrom any one input is given by p/b.Probability of not getting the request is:1–p/bProbability of not getting the request fromall ‘a’ inputs is given by:(1 – p / b)aProbability of one output getting therequest from all ‘a’inputs is given by:1-(1 – p / b) aThe total number of requests that it passesper unit time is given byb- b(1-p / b)aFig. 6: 16X16 OMEGA NETWORKSince the output rate of a stage is the inputrate of the next stage, output rate of anystage can be recursively calculated startingfrom stage 1. And the output rate of finalstage n determines the bandwidth of MIN.p0 pp1 1- ( 1 –p0 /2 ) 2p2 1- ( 1 –p1 /2 ) 2Probability of acceptance (Pa): Thisparameter is defined as the ratio ofexpected bandwidth to the expected numberof request generated by a source per cycle.Thus, it is the ratio of requests matured tothe total requests generated. The probabilityof acceptance of a request is given by:Pa b n pn / a n p0p3 1- ( 1 –p2 /2 ) 2p4 1- ( 1 –p3 /2 ) 2pn p4For Advance omega network (N 16)shown in figure 4 has three link stages.(2)p0 pWhere p0 is the request rate at each of thean inputs of an an x bn MIN and pn is theexpected rate of requests on any one of thebn output lines.p1 1- ( 1 –p0 /4 ) 4p2 1- ( 1 –p1 /4 ) 4pn p2Bandwidth: It is defined as the meannumber of active memory modules in atransfer cycle of interconnection network.So BW is the total number of requestsmatured.BW bn x pnPa pn/p0BW Pa x N x pThe following graphs in figure 7 (a) and (b)show the comparative probability ofacceptanceandbandwidthw.r.t.congestion. From the results it can beinferred that as the request generationprobability increases, probability of(3)The value of pn is calculated recursively asISSN: 1109-2750and1285Issue 8, Volume 7, August 2008
WSEAS TRANSACTIONS on COMPUTERSRita Mahajan and Renu VigSpace Redundancy: Multiple paths areprovided from each input port to eachoutput port by using redundant hardwareextra stages of switches, extra switches ineach stage and/or extra links, duplicatednetwork in each switch. In the presence offaults, an alternate path can be chosen tocontinue providing access.acceptance and bandwidth is better in caseof Advanced Omega network as comparedto omega network. Hence the AON showsoverall gain in performance.Time Redundancy:Inthiscase,multiple passes through the network can beallowed to route data from an input to an output.The ability to route packets from input to outputof the network in a finite number of passes iscalled dynamic full redundancy (DFA)property.Fault-tolerance is an important qualityfor MIN serving the communication needs oflarge-scale multiprocessor systems. Variousmethods have have been discussed for faulttolerance techniques[6][21] .This sectiondescribes the fault-tolerance methods usedin the Advanced Omega network andpresent the fault-tolerant Advanced Omeganetwork that is capable of operating inSIMD, multiple-SIMD, and partitionableSIMD/MIMD environments. The faulttolerant Advanced Omega Network consistsof an Advanced Omega network with oneadditional stage at the input to allow thebypass, when desired, of the extra stage orthe output stage. Thus, it has a relativelylow incremental cost over the AdvancedOmega network and achieves betterreliability. The extra stage provides someadditional paths from each source to eachdestination [18][19]. The distributed controlthrough each of routing tags is available inthe fault-tolerant Advanced Omeganetwork. The fault-tolerant AdvancedOmega network has all of theinterconnectioncapabilitiesoftheAdvanced Omega network. Furthermore,the network can be controlled when it has afailure, using a simple modification of arouting-tag scheme proposed for theAdvanced Omega network.The proposedrouting algorithm is as follows:Fig. 7(a): Comparative Probability ofacceptanceFig. 7(b): Comparative Bandwidth5 The fault-tolerance methodsA fault tolerant MIN is one that providesservice, in at least some cases, even when itcontainsafaultycomponentorcomponents. A network is single faulttolerant if it can function as specified by itsfault tolerance criterion despite any singlefault conforming to its fault model. Moregenerally, if any set of I faults can betolerated, then a network is I-faulttolerant[20]. Fault-tolerance in a MIN canbe provided by:ISSN: 1109-2750Step1: Read the destination address dndn-1dn 2 d1 d0.Step2: Apply tag 0 dn dn-1 d1 d0. If pathfree pass the message otherwise goto step3.1286Issue 8, Volume 7, August 2008
WSEAS TRANSACTIONS on COMPUTERSRita Mahajan and Renu VigStep3: Apply tag 1dn dn-1 d1 d0. If pathfree pass the message otherwise goto step4.Step4: Apply tag 2 dn dn-1 d1 d0. If pathfree pass the message otherwise goto step5.Step5: Apply tag 3 dn dn-1 d1 d0. If pathfree pass the message otherwise wait for theaverage pass time and goto step2.Normally, the network will be set so thatstage e is disabled (bypassed) and stage n-1is enable. If the fault is in stage n-1, stage eis enabled and stage n-1 is disabled, i.e.,stage e replaces the function of stage n-1.For a fault in a link or switch in stage 0 ton-2, both stage e and n-1 will be enabled.The fault-tolerant Advanced Omeganetwork gets its fault-tolerant abilities byhaving redundant paths from any source toany destination. In the fault-tolerantAdvanced Omega network with both stagee and n-1 enabled, there exist exactly 4paths between any source a
methods used in the Advanced Omega network. The Fault-Tolerant Advanced Omega network consists of an Advanced Omega network with one additional stage at the input allow the bypass, when desired, of the extra stage or the output stage. Thus, it has a relatively low incremental cost over the Advanced Omega network and achieves better reliability.
Test-Retest Reliability Alternate Form Reliability Criterion-Referenced Reliability Inter-rater reliability 4. Reliability of Composite Scores Reliability of Sum of Scores Reliability of Difference Scores Reliability
Human reliability analysis is the study of how human performance affects the reliability of systems in which humans determine, in whole or in part, the performance of the system. Human reliability analysis is usually part of a risk assessment in which other, nonhuman components and subsystems are also modeled. Human reliability analysis may be .
Reliability Infrastructure: Supply Chain Mgmt. and Assessment Design for reliability: Virtual Qualification Software Design Tools Test & Qualification for reliability: Accelerated Stress Tests Quality Assurance System level Reliability Forecasting: FMEA/FMECA Reliability aggregation Manufacturing for reliability: Process design Process variability
posing system reliability into component reliability in a deterministic manner (i.e., series or parallel systems). Consequentially, any popular reliability analysis tools such as Fault Tree and Reliability Block Diagram are inadequate. In order to overcome the challenge, this dissertation focuses on modeling system reliability structure using
Reliability Analysis Center First Quarter - 2000 A Discussion of Software Reliability Modeling Problems By: Jorge Romeu, Reliability Analysis Center Introduction A quarter of a century has passed since the first software reliability model appeared. Many dozens more, of various types, have been devel-oped since. And many practitioners still dis-
Evidence Brief: Implementation of HRO Principles Evidence Synthesis Program. 1. EXECUTIVE SUMMARY . High Reliability Organizations (HROs) are organizations that achieve safety, quality, and efficiency goals by employing 5 central principles: (1) sensitivity to operations (ie, heightenedFile Size: 401KBPage Count: 38Explore furtherVHA's HRO journey officially begins - VHA National Center .www.patientsafety.va.govHigh-Reliability Organizations in Healthcare: Frameworkwww.healthcatalyst.comSupporting the VA’s high reliability organization .gcn.com5 Principles of a High Reliability Organization (HRO)blog.kainexus.com5 Traits of High Reliability Organizations: How to .www.beckershospitalreview.comRecommended to you b
Electronic Parts Reliability Data (2000 pages) Nonelectronic Parts Reliability Data (1000 pages) Nonoperating Reliability Databook (300 pages) Recipe books: Recipe book: MIL-HDBK-217F Military Handbook 338B: Electronic Reliability Design Handbook Automotive Electronics Reliability SP-696 Reliability references:
Electronic Parts Reliability Data (2000 pages) Nonelectronic Parts Reliability Data (1000 pages) Nonoperating Reliability Databook (300 pages) Recipe books: Recipe book: MIL-HDBK-217F Military Handbook 338B: Electr onic Reliability Design Handbook Automotive Electronics Reliability SP-696 Reliability references:
