Course Theme 15 213 The Class That Gives CMU Its Zip Courses to date emphasize abstraction Introduction to Computer Systems Especially in the presence of bugs 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 class01a ppt Abstract data types Asymptotic analysis These abstractions have limits Seth Goldstein Bruce Maggs January 14 2003 Topics Abstraction is good but don t forget reality Become more effective programmers z Able to find and eliminate bugs efficiently z Able to tune program performance Prepare for later systems classes in CS ECE z Compilers Operating Systems Networks Computer CS 213 F 02 Architecture Embedded Systems 2 Great Reality 1 Computer Arithmetic Int s are not Integers Float s are not Reals Does not generate random values Examples Yes z Int s 40000 40000 1600000000 50000 50000 Due to finiteness of representations Integer operations satisfy ring properties Floating point operations satisfy ordering properties z Commutativity associativity distributivity Is x y z x y z z Unsigned Signed Int s z Monotonicity values of signs Yes Observation z Float s 1e20 1e20 3 14 3 14 1e20 1e20 3 14 3 Arithmetic operations have important mathematical properties Cannot assume usual properties Is x2 0 z Float s 15 213 S 03 15 213 S 03 4 Need to understand which abstractions apply in which contexts Important issues for compiler writers and serious application programmers 15 213 S 03 Great Reality 2 Assembly Code Example You ve got to know assembly Time Stamp Counter Chances are you ll never write program in assembly Compilers are much better more patient than you are Application Understanding assembly key to machinemachine level execution model Behavior of programs in presence of bugs Tuning program performance Implementing system software Special 64 bit register in Intel compatible machines Incremented every clock cycle Read with rdtsc instruction Measure time required by procedure z In units of clock cycles z High level language model breaks down double t start counter P t get counter printf P required f clock cycles n t z Understanding sources of program inefficiency z Compiler has machine code as target z Operating systems must manage process state 15 213 S 03 5 Code to Read Counter 15 213 S 03 Code to Read Counter Write small amount of assembly code using GCC s asm facility 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 03 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 03 Measuring Time Timing System Performance Trickier than it Might Look Many sources of variation Example 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 03 9 Timing System Performance int count int n int count int n main int argc char argv n 10 10 1000 1000 cycles n 1649 2 17 2 24 3 6 1 Experiment 1 2 1a 2a 3a 4a n 10 10 10 10 1000 1000 15 213 S 03 10 Great Reality 3 main int argc char argv Experiment 1 2 3 4 for i 0 i n i sum i return sum Memory Matters cycles n 1657 6 26 20 16 4 1 7 1 6 Memory is not unbounded It must be allocated and managed Many applications are memory dominated Memory performance is not uniform Cache and virtual memory effects can greatly affect program performance Adapting program to characteristics of memory system can lead to major speed improvements Memory referencing bugs especially pernicious It s the system stupid 11 15 213 S 03 12 Effects are distant in both time and space 15 213 S 03 Hardware Organization Na ve Memory Performance Example Implementations of Matrix Multiplication Multiple ways to nest loops 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 15 213 S 03 13 Matmult Performance Alpha 21164 Too big for L1 Cache 14 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 03 Memory System Too big for L2 Cache 160 Iterations time 140 120 ijk 100 ikj jik 80 jki kij 60 kji 40 20 0 matrix size n 15 15 213 S 03 16 15 213 S 03 Blocked matmult perf Alpha 21164 Memory Referencing Bug Example main main long long int int a 2 a 2 double double dd 3 14 3 14 a 2 1073741824 a 2 1073741824 Out Out of of bounds bounds reference reference printf d printf d 15g n 15g n d d exit 0 exit 0 160 140 Iterations time 120 100 bijk bikj 80 ijk ikj 60 Alpha 40 20 MIPS Linux g 5 30498947741318e 315 3 1399998664856 3 14 O 3 14 3 14 3 14 0 50 75 100 125 150 175 200 225 250 275 300 325 350 375 400 425 450 475 500 Linux version gives correct result but implementing as separate function gives segmentation fault matrix size n 15 213 S 03 17 Memory Referencing Errors Great Reality 4 C and C do not provide any memory protection Out of bounds array references Invalid pointer values Abuses of malloc free There s more to performance than asymptotic complexity Constant factors matter too Can lead to nasty bugs Whether or not bug has any effect depends on system and compiler Action at a distance z Corrupted object logically unrelated to one being accessed 19 Easily see 10 1 performance range depending on how code written …
View Full Document
Unlocking...