Dynamic Interconnection Networks BusesOverviewBig PictureInterconnection Network Taxonomy [5]Addressing and Timing [2]Bus arbitrationIndependent Request and Grant [1]Bus allocation techniques [1]Bus Pipelining [1]Slide 10Split Transactions [1]Slide 12Burst Messages [1]Avalon BusTraditional Multi-MastersSimultaneous Multi-Master BusMaster Arbitration SchemeSet Arbitration PriorityAddress Decoding [4]Data-Path Multiplexing [4]Master Read Transfer [3]Master Write Transfer [3]Slave Read Transfer [3]Slide 24Slave Write Transfer [3]Slide 26References1Dynamic Interconnection NetworksBusesCEG 4131 Computer Architecture IIIMiodrag Bolic2Overview•Basic theory on buses –Arbitration–High performance bus protocols•Avalon bus3Big PictureInterconnection NetworksM M M MP P P P PFocus of this lecture4Interconnection NetworkStaticDynamicBus-based Switch-based1-D 2-D HCSingle MultipleSS MSCrossbarInterconnection Network Taxonomy [5]5Addressing and Timing [2]•Bus Addressing•Broadcast: –write involving multiple slaves•Synchronous Timing: –All bus transaction steps take place at a fixed clock edges –simple to control–suitable for connecting devices having relatively the same speed•Asynchronous Timing: –based on a handshaking –offers better flexibility via allowing fast and slow devices to be connected in the same bus.Typical time sequence when information is transferred from the master to slave.6Bus arbitration•Bus arbitration scheme:–A bus master wanting to use the bus asserts the bus request–A bus master cannot use the bus until its request is granted–A bus master must signal to the arbiter the end of the bus utilization•Bus arbitration schemes usually try to balance two factors:–Bus priority: the highest priority device should be serviced first–Fairness: Even the lowest priority device should be allowed to access the bus•Bus arbitration schemes can be divided into several broad classes:–Daisy chain arbitration (not used nowadays)–Arbitration with the independent request and grant–Distributed arbitration7Independent Request and Grant [1]•Multiple bus-request and bus-grant signal lines are provided for each master •Any priority-based or fairness based bus allocation can be used.•Advantages –flexibility –faster arbitration time •Disadvantages:–large number of arbitration lines8Bus allocation techniques [1]•Round-robin–The request that was just served should have the lowest priority on the next round•TDMA–Fixed allocation of the slot to the master•Unequal-priority protocol–Each processor is assigned a unique priority.–Additional procedures are required to establish fairness9Bus Pipelining [1]•Several cycles are needed to read or write one data•Since the bus is not used in all cycles, pipelining canbe used to increase the performanceAR – Arbitration request, ARB cycle for processing inside the arbiter, AG – Grant signal is setRQ – request signal is setP- pauseRPLY – reply from the memory or I/O10Bus Pipelining [1]11Split Transactions [1]•In a split-transaction bus a transaction is divided into a two transactions–request-transaction–reply-transaction •Both transactions have to compete for the bus by arbitration12Split Transactions [1]13Burst Messages [1]14Avalon Bus•Proprietary bus specification used with Nios II•Principal design goals of the Avalon Bus–Address Decoding –Data-Path Multiplexing –Wait-State Insertion–Arbitration for Multi-Master Systems•Transfer Types–Slave Transfers–Master Transfers–Pipelined Transfers–Burst transfers32-BitNiosProcessorSwitch PIOLED PIO7-SegmentLED PIOPIO-32User-Defined InterfaceROM(with Monitor)UART TimerAddress (32)ReadWriteData In (32)Data Out (32)IRQIRQ #(6)Avalon BusNios Processor15•Direct Memory Access (DMA)–Processor Waits For Bus During DMASystem CPU(Master 1)DMA Arbitor100Base-T(Master 2)System BusI/O1I/O2DataMemoryDMA Bus ArbiterDMA Bus ArbiterBottleneckArbiter Determines Which Master Has Access To Shared BusProgramMemoryMastersSlavesTraditional Multi-MastersControl direction16Master 1(Nios CPU)I/O1ProgramMemoryArbiterDataMemory1Master 2(100Base-T)I DI/O2Avalon Bus Avalon BusUses Fairness ArbitrationMastersSlavesSimultaneous Multi-Master BusControl direction17Master Arbitration Scheme•Nios Multi-Master Avalon Bus utilizes Fairness arbitration scheme–Each Master/Slave pair is assign an integer “shares”–Upon conflict Master with most shares takes bus until all shares are used–Master with least shares then takes bus until all shares are used–Assuming all Masters continuously request the bus, they will each be granted the bus for a percentage of time equal to the percentage of total master shares that they own18Set Arbitration Priority•View => Show Arbitration Priorities19Address Decoding [4]20Data-Path Multiplexing [4]21Master Read Transfer [3]•Assert addr, be, read•Wait for waitrequest = ‘0’•Read in Data•End of transfer22Master Write Transfer [3]•Assert addr, be, read•Assert Write Data•Wait for waitrequest = ‘0’•End of transfer23Slave Read Transfer [3]•0 Setup Cycles•0 Wait Cyclesclkaddress,be_nreadnchipselectreaddataaddress, be_nreaddataA C D EB24clkaddress,be_nchipselectreadnreaddataaddress, be_nreaddataTsuA B C D E F GHSlave Read Transfer [3]•1 Setup Cycle•1 Wait Cycle25clkaddress,be_nwritedatawritenchipselectaddress, be_nwritedataAB C DSlave Write Transfer [3]•0 Setup Cycles•0 Wait Cycles•0 Hold Cycles26clkaddress,be_nwritedatawritenchipselectaddress, be_nwritedataB C D EFAGSlave Write Transfer [3]•1 Setup Cycle•0 Wait Cycles•1 Hold Cycle27References1. W. Dally, B. Towles, Principles And Practices Of Interconnection Networks, Morgan Kauffman, 2004. 2. K. Hwang, Advanced Computer Architecture Parallelism, Scalability, Programmability, McGraw-Hill 1993. 3. Altera Corp., Avalon Interface Specification, 2005.4. Altera Corp., Quartus II Handbook, Volume 4, 20055. H. El-Rewini and M. Abd-El-Barr, Advanced Computer Architecture and Parallel Processing, John Wiley and Sons,