16 4,080 Inputs 4080 Sequential Logic

Review of Combinational CircuitsCombinational circuits. Basic abstraction switch.In principle, can build TOY computer with acombinational circuit.–Sequential Logic––255 16 4,080 inputs 24080 rows in truth table!no simple patterneach circuit element used at most onceSequential circuits. Reuse circuit elementsby storing bits in "memory."Introduction to ComputerYung-Yu ChuangALUcombinationalMemorywith slides by Sedgewick & Wayne (introcs.cs.princeton.edu), Nisan & Schocken(www.nand2tetris.org) and Harris & Harris (DDCA)state2Combinational vs. Sequential CircuitsFlip-FlopCombinational circuits. Flip-flopOutput determined solely by inputs.Can draw with no loops.Ex: majority, adder, ALU. A small and useful sequential circuitAbstraction that remembers one bitBasis of important computer components for––Sequential circuits. –Output determined by inputs andprevious outputs.Ex: memory, program counter,CPU. 3registermemorycounterThere are several flavors4

S-R flip flopR0S0011011Relay-based flip-flopQEx. Simplest feedback loop.Two relays A and B, both connectedto power, each blocked by the other.State determined by whichever switches first. Thestate is latched.Stable. output1Q S RQinput1input2output256SR Flip FlopFlip-FlopSR flip flop. Two cross-coupled NOR gates.SRQFlip-flop. Q R(S Q) R0S0011011A way to control the feedback loop.Abstraction that "remembers" one bit.Basic building block for memory and registers.QCaveat. Need to deal with switching delay.78

Truth Table and Timing DiagramTruth table. Values vary over time.S(t), R(t), Q(t) denote value at time t.S(t)R(t) Q(t)Clock.Q(t )0000001101000110 1001 1011110111Sample timing diagram for SR flip-flop. ClockSR Flip Flop Truth Table Fundamental abstraction: regular on-off pulse.– on: fetch phase– off: execute phaseExternal analog device.Synchronizes operations of different circuitelements.Requirement: clock cycle longer than maxswitching time.cycle time 1Qon01R0Clockoff1S0time9How much does it Hert?10Clocked S-R flip-flopFrequency is inverse of cycle time. Expressed in hertz.Frequency of 1 Hz means that there is 1 cycle persecond.––––1 kilohertz (kHz) means 1000 cycles/sec.1 megahertz (MHz) means 1 million cycles/sec.1 gigahertz (GHz) means 1 billion cycles/sec.1 terahertz (THz) means 1 trillion cycles/sec.Heinrich Rudolf Hertz(1857-1894)1112

Clocked D flip-flopStand-Alone Register13Register file interface14Register file implementation1516

MultiplexerWhen s 0, return x; otherwise,return y.Example: (Y S) (X S)4-to-1 multiplexerSXmuxZYTwo-input multiplexerx0x1x24MUXzx3s0s117188-to-1 Multiplexer4-to-1 multiplexer2N-to-1 multiplexer x0x0x1x1x24MUXx32MUXz2MUXx2x3s0 N select inputs, 2N datainputs, 1 outputCopies “selected” data inputbit to outputz2MUXs1s0s11920

8-to-1 Multiplexer4-Wide 2-to-1 Multiplexer2N-to-1 multiplexerGoal: select from one of two 4-bit busesN select inputs, 2N datainputs, 1 outputCopies “selected” data inputbit to output 21224-Wide 2-to-1 Multiplexerk-Wide n-to-1 MultiplexerGoal: select from one of two 4-bit buses Goal: select from one of n k-bit busesImplemented by layering 4 2-to-1 multiplexer 23Implemented by layering k n-to-1 multiplexer24

Memory OverviewRegister file implementationComputers and TOY have several memorycomponents. Program counter.Registers.Main memory.Implementation. Use one flip-flop for eachbit of memory.Access. Memory components have differentaccess mechanisms.TOY has 16 bit words,8 bit memory addresses, and4 bit register names.Organization. Need mechanism to manipulategroups of related bits.2526Register BitRegister BitRegister bit. Extend a flip-flop to allow easyaccess to values.Register bit. Extend a flip-flop to allow easyaccess to values.DWDW27DW28

Memory Bit: InterfaceMemory Bit: Switch Level ImplementationMemory bit. Extend a flip-flop to allow easyaccess to values.[ TOY PC, IR ][ TOY main memory ]Memory bit. Extend a flip-flop to allow easyaccess to values.[ TOY registers ][ TOY PC, IR ][ TOY main memory ][ TOY registers ]2930Processor RegisterProcessor RegisterProcessor register. Processor register.Stores k bits.Register contents always available on output bus.If enable write is asserted, k input bits get copiedinto register. Ex 1. TOY program counter (PC) holds 8-bit address.Ex 2. TOY instruction register (IR) holds 16-bitcurrent instruction.Stores k bits.Register contents always available on output bus.If enable write is asserted, k input bits get copiedinto register.Ex 1. TOY program counter (PC) holds 8-bit address.Ex 2. TOY instruction register (IR) holds 16-bitcurrent instruction.3132

