中科大程序设计与计算机系统lec01intro_20141116173438874

1、CSAPP L1 Intro.1Wu Fall 14 USTCComputer Systems:A Programmers Perspective程序设计与计算机系统程序设计与计算机系统Lecture 1IntroNovember 17, 2014 Wu junmin ()CSAPP L1 Intro.2Wu Fall 14 USTCOutlineCourse ThemeFive great realities of computer systemsAdministrative Matters Lecture topics and assignmentsCSAPP L1 Intro.3Wu F

2、all 14 USTCCourse ThemeAbstraction is good, but dont 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 progra

3、mmers-Able to find and eliminate bugs efficiently-Able to understand and tune program performance Prepare for other “systems” classes -Compilers, Operating Systems, Networks, Computer Architecture, Embedded SystemsCSAPP L1 Intro.4Wu Fall 14 USTCGreat Reality #1Ints are not Integers, Floats are not R

4、ealsExamples Is x2 0?-Floats: Yes!-Ints: 40000 * 40000 - 1600000000 50000 * 50000 - ? Is (x + y) + z = x + (y + z)?-Unsigned & Signed Ints: Yes!-Floats: (1e20 + -1e20) + 3.14 - 3.14 1e20 + (-1e20 + 3.14) - ?-1794967296 0 CSAPP L1 Intro.5Wu Fall 14 USTCCode Security Example/* Kernel memory region

5、 holding user-accessible data */#define KSIZE 1024char kbufKSIZE;/* Copy at most maxlen bytes from kernel region to user buffer */int copy_from_kernel(void *user_dest, int maxlen) /* Byte count len is minimum of buffer size and maxlen */ int len = KSIZE maxlen ? KSIZE : maxlen; memcpy(user_dest, kbu

6、f, len); return len;Similar to code found in FreeBSDs implementation of getpeernameThere are legions of smart people trying to find vulnerabilities in programsCSAPP L1 Intro.6Wu Fall 14 USTCTypical Usage/* Kernel memory region holding user-accessible data */#define KSIZE 1024char kbufKSIZE;/* Copy a

7、t most maxlen bytes from kernel region to user buffer */int copy_from_kernel(void *user_dest, int maxlen) /* Byte count len is minimum of buffer size and maxlen */ int len = KSIZE maxlen ? KSIZE : maxlen; memcpy(user_dest, kbuf, len); return len;#define MSIZE 528void getstuff() char mybufMSIZE; copy

8、_from_kernel(mybuf, MSIZE); printf(“%sn”, mybuf);CSAPP L1 Intro.7Wu Fall 14 USTCMalicious Usage#define MSIZE 528void getstuff() char mybufMSIZE; copy_from_kernel(mybuf, -MSIZE); . . ./* Kernel memory region holding user-accessible data */#define KSIZE 1024char kbufKSIZE;/* Copy at most maxlen bytes

9、from kernel region to user buffer */int copy_from_kernel(void *user_dest, int maxlen) /* Byte count len is minimum of buffer size and maxlen */ int len = KSIZE ncyc_lo; hi = ncyc_hi - cyc_hi - borrow; return (double) hi * (1 30) * 4 + lo;CSAPP L1 Intro.13Wu Fall 14 USTCMeasuring Time Trickier than i

10、t Might Look Many sources of variation Example Sum integers from 1 to n nCyclesCycles/n1009619.611,0008,4078.411,0008,4268.4310,00082,8618.2910,00082,8768.291,000,0008,419,9078.421,000,0008,425,1818.431,000,000,0008,371,2305,5918.37CSAPP L1 Intro.14Wu Fall 14 USTCGreat Reality #3 Memory MattersRando

11、m Access Memory is an unphysical abstractionMemory is not unbounded It must be allocated and managed Many applications are memory dominatedMemory performance is not uniform Cache and virtual memory effects can greatly affect program performance Adapting program to characteristics of memory system ca

12、n lead to major speed improvementsMemory referencing bugs especially pernicious Effects are distant in both time and spaceCSAPP L1 Intro.15Wu Fall 14 USTCMemory Referencing Bug Exampledouble fun(int i) volatile double d1 = 3.14; volatile long int a2; ai = 1073741824; /* Possibly out of bounds */ ret

