UNIT -3 Interconnection Network Design An interconnection network in a parallel machine transfers information from any source node to any desired destination node. This task should be completed with as small latency as possible. It should allow a large number of(Such transfers to take place concurrently. Moreover, it should be inexpensive as compared to the cost of the rest of the machine. The network is composed of links and switches, which helps to’Send the information from the source node to the destination node. Ainetwork is specified by its topology, routing algorithm, switching strategy, and flow control mechanism Organizational Structure Interconnection networks are composed of following|three basi¢ components — Interconnection networks ate composed of following three basic components - Links - A link is a cable of oné)or more optical fibers or electrical wires with a connector at each endhattached to a)switch or network interface port. Through this, an analog signal is transmitted from one end, received at the other to obtain the original digital information stream. Switches = A switch is composed of a set of input and output ports, an internal “oross-bar" connecting, all input to all output, internal buffering, and control logic to effect the input-output eonnection at each point in time. Generally, the number of input ports is equal to the number of output ports. Network Interfaces - The network interface behaves quite differently than switch nodes and may be connected via special links. The network interface formats the packets and constructs the routing and control information. It may have input and output buffering, compared to a switch. It may perform end-to-end error checking and flow control. Hence, its cost is influenced by its processing complexity, storage capacity, and number of ports. Interconnection NetworkInterconnection networks are composed of switching elements. Topology is the pattern to connect the individual switches to other elements, like processors, memories and other switches, A network allows exchange of data between processors in the parallel system Direct connection networks - pirect networks have point-to-point connections between neighboring nodes. These networks are static, which means that the point-to-point connections are fixed. Some examples of direct networks are rings, meshes and cubes. Indirect connection networks - indirect networks have no fixed neighbors. The communication topology can be changed dynamically based on the application demands. Indirect networks can be subdivided into)three parts: bus networks, multistage networks and crossbar switches. Bus networks — A bus network is composéd»of a number of bit lines onto which a number of resources are attached, When busses use the same physical lines for data and addresses, the data and the address lines are\time multiplexed When there are multiple bus-masters attached to the bus, an arbiter is required. Multistage networks ~A multistage network.consists of multiple stages of switches. It is composed of ‘axb’ switches which are connected using a particular interstage connection pattern (ISC). Small 2x2 switch elements are a common choice for many multistage networks. The numberof stages determine the delay of the network. By choosing different interstage connection patterns, various types of multistage network can, be created. Crossbar switches - a crossbar switch contains a matrix of simple switch elements that can switehyon and off to create or break a connection. Turning ‘on a switch elementiin the matrix,a connection between a processor and a memory can be made. Crossbar switches are non-blocking, that is all communication permutations can be performed without blocking. Evaluating Design Trade-offs in Network Topology If the main concern is the routing distance, then the dimension has to be maximized and a hypercube made. In store-and-forward routing, assuming that the degree of the switch and the number of links were not a significant cost factor, and the numbers of links or the switch degree are the main costs, the dimension has to be minimized and a mesh built In worst case traffic pattern for each network, itis preferred to have high dimensional networks where all the paths are short. In patterns where each node iscommunicating with only one or two nearby neighbors, it is preferred to have low dimensional networks, since only a few of the dimensions are actually used. Routing The routing algorithm of a network determines which of the possible paths from source to destination is used as routes and how the route followed by each particular packet is determined. Dimension order routing limits the set of legal paths so that there is exactly one route from each source to each destination. The one obtained by first traveling the correct distance in the high-order dimension, then the next dimension and so on. Routing Mechanisms Arithmetic, source-based port select, and table look-up ate thrée mechanisms that high-speed switches use to determine the outpiit channel from information in the packet header, All of these mechanisms are simpler than the kind of general routing computations implemented in traditional LAN and WAN routers. In)parallel computer networks, the switch needs to make the routing, decision for all its inputs in every cycle, so the mechanism needs to be'Simple and fast. Deterministic Routing ‘A routing algorithm is deterministic if the route taken by a message is determined exclusively by its source and destination, and not by other traffic in the network. If a routing algorithm onlyyselects shortest paths toward the destination, it is minimal, otherwise it is non-minimal, Deadlock Freedom Deadlock can occur in/a various situations. When two nodes attempt to send data to each other and each begins sending before either receives, a ‘head-on’ deadlock may occur. Another case of deadlock occurs, when there are multiple messages competing for resources within the network. The basic technique for proving a network is deadlock free, is to clear the dependencies that can occur between channels as a result of messages moving through the networks and to show that there are no cycles in the overall channel dependency graph; hence there is no traffic patterns that can lead to a deadlock. The common way of doing this is to number the channel resources such that all routes follow a particular increasing or decreasing sequences, so that no dependency cycles arise.Switch Design Design of a network depends on the design of the switch and how the switches are wired together. The degree of the switch, its internal routing mechanisms, and its internal buffering decides what topologies can be supported and what routing algorithms can be implemented. Like any other hardware component of a computer system, a network switch contains data path, control, and storage Ports The total number of pins is actually the total number of input and output ports times the channel width. As the perimeter of the chip grows slowly compared to the area, switches tend to be pin limited. Internal Datapath The datapath is the connectivity between each of the set of input ports and every output port. It is generally referred to as the internal cross-bar. A non.blocking cross- bar is one where each input port canbe connected to a distinct output in any permutation simultaneously. Channel Buffers The organization of the biiffer'storage within\the switch has an important impact on the switch performancé, Traditional routers and switches tend to have large SRAM or DRAM buffers external to the switch fabric, while in VLSI switches the buffering is internal to the switch and.comes out of the same silicon budget as the datapath and the control séction. As the chip size and density increases, more buffering is available and the network designer has more options, but stil the buffer real-estate comes ata prime choice and its organization is important. Flow Control When multiple data flows in the network attempt to use the same shared network resources at the same time, some action must be taken to control these flows. If we don't want to lose any data, some of the flows must be blocked while others proceed. The problem of flow control arises in all networks and at many levels. But it is qualitatively different in parallel computer networks than in local and wide area networks. In parallel computers, the network traffic needs to be delivered about as accurately as traffic across a bus and there are a very large number of parallel flows on very small-time scale. Parallel AlgorithmAn algorithm is a sequence of steps that take inputs from the user and after some computation, produces an output. A parallel algorithm is an algorithm that can execute several instructions simultaneously on different processing devices and then combine all the individual outputs to produce the final result. Concurrent Processing-: The easy availability of computers along with the growth of Internet has changed the way we store and process data. We are living in a day afid. age where data is available in abundance. Every day we deal with huge volumes of data that require complex computing and that too, in quick time. Sometimes, we need to fetch data from similar or interrelated events that occur simultaneously.This is, where we require concurrent processing that can divide a complex task and process |it multiple systems to produce the output in quick time. Concurrent processing is essential where the task involves processing a huge bulk of complex data. Examples include ~ accessing large databases, aircraft testing, astronomical calculations, atomic! and nuclear »physics,/ biomedical analysis, economic planning, image processing, robotics, weathet forecasting, web-based services, etc. Types of Array Processor Array Processor performs computations on large array of data. These are)two types of Array Processors: Attached Array Processor, and SIMD Array Processor. These are explained as following below. 1. Attached Array Processor : To improve the performance of the host computer in numerical computational tasks auxiliary processor is attached to it.Attached array processor has two interfaces. Input output interface to a common processor. Interface with a local memory. Here local memory interconnects main memory. Host computer is general purpose computer. Attached processor is back end machine driven by the host computer. The array processor is connected through)an J/O controller to the computer & the computer “treats it as an external interface. 2. SIMD array processor : This is computer with multiple process unit operating in parallel Both types of array processors, manipulate vectors but their internal organization is different. SIMD isa computer with multiple processing units operating in parallel. The processing units are synchronized to perform the same operation under the control of a common control unit. Thus providing a single instruction stream, multiple data stream (SIMD) organization. As shown in figure, SIMD contains a set of identical processing elements (PES) each having a local memory M. Each PE includes -ALU Floating point arithmetic unit Workingregisters Master control unit controls the operation in the PEs. The function of master control unit is to decode the instruction and determine how the instruction to be executed. If the instruction is scalar or program control instruction then, it is directly executed within the master control unit. Main memory is used for storage of the program while each PE uses operands stored in its local memory. Whether you're preparing for your first job interview or aiming to up skill in this ever-evolving tech landscape, are your key to success. We provide top-quality content at affordable prices, all gearedstowards accelerating your growth in a time- bound manner. Join.the millions we've already empowered, and we're here to do the same for you Searching Algorithms Searching Algorithms are designed to check for an element or retrieve an element from any data structure where it is stored. Based on the type of search operation, these algorithms are generally classified into two categories: 1, Sequential Search: In this, the list or array is traversed sequentially and every element is checked. For example:2. Interval Search: These algorithms are specifically designed for searching in sorted data-structures. These type of searching algorithms are much more efficient than Linear Search as they repeatedly target the center of the search structure and divide the search space in half. For Example:- Binary search Searching Algorithm: 1. Linear Search 2. Sentinel Linear Search 3. Binary Search 4. Meta Binary Search | One-Sided Binary Search 5. Ternary Search 6. Jump Search 7. Interpolation Search 8. Exponential Search 9. Fibonacci Search 10. The Ubiquitous Binary Search MIMD Architecture:- wimp. stands for Multiple- instruction multiple-data streams. It includes parallel architectures are made of multiple processors and multiple memory modules linked via some intercénnection hetwork. They fall into two broad types including shared memory or message passing A shared memory, system generally accomplishes interprocessor coordination through a’global memory shared by all processors. These are frequently server systems that communicate through a bus and cache memory controller. The bus/ cache architecture alleviates the need for expensive multi- ported memories and interface circuitry as well as the need to adopt a message-passing paradigm when developing application software. Because access to shared memory is balanced, these systems are also called SMP (symmetric multiprocessor) systems. Each processor has anequal opportunity to read/write to memory, including equal access speed ee | [=] << merconnection Network << Co Gy Gre) Shared Memory MIMD Architectures a jercommection Network y Oo © © [| [i] Message Passing MIMD Architectures ‘A message-passing system is also defined as distributed memory. It generally combines the local memory and processor at each node of the interconnection network. There is no global memory, so it is important to transfer data from one local memory to another using message passing.This is frequently done by a Send/Receive pair of commands, which should be written into the application software by a programmer Thus, programmers should understand the message-passing paradigm, which contains data copying and dealing with consistency problems. Commercial examples of message-passing architectures c. 1990 were the nCUBE, iPSC/2, and multiple Transputer-based systems.\