Introduction toComputer SystemsTopics:• Theme• Five great realities of computer systems• How this fits within CS curriculumCS 213 F’00class01a.ppt15-213“The Class That Gives CMU Its Zip!”Randal E. BryantAugust 29, 2000CS 213 F ‘00 –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–Compilers, Operating Systems, Networks, Computer ArchitectureCS 213 F ‘00 –3–class01a.pptGreat Reality #1Int’s are not Integers, Float’s are not RealsExamples• Is x2 ≥ 0?–Float’s: Yes!–Int’s:» 65535 * 65535 --> -131071 (On most machines)» 65535L * 65535 --> 4292836225 (On Alpha)• Is (x + y) + z = x + (y + z)?–Unsigned & Signed Int’s: Yes!–Float’s:» (1e10 + -1e10) + 3.14 --> 3.14» 1e10 + (-1e10 + 3.14) --> 0.0CS 213 F ‘00 –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 (usually)–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 ‘00 –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 ‘00 –6–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 ‘00 –7–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 Sun-g 5.30498947741318e-315 3.1399998664856 3.14-O 3.14 3.14 3.14CS 213 F ‘00 –8–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 ‘00 –9–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 ‘00 –10–class01a.ppt020406080100120140160matrix size (n)ijkikjjikjkikijkjiMatmult Performance (Alpha 21164)Too big for L1 Cache Too big for L2 CacheCS 213 F ‘00 –11–class01a.pptBlocked matmult perf (Alpha 21164)02040608010012014016050 75 100 125 150 175 200 225 250 275 300 325 350 375 400 425 450 475 500matrix size (n)bijkbikjijkikjCS 213 F ‘00 –12–class01a.pptGreat Reality #4There’s more to performance than asymptoticcomplexityConstant factors matter too!• Easily see 10:1 performance range depending on how code written• Must optimize at multiple levels: algorithm, data representations,procedures, and loopsMust understand system to optimize performance• How programs compiled and executed• How to measure program performance and identify bottlenecks• How to improve performance without destroying code modularityand generalityCS 213 F ‘00 –13–class01a.pptGreat Reality #5Computers do more than execute programsThey need to get data in and out• I/O system critical to program reliability and performanceThey communicate with each other over networks• Many system-level issues arise in presence of network–Concurrent operations by autonomous processes–Coping with unreliable media–Cross platform compatibility–Complex performance issuesCS 213 F ‘00 –14–class01a.pptRole within CurriculumTransition from Abstract toConcrete!• From: high-level languagemodel• To: underlying implementationCS 211FundamentalStructuresCS 213SystemsCS 412OperatingSystemsCS 411CompilersProcessesMem. MgmtMachine CodeOptimizationData StructuresApplicationsProgrammingCS 212ExecutionModelsCS 441NetworksNetworkProtocolsECE 347ArchitectureECE 349EmbeddedSystemsExec. ModelMemory SystemCS 213 F ‘00 –15–class01a.pptCourse PerspectiveMost Systems Courses are Builder-Centric• Computer Architecture–Design pipelined processor in Verilog• Operating Systems–Implement large portions of operating system• Compilers–Write compiler for simple language• Networking–Implement and simulate network protocolsCS 213
View Full Document