13、urn d0;fun(0) 3.14fun(1) 3.14fun(2) 3.1399998664856fun(3) 2.00000061035156fun(4) 3.14, then segmentation fault Result is architecture specificCSAPP L1 Intro.16Wu Fall 14 USTCMemory Referencing Bug Exampledouble fun(int i) volatile double d1 = 3.14; volatile long int a2; ai = 1073741824; /* Possibly

14、out of bounds */ return d0;fun(0) 3.14fun(1) 3.14fun(2) 3.1399998664856fun(3) 2.00000061035156fun(4) 3.14, then segmentation faultLocation accessed by fun(i)Explanation:Saved State4d7 . d43d3 . d02a11a00CSAPP L1 Intro.17Wu Fall 14 USTCMemory Referencing ErrorsC and C+ do not provide any memory prote

15、ction 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 i

16、s generatedHow can I deal with this? Program in Java,Ruby, or ML Understand what possible interactions may occur Use or develop tools to detect referencing errors (e.g. Valgrind)CSAPP L1 Intro.18Wu Fall 14 USTCMemory System Performance Example Hierarchical memory organization Performance depends on

17、access patterns-Including how step through multi-dimensional arrayvoid copyji(int src20482048, int dst20482048) int i,j; for (j = 0; j 2048; j+) for (i = 0; i 2048; i+) dstij = srcij;void copyij(int src20482048, int dst20482048) int i,j; for (i = 0; i 2048; i+) for (j = 0; j 2048; j+) dstij = srcij;

18、59,393,288 clock cycles1,277,877,876 clock cycles21.5 times slower!(Measured on 2GHzIntel Pentium 4)CSAPP L1 Intro.19Wu Fall 14 USTCThe Memory MountainIntel Core i72.67 GHz32 KB L1 d-cache256 KB L2 cache8 MB L3 cacheCSAPP L1 Intro.20Wu Fall 14 USTCGreat Reality #4Theres more to performance than asym

19、ptotic complexityConstant factors matter too!And even exact op count does not predict performance 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

20、 programs compiled and executed How to measure program performance and identify bottlenecks How to improve performance without destroying code modularity and generalityCSAPP L1 Intro.21Wu Fall 14 USTCMemory Performance ExampleImplementations of Matrix-Matrix Multiplication Multiple ways to nest loop

21、s/* ijk */for (i=0; in; i+) for (j=0; jn; j+) sum = 0.0; for (k=0; kn; k+) sum += aik * bkj; cij += sum; /* ikj */for (i=0; in; i+) for (k=0; kn; k+) r = aik; for (j=0; jn; j+) cij += r * bkj; CSAPP L1 Intro.22Wu Fall 14 USTCExample Matrix MultiplicationMatrix-Matrix Multiplication (MMM) on 2 x Core

22、 2 Duo 3 GHz (double Matrix-Matrix Multiplication (MMM) on 2 x Core 2 Duo 3 GHz (double precision)precision)Gflop/sGflop/s160 xTriple loopBest code (K. Goto)Standard desktop computer, vendor compiler, using optimization flagsBoth implementations have exactly the same operations count (2n3)What is go

23、ing on?CSAPP L1 Intro.23Wu Fall 14 USTCMMM Plot: AnalysisMatrix-Matrix Multiplication (MMM) on 2 x Core 2 Duo 3 GHzMatrix-Matrix Multiplication (MMM) on 2 x Core 2 Duo 3 GHzGflop/sGflop/sMemory hierarchy and other optimizations: 20 xVector instructions: 4xMultiple threads: 4xReason for 20 x: Blockin

24、g or tiling, loop unrolling, array scalarization, instruction scheduling, search to find best choiceEffect: fewer register spills, L1/L2 cache misses, and TLB missesCSAPP L1 Intro.24Wu Fall 14 USTCMemory SystemCSAPP L1 Intro.25Wu Fall 14 USTCGreat Reality #5Computers do more than execute programsThe

25、y 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

26、 performance issuesCSAPP L1 Intro.26Wu Fall 14 USTCHardware Organization (Nave)CSAPP L1 Intro.27Wu Fall 14 USTCOutlineCourse ThemeFive great realities of computer systemsAdministrative MattersLecture topics and assignmentsCSAPP L1 Intro.28Wu Fall 14 USTCCourse PerspectiveMost Systems Courses are Bui

27、lder-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 protocolsCSAPP L1 Intro.29Wu Fall 14 USTCCourse Perspective (Cont.)Our Course

28、 is Programmer-Centric Purpose is to show how knowing more about the underlying system, leads one to be a more effective programmer Enable you to-Write programs that are more reliable and efficient-Incorporate features that require hooks into OSE.g., concurrency, signal handlers Not just a course fo

