Carnegie Mellon Introduction to Computer Systems 15 213 fall 2009 12th Lecture Oct 7th Instructors Majd Sakr and Khaled Harras Carnegie Mellon Last Time Cache Organization Memory Mountain Optimization for the memory hierarchy Carnegie Mellon Cache Read E 2e lines per set Locate set Check if any line in set has matching tag Yes line valid hit Locate data starting at offset Address of word t bits S 2s sets tag s bits b bits set block index offset data begins at this offset v tag 0 1 2 B 1 valid bit B 2b bytes per cache block the data Carnegie Mellon Example Direct Mapped Cache E 1 Direct mapped One line per set Assume cache block size 8 bytes v tag 0 1 2 3 4 5 6 7 v tag 0 1 2 3 4 5 6 7 v tag 0 1 2 3 4 5 6 7 v tag 0 1 2 3 4 5 6 7 S 2s sets Address of int t bits 0 01 find set 100 Carnegie Mellon E way Set Associative Cache Here E 2 E 2 Two lines per set Assume cache block size 8 bytes Address of short int t bits v tag 0 1 2 3 4 5 6 7 v tag 0 1 2 3 4 5 6 7 v tag 0 1 2 3 4 5 6 7 v tag 0 1 2 3 4 5 6 7 v tag 0 1 2 3 4 5 6 7 v tag 0 1 2 3 4 5 6 7 v tag 0 1 2 3 4 5 6 7 v tag 0 1 2 3 4 5 6 7 0 01 100 find set Carnegie Mellon Strided Access Question E 2e lines per set Address of word t bits S 2s sets tag s bits b bits set block index offset What happens if arrays are accessed in two power strides Example on the next slide Carnegie Mellon The Strided Access Problem Blackboard Example L1 cache Core 2 Duo 32 KB 8 way associative 64 byte cache block size What is S E B Answer B 26 E 23 S 26 Consider an array of ints accessed at stride 2i i 0 What is the smallest i such that only one set is used Answer i 10 What happens if the stride is 29 Answer two sets are used Source of two power strides Example Column access of 2 D arrays images Carnegie Mellon Pentium III 550 MHz 16 KB on chip L1 d cache 16 KB on chip L1 i cache 512 KB off chip unified L2 cache 1000 L1 800 600 400 xe L2 0 8k 32k 128k 512k 2m 8m s15 s13 s11 Stride words s9 s7 s5 mem 2k 200 s3 Slopes of Spatial Locality 1200 s1 Throughput MB sec The Memory Mountain Ridges of Temporal Locality Working set size bytes Carnegie Mellon Pentium Blocked Matrix Multiply Performance Blocking bijk and bikj improves performance by a factor of two over unblocked versions ijk and jik relatively insensitive to array size 60 kji jki kij ikj jik ijk bijk bsize 25 bikj bsize 25 40 30 20 10 75 10 0 12 5 15 0 17 5 20 0 22 5 25 0 27 5 30 0 32 5 35 0 37 5 40 0 50 0 25 Cycles iteration 50 Array size n No blocking 9 8 n3 Blocking 1 4B n3 Carnegie Mellon Today Exceptional Control Flow Processes Carnegie Mellon Control Flow Processors do only one thing From startup to shutdown a CPU simply reads and executes interprets a sequence of instructions one at a time This sequence is the CPU s control flow or flow of control Physical control flow Time startup inst1 inst2 inst3 instn shutdown Carnegie Mellon Altering the Control Flow Up to now two mechanisms for changing control flow Jumps and branches Call and return Both react to changes in program state Insufficient for a useful system Difficult to react to changes in system state data arrives from a disk or a network adapter instruction divides by zero user hits Ctrl C at the keyboard System timer expires System needs mechanisms for exceptional control flow Carnegie Mellon Exceptional Control Flow Exists at all levels of a computer system Low level mechanisms Exceptions change in control flow in response to a system event i e change in system state Combination of hardware and OS software Higher level mechanisms Process context switch Signals Nonlocal jumps setjmp longjmp Implemented by either OS software context switch and signals C language runtime library nonlocal jumps Carnegie Mellon Exceptions An exception is a transfer of control to the OS in response to some event i e change in processor state User Process event I current I next OS exception exception processing by exception handler return to I current return to I next abort Examples div by 0 arithmetic overflow page fault I O request completes Ctrl C Carnegie Mellon Interrupt Vectors Exception numbers code for exception handler 0 Exception Table 0 1 2 n 1 code for exception handler 1 Each type of event has a unique exception number k k index into exception table a k a interrupt vector Handler k is called each time exception k occurs code for exception handler 2 code for exception handler n 1 Carnegie Mellon Asynchronous Exceptions Interrupts Caused by events external to the processor Indicated by setting the processor s interrupt pin Handler returns to next instruction Examples I O interrupts hitting Ctrl C at the keyboard arrival of a packet from a network arrival of data from a disk Hard reset interrupt hitting the reset button Soft reset interrupt hitting Ctrl Alt Delete on a PC Carnegie Mellon Synchronous Exceptions Caused by events that occur as a result of executing an instruction Traps Intentional Examples system calls breakpoint traps special instructions Returns control to next instruction Faults Unintentional but possibly recoverable Examples page faults recoverable protection faults unrecoverable floating point exceptions Either re executes faulting current instruction or aborts Aborts unintentional and unrecoverable Examples parity error machine check Aborts current program Carnegie Mellon Trap Example Opening File User calls open filename options Function open executes system call instruction int 0804d070 libc open 804d082 cd 80 804d084 5b User Process int pop int pop 0x80 ebx OS exception open file returns OS must find or create file get it ready for reading or writing Returns integer file descriptor Carnegie Mellon Fault Example Page Fault User writes to memory location That portion page of user s memory is currently on disk 80483b7 c7 05 10 9d 04 08 0d User Process movl movl OS exception page fault returns int a 1000 main a 500 13 Create page and load into memory Page handler must load page into physical memory Returns to faulting instruction Successful on second try 0xd 0x8049d10 Carnegie Mellon Fault Example Invalid Memory Reference int a 1000 main a 5000 13 80483b7 c7 05 60 e3 04 08 0d User Process movl movl 0xd 0x804e360 OS exception page fault detect invalid address signal process Page handler detects invalid address Sends SIGSEGV signal to user process …
View Full Document
Unlocking...