Fundamentals Of Computer Systems

Fundamentals of Computer SystemsThinking DigitallyStephen A. EdwardsColumbia UniversitySummer 2020

The Subject of this Class0

The Subjects of this Class01

But let your communication be, Yea, yea; Nay, nay: forwhatsoever is more than these cometh of evil.— Matthew 5:37

Engineering Works Because of AbstractionApplication SoftwareOperating SystemsArchitectureMicro-ArchitectureLogicDigital CircuitsAnalog CircuitsDevicesPhysics

Engineering Works Because of AbstractionApplication SoftwareCOMS 3157, 4156, et al.Operating SystemsCOMS W4118ArchitectureSecond Half of 3827Micro-ArchitectureSecond Half of 3827LogicFirst Half of 3827Digital CircuitsFirst Half of 3827Analog CircuitsELEN 3331DevicesELEN 3106PhysicsELEN 3106 et al.

Boring Stuffhttp://www.cs.columbia.edu/ sedwards/classes/2020/3827-summer/Prof. Stephen A. Edwardssedwards@cs.columbia.eduLectures 1:00 – 4:00 PM, Mondays and WednesdaysMay 27–July 1Weight40%60%WhatWhenHomeworksFinal examSee WebpageJuly 1stSubmit homework online via Courseworks

Software You NeedThe Inkscape SVG File Editor inkscape.orgDo homework by downloading an SVG file from the classwebsite, edit it in Inkscape, and upload it to CourseworksThe Digital Circuit Simulator github.com/hneemann/DigitalCircuit design problems: download (class website) .zip filewith .dig files, edit with Digital, upload to CourseworksSPIM: A MIPS32 Simulator spimsimulator.sourceforge.netMIPS assembly coding:, download .zip file with .s files,edit in favorite text editor, test and debug in SPIM,upload to Courseworks

Rules and RegulationsEach assignment turned in must be unique; work mustultimately be your own.Don’t cheat: Columbia Students Aren’t CheatersTest will be closed-book; you may use a single sheet of yourown notes

Optional Texts: Alternative 1No required text. One option:Ï David Harris and Sarah Harris. Digital Design andComputer Architecture. Either 1st or 2nd ed.Almost precisely right for the scope of this class: digitallogic and computer architecture.

Optional Texts: Alternative 2Ï M. Morris Mano andCharles Kime. Logic andComputer DesignFundamentals. 4th ed.Ï David A. Patterson andJohn L. Hennessy.Computer Organizationand Design, TheHardware/SoftwareInterface. 4th ed.

thinkgeek.com

Which Numbering System Should We Use?Roman: I II III IV V VI VII VIII IX XMayan: base 20, Shell 0Babylonian: base 60

The Decimal Positional Numbering SystemTen figures: 0 1 2 3 4 5 6 7 8 973010 7 102 3 101 0 10099010 9 102 9 101 0 100Why base ten?

Hexadecimal, Decimal, Octal, and 001001101010111100110111101111

Binary and Octal: Electronics Likes Powers of TwoBin01234567011011100101110111DEC PDP-8/I, c. 1968OctPC 0101101111012 0 211 1 210 0 29 1 28 1 27 0 26 1 25 1 24 1 23 1 22 0 21 1 20 26758 2 83 6 82 7 81 5 80 146910

Hexadecimal NumbersBase 16: 0 1 2 3 4 5 6 7 8 9 A B C D E FInstead of groups of 3 bits (octal), Hex uses groups of 4.CAFEF00D16 12 167 10 166 15 165 14 164 15 163 0 162 0 161 13 160 3, 405, 705, 22910CAFEF00D110010101111111011110000000011013 1 2 7 7 5 7 0 0 1 5HexBinaryOctal

Computers Rarely Manipulate True NumbersInfinite memory still very expensiveFinite-precision numbers typical32-bit processor: naturally manipulates 32-bit numbers64-bit processor: naturally manipulates 64-bit numbersHow many different numbers can youbinaryoctalrepresent with 5digits?decimalhexadecimal

JargonBitBinary digit: 0 or 1ByteEight bitsWordNatural number of bits for theprocessor, e.g., 16, 32, 64LSBLeast Significant Bit (“rightmost”)MSBMost Significant Bit (“leftmost”)

Decimal Addition Algorithm434 6284 8 12 0123456789100 1 2 3 4 5 6 7 8 1213141516171819

Decimal Addition Algorithm1434 62824 8 121 3 2 6 0123456789100 1 2 3 4 5 6 7 8 1213141516171819

Decimal Addition Algorithm1434 628624 8 121 3 2 64 6 10 0123456789100 1 2 3 4 5 6 7 8 1213141516171819

Decimal Addition Algorithm1 1434 6280624 8 121 3 2 64 6 10 0123456789100 1 2 3 4 5 6 7 8 1213141516171819

Decimal Addition Algorithm1 1434 62810624 8 121 3 2 64 6 10 0123456789100 1 2 3 4 5 6 7 8 1213141516171819

Binary Addition Algorithm10011 110011 1 10 0 1011000 0101 1010 11

Binary Addition Algorithm110011 1100101 1 101 1 0 10 0 1011000 0101 1010 11