29、r dedicated hackers-We bring out the hidden hacker in everyone Cover material in this course that you wont see elsewhereCSAPP L1 Intro.30Wu Fall 14 USTCCourse AdministrationInstructor: 吴俊敏吴俊敏 TA： 赵小雨赵小雨 Lab：思贤楼：思贤楼408室室(Multicore system and application)Materials:软件学院信息平台软件学院信息平台TextBook: Randal E. B

30、ryant and David R. OHallaron, “Computer Systems: A Programmers Perspective”, 英文版英文版.第二版，机械工业出版社（第二版，机械工业出版社（2011）/ 中译本，深入理解计算机系统（原书第二版），龚亦利中译本，深入理解计算机系统（原书第二版），龚亦利等译，机械工业出版社等译，机械工业出版社(2011)Reference Book: Samuel P. Harbison III and Guy L. Steele Jr., “C A Reference Manual 5th E

31、dition”,Prentice Hall, 2002 http:/ L1 Intro.31Wu Fall 14 USTCGradingLab : 25Homework Assignments: 15Class Participation: 10(5+5)Final Exam: 50 CSAPP L1 Intro.32Wu Fall 14 USTCAbout the TextbookAuthors: Randal E. Bryant: CMU, Professor, ACM IEEE Fellow OHallaron: CMU，ProfessorOrganization: Introducti

32、on Representing and Manipulating Information Machine-Level Representing of Programs Processor Architecture Optimizing Program Performance The Memory Hierarchy Linking Exceptional Control Flow Virtual Memory System-Level I/O Network Programming Concurrent ProgrammingCSAPP L1 Intro.33Wu Fall 14 USTCCo

33、urse StructureLectures:1 Lec on Introduction (chap.1,11-17)2 lec on Information Representing (chap.2,11-18,11-24)3 lecs on Machine Language (chap.3, 11-25,12-1,12-2)1 lecs on Code Optimization(chap.5,12-8)1 lecs on Memory Hierarchy (chap.6,12-9)1 lecs on Linking (chap.7,12-15)1 lecs on Exception Con

34、trol(chap.8,12-16)2 lecs on Virtual Memory(Chap.10,12-22,12-23)1 lec on I/O(Chap.11,12-29)1 lecs on Network Programming(Chap.12,12-30)1 lecs on Concurrent Programming(Chap.13,1-5)CSAPP L1 Intro.34Wu Fall 14 USTCOutlineCourse ThemeFive great realities of computer systemsAdministrative Matters Lecture

35、 topics and assignmentsCSAPP L1 Intro.35Wu Fall 14 USTCPrograms and DataTopics Bits operations, arithmetic, assembly language programs Representation of C control and data structures Includes aspects of architecture and compilersAssignments L1: Manipulating bits L2: Defusing a binary bomb L3: Hackin

36、g a buffer bombCSAPP L1 Intro.36Wu Fall 14 USTCThe Memory HierarchyTopics Memory technology, memory hierarchy, caches, disks, locality Includes aspects of architecture and OS.Assignments L4 (Perflab): Optimize the performance of an application kernel function.-Learn how to exploit locality in your p

37、rograms. CSAPP L1 Intro.37Wu Fall 14 USTCLinking and Exceptional Control FlowTopics Object files, static and dynamic linking, libraries, loading Hardware exceptions, processes, process control, Unix signals, nonlocal jumps Includes aspects of compilers, OS, and architecture CSAPP L1 Intro.38Wu Fall

38、14 USTC Virtual memoryTopics Virtual memory, address translation, dynamic storage allocation Includes aspects of architecture and OSAssignments L5: Writing your own malloc package-Get a real feel for systems programmingCSAPP L1 Intro.39Wu Fall 14 USTC I/O, Networking, and ConcurrencyTopics High leve

39、l and low-level I/O, network programming Internet services, Web servers concurrency, concurrent server design, threads I/O multiplexing with select. Includes aspects of networking, OS, and architecture.CSAPP L1 Intro.40Wu Fall 14 USTCL1:Data LabStudents implement simple logical and arithmetic functi

40、ons, but using a highly restricted subset of C. For example, they must compute the absolute value of a number using only bit-level operations. This lab helps students understand the bit-level representations of C data types and the bit-level behavior of the operations on data. CSAPP L1 Intro.41Wu Fa

41、ll 14 USTCL2:Bomb LabA binary bomb is a program provided to students as an object code file. When run, it prompts the user to type in 6 different strings. If any of these is incorrect, the bomb explodes, printing an error message and logging the event on a grading server. Students must defuse their own unique bomb by disassembling and reverse engineering the program to determine what the 6