Course Theme 15 213 The Class That Gives CMU Its Zip n Courses to date emphasize abstraction Introduction to Computer Systems n n n n n n n Abstract data types Asymptotic analysis These abstractions have limits Seth Goldstein Andreas Nowatzyk January 13 2004 Topics n Abstraction is good but don t forget reality n Especially in the presence of bugs n Need to understand underlying implementations Useful outcomes Theme Five great realities of computer systems How this fits within CS curriculum Staff text and policies Lecture topics and assignments Lab rationale n Become more effective programmers l Able to find and eliminate bugs efficiently l Able to tune program performance n Prepare for later systems classes in CS ECE l Compilers Operating Systems Networks Computer Architecture Embedded Systems 2 class01 ppt Great Reality 1 Computer Arithmetic Int s are not Integers Float s are not Reals Does not generate random values n Examples n Yes l Int s 40000 40000 1600000000 1794967296 50000 50000 n n Due to finiteness of representations n Integer operations satisfy ring properties n Floating point operations satisfy ordering properties l Commutativity associativity distributivity Is x y z x y z l Unsigned Signed Int s l Monotonicity values of signs Yes Observation l Float s 1e20 1e20 3 14 3 14 0 1e20 1e20 3 14 3 Arithmetic operations have important mathematical properties Cannot assume usual properties Is x2 0 l Float s 15 213 S 04 15 213 S 04 4 n Need to understand which abstractions apply in which contexts n Important issues for compiler writers and serious application programmers 15 213 S 04 Great Reality 2 Assembly Code Example You ve got to know assembly Time Stamp Counter n Special 64 bit register in Intel compatible machines Incremented every clock cycle n Read with rdtsc instruction n Chances are you ll never write program in assembly n Compilers are much better more patient than you are Application Understanding assembly key to machine level execution model n Behavior of programs in presence of bugs n Tuning program performance n Implementing system software n Measure time required by procedure l In units of clock cycles l High level language model breaks down double t start counter P t get counter printf P required f clock cycles n t l Understanding sources of program inefficiency l Compiler has machine code as target l Operating systems must manage process state 15 213 S 04 5 Code to Read Counter 15 213 S 04 Code to Read Counter n Write small amount of assembly code using GCC s asm facility n Inserts assembly code into machine code generated by compiler static unsigned cyc hi 0 static unsigned cyc lo 0 Set hi and lo to the high and low order bits of the cycle counter void access counter unsigned hi unsigned lo asm rdtsc movl edx 0 movl eax 1 r hi r lo edx eax 7 6 15 213 S 04 Record the current value of the cycle counter void start counter access counter cyc hi cyc lo Number of cycles since the last call to start counter double get counter unsigned ncyc hi ncyc lo unsigned hi lo borrow Get cycle counter access counter ncyc hi ncyc lo Do double precision subtraction lo ncyc lo cyc lo borrow lo ncyc lo hi ncyc hi cyc hi borrow return double hi 1 30 4 lo 8 15 213 S 04 Measuring Time Timing System Performance Trickier than it Might Look n Many sources of variation Example n Sum integers from 1 to n n 100 1 000 1 000 10 000 10 000 1 000 000 1 000 000 1 000 000 000 Cycles 961 8 407 8 426 82 861 82 876 8 419 907 8 425 181 8 371 2305 591 Cycles n 9 61 8 41 8 43 8 29 8 29 8 42 8 43 8 37 main int argc char argv for i 0 i t i start counter count n times i get counter int count int n int i int sum 0 int count int n int i int sum 0 main int argc char argv for i 0 i t i start counter count n times i get counter for i 0 i n i sum i return sum 15 213 S 04 9 Timing System Performance for i 0 i n i sum i return sum 15 213 S 04 10 Great Reality 3 main int argc char argv int count int n Memory Matters int count int n main int argc char argv Memory is not unbounded Experiment 1 2 1a 2a 3a 4a Memory performance is not uniform Experiment 1 2 3 4 n 10 10 1000 1000 cycles n 1649 2 17 2 24 3 6 1 n 10 10 10 10 1000 1000 cycles n 1657 6 26 20 16 4 1 7 1 6 Random Access Memory is an un physical abstraction n It must be allocated and managed n Many applications are memory dominated n Cache and virtual memory effects can greatly affect program performance n Adapting program to characteristics of memory system can lead to major speed improvements Memory referencing bugs especially pernicious It s the system stupid 11 n 15 213 S 04 12 Effects are distant in both time and space 15 213 S 04 Memory Performance Example Matmult Performance Alpha 21164 Too big for L1 Cache Implementations of Matrix Multiplication n Multiple ways to nest loops Too big for L2 Cache 160 ijk for i 0 i n i for j 0 j n j sum 0 0 for k 0 k n k sum a i k b k j c i j sum 13 ikj for i 0 i n i for k 0 k n k sum 0 0 for j 0 j n j sum a i k b k j c i j sum 15 213 S 04 Iterations time 140 120 ijk 100 ikj jik 80 jki kij 60 kji 40 20 0 matrix size n 15 213 S 04 14 Blocked matmult perf Alpha 21164 Memory System 160 140 Iterations time 120 100 bijk bikj 80 ijk ikj 60 40 20 0 50 75 100 125 150 175 200 225 250 275 300 325 350 375 400 425 450 475 500 matrix size n 15 15 213 S 04 16 15 213 S 04 Real Memory Performance Memory Referencing Bug Example Pointer Chase Results Iteration Time ns 1000 main main long long int int a 2 a 2 double double dd 3 14 3 14 a 2 a 2 1073741824 1073741824 Out Out of of bounds bounds reference reference printf d printf d 15g n 15g n d d exit 0 exit 0 100 10 Alpha 1 From Tom Womack s memory latency benchmark 15 213 S 04 17 Memory Referencing Errors Out of bounds array references n Invalid pointer values n Abuses of malloc free Whether or not bug has any effect depends on system and compiler n Action at a distance l Corrupted object logically unrelated to one being accessed 15 213 S 04 There s more …
or
We will never post anything without your permission.
Don't have an account? Sign up