Introduction to Computer SystemsIntroduction to Computer SystemsTopics:Topics: Theme Five great realities of computer systems How this fits within CS curriculumCS 213 F ’03class01a.ppt15-213“The Class That Gives CMU Its Zip!”Andreas G. NowatzykAugust 26, 2003– 2 –15-213, F’03AcknowledgementAcknowledgement1515--213 was developed and fine213 was developed and fine--tuned by tuned by Randal E. Bryant and David Randal E. Bryant and David O’HallaronO’Hallaron. . They wrote They wrote The BookThe Book!!– 3 –15-213, F’03Course ThemeCourse Theme Abstraction is good, but don’t forget reality!Courses to date emphasize abstractionCourses to date emphasize abstraction Abstract data types Asymptotic analysisThese abstractions have limitsThese abstractions have limits Especially in the presence of bugs Need to understand underlying implementationsUseful outcomesUseful 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 Systems– 4 –15-213, F’03Great Reality #1Great Reality #1Int’sInt’sare not Integers, Float’s are not are not Integers, Float’s are not RealsRealsExamplesExamples 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) --> ??– 5 –15-213, F’03Computer ArithmeticComputer ArithmeticDoes not generate random valuesDoes not generate random values Arithmetic operations have important mathematical propertiesCannot assume “usual” 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 signsObservationObservation Need to understand which abstractions apply in which contexts Important issues for compiler writers and serious application programmers– 6 –15-213, F’03Great 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 assembly Compilers are much better & more patient than you areUnderstanding assembly key to machineUnderstanding assembly key to machine--level level execution modelexecution 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 state– 7 –15-213, F’03Assembly Code ExampleAssembly Code ExampleTime Stamp CounterTime Stamp Counter Special 64-bit register in Intel-compatible machines Incremented every clock cycle Read with rdtsc instructionApplicationApplication 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);– 8 –15-213, F’03Code to Read CounterCode 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 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");}– 9 –15-213, F’03Code 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;}– 10 –15-213, F’03Measuring TimeMeasuring TimeTrickier than it Might LookTrickier than it Might Look Many sources of variationExampleExample 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– 11 –15-213, F’03Great Reality #3Great Reality #3Memory Matters: Memory Matters: Random Access Memory is anRandom Access Memory is anunun--physical abstractionphysical abstractionMemory is not unboundedMemory is not unbounded It must be allocated and managed Many applications are memory dominatedMemory referencing bugs especially perniciousMemory referencing bugs especially pernicious Effects are distant in both time and spaceMemory performance is not uniformMemory performance is not uniform Cache and virtual memory effects can greatly affect program performance Adapting program to characteristics of memory system can lead to major speed improvements– 12 –15-213, F’03Memory 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, but implementing as separate function gives segmentation fault.)– 13 –15-213, F’03Memory Referencing ErrorsMemory Referencing ErrorsC and C++ do not provide any memory protectionC and C++ do not provide any memory protection Out of bounds array references Invalid pointer values Abuses of malloc/freeCan lead to nasty bugsCan 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?How can I deal with this? Program in Java, Lisp, or ML Understand what possible interactions may occur Use or
View Full Document