Processor RegisterMemory BankProcessor register. Memory bank.Stores k bits.Register contents always available on output bus.If enable write is asserted, k input bits get copiedinto register. Ex 1. TOY program counter (PC) holds 8-bit address.Ex 2. TOY instruction register (IR) holds 16-bitcurrent instruction.Bank of n registers; each stores k bits.Read and write information to one of n registers.Address inputs specify which one. log n address bits neededAddressed bits always appear on output.If write enabled, k input bits are copied intoaddressed register.2Ex 1. TOY main memory. (four 6-bit words)6-bit input bus256-by-16 memory bank.Ex 2. TOY registers. 16-by-16 memory bank.Two output buses.2-bit address6-bit output bus33Memory: Interface34Memory: Component Level Implementation(four 6-bit words)3536

Memory: Switch Level ImplementationSummarySequential circuits add "state" to digitalhardware.(four 6-bit words) Flip-flop.TOY word.TOY registers.TOY main memory.[represents 1 bit][16 flip-flops][16 words][256 words]Modern technologies for registers and mainmemory are different. Few registers, easily accessible, high cost per bit.Huge main memories, less accessible, low cost perbit.Drastic evolution of technology over time.Next. Build a complete TOY computer.3738Flip-flopThe ClockintocktocktockDFFouttockout(t) ycleIn our jargon, a clock cycle tick-phase (low), followed by atock-phase (high) A fundamental state-keeping deviceFor now, let us not worry about the DFF implementationMemory devices are made from numerous flip-flops,all regulated by the same master clock signalNotational convention:In real hardware, the clock is implemented by an oscillator inIn our hardware simulator, clock cycles can be simulated either sequentialchip (notation)Manually, by the user, or“Automatically,” by a test script.outclocksignalinsequentialchipout

1-bit register (we call it “Bit”)Bit register (cont.)loadObjective: build a storage unit that can:(a)Change its state to a given input(b)Maintain its state over time (until changed)inInterfaceoutBitloadif load(t-1) then out(t) in(t-1)else out(t) out(t-1)loadDFFoutinoutinDFFoutif load(t-1) then out(t) in(t-1)else out(t) out(t-1)outDFFBitMUXininImplementationout(t) in(t-1)Basic building blocko Load bitout(t) out(t-1) ?out(t) in(t-1) ?o Read logicWon’t worko Write logicMulti-bit registerloadloadinAside: Hardware SimulationoutBitif load(t-1) then out(t) in(t-1)else out(t) out(t-1)1-bit registerinwBit Bit.Bitwif load(t-1) then out(t) in(t-1)else out(t) out(t-1)w-bit registeroutRelevant topics from the HW simulator tutorial:Clocked chips: When a clocked chip is loaded into thesimulator, the clock icon is enabled, allowing clockcontrolBuilt-in chips:feature a standard HDL interface yet a JavaimplementationProvide behavioral simulation servicesMay feature GUI effects (at the simulator levelonly). oooRegister’s width: a trivial parameterRead logicWrite logic

Random Access Memory (RAM)RAM interfaceloadloadregister 0register 1register 2inout.(word)in(word)register n-1out16 bitsRAMnRAM naddressaddress16 bitsDirect Access Logiclog 2 nbits(0 to n-1)ooRead logicWrite logic.RAM anatomyCounterNeeded: a storage device that can:RAM 64(a) set its state to some base value(b) increment the state in every clock cycle(c) maintain its state (stop incrementing) over clock cyclesRAM8(d) reset its state.RAM 8RegisterinBit Bit. .RAM8registerBitRecursive ascentregister.outPC (counter)w bits8load reset8register.incw bitsIf reset(t-1) then out(t) 0else if load(t-1) then out(t) in(t-1)else if inc(t-1) then out(t) out(t-1) 1else out(t) out(t-1)Typical function: program counterImplementation: register chip some combinational logic.

Recap: Sequential VS combinational logicTime matterstockCombinational chip(optional)time ycleImplications:Reg1out bPerspectiveAll the memory units described in this lecture are standardTypical memory hierarchyAccesstimeCostSRAM (“static”), typically used for the cacheDRAM (“dynamic”), typically used for main memoryDisk(Elaborate caching / paging algorithms)A Flip-flop can be built from Nand gatesBut . real memory units are highly optimized, using a great variety of storagetechnologies.tickout(t) some function of (in(t-1), out(t-1))sel tick During a tick-tock cycle, the internal states of all the clocked chips are allowedto change, but their outputs are “latched”a tock At the beginning of the next cycle, the outputs of all the clocked chips in thearchitecture commit to the new values.out some function of (in) tocktockSequential chip Challenge: propagation delays Solution: clock synchronization Cycle length and processing speed.Reg2

Implementation o Load bit o Read logic o Write logic Multi-bit register Bit out load in if load(t-1) then out(t) in(t-1) else out(t) out(t-1) 1-bit register o Register’s width: a trivial parameter o Read logic o Write logic Bit. . . w-bit register out load in w w Bit Bit Aside: Hardware Simulation Relevant topics from the HW simulator tutorial: