Introduction to Computer SystemsIntroduction to Computer SystemsTopics:Topics: Theme Five great realities of computer systems How this fits within CS curriculum15-213 F ’06class01a.ppt15-213“The Class That Gives CMU Its Zip!”Randal E. BryantAugust 30, 2006– 2 –15-213, F’06Course ThemeCourse Theme Abstraction is good, but don’t forget reality!Courses to date emphasize abstractionCourses to date emphasize abstraction Abstract data types Asymptotic analysisThese abstractions have limitsThese abstractions have limits Especially in the presence of bugs Need to understand underlying implementationsUseful outcomesUseful outcomes Become more effective programmers Able to find and eliminate bugs efficiently Able to tune program performance Prepare for later “systems” classes in CS & ECE Compilers, Operating Systems, Networks, Computer Architecture, Embedded Systems– 3 –15-213, F’06Great Reality #1Great Reality #1IntInt’’ssare not Integers, Floatare not Integers, Float’’s are not s are not RealsRealsExamplesExamples Is x2≥ 0? Float’s: Yes! Int’s:» 40000 * 40000 --> 1600000000» 50000 * 50000 --> ?? Is (x + y) + z = x + (y + z)? Unsigned & Signed Int’s: Yes! Float’s:» (1e20 + -1e20) + 3.14 --> 3.14» 1e20 + (-1e20 + 3.14) --> ??– 4 –15-213, F’06Computer ArithmeticComputer ArithmeticDoes not generate random valuesDoes not generate random values Arithmetic operations have important mathematical propertiesCannot assume Cannot assume ““usualusual””propertiesproperties Due to finiteness of representations Integer operations satisfy “ring” properties Commutativity, associativity, distributivity Floating point operations satisfy “ordering” properties Monotonicity, values of signsObservationObservation Need to understand which abstractions apply in which contexts Important issues for compiler writers and serious application programmers– 5 –15-213, F’06Great Reality #2Great Reality #2YouYou’’ve got to know assemblyve got to know assemblyChances are, youChances are, you’’ll never write program in assemblyll never write program in assembly Compilers are much better & more patient than you areUnderstanding assembly key to machineUnderstanding assembly key to machine--level level execution modelexecution model Behavior of programs in presence of bugs High-level language model breaks down Tuning program performance Understanding sources of program inefficiency Implementing system software Compiler has machine code as target Operating systems must manage process state Creating / fighting malware x86 assembly is the language of choice!– 6 –15-213, F’06Assembly Code ExampleAssembly Code ExampleTime Stamp CounterTime Stamp Counter Special 64-bit register in Intel-compatible machines Incremented every clock cycle Read with rdtsc instructionApplicationApplication Measure time required by procedure In units of clock cyclesdouble t;start_counter();P();t = get_counter();printf("P required %f clock cycles\n", t);– 7 –15-213, F’06Code to Read CounterCode to Read Counter Write small amount of assembly code using GCC’s asmfacility Inserts assembly code into machine code generated by compilerstatic unsigned cyc_hi = 0;static unsigned cyc_lo = 0;/* Set *hi and *lo to the high and low order bitsof the cycle counter. */void access_counter(unsigned *hi, unsigned *lo){asm("rdtsc; movl %%edx,%0; movl %%eax,%1": "=r" (*hi), "=r" (*lo) :: "%edx", "%eax");}– 8 –15-213, F’06Great Reality #3Great Reality #3Memory Matters: Memory Matters: Random Access Memory is anRandom Access Memory is anunun--physical abstractionphysical abstractionMemory is not unboundedMemory is not unbounded It must be allocated and managed Many applications are memory dominatedMemory referencing bugs especially perniciousMemory referencing bugs especially pernicious Effects are distant in both time and spaceMemory performance is not uniformMemory 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– 9 –15-213, F’06Memory Referencing Bug ExampleMemory Referencing Bug Exampledouble fun(int i){volatile double d[1] = {3.14};volatile long int a[2];a[i] = 1073741824; /* Possibly out of bounds */return d[0];}double fun(int i){volatile double d[1] = {3.14};volatile long int a[2];a[i] = 1073741824; /* Possibly out of bounds */return d[0];}fun(0) –> 3.14fun(1) –> 3.14fun(2) –> 3.1399998664856fun(3) –> 2.00000061035156fun(4) –> 3.14, then segmentation faultfun(0) –> 3.14fun(1) –> 3.14fun(2) –> 3.1399998664856fun(3) –> 2.00000061035156fun(4) –> 3.14, then segmentation fault– 10 –15-213, F’06Referencing Bug ExplanationReferencing Bug Explanation C does not implement bounds checking Out of range write can affect other parts of program stateSaved Stated7 … d4d3 … d0a[1]a[0]01234Location accessedby fun(i)– 11 –15-213, F’06Memory Referencing ErrorsMemory Referencing ErrorsC and C++ do not provide any memory protectionC and C++ do not provide any memory protection Out of bounds array references Invalid pointer values Abuses of malloc/freeCan lead to nasty bugsCan lead to nasty bugs Whether or not bug has any effect depends on system and compiler Action at a distance Corrupted object logically unrelated to one being accessed Effect of bug may be first observed long after it is generatedHow can I deal with this?How can I deal with this? Program in Java, Lisp, or ML Understand what possible interactions may occur Use or develop tools to detect referencing errors– 12 –15-213, F’06Memory System Performance ExampleMemory System Performance Example Hierarchical memory organization Performance depends on access patterns Including how step through multi-dimensional arrayvoid copyji(int src[2048][2048],int dst[2048][2048]){int i,j;for (j = 0; j < 2048; j++)for (i = 0; i < 2048; i++)dst[i][j] = src[i][j];}void copyij(int src[2048][2048],int dst[2048][2048]){int i,j;for (i = 0; i < 2048; i++)for (j = 0; j < 2048; j++)dst[i][j] = src[i][j];}59,393,288 clock cycles 1,277,877,876 clock cycles21.5 times slower!(Measured on 2GHzIntel Pentium 4)– 13 –15-213, F’06The Memory MountainThe Memory
View Full Document