Cache Memory Midterm 2 Revision 2Slide 2Slide 3Slide 4von Neumann Architecture PrincetonSlide 6Slide 7Slide 8Cache MemorySlide 10Cache Memory - Three Levels ArchitectureSlide 12Cache (1)Slide 14Slide 15Slide 16Subtract by SummationX-YY-XHow To Represent Signed Numbers1. signed magnitude2. One’s Complement Representation3. Two’s Complement RepresentationSlide 24Arithmetic SubtractionSlide 264 to 1 MUX4-to-1 MUX (Gate level)Slide 29Example: Quad 2-to-1 MUXImplementing Boolean functions with MultiplexersExampleEfficient Method for implementing Boolean functionsAnother ExampleMUX Example (cont.)MUX implementation of F(A,B,C) = m(1,3,5,6)Slide 37Slide 38Slide 39Slide 40Slide 41AdderAdditionOne ImplementationBinary addition and our adderWhat about the second column?Truth Table for AdditionSlide 48Synchronous Sequential Circuit with T Flip-Flop --Timing DiagramState Table and State DiagramK-Maps for ExampleExample 2.Synchronous Sequential Circuit with JK Flip-flopsTiming Diagram and State Table for Example 2K-Maps for Example 2Generating the State Table From K-maps -- Example 2Example 3.Synchronous Sequential Circuit SynthesisIntroductory Synthesis Example -- Example 3Flip-flop Input Tables -- Example 3Generating the JK Flip-flop Excitation Maps -- Example 3Clocked JK Flip-Flop Implementation -- Example 3Application Equation Method for Deriving Excitation Equations -- Example 3Slide 63RegistersUsing T Flip Flop and JK Flip FlopStep 1 - Translate diagram into State TableStep 2 - Create maps for T and JKStep 3 - Determine T, J, and K equationsStep 4 - Draw resulting diagramCache MemoryMidterm 2 Revision 2Prof. Sin-Min LeeDepartment of Computer ScienceThe Processor PictureThe Five Classic Components of a ComputerControlDatapathMemoryProcessorInputOutputvon NeumannArchitecturePrincetonAddress PointerArithmeticLogic Unit(ALU)MemoryProgram CounterPc = Pc + 1Data/InstructionsFeaturing Deterministic ExecutionCache Memory•Physical memory is slow (more than 30 times slower than processor)•Cache memory uses SRAM chips.–Much faster–Much expensive–Situated closest to the processor•Can be arranged hierarchically–L1 cache is incorporated into processor–L2 cache is outsideCache Memory This photo shows level 2 cache memory on the Processor board, beside the CPUCache Memory- Three LevelsArchitectureAddress PointerMemoryMulti-GigabytesLarge and Slow160 X16XL3 CacheMemoryCache ControlLogicL2 CacheMemoryL1 CacheMemory2X8X16 Megabytes128 Kilobytes32 Kilobytes 2 Gigahertz Clock Featuring Really Non-Deterministic ExecutionCache (1)•Is the first level of memory hierarchy encountered once the address leaves the CPU–Since the principle of locality applies, and taking advantage of locality to improve performance is so popular, the term cache is now applied whenever buffering is employed to reuse commonly occurring items•We will study caches by trying to answer the four questions for the first level of the memory hierarchySubtract by Summation •Subtraction with complement is done with binary numbers in a similar way.•Using two binary numbers X=1010100 and Y=1000011•We perform X-Y and Y-XX-Y•X= 1010100•2’s com. of Y= 0111101•Sum= 10010001•Answer= 0010001Y-X•Y= 1000011•2’s com. of X= 0101100•Sum= 1101111•There’s no end carry: answer is negative --- 0010001 (2’s complement of 1101111)How To Represent Signed Numbers•Plus and minus signs used for decimal numbers: 25 (or +25), -16, etc.•For computers, it is desirable to represent everything as bits..•Three types of signed binary number representations: 1. signed magnitude, 2. 1’s complement, and 3. 2’s complement1. signed magnitude•In each case: left-most bit indicates sign: positive (0) or negative (1).Consider 1. signed magnitude: 000011002 = 1210Sign bit Magnitude100011002 = -1210Sign bit Magnitude2. One’s Complement Representation•The one’s complement of a binary number involves inverting all bits.•To find negative of 1’s complement number take the 1’s To find negative of 1’s complement number take the 1’s complement of whole number including the sign bit.complement of whole number including the sign bit.000011002 = 1210Sign bit Magnitude111100112 = -1210Sign bit 1’complement3. Two’s Complement Representation•The two’s complement of a binary number involves inverting all bits and adding 1.•To find the negative of a signed number take the 2’s the 2’s complement of the positive number including the sign bit.000011002 = 1210Sign bit Magnitude111101002 = -1210Sign bit 2’s complementThe rule for addition is add the two numbers, including their sign bits, and discard any carry out of the sign (leftmost) bit position. Numerical examples for addition are shown below.Example:+ 6 00000110 - 6 11111010+13 00001101 +13 00001101+19 00010011 +7 00000111+6 00000110 -6 11111010-13 11110011 -13 11110011-7 11111001 -19 11101101In each of the four cases, the operation performed is always addition, including the sign bits.Only one rule for addition, no separate treatment of subtraction. Negative numbers are always represented in 2’s complement. Sign addition in 2’s complementArithmetic Subtraction•A subtraction operation can be changed to an addition operation if the sign of the subtrahend is changed.•(±A) - (+B) = (±A) + (-B)•(±A) - (-B) = (±A) + (+B)Arithmetic Subtraction•Consider the subtraction of (-6) - (-13) = +7. In binary with eight bits this is written as 11111010 - 11110011. The subtraction is changed to addition by taking the 2’s complement of the subtrahend (-13) to give (+13). In binary this is 11111010 + 00001101 = 100000111. •Removing the end carry, we obtain the correct answer 00000111 (+ 7).4 to 1 MUX2 - 4 DecoderControlDataFlowD3:D04Sel(3:0)4S1:S02Dout4-to-1 MUX (Gate level)Three of these signal inputs will always be 0. The other will depend on the data value selectedControl Section•Until now, we have examined single-bit data selected by a MUX. What if we want to select m-bit data/words? Combine MUX blocks in parallel with common select and enable signals•Example: Construct a logic circuit that selects between 2 sets of 4-bit inputs (see next slide for solution).Multiplexer (cont.)Example: Quad 2-to-1 MUX•Uses four 4-to-1 MUXs with common select (S) and enable (E).•Select line chooses between Ai’s and Bi’s. The selected four-wire digital signal is sent to the Yi’s•Enable
View Full Document
Unlocking...