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: Theme Five great realities of computer systems How 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 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 programmersz Able to find and eliminate bugs efficientlyz Able to tune program performance Prepare for later “systems” classes in CS & ECEz Compilers, Operating Systems, Networks, Computer Architecture, Embedded Systems315-213: Intro to Computer SystemsFall 2009 ©Great Reality #1Great Reality #1IntInt’’ssare not Integers, Floatare not Integers, Float’’s are not s are not RealsRealsExamplesExamples Is x2≥ 0?z Float’s: Yes!z Int’s:» 40000 * 40000 --> 1600000000» 50000 * 50000 --> ?? Is (x + y) + z = x + (y + z)?z Unsigned & Signed Int’s: Yes!z 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 values Arithmetic operations have important mathematical propertiesCannot assume Cannot assume ““usualusual””propertiesproperties Due to finiteness of representations Integer operations satisfy “ring” propertiesz Commutativity, associativity, distributivity Floating point operations satisfy “ordering” propertiesz Monotonicity, values of signsObservationObservation Need to understand which abstractions apply in which contexts Important issues for compiler writers and serious application programmers515-213: Intro to Computer SystemsFall 2009 ©Great Reality #2Great Reality #2YouYou’’ve got to know assemblyve got to know assemblyChances are, youChances are, you’’ll never write program in assemblyll 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 bugsz High-level language model breaks down Tuning program performancez Understanding sources of program inefficiency Implementing system softwarez Compiler has machine code as targetz Operating systems must manage process state Creating / fighting malwarez x86 assembly is the language of choice!615-213: Intro to Computer SystemsFall 2009 ©Assembly 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 procedurez In 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 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 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 Explanation C does not implement bounds checking Out 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 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 distancez Corrupted object logically unrelated to one being accessedz 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 develop tools to detect referencing errors1115-213: Intro to Computer SystemsFall 2009 ©Memory System Performance ExampleMemory System Performance Example Hierarchical memory organization Performance depends on access patternsz Including 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 <
View Full Document