CS61C Machine Structures Lecture 36 Input Output 4 21 2006 John Wawrzynek www cs berkeley edu johnw www inst eecs berkeley edu cs61c CS 61C L36 Input Output 1 Wawrzynek Spring 2006 UCB 4 Qs for any Memory Hierarchy Q1 Where can a block be placed One place direct mapped A few places set associative Any place fully associative Q2 How is a block found Indexing as in a direct mapped cache Limited search as in a set associative cache Full search as in a fully associative cache Separate lookup table as in a page table Q3 Which block is replaced on a miss Least recently used LRU Random Q4 How are writes handled Write through Level never inconsistent w lower Write back Could be dirty must have dirty bit CS 61C L36 Input Output 2 Wawrzynek Spring 2006 UCB Q1 Where block placed in upper level Block 12 placed in 8 block cache Fully associative Direct mapped 2 way set associative Set Associative Mapping Block Mod of Sets Block no Block no 01234567 Fully associative block 12 can go anywhere 01234567 Block no 01234567 Set Set Set Set 0 1 2 3 Set associative block 12 can go anywhere in set 0 12 mod 4 Direct mapped block 12 can go only into block 4 12 mod 8 CS 61C L36 Input Output 3 Wawrzynek Spring 2006 UCB Q2 How is a block found in upper level Block Address Tag Block offset Index Set Select Data Select Direct indexing using index and block offset tag compares or combination Increasing associativity shrinks index expands tag CS 61C L36 Input Output 4 Wawrzynek Spring 2006 UCB Q3 Which block replaced on a miss Easy for Direct Mapped Set Associative or Fully Associative Random LRU Least Recently Used Miss Rates Associativity 2 way 4 way Size LRU Ran LRU 16 KB 64 KB 8 way Ran LRU Ran 5 2 5 7 4 7 5 3 4 4 5 0 1 9 2 0 1 5 1 7 1 4 1 5 256 KB 1 15 1 17 1 13 1 13 1 12 1 12 CS 61C L36 Input Output 5 Wawrzynek Spring 2006 UCB Q4 What to do on a write hit Write through update the word in cache block and corresponding word in memory Write back update word in cache block allow memory word to be stale add dirty bit to each line indicating that memory be updated when block is replaced OS flushes cache before I O Performance trade offs WT read misses cannot result in writes WB no writes of repeated writes CS 61C L36 Input Output 6 Wawrzynek Spring 2006 UCB Three Advantages of Virtual Memory 1 Translation Program can be given consistent view of memory even though physical memory is scrambled Makes multiple processes reasonable Only the most important part of program Working Set must be in physical memory Contiguous structures like stacks use only as much physical memory as necessary yet still grow later CS 61C L36 Input Output 7 Wawrzynek Spring 2006 UCB Three Advantages of Virtual Memory 2 Protection Different processes protected from each other Different pages can be given special behavior Read Only Invisible to user programs etc Kernel data protected from User programs Very important for protection from malicious programs Far more viruses under Microsoft Windows Special Mode in processor Kernel mode allows processor to change page table TLB 3 Sharing Can map same physical page to multiple users Shared memory CS 61C L36 Input Output 8 Wawrzynek Spring 2006 UCB Why Translation Lookaside Buffer TLB Paging is most popular implementation of virtual memory vs base bounds Every paged virtual memory access must be checked against Entry of Page Table in memory to provide protection Cache of Page Table Entries TLB makes address translation possible without memory access in common case to make fast CS 61C L36 Input Output 9 Wawrzynek Spring 2006 UCB And in Conclusion Virtual memory to Physical Memory Translation too slow Add a cache of Virtual to Physical Address Translations called a TLB Spatial Locality means Working Set of Pages is all that must be in memory for process to run fairly well Virtual Memory allows protected sharing of memory between processes with less swapping to disk CS 61C L36 Input Output 10 Wawrzynek Spring 2006 UCB Administrivia Switch in order of lectures from original schedule Performance will come after I O section We re late getting the homework out this week sorry busy with exam stuff Will be posted later today New set of reading assignments posted CS 61C L36 Input Output 11 Wawrzynek Spring 2006 UCB Recall 5 components of any Computer Earlier Lectures Current Lectures Computer Processor Memory active passive Control brain where programs Datapath data live brawn when running CS 61C L36 Input Output 12 Devices Input Output Keyboard Mouse Disk Network Display Printer Wawrzynek Spring 2006 UCB Motivation for Input Output I O is how humans interact with computers I O is how computers interconnect Internet www I O is how computers sense and control the environment I O gives computers long term memory Computer without I O like a car without wheels great technology but won t get you anywhere CS 61C L36 Input Output 13 Wawrzynek Spring 2006 UCB I O Device Examples and Speeds I O Speed bytes transferred per second from mouse to Gigabit LAN 10 million to 1 Device Behavior Partner Keyboard Input Mouse Input Voice output Output Floppy disk Storage Laser Printer Output Magnetic Disk Storage Wireless Network I or O Graphics Display Output Wired LAN Network I or O Human Human Human Machine Human Machine Machine Human Machine CS 61C L36 Input Output 14 Data Rate KBytes s 0 01 0 02 5 00 50 00 100 00 10 000 00 10 000 00 30 000 00 125 000 00 Wawrzynek Spring 2006 UCB What do we need to make I O work A way to connect many types of devices to the Proc Mem A way to control these devices respond to them and transfer data Files APIs Operating System Proc Mem PCI Bus A way to present them to user programs so they are useful SCSI Bus cmd reg data reg CS 61C L36 Input Output 15 Wawrzynek Spring 2006 UCB Instruction Set Architecture for I O What must the processor do for I O Input reads a sequence of bytes Output writes a sequence of bytes Some processors have special input and output instructions Alternative model used by MIPS Use loads for input stores for output Called Memory Mapped Input Output A portion of the address space dedicated to communication paths to Input or Output devices no memory there CS 61C L36 Input Output 16 Wawrzynek Spring 2006 UCB Memory Mapped I O Certain addresses are not regular memory Instead they correspond to registers in I O devices address 0xFFFFFFFF 0xFFFF0000 cntrl reg data reg 0 CS 61C L36 Input Output 17 Wawrzynek Spring 2006 UCB Processor I O Speed Mismatch 1GHz microprocessor can
View Full Document
Unlocking...