Binary Addition Algorithm1110011 11001001 1 101 1 0 101 0 0 01 0 1011000 0101 1010 11

Binary Addition Algorithm01110011 110011001 11 1 01 0 00 0 1 10 10 01 01 0 1011000 0101 1010 11

Binary Addition Algorithm001110011 1100111001 11 1 01 0 00 0 10 1 1 10 10 01 01 10 0 1011000 0101 1010 11

Binary Addition Algorithm1001110011 110011011001 11 1 01 0 00 0 10 1 1 10 10 01 01 10 0 1011000 0101 1010 11

Signed Numbers: Dealing with NegativityHow should we represent negative numbers?

Binary Signed Magnitude NumbersThe familiar notation: negative numbers have a leading Binary signed-magnitude encoding: leading 1 indicatesnegative; remaining bits treated as binary.00002 000102 210102 211112 710002 0?Can be made to work, but addition isannoying:If the signs match, add the magnitudesand use the same sign.If the signs differ, subtract the smallernumber from the larger; return the signof the larger.

One’s Complement NumbersLike Signed Magnitude, a leading 1 indicates a negativeOne’s Complement number. However, number magnitude iscomplement of remaining bits interpreted as binary.To negate a number, complement (flip) each bit.00002 000102 211012 210002 711112 0?Addition is nicer: just add the one’scomplement numbers as if they werenormal binary.Really annoying having a 0: twonumbers are equal if their bits are thesame or if one is 0 and the other is 0.

Two’s Complement NumbersReally neat trick: just make only the mostsignificant bit represent a negative numberinstead of positive; treat the rest as binary.11012 8 4 1 311112 8 4 2 1 101112 4 2 1 710002 8Easy addition: just add in binary and discard any carry.Negation: complement each bit (as in one’s complement)then add 1.Subtraction done with negation and addition.Very good property: no 0Two’s complement numbers are equal if and only if all theirbits are the same.

Number Representations p.00000001.01010101011110001001.789777 0 1 7 6 8 7111011111415 6 7 1 0 2 1Smallest numberLargest number

https://xkcd.com/571/How many bits in his brain?

Fixed-point NumbersHow to represent fractionalnumbers? In decimal, we continuewith negative powers of 10:31.4159 3 101 1 100 4 10 1 1 10 2 5 10 3 9 10 4Also works in binary:1011.01102 1 23 0 22 1 21 1 20 0 2 1 1 2 2 1 2 3 0 2 4 8 2 1 0.25 0.125 11.375Addition and subtraction algorithms the same.

FFaucInterestingThe ancient Egyptians used binary fractions:The Eye of Horus

Binary-Coded DecimalHumans preferreading decimalnumbers;computers preferbinary.thinkgeek.comBCD is acompromise: everyfour bitsrepresents adecimal digit.DecBCD012.0000 00000000 00010000 0010.891011.0000 10000000 10010001 00000001 0001.181920.0001 10000001 10010010 0000.

BCD AdditionBinary additionfollowed by a possiblecorrection.Any four-bit groupgreater than 9 musthave 6 added to it.Example:158 242000101011000 0010010000101010 First group

BCD AdditionBinary additionfollowed by a possiblecorrection.Any four-bit groupgreater than 9 musthave 6 added to it.Example:158 242000101011000 0010010000101010 First group 0110 Correction

BCD AdditionBinary additionfollowed by a possiblecorrection.Any four-bit groupgreater than 9 musthave 6 added to it.1000101011000 0010010000101010 First group 0110 CorrectionExample:10100000 Second group1158 2420

BCD AdditionBinary additionfollowed by a possiblecorrection.Any four-bit groupgreater than 9 musthave 6 added to it.1000101011000 0010010000101010 First group 0110 CorrectionExample:1158 242010100000 Second group 0110Correction

BCD AdditionBinary additionfollowed by a possiblecorrection.Any four-bit groupgreater than 9 musthave 6 added to it.11000101011000 0010010000101010 First group 0110 CorrectionExample:11158 2420010100000 Second group 0110Correction01000000Third group

BCD AdditionBinary additionfollowed by a possiblecorrection.Any four-bit groupgreater than 9 musthave 6 added to it.11000101011000 0010010000101010 First group 0110 CorrectionExample:11158 24240010100000 Second group 0110Correction01000000Third group(No correction)010000000000 Result

Floating-Point Numbers: “Scientific Notation”Greater dynamic range at the expense of precisionExcellent for real-world measurementsIEEE 754 Single-Precision (32-bit)Sign 8-bit Exponent23-bit Fraction11000000101100000000000000000000implicit 1.01100002 1.375 22 5.5“excess 127” 2100000012 127

ASCII For Representing Characters and SUBESCFSGSRSUSSP0123456789:; ?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\] ‘abcdefghijklmnopqrstuvwxyz{ } !"# %&’()* , ./DEL

Fundamentals. 4th ed. . Computers Rarely Manipulate True Numbers Infinite memory still very expensive Finite-precision numbers typical 32-bit processor: naturally manipulates 32-bit numbers 64-bit processor: naturally manipulates 64-bit numbers How many different numbers can you