CS 105 Tour of the Black Holes of Computing Computer Systems Overview Geoff Kuenning Fall 2008 Topics Staff text and policies Lecture topics and assignments Lab rationale CS 105 Textbooks Randal E Bryant and David R O Hallaron Computer Systems A Programmer s Perspective Prentice Hall 2003 Brian Kernighan and Dennis Ritchie The C Programming Language Second Edition Prentice Hall 1988 Larry Miller and Alex Quilici 2 The Joy of C Wiley 1997 CS 105 Syllabus 3 Syllabus on Web http www cs hmc edu geoff cs105 Calendar defines due dates Labs cs105submit for some others have specific directions CS 105 Course Components Lectures Higher level concepts Problems and Quizzes Labs 4 Applied concepts important tools and skills for labs clarification of lectures exam coverage The heart of the course 1 or 2 weeks Provide in depth understanding of an aspect of systems Programming and measurement Time to learn avoid trying to optimize Teams of two CS 105 Notes Work groups You must work in pairs on all labs Honor code violation to work without your partner Handins Check calendar Electronic submissions only Grading Characteristics Lab scores tend to be high Serious handicap if you don t hand a lab in Tests quizzes typically have a wider range of scores I e they re primary determinant of your grade Do your share of lab work and reading or bomb tests 5 CS 105 Cheating What is cheating Sharing code either by copying web search etc retyping looking at or supplying a copy of a file What is NOT cheating 6 Helping others use systems or tools Helping others with high level design issues Helping others debug their code CS 105 Facilities Assignments will use Intel computer systems Not all machines are created alike Some Macs are PowerPCs Even Intel Macs aren t necessarily compatible Knuth is a 64 bit server Wilkes x86 Linux specifically set up for this class Log in on a Mac then ssh to Wilkes If you want fancy programs start X11 first Directories are cross mounted so you can edit on Knuth or your Mac and Wilkes will see your files 7 or ssh into Wilkes from your dorm All programs must run on Wilkes that s where we grade CS 105 Lab Rationale Each lab has a well defined goal such as solving a puzzle or winning a contest Defusing a binary bomb Winning a performance contest Doing a lab should result in new skills and concepts Data Lab computer arithmetic digital logic Bomb Labs assembly language using a debugger understanding the stack Threads Lab Concurrency We try to use competition in a fun and healthy way 8 Set a threshold for full credit Post intermediate results anonymized on Web page for glory CS 105 Course Theme Abstraction is good but don t forget reality Many CS Courses emphasize abstraction Abstract data types Asymptotic analysis These abstractions have limits Especially in the presence of bugs Need to understand underlying implementations Useful outcomes Become more effective programmers Able to find and eliminate bugs efficiently Able to tune program performance Prepare for later systems classes in CS Compilers Operating Systems Networks Computer 9 Architecture Robotics etc CS 105 Great Reality 1 Ints are not integers Floats are not reals Examples Is x2 0 Floats Ints Yes 40000 40000 1600000000 50000 50000 Is x y z x y z Unsigned Signed Ints Floats Yes 1e20 1e20 3 14 3 14 1e20 1e20 3 14 10 CS 105 Computer Arithmetic Does not generate random values Arithmetic operations have important mathematical properties BUT Cannot assume usual properties Due to finiteness of representations Integer operations satisfy ring properties Commutativity associativity distributivity Floating point operations satisfy ordering properties Monotonicity values of signs Observation 11 Need to understand which abstractions apply in which contexts Important issues for compiler writers and serious application programmers CS 105 Great Reality 2 You ve got to know assembly Chances are you ll never program in assembly Compilers are much better more patient than you are BUT understanding assembly key to machine level execution 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 state 12 CS 105 Assembly Code Example Time Stamp Counter Special 64 bit register in Intel compatible machines Incremented every clock cycle Read with rdtsc instruction Application Measure time required by procedure In units of clock cycles NOT instructions double t start counter need to access reg P t get counter need to access reg printf P required f clock cycles n t 13 CS 105 Code to Read Counter Write small amount of assembly code using GCC s asm facility Inserts assembly code into machine code generated by compiler static unsigned cyc hi 0 static unsigned cyc lo 0 Set hi and lo to the high and low order bits of the cycle counter void access counter unsigned hi unsigned lo asm rdtsc movl edx 0 movl eax 1 r hi r lo edx eax 14 CS 105 Code to Read Counter Record the current value of the cycle counter void start counter access counter cyc hi cyc lo Number of cycles since the last call to start counter double get counter unsigned ncyc hi ncyc lo unsigned hi lo borrow Get cycle counter access counter ncyc hi ncyc lo Do double precision subtraction lo ncyc lo cyc lo borrow lo ncyc lo hi ncyc hi cyc hi borrow return double hi 1 30 4 lo 15 CS 105 Measuring Time Trickier than it Might Look Many sources of variation Example Sum integers from 1 to n n 100 1 000 1 000 10 000 10 000 1 000 000 1 000 000 1 000 000 000 16 Cycles 961 8 407 8 426 82 861 82 876 8 419 907 8 425 181 8 371 305 591 Cycles n 9 61 8 41 8 43 8 29 8 29 8 42 8 43 8 37 CS 105 Great Reality 3 Memory Matters Memory is not unbounded It must be allocated and managed Many applications are memory dominated Memory referencing bugs especially pernicious Effects are distant in both time and space segfault Memory performance is not uniform 17 Cache and virtual memory effects can greatly affect program performance Adapting program to characteristics of memory system can lead to major speed improvements CS 105 Memory Referencing Bug Example main main long long int int a 2 a 2 double double dd 3 14 3 14 a 2 1073741824 a 2 1073741824 Out Out of of bounds bounds reference reference printf d printf d 15g n 15g n d d exit 0 exit 0 Alpha 18 MIPS x86 g 5 30498947741318e 315 3 1399998664856 3 14 O 3 14 3 14 3 14 x86
View Full Document
Unlocking...