Introduction toComputer SystemsIntroduction toComputer SystemsTopics:Topics:n Themen Five great realities of computersystemsn How this fits within CS curriculumCS 213 F Õ02class01a.ppt15-213ÒThe Class That Gives CMU Its Zip!ÓRandal E. BryantAugust 27, 2002– 2 –15-213, F’02Course ThemeCourse Themen Abstraction is good, but don’t forget reality!Courses to date emphasize abstractionCourses to date emphasize abstractionn Abstract data typesn Asymptotic analysisThese abstractions have limitsThese abstractions have limitsn Especially in the presence of bugsn Need to understand underlying implementationsUseful outcomesUseful 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, ComputerArchitecture, Embedded Systems– 3 –15-213, F’02Great Reality #1Great Reality #1Int’sInt’s are not Integers, Float’s are not are not Integers, Float’s are not RealsRealsExamplesExamplesn 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) --> ??– 4 –15-213, F’02Computer ArithmeticComputer ArithmeticDoes not generate random valuesDoes not generate random valuesn Arithmetic operations have important mathematicalpropertiesCannot assume “usual” 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 signsObservationObservationn Need to understand which abstractions apply in whichcontextsn Important issues for compiler writers and serious applicationprogrammers– 5 –15-213, F’02Great 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 assemblyn Compilers are much better & more patient than you areUnderstanding assembly key to machine-levelUnderstanding assembly key to machine-levelexecution modelexecution 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, F’02Assembly Code ExampleAssembly Code ExampleTime Stamp CounterTime Stamp Countern Special 64-bit register in Intel-compatible machinesn Incremented every clock cyclen Read with rdtsc instructionApplicationApplicationn 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, F’02Code to Read CounterCode to Read Countern Write small amount of assembly code using GCC’s asmfacilityn Inserts assembly code into machine code generated bycompilerstatic 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, F’02Code to Read CounterCode 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, F’02Measuring TimeMeasuring TimeTrickier than it Might LookTrickier than it Might Lookn Many sources of variationExampleExamplen 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.37– 10 –15-213, F’02Great Reality #3Great Reality #3Memory MattersMemory MattersMemory is not unboundedMemory is not unboundedn It must be allocated and managedn Many applications are memory dominatedMemory referencing bugs especially perniciousMemory referencing bugs especially perniciousn Effects are distant in both time and spaceMemory performance is not uniformMemory performance is not uniformn Cache and virtual memory effects can greatly affect programperformancen Adapting program to characteristics of memory system canlead to major speed improvements– 11 –15-213, F’02Memory Referencing Bug ExampleMemory 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.)– 12 –15-213, F’02Memory Referencing ErrorsMemory Referencing ErrorsC and C++ do not provide any memory protectionC and C++ do not provide any memory protectionn Out of bounds array referencesn Invalid pointer valuesn Abuses of malloc/freeCan lead to nasty bugsCan lead to nasty bugsn Whether or not bug has any effect depends on system andcompilern Action at a distancel Corrupted object logically unrelated to one being accessedl Effect of bug may be first observed long after it is generatedHow can I deal with this?How can I deal with this?n Program in Java, Lisp, or MLn Understand what possible interactions may occurn Use or develop tools to detect referencing errors– 13 –15-213, F’02Memory Performance ExampleMemory Performance ExampleImplementations of Matrix MultiplicationImplementations 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; }}/* ijk */for (i=0; i<n; i++) { for (j=0; j<n; j++)
View Full Document
Unlocking...