Chapter 5(and some of Ch. 4)The Von Neumann Model & LC3Based on slides © McGraw-HillAdditional material © 2004/2005/2006 Lewis/Martin 5-2CSE 240What Do We Know?A LOT!!• Data representation (binary, 2’s complement, floating point, …)• Transistors (p-type, n-type, CMOS)• Gates (complementary logic)• Combinational logic circuits (PLAs), memory (latches, flip-flops, …)• Sequential logic circuits (state machines)• Simple “processors” (programmable traffic sign)What’s next?• Apply all this to traditional computing• Software interface: instructions• Hardware implementation: data path5-3CSE 24023 by 16-bit memory - Two Read Ports, One WriteD0 16 16D1 16 16D2 16 16D7 16 16 16DR2AR2 3WE 16DW DecoderAW 16DR1AR1 3 3. . .. . . . .5-4CSE 240 Adder/SubtracterCarryInS 16A 16 16B 16Add/Sub 116-bit Adder/Subtracter5-5CSE 240 16AR2 3WE 16DWAW 16AR1 3 323 x 16-bitMemory“RegisterFile”SAdd/Sub 1Adder/SubtractorSimple Processing Machine nn x k-bitRead-onlyMemoryNextnzNextpPos?01 n nAddrPC n5-6CSE 240Can we make it multiply?Goal: A * B into CInitial register values• R2 is “A”, R3 is “B”, R4 will be “C”• R0 is zero, R1 is oneEnd program with infinite loopWhat should the control memory contents be?#3#2#1#0NextpNextnzAWWEAR2AR1Add/SubWhile (B > 0) C = C + A B = B - 15-7CSE 240Can we make it multiply?Goal: A * B into CInitial register values• R2 is “A”, R3 is “B”, R4 will be “C”• R0 is zero, R1 is oneEnd program with infinite loopWhat should the control memory contents be?#3#3X0XXX#3#0#0R31R1R31#2#2#2R41R2R40#1#1#3X0R0R30#0NextpNextnzAWWEAR2AR1Add/SubWhile (B > 0) C = C + A B = B - 15-8CSE 240Multiply Execution Trace#3#0#2#1#0#2#1#0PC706---R7---R6---R51050R4 (“C”)12R3 (“B”)5R2 (“A”)1R10R0543210Cycle5-9CSE 240Can we make it divide?3210NextpNextnzAWWEAR2AR1Add/SubGoal: A / B into CInitial register values• R2 is “A”, R3 is “B”, R4 will be “C”• R0 is zero, R1 is oneEnd program with infinite loopWhat should the control memory contents be?5-10CSE 240Can we make it divide?#3#3X0XXX3#0#0R41R1R402#2#3X0R1R201#1#1R21R3R210NextpNextnzAWWEAR2AR1Add/SubGoal: A / B into CInitial register values• R2 is “A”, R3 is “B”, R4 will be “C”• R0 is zero, R1 is oneEnd program with infinite loopWhat should the control memory contents be?A = A - BIf (A+1 > 0) C = C + 1 goto startA >= 05-11CSE 240Divide Execution Trace#38#1#0#2#1#0#2#1#0PC-5726---R7---R6---R510R4 (“C”)5R3 (“B”)0510R2 (“A”)1R10R0543210Cycle5-12CSE 240How might we improve our processing machine?More operations & conditions• And, Not?• Control next operation via any of negative/positive/zero combinationsMore data storage?• Add a separate data memory structure• Register file used as “temporary” storage• Add new logic elements to read and write this memoryHow would we sum all the numbers in memory?• Need “addressing modes” to allow this• E.g., Read from the location in memory specified by R1Smaller encoding• Use fewer bits for “Next” (too large when control memory is big)• Also want more “dynamic” control! E.g., next operation is at the location specified by R1’s value5-13CSE 240 16AR2 3WE 16DWAW 16AR1 3 323 x 16-bitMemory“RegisterFile”SAdd/Sub 1Adder/SubtractorSimple Processing Machine -- Modified nn x k-bitRead-onlyMemoryNextPCN/Z/P01 nAddrPC n+1 3nzp n5-14CSE 240Multiply for Modified MachineGoal: A * B into CInitial register values• R2 is “A”, R3 is “B”, R4 will be “C”• R0 is zero, R1 is oneEnd program with infinite loopWhat should the control memory contents be?#3111X0XXX#3#0111R31R1R31#2X000R41R2R40#1#3110X0R0R30#0NextN/Z/PAWWEAR2AR1Add/SubWhile (B > 0) C = C + A B = B - 15-15CSE 240Divide for Modified Machine#3111X0XXX3#0111R41R1R412#3100X0R1R201X000R21R3R210NextN/Z/PAWWEAR2AR1Add/SubGoal: A / B into CInitial register values• R2 is “A”, R3 is “B”, R4 will be “C”• R0 is zero, R1 is oneEnd program with infinite loopWhat should the control memory contents be?A = A - BIf (A >= 0) C = C + 1 goto start5-16CSE 240How might we improve our processing machine?More operations & conditions• And, Not?• Control next operation via any of negative/positive/zero combinationsMore data storage?• Add a separate data memory structure• Register file used as “temporary” storage• Add new logic elements to read and write this memoryHow would we sum all the numbers in memory?• Need “addressing modes” to allow this• E.g., Read from the location in memory specified by R1Smaller encoding• Use fewer bits for “Next” (too large when control memory is big)• Also want more “dynamic” control! E.g., next operation is at the location specified by R1’s value5-17CSE 240Warning!This is a bottom-up course• No secrets, no magice.g., gates build on transistors, logic circuits from gates, etc.But… some of this lecture is top-down• You’ll have to trust me for a couple slides• Start with very abstract discussion of computer architecture• Meet with Chapter 3 material soon5-18CSE 240A Little Context1943: ENIAC• First general electronic computer (Presper Eckert and John Mauchly)(Or was it Atananasoff in 1939? Or Konrad Zuse in 1941?)• 18,000 tubes (had to replace 50 a day!)• Memory: 20 10-digit numbers (decimal)• Hard-wired program (via dials, switches,and cables)• Completed in 19461944: Beginnings of EDVAC• Among other improvements, includesprogram stored in memory• Gave birth to UNIVAC-I (1951)• Completed in 19525-19CSE 240Context Continued: Stored Program Computer1945: John von Neumann• First Draft of a Report on EDVACSee John von Neumann and the Origins of Modern Computing by William AsprayVon Neumann Machine (or Model)• Memory, containing instructions and data• Control unit, for interpreting instructions• Processing unit, for performing arithmetic and logical operations• Input/Output units, for interacting with real world5-20CSE 240Remember Finite State Machines?State MachineCombinationalLogic CircuitStorageElementsInputs OutputsStateNext stateCurrent statePCControl signals5-21CSE 240Von Neumann ModelMEMORY INPUT KeyboardMouseScannerDisk OUTPUT MonitorPrinterLEDDisk PROCESSING UNIT ALU Regs CONTROL UNIT PC5-22CSE 240Processing UnitFunctional Units• ALU = Arithmetic and Logic Unit• Could have many functional units(some special-purpose,e.g., multiply, square