CSCI 8150 Advanced Computer ArchitectureGeneralized Multiprocessor SystemSlide 3Interconnection Network ChoicesDigital BusesBus SystemsHierarchical Bus SystemsBridgesCrossbar Switch and Multiport MemoryMultistage NetworksCrossbar NetworksCrosspoint Switch DesignSchematic of a Crosspoint SwitchMultiport MemoryMultiport Memory ExamplesOmega NetworksOmega Network without BlockingBlocking EffectsOmega Network with BlockingOmega BroadcastSlide 21Larger SwitchesOmega Network with 44 SwitchesButterfly NetworksHot SpotsDealing With Hot SpotsImplementing Fetch&AddThe Cost of Fetch&AddCSCI 8150Advanced Computer ArchitectureHwang, Chapter 7Multiprocessors and Multicomputers7.1 Multiprocessor System InterconnectsGeneralized Multiprocessor SystemGeneralized Multiprocessor SystemEach processor Pi is attached to its own local memory and private cache.Multiple processors connected to shared memory through interprocessor memory network (IPMN).Processors share access to I/O and peripherals through processor-I/O network (PION).Both IPMN and PION are necessary in a shared-resource multiprocessor.An optional interprocessor communication network (IPCN) can permit processor communication without using shared memory.Interconnection Network ChoicesTimingSynchronous – controlled by a global clockAsynchronous – use handshaking or interlock mechanismsSwitching MethodCircuit switching – a pair of communicating devices control the path for the entire duration of data transferPacket switching – large data transfers broken into smaller pieces, each of which can compete for use of the pathNetwork ControlCentralized – global controller receives and acts on requestsDistributed – requests handled by local devices independentlyDigital BusesDigital buses are the fundamental interconnects adopted in most commercial multiprocessor systems with less than 100 processors.The principal limitation to the bus approach is packaging technology.Complete bus specifications include logical, electrical and mechanical properties, application profiles, and interface requirements.Bus SystemsA bus system is a hierarchy of buses connection various system and subsystem components.Each bus has a complement of control, signal, and power lines.There is usually a variety of buses in a system:Local bus – (usually integral to a system board) connects various major system components (chips)Memory bus – used within a memory board to connect the interface, the controller, and the memory cellsData bus – might be used on an I/O board or VLSI chip to connect various componentsBackplane – like a local bus, but with connectors to which other boards can be attachedHierarchical Bus SystemsThere are numerous ways in which buses, processors, memories, and I/O devices can be organized.One organization has processors (and their caches) as leaf nodes in a tree, with the buses (and caches) to which these processors connect forming the interior nodes.This generic organization, with appropriate protocols to ensure cache coherency, can model most hierarchical bus organizations.BridgesThe term bridge is used to denote a device that is used to connect two (or possibly more) buses.The interconnected buses may use the same standards, or they may be different (e.g. PCI and ISA buses in a modern PC).Bridge functions includeCommunication protocol conversionInterrupt handlingServing as cache and memory agentsCrossbar Switch and Multiport MemorySingle stage networks are sometimes called recirculating networks because data items may have to pass through the single stage many times.The crossbar switch and the multiported memory organization (seen later) are both single-stage networks.This is because even if two processors attempted to access the same memory module (or I/O device at the same time, only one of the requests is serviced at a time.Multistage NetworksMultistage networks consist of multiple sages of switch boxes, and should be able to connect any input to any output.A multistage network is called blocking if the simultaneous connections of some multiple input-output pairs may result in conflicts in the use of switches or communication links.A nonblocking multistage network can perform all possible connections between inputs and outputs by rearranging its connections.Crossbar NetworksCrossbar networks connect every input to every output through a crosspoint switch.A crossbar network is a single stage, non-blocking permutation network.In an n-processor, m-memory system, n  m crosspoint switches will be required. Each crosspoint is a unary switch which can be open or closed, providing a point-to-point connection path between the processor and a memory module.Crosspoint Switch DesignOut of n crosspoint switches in each column of an n  m crossbar mesh, only one can be connected at a time.Crosspoint switches must be designed to handle the potential contention for each memory module.Each processor provides a request line, a read/write line, a set of address lines, and a set of data lines to a crosspoint switch for a single column.The crosspoint switch eventually responds with an acknowledgement when the access has been completed.Schematic of a Crosspoint SwitchMultiport MemorySince crossbar switches are expensive, and not suitable for systems with many processors or memory modules, multiport memory modules may be used instead.A multiport memory module has multiple connections points for processors (or I/O devices), and the memory controller in the module handles the arbitration and switching that might otherwise have been accomplished by a crosspoint switch.Multiport Memory ExamplesOmega NetworksN-input Omega networks, in general, have log2n stages, with the input stage labeled 0.The interstage connection (ISC) pattern is a perfect shuffle.Routing is controlled by inspecting the destination address. When the i-th highest order bit is 0, the 22 switch in stage i connects the input to the upper output. Otherwise it connects the input to the lower output.Omega Network without BlockingBlocking EffectsBlocking exists in an Omega network when the requested permutation would require that a single switch be set in two positions simultaneously.Obviously this is impossible, and requires that one of the permutation requests be blocked and tried in a later pass.In general, with 22 switches, an Omega network can implement n n/2 permutations in a single pass. For n = 8, this is about 10% of all possible permutations.In general, a maximum of