University of Texas at Austin CS429H - Introduction to Computer Systems Fall 2011 Don FussellSystems I Introduction to Computer SystemsDon FussellSpring 2011Topics: Theme Five great realities of computer systems How this fits within CS curriculumUniversity of Texas at Austin CS429H - Introduction to Computer Systems Fall 2011 Don Fussell 2Course ThemeAbstraction is good, but don’t forget reality!Courses to date emphasize abstractionAbstract data typesAsymptotic analysisThese abstractions have limitsEspecially in the presence of bugsNeed to understand underlying implementationsUseful outcomesBecome more effective programmersAble to find and eliminate bugs efficientlyAble to tune program performancePrepare for later “systems” classes in CSCompilers, Operating Systems, Networks, Computer Architecture, etc.University of Texas at Austin CS429H - Introduction to Computer Systems Fall 2011 Don Fussell 3Great Reality #1Int’s are not Integers, Float’s are not RealsExamplesIs 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) --> ??University of Texas at Austin CS429H - Introduction to Computer Systems Fall 2011 Don Fussell 4Computer ArithmeticDoes not generate random valuesArithmetic operations have important mathematical propertiesCannot assume “usual” propertiesDue to finiteness of representationsInteger operations satisfy “ring” propertiesCommutativity, associativity, distributivityFloating point operations satisfy “ordering” propertiesMonotonicity, values of signsObservationNeed to understand which abstractions apply in which contextsImportant issues for compiler writers and serious applicationprogrammersUniversity of Texas at Austin CS429H - Introduction to Computer Systems Fall 2011 Don Fussell 5Great Reality #2You’ve got to know assemblyChances are, you’ll never write program in assemblyCompilers are much better & more patient than you areUnderstanding assembly key to machine-level executionmodelBehavior 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 stateUniversity of Texas at Austin CS429H - Introduction to Computer Systems Fall 2011 Don Fussell 6Assembly Code ExampleTime Stamp CounterSpecial 64-bit register in Intel-compatible machinesIncremented every clock cycleRead with rdtsc instructionApplicationMeasure time required by procedureIn units of clock cyclesdouble t;start_counter();P();t = get_counter();printf("P required %f clock cycles\n", t);University of Texas at Austin CS429H - Introduction to Computer Systems Fall 2011 Don Fussell 7Code 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");}University of Texas at Austin CS429H - Introduction to Computer Systems Fall 2011 Don Fussell 8Code to Read Counter/* 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;}University of Texas at Austin CS429H - Introduction to Computer Systems Fall 2011 Don Fussell 9Measuring TimeTrickier than it Might LookMany sources of variationExampleSum integers from 1 to n n Cycles Cycles/n100 961 9.611,000 8,407 8.411,000 8,426 8.4310,000 82,861 8.2910,000 82,876 8.291,000,000 8,419,907 8.421,000,000 8,425,181 8.431,000,000,000 8,371,2305,591 8.37University of Texas at Austin CS429H - Introduction to Computer Systems Fall 2011 Don Fussell 10Great Reality #3Memory MattersMemory is not unboundedIt must be allocated and managedMany applications are memory dominatedMemory referencing bugs especially perniciousEffects are distant in both time and spaceMemory performance is not uniformCache and virtual memory effects can greatly affect programperformanceAdapting program to characteristics of memory system can lead tomajor speed improvementsUniversity of Texas at Austin CS429H - Introduction to Computer Systems Fall 2011 Don Fussell 11Memory Referencing Bug Examplemain (){ long int a[2]; double d = 3.14; a[2] = 1073741824; /* Out of bounds reference */ printf("d = %.15g\n", d); exit(0);}Alpha MIPS Linux-g 5.30498947741318e-315 3.1399998664856 3.14-O 3.14 3.14 3.14(Linux version gives correct result, butimplementing as separate function givessegmentation fault.)University of Texas at Austin CS429H - Introduction to Computer Systems Fall 2011 Don Fussell 12Memory Referencing ErrorsC and C++ do not provide any memory protectionOut of bounds array referencesInvalid pointer valuesAbuses of malloc/freeCan 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?Program in Java, Lisp, or MLUnderstand what possible interactions may occurUse or develop tools to detect referencing errorsUniversity of Texas at Austin CS429H - Introduction to Computer Systems Fall 2011 Don Fussell 13Memory Performance ExampleImplementations of Matrix MultiplicationMultiple 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; }}/* jik */for (j=0; j<n; j++) { for (i=0; i<n; i++) { sum = 0.0; for (k=0; k<n; k++) sum += a[i][k] * b[k][j]; c[i][j] = sum }}University of Texas at Austin CS429H - Introduction to Computer Systems