CS33 : Introduction to Computer OrganizationJochen Haber3400 Boelter [email protected]:Farnoosh Javadi ([email protected])Xingyu Ma ([email protected])Mo Xu ([email protected])Teng Xu ([email protected])Lecture: MW 4PM-6PMOffice Hours:M: 6PM-7PMW: 6PM-7PMBH4532BDiscussion:As Enrolled- 2 hours per weekSec 1A BH5419 F: 2PM-4PM Teng XuSec 1B BH5419 F: 4PM-6PM Xingyu MaSec 1C BH5273 F: 4PM-6PM Mo XuSec 1D BH9436 F: 4PM-6PM Farnoosh JavadiText:Randal E. Bryant and David R. O’Hallaron. “Computer Systems: A Programmer’s Perspective” 2nd Edition, Prentice Hall 2010.What this course is about: Computer organization: How does a computer really work?From a hardware perspective but exposed by softwareCourse focus:chemicals and manufacturing: NOimbedded architecture NO, but just an exposuregeneral architecture YES, mostly about softwarecompilers YESenabling software (systems programs) NOOutline of course:IntroductionTour of systemsData representationMachine languageCode optimizationMemory hierarchyLinkingException control flowVirtual memoryConcurrent programmingCourse details:19 lectures 37 hours minus exam and breaks10 discussions 18 hoursoutside work 90 hours1 mid-term exam: open book, notes: 20% of grade final exam: open book, notes: 30% of grade5 labs: 10% of grade eachDue date every 2cd Mondayhomework: undetermined number: only passing grade +1% for passDue date Monday after assigned.Labs/homeworksWill be tested on SEAS Linux machines.Collaboration is encouraged but should be symmetrically acknowledged.Late submissions not accepted.Exams:Postponed exams by prior notice only- 2 -What is a computer?***Admin Interlude***A short history: Gerald EstrinAnalog versus digital (continuous vs discrete, real vs rational)Non-programmable versus programable Stored program vs fixed.Modify its stored programAbacusCash Register1890 Hollerith punched cards tabulator- 3 -AnalogTransducersStereo amplifierA/D converter (hybrid)Digital Mainframe computers1855 Charles Babbage difference engine1985-1991 Science Museum in London- 4 -Digital Mainframe computersMechanical1855 Babbage difference engine1941 Konrad Zuse Z3 (mechanical) ... programming languageVacuum Tube1946 ENIAC U Penn1955 WEIZAC Weizmann Institute- 5 -TransistorIBM (605, 1401, 7040, 7094, 360, Model 91, 370)1954 1959 1961 1962 1964 1968 1970NCRCray, IlliacUnivacMini Computers1965 Digital Equipment PDP-8Hewlett PackardPCs1971 Intel 1975 ALTAIR 1976 Apple1977 Radio Shack TRS=80, Commodore1981 IBM DOS/IBM PCsCompaqSunDellHPHandheldSlide ruleDigital WatchesSimple calculatorsHP55BlackberrySmartphonesBuiltinCarsAir NavigationAppliances Theoretical (automata)Finite state machines (FSM)Push down automata (PDA)Linear bounded automata (LBA)Turing Machine (TM)TMHP, Goedel’s Incompleteness, Russell’s paradoxRelationship to grammarsChomsky, Greibach- 6 -Overview of a digital computer: Two architectures in this course IA32, X86-64.Clock Input/Output DevicesKeyboardsCPU MouseProgram Counter Outside world devicesRegisters NetworksArithmetic/Logical unit Screen PrintersShort Term Main Memory Output devicesPrintersLong Term MemoryDisks BussesPunched paper tapePunched cardsMagnetic tapes- 7 -How does it work?- 8 -- 9 -Data Representation:BINARY!- 10 -Main MemoryA large array of bytes: IA32 limit 2 . X86-64 limit 2 (theoretical) but 2 (practical)32 64 48Each byte has an address: 0 to limit-1.Characters: (one byte)ASCIITeletypeEBCDICNumbers many different uses, sizesIntegerFloating pointDecimal?PointersBit matricesImages: RGBMachine instructionsOp code, operandsASCII Codes TableC++ data types, size in bytes on X86-64, mnemonic, description - 11 -Errors and Omissions in first lectureMid-term: Wednesday, October 30. To cover through Chapter 3Reading: suggest reading twice, try some of the problemsHomework 1? Lab 1?Slide rule storyNoam Chomsky: still alive: article published in 1959: On certain formal properties of grammars Information and Control 2 (2): 137–167.char 1 b Character (can also be interpreted as integer) short 2 w Short integerint 4 1 Integerlong int 8 q Long integerlong long int 8 q Long integerchar * 8 q Pointerfloat 4 s Single precision floating pointdouble 8 d Double precision floating pointlong double 16 t Extended precision floating pointNo bit data typeC allows “Boolean” (George Boole, 1847: Mathematical Analysis of Logic) operations on anydata types.Bitwise or logicalAnd: & or && 0 10 0 01 0 1Or: | or || 0 10 0 11 1 1- 12 -Exclusive Or: ^0 10 0 11 1 0Not: ~ or !0 11 0bit wise examplechar a = 0x23 ; /* equals 00100011 in binary */char b = 0xc5 /* 11000101 */char c = a & b ; /* 00000001 0x01 */ c = a | b ; /* 11100111 0xe7 */ c = a ^ b ; /* 11100110 0xe6 */ c = ~a /* 11011100 0xdc */logical c = a && b /* 00000001 0x01 */ c = a || b /* 00000001 0x01 */ c = !a /* 00000000 0x00 */~ is unary. Precedence: & then ^ then |. Same precedence, left to rightFor instance A | B & C ( A | B ) & C e.g 1 | 0 & 0 1 | 0 & 0 1 | 0 1 & 0 1 0Truth TablesA B C A|B&C A B C (A|B)&C0 0 0 0 0 0 0 00 0 1 0 0 0 1 00 1 0 0 0 1 0 00 1 1 1 0 1 1 11 0 0 1 1 0 0 01 0 1 1 1 0 1 11 1 0 1 1 1 0 01 1 1 1 1 1 1 1- 13 -A & ( B | C ) = ( A & B ) | ( B & C ) A | ( B & C ) = ( A | B ) & ( B | C )A & B = B & AA | B = B | AAlso ~( A & B ) = ~A | ~B and ~( A | B ) = ~A & ~B Augustus De Morgan’s lawlots of other rules: similar to arithmetic, set theoryNotice that A ^ B = ( A | B ) & ~( A & B ) A B A|B A&B ~(A&B) A^B0 0 0 0 1 00 1 1 0 1 11 0 1 0 1 11 1 1 1 0 0- 14 -Integersw-1 w-2 1 0vector x of bits of width w: [x ,x , ... ,x ,x ]Type wchar 8short 16int 32long int 64Unsignedw-1 w-2 + 1 0Value represented = 2 x +2 x + ... 2 x +2 xw-1 w-2 1 0Smallest possible value: 0, Largest: 2 -1we.g, w= 32 largest = 4,294,967,295Signed (two’s complement)w-1 w-2 1 0Value represented = -2 x +2 x + ... +2 x +2 xw-1 w-2 1