Introduction to Computer Systems*Course ThemeGreat Reality #1Computer ArithmeticGreat Reality #2Assembly Code ExampleGreat Reality #3Memory Referencing Bug ExampleReferencing Bug ExplanationMemory Referencing ErrorsMemory System Performance ExampleThe Memory MountainMemory Performance ExampleMatmult Performance (Alpha 21164)Blocked matmult perf (Alpha 21164)Great Reality #4Great Reality #5Role within CurriculumCourse PerspectiveCourse Perspective (Cont.)Introduction to Computer Systems*Introduction to Computer Systems*Topics:Topics:ThemeFive great realities of computer systemsHow this fits within CS curriculum15-213 F ’09class01a.ppt15-213Khaled A. HarrasAugust 24, 2009* Slide Credits: Prof. Randal E. Bryant215-213: Intro to Computer SystemsFall 2009 ©Course ThemeCourse ThemeAbstraction is good, but don’t forget reality!Courses to date emphasize abstractionCourses to date emphasize abstractionAbstract data typesAsymptotic analysisThese abstractions have limitsThese abstractions have limitsEspecially in the presence of bugsNeed to understand underlying implementationsUseful 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 Systems315-213: Intro to Computer SystemsFall 2009 ©Great Reality #1Great Reality #1Int’s are not Integers, Float’s are not RealsInt’s are not Integers, Float’s are not RealsExamplesExamplesIs 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) --> ??415-213: Intro to Computer SystemsFall 2009 ©Computer 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 programmers515-213: Intro to Computer SystemsFall 2009 ©Great 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 assemblyCompilers are much better & more patient than you areUnderstanding assembly key to machine-level execution Understanding assembly key to machine-level execution modelmodelBehavior 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 stateCreating / fighting malwarex86 assembly is the language of choice!615-213: Intro to Computer SystemsFall 2009 ©Assembly Code ExampleAssembly Code ExampleTime Stamp CounterTime Stamp CounterSpecial 64-bit register in Intel-compatible machinesIncremented every clock cycleRead with rdtsc instructionApplicationApplicationMeasure time required by procedureIn units of clock cyclesdouble t;start_counter();P();t = get_counter();printf("P required %f clock cycles\n", t);715-213: Intro to Computer SystemsFall 2009 ©Great Reality #3Great Reality #3Memory Matters: Memory Matters: Random Access Memory is anRandom Access Memory is anun-physical abstractionun-physical 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 improvements815-213: Intro to Computer SystemsFall 2009 ©Memory Referencing Bug ExampleMemory Referencing Bug Exampledouble fun(int i){ volatile double d[1] = {3.14}; volatile long int a[2]; a[i] = 1073741824; /* Possibly out of bounds */ return d[0];}double fun(int i){ volatile double d[1] = {3.14}; volatile long int a[2]; a[i] = 1073741824; /* Possibly out of bounds */ return d[0];}fun(0) –> 3.14fun(1) –> 3.14fun(2) –> 3.1399998664856fun(3) –> 2.00000061035156fun(4) –> 3.14, then segmentation faultfun(0) –> 3.14fun(1) –> 3.14fun(2) –> 3.1399998664856fun(3) –> 2.00000061035156fun(4) –> 3.14, then segmentation fault915-213: Intro to Computer SystemsFall 2009 ©Referencing Bug ExplanationReferencing Bug ExplanationC does not implement bounds checkingOut of range write can affect other parts of program stateSaved Stated7 … d4d3 … d0a[1]a[0]01234Location accessedby fun(i)1015-213: Intro to Computer SystemsFall 2009 ©Memory 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, or MLUnderstand what possible interactions may occurUse or develop tools to detect referencing errors1115-213: Intro to Computer SystemsFall 2009 ©Memory 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
View Full Document