Introduction to Computer SystemsIntroduction to Computer SystemsTopics:Topics: Theme Five great realities of computer systems How this fits within CS curriculum15-213 S ‘08class01a.ppt15-213“The Class That Gives CMU Its Zip!”Randal E. BryantJanuary 15, 2008–2–15-213, S ‘08Course ThemeCourse Theme Abstraction is good, but don’t forget reality!Most CS courses emphasize abstractionMost CS courses 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 programmersz Able to find and eliminate bugs efficientlyz Able to tune program performance Prepare for later “systems” classes in CS & ECEz Compilers, Operating Systems, Networks, Computer Architecture, Embedded Systems–3–15-213, S ‘08Great Reality #1Great Reality #1IntInt’’ssare not Integers, Floatare not Integers, Float’’s are not s are not RealsRealsExamplesExamples Is x2≥ 0?z Float’s: Yes!z Int’s:» 40000 * 40000 --> 1600000000» 50000 * 50000 --> ?? Is (x + y) + z = x + (y + z)?z Unsigned & Signed Int’s: Yes!z Float’s:» (1e20 + -1e20) + 3.14 --> 3.14» 1e20 + (-1e20 + 3.14) --> ??–4–15-213, S ‘08Computer 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” propertiesz Commutativity, associativity, distributivity Floating point operations satisfy “ordering” propertiesz 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, S ‘08Great 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 bugsz High-level language model breaks down Tuning program performancez Understanding sources of program inefficiency Implementing system softwarez Compiler has machine code as targetz Operating systems must manage process state Creating / fighting malwarez x86 assembly is the language of choice!–6–15-213, S ‘08Assembly 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 procedurez In units of clock cyclesdouble t;start_counter();P();t = get_counter();printf("P required %f clock cycles\n", t);–7–15-213, S ‘08Code 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, S ‘08Great 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, S ‘08Memory 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, S ‘08Referencing 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, S ‘08Memory 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 distancez Corrupted object logically unrelated to one being accessedz 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 or ML Understand what possible interactions may occur Use or develop tools to detect referencing errors–12–15-213, S ‘08Memory System Performance ExampleMemory System Performance Example Hierarchical memory organization Performance depends on access patternsz 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, S ‘08The Memory MountainThe Memory
View Full Document