Introduction to Computer SystemsIntroduction to Computer SystemsTopics:Topics:Theme and objectiveFive great realities of computer systemsHow this fits within CS curriculumCourse mechanics and overview15-213 S’0601-overview.ppt15-213“The Class That Gives CMU Its Zip!”Frank PfenningJanuary 17, 2006– 2 –15-213, S’06Course ThemeCourse ThemeAbstraction is good, but programs run on real hardware!Courses to date emphasize abstractionCourses to date emphasize abstractionAbstract data typesAsymptotic analysisThese abstractions have limitsThese abstractions have limitsNeed to understand underlying implementationsPerformance (time and space)Useful outcomesUseful 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’06Great Reality #1Great Reality #1Int’sInt’sare not Integers, Float’s are not are not Integers, Float’s are not RealsRealsExamplesExamplesIs 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) --> ??– 4 –15-213, S’06Computer ArithmeticComputer ArithmeticDoes not generate random valuesDoes not generate random valuesArithmetic operations have important mathematical propertiesCannot assume “usual” propertiesCannot assume “usual” propertiesDue to finiteness of representationsInteger operations satisfy “ring” propertiesCommutativity, associativity, distributivityFloating point operations satisfy “ordering” propertiesMonotonicity, values of signsObservationObservationNeed to understand which abstractions apply in which contextsImportant issues for compiler writers and serious application programmers– 5 –15-213, S’06Great Reality #2Great Reality #2You’ve got to know assemblyYou’ve got to know assemblyChances are, you’ll never write a program in assemblyChances are, you’ll never write a program in assemblyCompilers are much better and more patient than you areUnderstanding assembly key to machineUnderstanding assembly key to machine--level level execution modelexecution modelBehavior of programs in presence of bugsHigh-level language model is inadequateTuning program performanceUnderstanding sources of program inefficiencyImplementing system softwareCompiler has machine code as targetOperating systems must manage process state– 6 –15-213, S’06Measuring TimeMeasuring TimeTrickier than it Might LookTrickier than it Might LookMany sources of variationExampleExampleSum 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– 7 –15-213, S’06Great Reality #3Great Reality #3Memory Matters: Memory Matters: Random Access Memory is anRandom Access Memory is anunun--physical abstractionphysical abstractionMemory is not unboundedMemory is not unboundedIt must be allocated and managedMany applications are memory dominatedMemory referencing bugs especially perniciousMemory referencing bugs especially perniciousEffects are distant in both time and spaceMemory performance is not uniformMemory performance is not uniformCache and virtual memory effects can greatly affect program performanceAdapting program to characteristics of memory system can lead to major speed improvements– 8 –15-213, S’06Memory 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.)– 9 –15-213, S’06Memory Referencing ErrorsMemory Referencing ErrorsC and C++ do not provide any memory protectionC and C++ do not provide any memory protectionOut of bounds array referencesInvalid pointer valuesAbuses of malloc/freeCan lead to nasty bugsCan lead to nasty bugsWhether or not bug has any effect depends on system and compilerAction at a distanceCorrupted object logically unrelated to one being accessedEffect 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, ML, or CycloneUnderstand what possible interactions may occurUse or develop tools to detect referencing errors– 10 –15-213, S’06Memory System Performance ExampleMemory System Performance ExampleHierarchical memory organizationPerformance depends on access patternsIncluding how step through multi-dimensional arrayvoid copyji(int src[2048][2048],int dst[2048][2048]){int i,j;for (j = 0; j < 2048; j++)for (i = 0; i < 2048; i++)dst[i][j] = src[i][j];}void copyij(int src[2048][2048],int dst[2048][2048]){int i,j;for (i = 0; i < 2048; i++)for (j = 0; j < 2048; j++)dst[i][j] = src[i][j];}59,393,288 clock cycles 1,277,877,876 clock cycles21.5 times slower!(Measured on 2GHzIntel Pentium 4)– 11 –15-213, S’06The Memory MountainThe Memory Mountains1s3s5s7s9s11s13s158m2m512k128k32k8k2k020040060080010001200Read throughput (MB/s)Stride (words)Working set size (bytes)Pentium III Xeon550 MHz16 KB on-chip L1 d-cache16 KB on-chip L1 i-cache512 KB off-chip unifiedL2 cacheL1L2Memxecopyijcopyji– 12 –15-213, S’06Memory Performance ExampleMemory Performance ExampleImplementations of Matrix MultiplicationImplementations 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;}} /* 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] =
View Full Document