Introduction to Computer SystemsTopics:n Themen Five great realities of computer systemsn How this fits within CS curriculumn Staff, text, and policiesn Lecture topics and assignmentsn Lab rationaleclass01.ppt15-213“The Class That Gives CMU Its Zip!”Seth Goldstein & Andreas NowatzykJanuary 13, 2004– 2 –15-213, S’04Course ThemenAbstraction is good, but don’t forget reality!Courses to date emphasize abstractionn Abstract data typesn Asymptotic analysisThese abstractions have limitsn Especially in the presence of bugsn Need to understand underlying implementationsUseful outcomesn Become more effective programmersl Able to find and eliminate bugs efficientlyl Able to tune program performancen Prepare for later “systems” classes in CS & ECEl Compilers, Operating Systems, Networks, Computer Architecture, Embedded Systems– 3 –15-213, S’04Great Reality #1Int’s are not Integers, Float’s are not RealsExamplesn Is x2≥ 0?l Float’s: Yes!l Int’s:» 40000 * 40000 --> 1600000000» 50000 * 50000 --> ??n Is (x + y) + z = x + (y + z)?l Unsigned & Signed Int’s: Yes!l Float’s:» (1e20 + -1e20) + 3.14 --> 3.14» 1e20 + (-1e20 + 3.14) --> ??-17949672960 – 4 –15-213, S’04Computer ArithmeticDoes not generate random valuesn Arithmetic operations have important mathematical propertiesCannot assume “usual” propertiesn Due to finiteness of representationsn Integer operations satisfy “ring” propertiesl Commutativity, associativity, distributivityn Floating point operations satisfy “ordering” propertiesl Monotonicity, values of signsObservationn Need to understand which abstractions apply in which contextsn Important issues for compiler writers and serious application programmers– 5 –15-213, S’04Great Reality #2You’ve got to know assemblyChances are, you’ll never write program in assemblyn Compilers are much better & more patient than you areUnderstanding assembly key to machine-level execution modeln Behavior of programs in presence of bugsl High-level language model breaks downn Tuning program performancel Understanding sources of program inefficiencyn Implementing system softwarel Compiler has machine code as targetl Operating systems must manage process state– 6 –15-213, S’04Assembly Code ExampleTime Stamp Countern Special 64-bit register in Intel-compatible machinesn Incremented every clock cyclen Read with rdtsc instructionApplicationn Measure time required by procedurel In units of clock cyclesdouble t;start_counter();P();t = get_counter();printf("P required %f clock cycles\n", t);– 7 –15-213, S’04Code to Read CounternWrite small amount of assembly code using GCC’s asmfacilityn 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’04Code 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;}– 9 –15-213, S’04Measuring TimeTrickier than it Might Lookn Many sources of variationExamplen Sum integers from 1 to nn 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.37– 10 –15-213, S’04main(int argc, char** argv){...for (i=0; i<t; i++) {start_counter();count(n);times[i] = get_counter();}...}intcount(int n){int i;int sum = 0;for (i=0; i<n; i++) {sum += i;}return sum;}Timing System Performanceint count(int n){int i;int sum = 0;for (i=0; i<n; i++) {sum += i;}return sum;}main(int argc, char** argv){...for (i=0; i<t; i++) {start_counter();count(n);times[i] = get_counter();}...}– 11 –15-213, S’04Timing System Performanceint count(int n){...}main(int argc, char** argv){...}main(int argc, char** argv){...}intcount(int n){...}Experiment n cycles/n1 10 1649.22 10 17.23 1000 24.34 1000 6.1Experiment n cycles/n1 10 1657.62 10 261a 10 202a 10 16.43a 1000 1.74a 1000 1.6It’s the system, stupid!It’s the system, stupid!– 12 –15-213, S’04Great Reality #3Memory Matters Random Access Memory is anun-physical abstractionMemory is not unboundedn It must be allocated and managedn Many applications are memory dominatedMemory performance is not uniformn Cache and virtual memory effects can greatly affect program performancen Adapting program to characteristics of memory system can lead to major speed improvementsMemory referencing bugs especially perniciousn Effects are distant in both time and space– 13 –15-213, S’04Memory Performance ExampleImplementations of Matrix Multiplicationn 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;}} /* 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}}– 14 –15-213, S’04020406080100120140160matrix size (n)ijkikjjikjkikijkjiMatmult Performance (Alpha 21164)Too big for L1 Cache Too big for L2 CacheIterations/time– 15 –15-213, S’04Memory System– 16 –15-213, S’04Blocked matmult perf (Alpha 21164)02040608010012014016050 75 100 125 150 175 200 225 250 275 300 325 350 375 400 425 450 475 500matrix size (n)bijkbikjijkikjIterations/time– 17 –15-213, S’04Real Memory PerformanceFrom Tom Womack’smemory latency benchmarkPointer-Chase Results1101001000Iteration Time [ns]– 18 –15-213, S’04Memory 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);}main (){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, but implementing as separate function gives segmentation fault.)– 19 –15-213, S’04Memory Referencing ErrorsC and C++ do not