Introduction to Computer SystemsCourse ThemeGreat Reality #1Computer ArithmeticGreat Reality #2Assembly Code ExampleCode to Read CounterGreat Reality #3Memory Referencing Bug ExampleReferencing Bug ExplanationMemory Referencing ErrorsMemory System Performance ExampleThe Memory MountainGreat Reality #4Code Performance ExampleLoop Unrollingsu2: Serial Computationu2r: Reassociated ComputationGreat Reality #5Role within CurriculumCourse PerspectiveCourse Perspective (Cont.)Introduction to Computer SystemsIntroduction to Computer SystemsTopics:Topics:ThemeFive great realities of computer systemsHow 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 ThemeAbstraction is good, but don’t forget reality!Most CS courses emphasize abstractionMost CS courses emphasize abstractionAbstract data typesAsymptotic analysisThese abstractions have limitsThese abstractions have limitsEspecially in the presence of bugsNeed to understand underlying implementationsUseful outcomesUseful outcomesBecome more effective programmersAble to find and eliminate bugs efficientlyAble to tune program performancePrepare for later “systems” classes in CS & ECECompilers, Operating Systems, Networks, Computer Architecture, Embedded Systems– 3 –15-213, S ‘08Great Reality #1Great Reality #1Int’s are not Integers, Float’s are not RealsInt’s are not Integers, Float’s are not RealsExamplesExamplesIs 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, S ‘08Computer ArithmeticComputer ArithmeticDoes not generate random valuesDoes not generate random valuesArithmetic operations have important mathematical propertiesCannot assume “usual” propertiesCannot assume “usual” propertiesDue to finiteness of representationsInteger operations satisfy “ring” propertiesCommutativity, associativity, distributivityFloating point operations satisfy “ordering” propertiesMonotonicity, values of signsObservationObservationNeed to understand which abstractions apply in which contextsImportant issues for compiler writers and serious application programmers– 5 –15-213, S ‘08Great Reality #2Great Reality #2You’ve got to know assemblyYou’ve got to know assemblyChances are, you’ll never write program in assemblyChances are, you’ll never write program in assemblyCompilers are much better & more patient than you areUnderstanding assembly key to machine-level execution Understanding assembly key to machine-level execution modelmodelBehavior of programs in presence of bugsHigh-level language model breaks downTuning program performanceUnderstanding sources of program inefficiencyImplementing system softwareCompiler has machine code as targetOperating systems must manage process stateCreating / fighting malwarex86 assembly is the language of choice!– 6 –15-213, S ‘08Assembly Code ExampleAssembly Code ExampleTime Stamp CounterTime Stamp CounterSpecial 64-bit register in Intel-compatible machinesIncremented every clock cycleRead with rdtsc instructionApplicationApplicationMeasure time required by procedureIn 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 CounterWrite small amount of assembly code using GCC’s asm facilityInserts 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 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");}– 8 –15-213, S ‘08Great Reality #3Great Reality #3Memory Matters: Memory Matters: Random Access Memory is anRandom Access Memory is anun-physical abstractionun-physical abstractionMemory is not unboundedMemory is not unboundedIt must be allocated and managedMany applications are memory dominatedMemory referencing bugs especially perniciousMemory referencing bugs especially perniciousEffects are distant in both time and spaceMemory performance is not uniformMemory performance is not uniformCache and virtual memory effects can greatly affect program performanceAdapting 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 ExplanationC does not implement bounds checkingOut 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 protectionOut of bounds array referencesInvalid pointer valuesAbuses of malloc/freeCan lead to nasty bugsCan lead to nasty bugsWhether or not bug has any effect depends on system and compilerAction at a distanceCorrupted object logically unrelated to one being accessedEffect 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 MLUnderstand what possible interactions may occurUse or develop tools to detect referencing errors– 12 –15-213, S ‘08Memory System Performance ExampleMemory System Performance ExampleHierarchical memory organizationPerformance depends on access patternsIncluding how step through
View Full Document