Cache memoryProblemNumber Of Flip-Flops NeededSteps To Solve The ProblemState TableK-Maps for QA+ and QB+JK Truth TableT Truth TableK-Map for TK-Map for J and KDraw Flip-Flop DiagramTwo Basic Types of Memory2 Basic Types of MemoryMemory HierarchySlide 15The Memory HierarchyCache MemoryCache Memory - Three Levels ArchitectureSlide 19Slide 20Slide 21Cache (2)Where can a block be placed in Cache? (1)Slide 24Current CPUsCache PerformanceAssociative CacheDirect-Mapped Cache2-Way Set Associative CacheAssociative Cache (FIFO Replacement Policy)Two-way set associative cache (LRU Replacement Policy)Associative Cache with 2 byte line size (FIFO Replacement Policy)Direct-mapped Cache with line size of 2 bytesTwo-way set Associative Cache with line size of 2 bytesCache memoryProf. Sin-Min LeeDepartment of Computer ScienceProblemImplement the following state diagram using T Flip-Flop(s) and J-K Flip-Flop(s)Number Of Flip-Flops NeededNeed 2 Flip-Flops1 T Flip-Flop2 JK Flip-FlopSteps To Solve The ProblemStep 1 – Create state tableStep 2 – K-Maps for QA+ and QB+Step 3 – K-Maps for T and JK Flip-FlopsStep 4 – Draw Flip-Flop diagramState TableDerived directly from the state diagram:K-Maps for QA+ and QB+QA+QB+JK Truth TableLet’s revisit JK Flip-Flops:T Truth TableLet’s revisit T Flip-Flops:K-Map for TT = QA’QBK-Map for J and KJKJ = XQA’+ X’ QAK = XDraw Flip-Flop DiagramTwo Basic Types of MemoryRAM (Random Access Memory)Used to store programs and data that computer needs when executing programsVolatile and loses information once power is turned off2 Basic Types of MemoryROM (Read-Only Memory)Stores critical information necessary to operate the system, such as program necessary to boot computerNot volatile and always retains its dataAlso embedded in systems where programming does not need to changeMemory HierarchyHierarchal MemoryApproach in which computer systems use combination of memory types to provide best performance at best costBasic types that constitute hierarchal memory system include registers, cache, main memory and secondary memoryMemory HierarchyToday’s computers each have small amount of very high-speed memory, called cache where data from frequently used memory locations may be temporarily storedCache is connected to main memory, which is typically medium-speed memoryMain memory is complemented by secondary memory, composed of hard disk and various removable mediaThe Memory HierarchyCache MemoryPhysical memory is slow (more than 30 times slower than processor)Cache memory uses SRAM chips.Much fasterMuch expensiveSituated closest to the processorCan be arranged hierarchicallyL1 cache is incorporated into processorL2 cache is outsideCache Memory- Three LevelsArchitectureAddress PointerMemoryMulti-GigabytesLarge and Slow160 X16XL3 CacheMemoryCache ControlLogicL2 CacheMemoryL1 CacheMemory2X8X16 Megabytes128 Kilobytes32 Kilobytes 2 Gigahertz Clock Featuring Really Non-Deterministic ExecutionCache (2)Every address reference goes first to the cache; if the desired address is not here, then we have a cache miss;The contents are fetched from main memory into the indicated CPU register and the content is also saved into the cache memoryIf the desired data is in the cache, then we have a cache hitThe desired data is brought from the cache, at very high speed (low access time)Most software exhibits temporal locality of access, meaning that it is likely that same address will be used again soon, and if so, the address will be found in the cacheTransfers between main memory and cache occur at granularity of cache lines or cache blocks, around 32 or 64 bytes (rather than bytes or processor words). Burst transfers of this kind receive hardware support and exploit spatial locality of access to the cache (future access are often to address near to the previous one)Where can a block be placed in Cache? (1)Our cache has eight block frames and the main memory has 32 blocksCurrent CPUsCache PerformanceCache hits and cache misses.Hit ratio is the percentage of memory accesses that are served from the cacheAverage memory access timeTM = h TC + (1- h)TPTc = 10 nsTp = 60 nsAssociative CacheAccess order A0 B0 C2 A0 D1 B0 E4 F5 A0 C2 D1 V0 G3 C2 H7 I6 A0 B0Tc = 10 nsTp = 60 nsFIFOh = 0.389TM = 40.56 nsDirect-Mapped CacheAccess order A0 B0 C2 A0 D1 B0 E4 F5 A0 C2 D1 V0 G3 C2 H7 I6 A0 B0Tc = 10 nsTp = 60 nsh = 0.167TM = 50.67 ns2-Way Set Associative CacheAccess order A0 B0 C2 A0 D1 B0 E4 F5 A0 C2 D1 V0 G3 C2 H7 I6 A0 B0Tc = 10 nsTp = 60 nsLRUh = 0.31389TM = 40.56 nsAssociative Cache(FIFO Replacement Policy)Data A B C A D B E F A C D B G C H I A BCACHEA A A A A A A A A A A A A A A I I I B B B B B B B B B B B B B B B A A C C C C C C C C C C C C C C C B D D D D D D D D D D D D D D E E E E E E E E E E E E F F F F F F F F F F F G G G G G G H H H HHit? * * * * * * * Hit ratio = 7/18Hit ratio = 7/18A0 B0 C2 A0 D1 B0 E4 F5 A0 C2 D1 B0 G3 C2 H7 I6 A0 B0Two-way set associative cache(LRU Replacement Policy)Hit ratio = 7/18Hit ratio = 7/18A0 B0 C2 A0 D1 B0 E4 F5 A0 C2 D1 B0 G3 C2 H7 I6 A0 B0Data A B C A D B E F A C D B G C H I A BCACHE0 A-0 A-1 A-1 A-0 A-0 A-1 E-0 E-0 E-1 E-1 E-1 B-0 B-0 B-0 B-0 B-0 B-1 B-00 B-0 B-0 B-1 B-1 B-0 B-1 B-1 A-0 A-0 A-0 A-1 A-1 A-1 A-1 A-1 A-0 A-11 D-0 D-0 D-0 D-1 D-1 D-1 D-0 D-0 D-0 D-0 D-0 D-0 D-0 D-01 F-0 F-0 F-0 F-1 F-1 F-1 F-1 F-1 F-1 F-1 F-12 C-0 C-0 C-0 C-0 C-0 C-0 C-0 C-0 C-0 C-0 C-0 C-0 C-0 C-1 C-1 C-12 I-0 I-0 I-03 G-0 G-0 G-1 G-1 G-1 G-13 H-0 H-0 H-0 H-0Hit? * * * * * * *Associative Cache with 2 byte line size (FIFO Replacement Policy)Hit ratio = 11/18Hit ratio = 11/18A0 B0 C2 A0 D1 B0 E4 F5 A0 C2 D1 B0 G3 C2 H7 I6 A0 B0A and J; B and D; C and G; E and F; and I and HA and J; B and D; C and G; E and F; and I and HData A B C A D B E F A C D B G C H I A BCACHE A A A A A A A A A A A A A A I I I I J J J J J J J J J J J J J J H H H H B B B B B B B B B B B B B B B A A D D D D D D D D D D D D D D D J J C C C C C C C C C C C C C C C B G G G G G G G G G G G G G G G
View Full Document
Unlocking...