Introduction to Computer SystemsCourse ThemeGreat Reality #1Computer ArithmeticGreat Reality #2Assembly Code ExampleCode to Read CounterSlide 8Measuring TimeTiming System PerformanceSlide 11Great Reality #3Memory Performance ExampleMatmult Performance (Alpha 21164)Memory SystemBlocked matmult perf (Alpha 21164)Real Memory PerformanceMemory Referencing Bug ExampleMemory Referencing ErrorsGreat Reality #4Great Reality #5Hardware Organization (Naïve)Role within CurriculumCourse PerspectiveCourse Perspective (Cont.)Teaching staffTextbooksCourse ComponentsGetting HelpPolicies: AssignmentsCheatingPolicies: GradingFacilitiesPrograms and DataPerformanceThe Memory HierarchyLinking and Exceptional Control FlowVirtual memoryI/O, Networking, and ConcurrencyLab RationaleAutolab Web ServiceAcknowledgementHave a Great Semester!Introduction to Computer SystemsTopics:ThemeFive great realities of computer systemsHow this fits within CS curriculumStaff, text, and policiesLecture topics and assignmentsLab rationaleclass01.ppt15-213“The Class That Gives CMU Its Zip!”Seth Goldstein & Andreas NowatzykJanuary 13, 2004– 2 –15-213, S’04Course 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 CS & ECECompilers, Operating Systems, Networks, Computer Architecture, Embedded Systems– 3 –15-213, S’04Great 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) --> ??-1794967296 0– 4 –15-213, S’04Computer 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 application programmers– 5 –15-213, S’04Great 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 execution modelBehavior 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 state– 6 –15-213, S’04Assembly 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);– 7 –15-213, S’04Code 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");}– 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 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.37– 10 –15-213, S’04main(int argc, char** argv){ ... for (i=0; i<t; i++) { start_counter(); count(n); times[i] = get_counter(); } ...}int count(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){ ...}int count(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 unboundedIt must be allocated and managedMany applications are memory dominatedMemory performance is not uniformCache and virtual memory effects can greatly affect program performanceAdapting program to characteristics of memory system can lead to major speed improvementsMemory referencing bugs especially perniciousEffects are distant in both time and space– 13 –15-213, S’04Memory 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; }} /* 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,
View Full Document
Unlocking...