Introduction toComputer SystemsTopics:• Theme• Five great realities of computer systems• How this fits within CS curriculumCS 213 F ’01class01a.ppt15-213“The Class That Gives CMU Its Zip!”Randal E. BryantAugust 28, 2001CS 213 F ‘01 –2–class01a.pptCourse ThemeAbstraction is good, but don’t forget reality!Courses to date emphasize abstraction• Abstract data types• Asymptotic analysisThese abstractions have limits• Especially in the presence of bugs• Need to understand underlying implementationsUseful 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 SystemsCS 213 F ‘01 –3–class01a.pptGreat Reality #1Int’s are not Integers, Float’s are not RealsExamples• 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) --> ??CS 213 F ‘01 –4–class01a.pptComputer ArithmeticDoes not generate random values• Arithmetic operations have important mathematical propertiesCannot assume “usual” properties• Due to finiteness of representations• Integer operations satisfy “ring” properties–Commutativity, associativity, distributivity• Floating point operations satisfy “ordering” properties–Monotonicity, values of signsObservation• Need to understand which abstractions apply in which contexts• Important issues for compiler writers and serious applicationprogrammersCS 213 F ‘01 –5–class01a.pptGreat Reality #2You’ve got to know assemblyChances are, you’ll never write program in assembly• Compilers are much better & patient at this than you areUnderstanding assembly key to machine-levelexecution 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 stateCS 213 F ‘01 –6–class01a.pptAssembly Code ExampleTime Stamp Counter• Special 64-bit register in Intel-compatible machines• Incremented every clock cycle• Read with rdtsc instructionApplication• 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);CS 213 F ‘01 –7–class01a.pptCode to Read Counter• Write small amount of assembly code using GCC’s asm facility• 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 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");}CS 213 F ‘01 –8–class01a.pptCode 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;}CS 213 F ‘01 –9–class01a.pptMeasuring TimeTrickier than it Might Look• Many sources of variationExample• Sum 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.37CS 213 F ‘01 –10–class01a.pptGreat Reality #3Memory MattersMemory is not unbounded• It must be allocated and managed• Many applications are memory dominatedMemory referencing bugs especially pernicious• Effects are distant in both time and spaceMemory performance is not uniform• Cache and virtual memory effects can greatly affect programperformance• Adapting program to characteristics of memory system can lead tomajor speed improvementsCS 213 F ‘01 –11–class01a.pptMemory 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, butimplementing as separate function givessegmentation fault.)CS 213 F ‘01 –12–class01a.pptMemory Referencing ErrorsC and C++ do not provide any memory protection• Out of bounds array references• Invalid pointer values• Abuses of malloc/freeCan 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?• Program in Java, Lisp, or ML• Understand what possible interactions may occur• Use or develop tools to detect referencing errors–E.g., PurifyCS 213 F ‘01 –13–class01a.pptMemory Performance ExampleImplementations of Matrix Multiplication• 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; }}/* 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 }}/* 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 }}CS 213 F ‘01 –14–class01a.ppt020406080100120140160matrix size (n)ijkikjjikjkikijkjiMatmult Performance (Alpha 21164)Too big for L1 Cache Too big for L2 CacheCS 213 F ‘01 –15–class01a.pptBlocked matmult perf (Alpha 21164)02040608010012014016050 75 100 125 150 175 200 225 250 275 300 325 350 375 400
View Full Document
Unlocking...