Hierarchical Memory SystemsSlide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Memory HierarchySlide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Slide 64Slide 65Slide 66Slide 67Slide 68Slide 69Slide 70Hierarchical Memory SystemsProf. Sin-Min LeeDepartment of Computer ScienceImplementing JK Flip-Flop using only a T Flip-FlopNote how the areas marked off with a blue box behave like a T flip-flop, while the area within the purple box behave like a D flip-flop.From this last chart, we can derive the following chart:Implementing JK Flip-Flop using only a T Flip-FlopTo derive the next chart, we work in reverse, asking, “What is the input into the T (toggle) function that will result in the output shown in the previous chart?” In this case, the first column of Q is 0 and our circled value is a 0; a 0 will give this result.The input that will give us a 1, when Q is 1, is also 0. Refer back to the T flip-flop chart to see that on 0, there is no change; 1 “toggles”.Implementing JK Flip-Flop using only a T Flip-FlopThis is the final Karnaugh map and the associated equation for T.Implementing T Flip-Flop using only a JK Flip-FlopThis time, we are doing the reverse again, asking what values of J and K will give us the corresponding values in the T chart above.00 or 01 will give 0, so weenter “0X”. X is our “don't care” value; it can be 0 or 1.Implementing T Flip-Flop using only a JK Flip-FlopOnce we derive all the values, we have to split this into two, in order to get an equation that defines J and another than defines K.Implementing T Flip-Flop using only a JK Flip-FlopHere is the final implementation.Finite State Machines and Flip-FlopsNow, suppose we have an FSM with two states like this:Although it may be confusing, the inputs and outputs are labeled “0” and “1”, and our two states are also have the labels “0” and “1”. This somewhat awkward naming convention means it is easier to translate this to computer code later on.X/Y:x = inputy = outputFinite State Machines and Flip-FlopsWe can think of the starting state as Q(t) and the ending state as Q(t+1), with x and y being our inputs and outputs, leading to this chart:Implementing this FSM using a T Flip-FlopUsing the values from the first chart, we can get this second chart.Then, we apply the same reverse method to determine what input values we would need to arrive at the ones listed in this second chart.Implementing this FSM using a T Flip-FlopT = XQ' + X'QImplementing this FSM using a D Flip-FlopThis time we use the same FSM and same initial chart, but now derive an equation for D.Implementing this FSM using a D Flip-FlopSince this is a delay, the corresponding chart is the same.Implementing this FSM using a D Flip-FlopFinally, here is our graph.Implementing with a D AND a T flip-flopUsing this FSM with three states, an operating only on inputs and transitions from one state to another, we will be using both D and T flip-flops.Implementing with a D AND a T flip-flopSince we have no state “11”, our Q(t+1) is “don't care” = “XX” for both of these transitions. Consider the first column of the Q(t+1) values to be “D” and the second to be “T” and then we derive two corresponding charts.D TImplementing with a D AND a T flip-flopThen we need to derive the corresponding equations.Implementing with a D AND a T flip-flopWe assume that Q(t) is actually a pair of QDQT. Now, with these equations, we can graph the results.Implementing with a D AND a T flip-flopMemory HierarchyCan only do useful work at the top 90-10 rule: 90% of time is spent of 10% of program Take advantage of locality temporal locality keep recently accessed memory locations in cache spatial locality keep memory locations nearby accessed memory locations in cacheThe connection between the CPU and cache is very fast; the connection between the CPU and memory is
View Full Document