ECE 15B Computer OrganizationSpring 2011Dmitri StrukovPartially adapted from Computer Organization and Design, 4thedition, Patterson and Hennessy,Advanced topics:Advanced topics: PipeliningpgECE 15B Spring 2011Datapath With ControlECE 15B Spring 2011Pipelining Analogy• Pipelined laundry: overlapping executionParallelism improves performance–Parallelism improves performanceFour loads:Four loads: Speedup= 8/3.5 = 2.3/ Non‐stop: Speeduppp= 2n/0.5n + 1.5 ≈ 4= number of stagesECE 15B Spring 2011Pipeline registers• Need registers between stagesTo hold information produced in previous cycle–To hold information produced in previous cycleECE 15B Spring 2011Multi‐Cycle Pipeline Diagram• Traditional formECE 15B Spring 2011Advanced topics: CacheAdvanced topics: Cache design basicsgECE 15B Spring 2011Datapath With ControlECE 15B Spring 2011Principle of LocalityPrinciple of Locality• Programs access a small proportion of their og a s access a sapopoto o teaddress space at any time• Temporal localityp y– Items accessed recently are likely to be accessed again sooniii l id i ibl–e.g., instructions in a loop, induction variables• Spatial localityItems near those a essed re entl are likel to be–Items near those accessed recently are likely to be accessed soon–E.g., sequential instruction access, array datag, q , yECE 15B Spring 2011Taking Advantage of Locality•Memory hierarchyMemory hierarchy• Store everything on diskC l d (d b)i•Copy recently accessed (and nearby) items from disk to smaller DRAM memory–Main memory• Copy more recently accessed (and nearby) items from DRAM to smaller SRAM memory– Cache memory attached to CPUECE 15B Spring 2011Tags and Valid Bits•How do we know which particular block isHow do we know which particular block is stored in a cache location?–Store block address as well as the data–Store block address as well as the data– Actually, only need the high‐order bitsCalled the tag–Called the tag• What if there is no data in a location?–Valid bit: 1 = present, 0 = not present– Initially 0ECE 15B Spring 2011Direct Mapped Cache• Location determined by address•Direct mapped: only one choice•Direct mapped: only one choice– (Block address) modulo (#Blocks in cache) #Blocks is a power of 2U ldUse low‐order address bitsECE 15B Spring 2011Example: Direct mapped cacheECE 15B Spring