35,66 €
Mehr erfahren.
- Herausgeber: Bentham Science Publishers
- Kategorie: Wissenschaft und neue Technologien
- Sprache: Englisch
This textbook provides a quick and easy understanding of multistage interconnection networks (MINs) for engineers. The book contents focus on the design, performance metrics, and evaluation of these networks which are crucial in modern computer architecture. The contents equip engineering students, apprentices and professionals with in-depth knowledge and analysis of MINS, enabling them to build complex computer architectures for efficient data communications and cost effective solutions for circuit design. The book starts with an introduction to MINS and subsequently progresses to the evaluation of a range of MINS (SEN, Gamma-Minus, FTSN, FTGN, SEGIN).
Key highlights of the book include:
· Easy to understand notes on design, reliability and fault tolerance
· Covers a wide range of MIN types with notes on design variants
· Supplementary information aiding comprehension of the main content.
· A curated list of references for further exploration and deeper understanding.
Das E-Book können Sie in Legimi-Apps oder einer beliebigen App lesen, die das folgende Format unterstützen:
Seitenzahl: 338
Veröffentlichungsjahr: 2001
Ähnliche
BENTHAM SCIENCE PUBLISHERS LTD.
End User License Agreement (for non-institutional, personal use)
This is an agreement between you and Bentham Science Publishers Ltd. Please read this License Agreement carefully before using the ebook/echapter/ejournal (“Work”). Your use of the Work constitutes your agreement to the terms and conditions set forth in this License Agreement. If you do not agree to these terms and conditions then you should not use the Work.
Bentham Science Publishers agrees to grant you a non-exclusive, non-transferable limited license to use the Work subject to and in accordance with the following terms and conditions. This License Agreement is for non-library, personal use only. For a library / institutional / multi user license in respect of the Work, please contact: [email protected].
Usage Rules:
All rights reserved: The Work is the subject of copyright and Bentham Science Publishers either owns the Work (and the copyright in it) or is licensed to distribute the Work. You shall not copy, reproduce, modify, remove, delete, augment, add to, publish, transmit, sell, resell, create derivative works from, or in any way exploit the Work or make the Work available for others to do any of the same, in any form or by any means, in whole or in part, in each case without the prior written permission of Bentham Science Publishers, unless stated otherwise in this License Agreement.You may download a copy of the Work on one occasion to one personal computer (including tablet, laptop, desktop, or other such devices). You may make one back-up copy of the Work to avoid losing it.The unauthorised use or distribution of copyrighted or other proprietary content is illegal and could subject you to liability for substantial money damages. You will be liable for any damage resulting from your misuse of the Work or any violation of this License Agreement, including any infringement by you of copyrights or proprietary rights.Disclaimer:
Bentham Science Publishers does not guarantee that the information in the Work is error-free, or warrant that it will meet your requirements or that access to the Work will be uninterrupted or error-free. The Work is provided "as is" without warranty of any kind, either express or implied or statutory, including, without limitation, implied warranties of merchantability and fitness for a particular purpose. The entire risk as to the results and performance of the Work is assumed by you. No responsibility is assumed by Bentham Science Publishers, its staff, editors and/or authors for any injury and/or damage to persons or property as a matter of products liability, negligence or otherwise, or from any use or operation of any methods, products instruction, advertisements or ideas contained in the Work.
Limitation of Liability:
In no event will Bentham Science Publishers, its staff, editors and/or authors, be liable for any damages, including, without limitation, special, incidental and/or consequential damages and/or damages for lost data and/or profits arising out of (whether directly or indirectly) the use or inability to use the Work. The entire liability of Bentham Science Publishers shall be limited to the amount actually paid by you for the Work.
General:
Any dispute or claim arising out of or in connection with this License Agreement or the Work (including non-contractual disputes or claims) will be governed by and construed in accordance with the laws of Singapore. Each party agrees that the courts of the state of Singapore shall have exclusive jurisdiction to settle any dispute or claim arising out of or in connection with this License Agreement or the Work (including non-contractual disputes or claims).Your rights under this License Agreement will automatically terminate without notice and without the need for a court order if at any point you breach any terms of this License Agreement. In no event will any delay or failure by Bentham Science Publishers in enforcing your compliance with this License Agreement constitute a waiver of any of its rights.You acknowledge that you have read this License Agreement, and agree to be bound by its terms and conditions. To the extent that any other terms and conditions presented on any website of Bentham Science Publishers conflict with, or are inconsistent with, the terms and conditions set out in this License Agreement, you acknowledge that the terms and conditions set out in this License Agreement shall prevail.Bentham Science Publishers Pte. Ltd. 80 Robinson Road #02-00 Singapore 068898 Singapore Email: [email protected]
PREFACE
In order to meet the demanding needs of ever-increasingly computationally intensive applications, such as SCADA, power distribution and management with prior load prediction, plasma dynamics for fusion energy applications, electronic structure calculations for the design of new materials and their characterization, fluid dynamics, the study of turbine behavior for electricity generator, weather prediction, and global climate change, military surveillance, symbolic computations, data mining for modeling business and financial processes, ocean sciences, enhanced oil and gas recovery, airbus design, nuclear weapon detonation, etc., Big Data Analysis must be conducted for these applications from several nodes dispersed across various locations. Fast calculation and communication are needed for this big data, which are made possible by the numerous processors connected to supercomputers.
The implementation of the switching fabric of high-capacity communication processors, such as ATM switches, gigabit Ethernet switches, and terabit routers, is also becoming more commonplace. MINs are frequently used in the context of SIMD (single-instruction multiple-data) and MIMD (multiple-instruction multiple-data) parallel machines. For instance, the nodes of the CARY X-MP and IBMSP series are typically connected using MINs. Real-world examples of practical applications that use MINs for communication include ATM Switches, the Butterfly parallel processor, the IBM SP series, the IBM research prototype RP3, AMD64, SPARC, MIPS, PA-RISC, Alpha, STARAN by Goodyear Aerospace Corporation, Ethernet switches and routers, IBM Power microprocessors, and the NYU ultra-computer.
The interconnection of these supercomputers' component parts, such as the processor and their memory modules, is crucial for the reliable operation of the system. Multistage Interconnection Networks (MIN) are typically used as interconnection systems for these frameworks due to the growing number of processors in supercomputer systems. MINs consist of multiple stages of a small interconnection network known as SE connected in a predefined connection pattern. MIN provides a compromise between a highly efficient and expensive crossbar network and a bus network, which is very cost-effective but at the same time, it provides data communication at very slow rates. MIN not only provides efficient communication at low cost but it also offers high fault tolerance capability, availability of multiple paths, high bandwidth, throughput, etc. Therefore, since MIN's development, researchers have been quite interested in finding ways to improve its reliability.
A lot of designs based on regular (uniform connection pattern between stages and a number of Switching Elements (SE) are also the same in each stage) and irregular (non-uniform connection pattern between stages and number of SE are also not same in each stage) MIN topologies have been proposed in the last five decades. During the last three decades, regular rectangular (number of input and output nodes are same) MIN, primarily the Gamma Interconnection Network (GIN) and the Shuffle Exchange Network (SEN), by offering numerous routes between each Source-Destination (SD) node pair, have been investigated and improved. The majority of the improvements were made by adding more hardware (either by expanding the size or quantity of SE per stage or by expanding the number of stages). Despite the fact that SEN and GIN have received a lot of attention, there are following points that need to be highlighted. (i) Literature on these topics lacks organization and classification; (ii) certain aspects, such as complexity, cost, the number of disjoint pathways under the assumption that the source and destination are fault-free, low latency, high bandwidth and throughput, CPU usage, etc., remain to be investigated; (iii) hardware reduction (number of SE/Stages); (iv) less research has been done on all three reliability evaluation metrics, including fault tolerance, network reliability (NR), broadcast reliability (BR), and terminal reliability (TR), for networks larger than 8×8.
In this book, these issues have been discussed and resolved by presenting the (i) Classification of SEN and GIN, (ii) A method based on using MUX and DEMUX of various sizes such as 2×1/1×2, 4×1/1×4 etc. at input and output stages respectively; (iii) Suggestions on connection patterns for MUX and DEMUX at input and output stages, respectively and (iv) design of MIN with fewer stages and more entirely isolated pathways.
ACKNOWLEDGEMENT
Success in life is never attained single handily. My deepest gratitude goes to my Professor, Dr. Gobind Lal Pahuja, Professor, NIT, Kurkukshetra for his guidance, help and encouragement throughout my work. His enlightening ideas, comments, interpretations and suggestions increased my cognitive awareness and helped considerably in the fruition of my objective.
I also wish to place my heartfelt thanks to all the worthy colleagues and friends for their critical suggestions and encouragement during the entire work. I am also thankful to all the anonymous reviewers of my research papers, whose contribution I will always value from the core of my heart. Fortunately, I have understanding friends, juniors and seniors who have helped me on many critical conditions. My sincere thanks to all those who have directly or indirectly provided me moral support and other kind of help. I like to express with all humility my indebt-ness towards my children and husband. Their love, affection and inspiration have given me the courage in difficult times. I just hope to live up to their expectations.
Finally, I wish to thank the Almighty, who has blessed me with the power to think and to articulate my thoughts. The book would have never been possible without his grace and guidance.
Multistage Interconnection Networks: Introduction
Shilpa Gupta1Abstract
Tremendous advancements have been reported in the computer and communication industries due to the high demands of big data analysis. This led to the use of parallel and distributed processors to play a part. These parallel processors have to be connected to a large number of memory modules. The connection between these processors and memory modules must be highly reliable for efficient big data analysis. Multistage interconnection networks (MIN) provide data communication between processors and memory modules at efficient speed with reasonably high reliability. This chapter provides a detailed introduction to MINs with their evolution and characterization. Further in this chapter, the research trends among researchers about various classes of MINs have also been discussed.
1.1. History and Evolution
Since the inception of Integrated Circuits (ICs) in 1959, there is a phenomenal growth in the field of VLSI technology in the form of computer and communication technologies [1-12]. To fulfill the demanding specifications of continuously increasing computational intensive applications such as power management at the substations and their load predictions, database management, and data mining, controlling and analyzing nuclear fusion reactions, characterization of materials at micro and nanoscale, fluid dynamics, weather prediction, navigation for security purpose and military surveillance, ocean sciences, advanced graphics and virtual reality, refineries, the detonation of nuclear weapons, quantum mechanics, networked videos and multimedia technologies, cryptanalysis, medical imaging and diagnosis etc., it is necessary to process efficiently at a very fast rate. [1-3, 5]. Though at present, computations of the order of Tera-Flops are feasible but the applications also have increased phenomenally in terms of computations requirement, and ultra-high speed is the need of the day. To cope with these technological advancements, higher transmission rates are needed with efficient processing, which are made amenable by using multiple processors connected in parallel and are termed as parallel or
distributed systems [6, 8]. These parallel or distributed systems can be characterized into three different classes; these are:
Pipelined computersArray processorsMultiprocessor systemsIn pipelined computers, the instructions are executed in an overlap fashion, whereas, array processors consist of a processing element (PE), a control unit (CU) and an interconnection network (IN). CU broadcasts the set of instructions to all PEs and PEs execute these instructions in a lock-set-up fashion, whereas IN is a communication network that communicates data between PEs and their respective memory modules. Array processors are also known as SIMD machine which performs the computation of array or matrices of data streams [7, 8, 12].
A multiprocessor system is a computer consisting of multiprocessors with their shared or individual memory modules. A single integrated operating system controls all the processors connected through an interconnection network in multiprocessing systems. These processors asynchronously or autonomously execute different instructions on different data and are considered as MIMD machines [2, 6, 9]. Multiprocessing systems can further be classified into two groups:
Loosely coupled multiprocessing systemsTightly coupled multiprocessing systems.Loosely coupled multiprocessing systems: also known as distributed systems. In these systems, processing elements contain their own memory modules as well as I/O devices (local memory modules and I/O devices). These elements communicate through interconnection networks. Most of the data in these systems is accessed from its own local memory.
Tightly coupled multiprocessing system: In these systems, PEs use shared memory modules, although, each PE may contain small local memory in the form of a small cache. INs are used to provide communication paths between all PEs with their shared memory modules and I/O devices [3] in these systems as well.
Fig. (1) shows the classification of parallel computer systems and Fig. (2) shows the configuration of loosely coupled and tightly coupled systems.
Fig. (1)) Classification of Parallel/ Distributed computing system.During the continuous research in parallel and distributed computing systems, researcher were attracted toward finding the efficient communication media, which can communicate data packets efficiently between multiple fabricated components. INs were found as an efficient communication media for these systems [4-7].
1.2. Interconnection Network
The early advancement of INs was motivated by the growing demands of the communication industry such as telephone switching. But with the growth of the computer industry and the advent of fast packet-switching networks, the application of INs became apparent. Early INs for parallel processing have now found application in fast packet-switching designs [8]. The need for fabricating hundreds and thousands of PEs on a single chip came into play where crossbars became a bottleneck. Researchers started considering the possibility to find cost-effective communication media which can connect thousands of processors to their respective memory modules [9]. In the early 70s, a network consisting of small cross-bar switches i.e. Switching Elements (SEs) connected in multiple stages was fabricated on a single chip to provide communication between each source and the desired destination, known as Multistage interconnection Networks (MINs) [1-8]. MINs had become a favorite choice for multiple/distributed processing systems due to their fault tolerance capability, multipath availability, cost-effectiveness, etc. [13-20]. From the early 80s, the majority of research has reported improvements or development in these types of MINs to provide communication through more number of paths with increased fault tolerance and reliability at a reduced cost [9-14, 21]. The design of IN is primarily based on the following factors:
Fig. (2)) (a) Loosely Coupled Multiprocessing System and (b) Tightly Coupled Multiprocessing System. Modes of operations of INs: There may be two modes of communication possible through INs i.e. synchronous or asynchronous. In synchronous mode of operation, all nodes connected to INs are synchronized through one global clock. These are basically used in data manipulation applications. In asynchronous mode of operation, no global clock is used.Control strategy of INs: INs consist of a number of SEs connected in some predefined pattern and these connected SEs are to be controlled for their proper functioning. If this control setting function is managed by centralized control, then it is known as centralized control, whereas if this control function is managed by individual SE, then it is known as a distributed control strategy.Switching methodologies: Major switching methodologies used in INs are: Circuit switching: In this type of switching, a dedicated path has been established between each source to every destination.Packet switching: In this type of switching, the long data sequences are divided into small data packets and are transmitted through INs.Integrated switching: It includes the capability of transmission using both types of switching techniques.Network Topology: Network topologies of INs can be subdivided into three categories, these are: Static Topology: In static topology, dedicated paths have to be established between each Source-Destination (S-D) node pair. For data transmission, paths are established using routing algorithm. A simple example of static topology is the bus network. Transmission through bus topology is very time consuming as it transmits only one packet at a time.Dynamic Topology: Dynamic topology is based on the establishment of paths by reconfiguring the active elements in a certain pattern. Dynamic topology can be built up as single stage MIN.Hybrid Topology: Hybrid networks are those networks that have complicated structures such as hyper-graph topologies.Classification of IN has been modified as shown in Fig. (3), Crossbar networks provide full connectivity between all input and output nodes of a system. These networks are considered non-blocking single-stage networks. Crossbar networks are considered an expensive way of transmission in parallel processing systems, whereas MINs provide cost-effective communication, hence preferred over crossbar networks [16-17]. Table (1) lists important hardware features of IN and a summary of performance parameters in IN is shown in Table (2).
Fig. (3)) Classification of Interconnection Networks (INs).1.3. Multistage Interconnection Network (MIN)
To provide fast, efficient, and reliable communication at a reasonably low cost for parallel processing systems, many networks have been introduced which are midway between completely crossbar networks and single bus networks. These networks are called Multistage Interconnection Networks (MIN), which are connected forms of single or multiple stages of some active components capable of forwarding data packets based on some priority Logic called Switching Elements (SE). Table (2) shows the performance parameters of three types of Interconnection Networks (INs) varying from single bus to Fully Cross-bar Networks.
From Table (2), it is evident that the use of MIN reduces the cost of an overall network. MINs are of two types:
Single-stage MINs are called re-circulating networks, which consist of a single stage of SEs. Data packets are circulated through one stage of SEs several times before getting delivered to the destination.Multistage INs are built from several single stages of the network inter-connected to each other. In these networks, one time passing through each stage is sufficient for data packets to be delivered to the destination. The connection pattern of MIN between the input and output terminal determines its functional characteristics.MIN consisting of multiple stages of single-stage network contains SEs with a small buffer. This buffer is used to store the packets in case of congestion and large data traffic. The smallest element, which is used as an active element in these MINs, is 2×2 input buffer crossbar SE which is shown in Fig. (4).
Fig. (4)) 2×2 input-buffered SE.These SEs take a packet from the input port, check its destination, and then forward it to the desired output link. If the required output link is busy then that packet is buffered so as to deliver it whenever the output link is empty or free. This process is called blocking of the data packets. These blocked packets are re-transmitted to the destination in the next consecutive clocks. In the synchronous design of a system, all SEs are connected to the same Global Clock, i.e. all SEs perform their function at the same time.
In MIN, successive stages are connected in a predefined connection pattern, which is called a permutation function [22-25]. This permutation or connection between each stage must satisfy one condition, i.e. each input port should be connected to every output port through some transmission path of a network. In other words, a network should possess full connectivity between all source terminals and destination terminals. Different topologies of MIN result due to the presence of different permutations between their stages, for example, the Delta Network of size N×N contains perfect shuffle between its successive stages [26]. The total number of stages in Delta networks is log2N, where ‘N’ is the number of inputs or outputs [27].
There are three basic forms of connections through a network, which are:
One-to-one connection, in which there is a direct connection between inputs and outputs where data packets are transmitted through one input port to one output port through one of its configurational paths known as the terminal path.Multiple one-to-one connections, in which multiple sources transmit their data packets to multiple destinations, provided that no two sources or destinations must be the same, through any of its path configurations known as a network path.One-to-multiple connections, in which one source transmits data to a multiple number of destinations. This communication is associated with the broadcast path.To transmit a data packet from a given source to the desired destination, it needs some Routing Tag to perform this operation. These Routing Tags are defined as a way of describing a path through a network with the help of a distributed network control. These Routing Tags may consist of multi-digit integers, where each digit may specify a connection of SE in the current stage to SE in the successive stage. There are three methods of generating routing tags for each source to select fault-free paths. These are:
Non-Adaptive Routing: When a source, which is attempting to establish path, strikes with any faulty component, then only it will get to know about that fault. After knowing that fault, the source will choose an alternative path. This process is very time-consuming and has poor performance.Adaptive Routing: In this routing, a source maintains a list of faults that occurred, which can be used for future routing. This information is collected by sending notification to all paths for the required destination. Broadcast adaptive routing is also a type of adaptive routing. In this scheme, a packet is broadcasted to every destination and checked whether this packet has reached to all destinations or not. If that packet has not been delivered to any of the destination, then that path is considered as faulty path in which fault may be detected and saved for future use.Dynamic Routing: In this routing scheme, all SEs encountered in specified paths are capable of revising the routing tag in the presence of a fault in the successive stage.In addition to offering effective communication at a reasonable cost, MIN also has high fault tolerance, multiple paths, high bandwidth, and throughput, among other features. The first MIN was in 1958 by Clos [28], and this was used in switching exchange in telephone systems, but it did not attract the attention of researchers. However, the MIN by Benes (1962) attracted the attention of researchers. It became notable and was used in simple systems [13]. MIN developed by authors in the early 70s was used in many applications, which include Delta networks and Data Manipulators [22, 29]. Since then, MINs have been improved a lot to cope up with the computing demands of today’s supercomputer systems. Real-world examples of practical applications that use MINs for communication include the Butterfly parallel processor [14], IBM research prototype RP3 [16], IBM SP series [16], STARAN by Goodyear Aerospace Corporation [18], Asynchronous Transfer Mode (ATM) switches [15], Ethernet switches and routers [15, 17], and the NYU ultra-computer [19]. Over the last three and a half decades, many researchers have contributed to improvements in MINs either by proposing new topologies or improving the existing topologies of MINs [16-19]. MINs on the basis of packet communication may be classified in three categories. These are:
Blocking Network: In these networks, connection between input/ output (I/O) node pair is not always possible because of the contentions [16, 17].Non-blocking: These networks have a property to establish a connection between Source-Destination (S-D) node pair despite the fact that there are several existing S-D routes, if no two sources go to the same destination [17–19].Rearrangeable/Reconfigurable networks: In these networks, any input node can be connected to any free output node by rearranging the existing paths, where multiple paths are a prerequisite.These three classes are further divided into sub-classifications which are shown with the help of a tree diagram in Fig. (5). There exists a number of classifications of MIN in the literature [16-19], where Fig. (5) shows the classification of MIN on the basis of packet communication.
MINs can also be classified on the basis of their topology [30-122]. These topologies are defined as:
Unique Path MIN: MIN with single path between each source to every destination is called unique path MIN. The unique path property in MINs enables routing to be performed in a simple manner. But full access capability is destroyed by the failure of a single component that has a significant probability for large networks.Multipath MIN: MIN with multiple paths between each source to every destination is called Multi-path MIN. The fundamental purpose for offering multiple paths for every single input-output pair is to provide fault tolerance when there are network failures. Multi-path MINs are again classified into two groups. These are: Regular Multipath MIN: If the number of SEs is the same in each stage, then the MIN is called a regular MIN. The regular class of MINs is further divided into two groups. These are: Unidirectional MIN: If a network is constructed from Switches and Links which can forward data in one direction (source to destination) only, provided that the source nodes are equal to the destination nodes of the network, then it is called a unidirectional MIN.Bidirectional MIN: If a network is constructed from Switches and Links which can forward data in both directions (source to destination or destination to source), and source nodes and destination nodes are distinct, then the network is called Bidirectional MIN.Irregular Multipath MIN: If the number of SEs is not the same in each stage, then the MIN is called irregular MIN.Fig. (5)) Classification of MINs [16-19].MIN is referred to as a square of size N×N, if it has 'N' number of inputs and outputs respectively connected by SEs as the number of input and output is the same. MIN has a feature of efficient crossbar networks and low cost of bus networks [20] and additional capability of fault tolerance due to an increase in the number of path sets [20-22], high bandwidth and throughput [24].
Fig. (6) shows the classification of MIN based on their topologies. Regular MINs possess same path length in general, which put a limit on their computational speed. Irregular networks, due to variable path lengths, make computations and recombination of data packets at the receiver’s end, more complex.
Fig. (6)) Classification of MINs based on topology and permutations.Among these designs till early 90s and afterwards, in the first two decades of the 21st century, most of the work [28-31, 42-47, 49-51, 55, 62-66, 69-76, 78-82, 84, 87-90, 93, 98, 100-101, 105-106] belong to regular topology mainly, Shuffle Exchange Network (SEN) and Gamma Interconnection Network (GIN). The trends towards the improvements can be well understood by the data on MIN publication shown in Table (3). From the data, it is clear that SEN has been regularly explored since the late 70s for reliability and fault tolerance, especially for regular SEN MINs. On the other hand, work on Gamma MIN started in the late 80s and the trend continues till date. One of the main reasons behind this trend of research in regular SEN and Gamma networks is their high reliability achieved with a simple structure.
Most of the advancements in research were aimed at improving the performance metrics of the network by proposing MIN of larger size using larger-sized components. Most of the work that exists is on the development of (i) the number of stages (SEN+1, SEN+2, Gamma+, etc.), (ii) the number of SEs in the given stage (SHSEN, Incomplete Gamma etc.), (iii) the size of SE used (Augmented SEN (ASEN), 3-Disjoint Gamma, etc.), (iv) replicating the whole network (Replicated ASEN, etc.), etc. The general goal of designing these reliable MINs with increased hardware and cost was to possess the desired level of performance in the presence of faults, high reliability and upholding high computational speeds. Though a large number of techniques/frameworks for MIN have been developed with improved performance indices but still there is a lot of scope in developing new techniques with increased fault tolerance, bandwidth and reliability with reduced cost. The next section describes the review of existing MIN.
1.4. Performance Metrics
The performance of a MIN is vital for an efficient computing system. It is desired that the performability of MIN to be employable in practical systems should be high. There are several performance parameters of MIN on which basis their designs and selection for various applications depend. These parameters are:
I. Reliability
II. Fault-Tolerance
III. Cost/ Cost-effectiveness
IV. Bandwidth
V. Throughput
VI. Probability of acceptance
VII. Processor utilization
1.4.1. Reliability
The likelihood that a system will complete its intended task successfully in a set amount of time under the specified operating conditions is one way to define reliability. Another way to define reliability is as a measure of connectedness between specific S-D node pairs. There are three measures of reliability in terms of connectivity mentioned as under:
Terminal Reliability (TR): TR is referred to as the likelihood that there will be at least one successful path between two specified or designated nodes. In order to construct a path between any S-D node pair, also known as Source-to-Terminal (ST) Reliability, the network is said to have failed.Broadcast Reliability (BR): The chance that at least one path exists from one input source to all destinations is known as BR. Source-to-All-Terminal (SAT) Reliability is the term used to describe this reliability.Network Reliability (NR): The network's entire connectivity pathways are represented by NR. It is described as the likelihood that there will be at least one fault-free path connecting all sources and destinations. All-Source-to-All-Terminal (ASAT) Reliability is the common name for it.1.4.2. Fault Tolerance
A network's capacity to run with the necessary functionality even in the presence of faults is referred to as fault tolerance. Faults in MIN can be permanent or transient in nature. Most of the faults are considered to be permanent and non-repairable [26, 41-42, 46-47, 50-51, 64-65, 74, 76, 78-79, 82, 91, 95, 98, 100]. So fault tolerance is an important feature that a network should possess. Systems with enhanced fault tolerance have increased reliability and availability. MIN is considered to be one fault-tolerant if it can tolerate a single fault in the network, or in general, it can be said that the network is i-fault tolerant if it can tolerate ‘i’ number of faults.
1.4.3. Cost and Cost Effectiveness
The cost of any MIN is a crucial factor because the cost of the MIN used is what drives the system costs the most. One popular method stated in the literature for calculating the cost of MIN involves calculating the overall complexity of the switch used in that network. Also, the complexity of SE is defined as the number of gates or the total number of cross-points used in that SE. For instance, a 2×2 switch has a complexity of “4 units (2×2),” which equates to a total hardware cost. Each and every element utilised in MIN has a cost, which may be estimated using Eq. (1.1).
(1.1)where, NOM: number of Multiplexer (MUXs)
NOD: number of Demultiplexer (DEMUXs)
NOS: number of switches.
Cost-effectiveness is also an important feature of MIN and is considered one of the performance indexes [4-42, 45, 69, 73].
1.4.4. Bandwidth
It is a crucial parameter that must be examined for synchronous MIN. It is described as the quantity of accepted input requests per unit of time. A bandwidth (BW) additionally considers memory access problems brought on by the input requests' unpredictable nature [18]. In other words, it is the total number of requests that have reached maturity or the anticipated number of requests that will reach their destinations in any given cycle. Therefore, having a large bandwidth is a feature of MIN that is desirable and should be affordable [18, 34].
1.4.5. Throughput
The most traffic that a network can handle in a given amount of time is referred to as its throughput. In other terms, it is the average number of packets that a network delivers from source to destination in a given amount of time. The units of measurement are packets per node each cycle. It gives the network the ability to send packets to their intended location [18, 34].
1.4.6. Probability of Acceptance
It is described as the relationship between projected bandwidth and predicted request volume per cycle. Expected requests refer to the request made in a random access situation by the source. [18, 34].
1.4.7. Processor Utilization
It is the expected amount of time that a processor is engaged. When a processor does calculations on its own without consulting global memory, it is said to be active [18, 34]. The next chapters provide mathematical details on these parameters and computational methods.
CONCLUSION
The reliability assessment of MINs is very important as it plays a key role in enhancing the efficacy of parallel and distributed systems and big data analysis. A thorough study of MINs depicts that lot of research has been pursued in enhancing the reliability of regular MINs as compared to irregular MINs. Regular MINs have simple topology and are easy to design and implement in network-on-chip (NoC). The two most important topologies i.e. shuffle exchange networks and gamma interconnection networks are the most prominent in MINs. Hence, all reliability parameters in this chapter are discussed in consideration of these two networks only.
