Computer Organization and Architecture

Computer Arithmetic

Outline

• The Arithmetic and Logic Unit (ALU)
• Integer Representation
• Integer Arithmetic
• Floating-Point Representation
• Floating-Point Arithmetic

The Arithmetic and Logic Unit (ALU)

Arithmetic & logic unit

• Core of computer

• Everything else in the computer is there to service this unit

• Does arithmetic and logic calculations

• Handles integers

  • May handle floating point (real) numbers

  • May be separate FPU ( maths co-processor)

  • May be on chip separate FPU ( 486DX + )

---

ALU input & output

• 一般CPU内部会有一组寄存器，用于用于临时存放数据

• 控制单元告诉ALU需要做什么操作，同时还控制数据的输入和输出

• 数据由寄存器送给ALU进行运算，运算之后的结果也保存在寄存器中

• ALU在计算后，会设置一些标志，比如溢出标志等，标志也保存在寄存器中

Integer Representation

• Electronic components generally have only two basic states

  • Whether there is charge, high and low level

  • Represents 0 and 1

• Computer use 0 & 1 to represent everything

  • Positive numbers stored in binary

  • e.g. 41=00101001

  • No minus sign

  • No period

• How to represent negative numbers

  • Sign-Magnitude

  • Two’s complement

---

• unsigned

  • Use only non-negative integers

  • sign bit does not need

• sign magnitude

  • Sign +magnitude

• one’s complement

  • represent the value by use inverse value of Sign +magnitude

• two’s complement

  • Use two’s complement to express integer

• biased

---

Sign-magnitude

• Left most bit is sign bit

• 0 means positive

• 1 means negative

$$ +18=00010010\newline -18=10010010\newline $$

---

$$ A=\begin{cases} \sum_{i=0}^{n-2}2^ia_i\ if\ a_{n-1}=0\newline -\sum_{i=0}^{n-2}2^ia_i\ if\ a_{n-1}=1\newline \end{cases} $$

$The\ number\ of\ bits\ is\ n\rightarrow Range: [-(2^{n-1}-1),2^{n-1}-1]\newline$

• Problems

  • Need to consider both sign and magnitude in arithmetic

  • Two representations of zero (+0 and -0)

    • 1000000(-0)
    • 0000000(+0)

  • Two methods are required to judge 0

---

One’s complement ! ! !

• Historically important, and we use this representation to get 2’s complement integers

• positive integers use the same representation as unsigned

• Negation is done by taking a bitwise complement of the positive representation

$$ Example:-3:0011\rightarrow 1100\newline ————————\newline \begin{align} &11100000:a\ negative\ number\newline &To\ find\ out\ the\ value,invert\ each\ bit\ 00011111\ is\ +31\ by\ sight,\newline &so\ 11100000=-31 \end{align} $$

• The 1’s complement number system using N bits has a range from $-(2^{N-1}-1)\ to\ +(2^{N-1}-1)\newline$

$$ \begin{align} &8-bit\ examples\newline &1111\ 1110\rightarrow 0000\ 0001\rightarrow -1\newline &1111\ 1111\rightarrow 0000\ 0000\rightarrow -0\newline &0000\ 0000\rightarrow +0\newline &0000\ 0001\rightarrow +1\newline \end{align} $$

• The two forms of zero are represented by

• $0000\ 0000(all\ zeros)\newline$

• $1111\ 1111(all\ ones)\newline$

---

Two’s complement ! ! !

• Two’s complement is a variation on 1’s complement

  • Does NOT have 2 representations for 0

• negative: (for example -5)

  • Take the positive value 00101 (+5)

  • Take the 1‘s complement 11010 (-5 in 1’s comp)

  • Add 1: 11011

$$ A=-2^{n-1}a_{n-1}+\sum^{n-2}_{i=0}2^ia_i\newline $$

Benefits

• One representation of zero

• Arithmetic works easily

• Negating is fairly easy

• Example: -3

$$ (3)_{10}=(00000011)_2\newline Boolean\ complement\ gives:11111100\newline Add\ 1\ to\ LSB:11111101\newline $$

$$ \begin{align} &One\ representation\ of\ zero\newline &0=00000000\newline &Bitwise\ not=11111111\newline &Add\ 1\ to\ LSB:+1\newline &Result:1\ 00000000\newline &Overflow\ is\ ignored\ so \rightarrow -0=0 \end{align} $$

Negation Special Case $$ \begin{align} &-128=10000000\newline &-(-128)is:\newline &1. bitwise\ not:01111111\newline &2. Add\ 1\ to\ LSB:+1\newline &3. Result:10000000\newline &\rightarrow -(-128)=-128\newline &??? \rightarrow\ \times\ \newline \end{align} $$

In two ‘s complement notation, the range of positive and negative numbers is not completely symmetric

Range of numbers

$The\ number\ of\ bits\ is\ n\rightarrow Range: [-2^{n-1},2^{n-1}-1]\newline$

Sign extension

• For sign magnitude number, simply move the sign bit to the new leftmost position and fill in with zeros

$$ +18=00010010 \rightarrow extension : 00000000\ 00010010\newline -18=10010010 \rightarrow extension : 10000000\ 00010010\newline $$

• It is not going to work for two’s complement

• The rule for two’s complement number is

  • Positive number pack with leading zeros $$ +18=00010010 \rightarrow extension : 00000000\ 00010010\newline $$
  • Negative numbers pack with leading ones $$ -18=10010010 \rightarrow extension : 11111111\ 10010010\newline $$

---

Characteristics of Two’s Complement

特点	描述
范围	$[-2^{n-1},2^{n-1}-1]$
0的表示方法	只有1个0的表示法
计算方法	按位取反后，在最后一位加1，可以得到这个数的相反数的补码
位的扩展	用符号位进行填充
溢出规则	如果2个相同符号的数相加，得到的新数的符号位和原数的符号位不一样，就是溢出
减法规则	取减数的补码，然后和被减数相加

Integer Arithmetic

Addition and Subtraction

• Addition

  • Normal binary addition

  • Monitor sign bit for overflow

• Subtraction

  • Take twos compliment of subtrahend and add to minuend

  • $a-b=a+(-b)\newline$

• So only need addition and complement circuits

• Straight forward approach consists of adding each bit together from right to left and propagating the carry from one bit to the

$$ \begin{align} Example:&\newline &-7_{10}+5_{10}=1001_{2}+0101_{2}=1110_{2}=-2_{10}\newline &3_{10}+4_{10}=0011_{2}+0100_{2}=0111_{2}=7_{10}\newline \end{align} $$

---

Geometric Depiction of Twos Complement Integers

• 圆周上列出了$4bit$的数表示的16种情况，从0000到1111

• 中间有一个对称轴，一个数的相反数就是它针对中间的对称轴的对称点

• 可以看到1000没有对称点，所以只有-8而没有+8的表示

• 对于加法，就是顺时针移动；而对于减法，就是逆时针移动

• 无论是顺时针移动，还是逆时针移动，如果越过了正负的交接点，就表示有溢出

---

Judgment of overflow

• For different representations, the judgment methods of overflow are different

• For example: 01111101+01111101 = 1 1111010

  • For unsigned addition, no overflow

  • For signed addition, overflow

• Another example: 11111101+01111101 = （1）01111010

  • For unsigned addition, overflow

  • For signed addition, no overflow

• Carry is not a flag to judge overflow

---

• No overflow when adding a positive and a negative number

• No overflow when signs are the same for subtraction

• Judgment method for two’s complement addition

  • When two numbers with the same sign are added, the sign bit of the result is opposite, which must be overflow

  • Subtraction is completed by addition, and the method to judge overflow is the same

---

Hardware for Addition and Subtraction

• 核心是一个加法器。寄存器A和B是加法器的输入

• 计算的结果保存在寄存器A中，如果有溢出，则溢出标志保存在OF中

• SW开关控制是加法还是减法。如果是加法，B寄存器的数直接输入到加法器中；如果是减法，则B寄存器的数据通过一个补码器生成它的相反数的补码，再输入到加法器中

Multiplication

• Much more complex than addition

• Multiply each bit of the multiplier by the multiplicand to get the partial product

• calculation of partial product should also take into account the position of the multiplying digit

• Add all partial products to get the product

• It’s similar to our manual multiplication

• Involves the generation of partial products

  • Equals 0 when the multiplier bit is 0

  • Equals the multiplicand when the multiplier is 1

  • Easier than decimal multiplication

• The total product is produced by summing the shifted partial products

• Two n binary number may result in a product of up to 2n bits in length

Example $$ \begin{align} &1011\newline \times&1101\newline &\rule[-10pt]{5cm}{0.03em}\newline &1011\newline 0&000\newline 10&11\newline 101&1\newline &\rule[-10pt]{5cm}{0.03em}\newline &10001111 \end{align} $$ Note: 结果需要双倍的比特位

Shift operation! ! !

• A shift operation is involved in multiplication

• Any number multiplied by 2 n results the number shifted left by n bits

  • 0000 0001 x 00000010 = 0000 0010

  • 0000 0001 x 00000100 = 0000 0100

  • 0000 0001 x 00001000 = 0000 1000

Unsigned binary multiplication

• 核心是一个n位加法器

• 先取乘数的最低位$Q_0$。如果是1，则将被乘数送到加法器中。如果是0，则不进行加法。

• 加法器将A和M相加，然后向右移位。有一个移位的寄存器C，用于保存进位

• 移位后，继续进行$Q_1$的判断，然后相加，移位。这样直到所有的Q都计算完成，这样就可以得到无符号的乘法结果

Example

• 初始值C为0，A寄存器为0，乘数为1101，被乘数位1011

• 先取乘数的最低位$Q_0$。如果是1，则将被乘数送到加法器中。如果是0，则不进行加法

• 第一步，乘数最后一位是1，A和M相加后，得到A为1011。然后移位(A最低位移向了Q的最高位，多出来的高位用0来补齐)，A和Q寄存器就变成了：0101 1110

• 第二步，乘数最后一位是0，A不变，然后移位，A和Q寄存器就变成了：0010 1111

• 第三步，乘数最后一位是1，将A和M相加，得到1101。然后移位，得到A和Q寄存器变成了：0110 1111

• 第四步，乘数最后一位是1，A和M相加，得到10001。产生了一个进位。然后移位，进位也右移到A的最高位。得到A和Q寄存器变成了：1000 1111

Summary

• 三个寄存器A、Q和M。其中A用于存放结果的高位，初始化为0。Q初始化为乘数，M初始化为被乘数。还有一个进位标志C。n表示计算次数

• 先检查$Q_0$，如果为1，将A和M相加，放到C，A。然后将C、A、Q右移一位。同时n-1，表示完成了1次计算

• 如果n不为0，继续进行$Q_0$的检测和计算。直到n为0

• 结果保存在A和Q中。A为高位，Q为低位

Multiplying negative numbers! ! !

• Solution 1

  • Convert to positive if required

  • Multiply as above

  • If signs were different, negate answer

  • Convert to two’s complement

  • It’s the same way we do multiplication. Regardless of the sign bit, multiply, and then determine the sign of the result

• Solution 2

  • Booth’s algorithm

  • Not only solves the problem, but also improves the efficiency

Booth’s algorithm! ! !

• In particular, consider a positive multiplier consisting of one block of 1s surrounded by 0s

Example $$ \begin{align} M \times (00011110)_2=&M \times (2^4+2^3+2^2+2^1)\newline =&M \times (16+8+4+2)\newline =&M \times 30\newline \end{align} $$

$$ 2^n+2^{N-1}+\dots+2^{n-K}=2^{n+1}-2^{n-K} $$

$$ \begin{align} M \times (00011110)_2&=M \times (2^5-2^1)\newline &=M \times 30\newline \end{align} $$

• For a binary number, we cannot require all its 1s to be connected together. What should we do？

• Use the idea of segmentation. Make the connected 1 into a block

• If single 1 is surrounded by 0, a single 1 is also a block

$$ \begin{align} M \times (01111010)_2&=M \times (2^6 + 2^5 + 2^4 + 2^3 + 2^1)\newline &=M \times (2^7 - 2^3 + 2^2-2^1)\newline \end{align} $$

• Booth’s algorithm makes use of this rule. For continuous 1, it need not calculate, but only at the beginning and end

• When 10 is encountered , subtraction is performed

• When 01 is encountered , addition is performed

• For continuous 1, it only needs to be calculated at the beginning and end to improve the calculation efficiency

$$ M \times (01111110)_2=M \times (2^7-2^0)\newline $$

• The worst case is that 0 and 1 alternate, so each time you need to calculate

$$ M \times (01010101)_2=M \times (2^7-2^6+2^5-2^4+2^3-2^2+2^1-2^0)\newline $$

---

Diagram of Booth’s algorithm

• A寄存器保存结果的高位，Q寄存器保存乘数和结果的低位，M寄存器保存被乘数。$Q_{-1}$寄存器保存上一个乘数数字。初始化时A和$Q_{-1}$均为0

• 开始计算，如果$Q_0$和$Q_{-1}$是11或00，A和Q以及$Q_{-1}$不处理，直接移位

• 如果$Q_0$和$Q_{-1}$是10，减去M，然后进行移位

• 如果$Q_0$和$Q_{-1}$是01，加上M，然后进行移位

• A、Q和$Q_{-1}$右移的时候，A的最高位往下移位时,最高位不是补0，而是将原来的最高位保留，也就是保留符号位

• 移位之后，继续判断$Q_0$和$Q_{-1}$，直到所有的位数都处理完毕

---

• Can the Booth’s algorithm just discussed solve the multiplication problem of negative numbers?

  • Yes

  • 关键点：符号位也进行了移位

Division

Division of unsigned binary integers

• 被除数的高4位都比除数小。到第五位，被除数是10010，比除数大，所以商位为1，然后减去除数，得到部分余数是111，继续下一位。直到被除数的最后一位

• 二进制的长除相对于10进制的长除简单一些。10进制的时候，因为商的每一位可能是0~9，所以我们还需要挨个儿去试，看商的每位是多大

• 对于二进制，商的每一位只能是0或者1，所以只需要对比被除数和除数的大小

• 结果包括商和余数

Flowchart for Unsigned Binary Division

• 除数在M寄存器中，被除数放在Q寄存器中。A的初始值为0，保存被除数的部分余数

• 每一次，先将A和Q进行移位，然后检查A和M的大小，用无符号减法来比较。如果A大于M，当前的余数可以减去M，得到一个商位为1，放在$Q_0$。如果A比M小，则$Q_0$为0，同时A恢复成减去M之前的值

• 然后继续移位(A与Q同时进行左移,类比乘法中的整体移位)并比较。一直到被除数的所有位都用完

• 最后得到的商在Q寄存器中，余数保存在A寄存器中

Floating-Point Representation

Real numbers

• Real number: number with fractions

• Could be represent in pure binary

$$ 1001.1010=2^4+2^0+2^{-1}+2^{-3}=9.625 $$

Scientific Notation

• In decimal, large numbers are represented by scientific notation

• Use a mantissa to multiply by the power of 10

$$ 6.02_{10}\times 10^{23} $$

• The same in binary

• Represent a large binary number by multiplying the mantissa and the power of 2

• Representation consists of three parts: sign bit, significant value and exponent

Floating point

• Floating point representation

  • Symbol represented by 0 or 1

  • Exponent of biased notation

  • Valid value, that is, the mantissa of the number

• Binary point is the first place on the right of the highest significant value

---

Exponent! ! !

• How to use biased notation?
  • For a k bit exponent,the bias is $2^{k-1}-1(exponent\ add\ \underbrace{0111111\dots111}_{k\ bits})\newline$
  • actual exponent range is: $[-(2^{k-1}-1),2^{k-1}]\newline$
  • The bias is added to the actual exponent to get the stored exponent

---

Example

• $-1.1010001 \times 2^{10100}\newline$

• Sign: 1

• Exponent: $\underbrace{01111111}_{bias}+\overbrace{10100}^{exponment}=10010011\newline$

• Significand: 101 0001 0000 0000 0000 0000

• The floating point representation for above number: 1 10010011 10100010000000000000000

Normalization

• To simplify operations on floating-point numbers, it is required to normalize the number

• How to normalize?

  • The leftmost bit of the significand is 1

    • e.g: $1.xxxxx \times 2^k\newline$

  • Because the most significand bit is always one, it is unnecessary to store this bit – implicit

  • 23-bit field is used to store a 24-bit significant

Floating point range and accuracy

• For a 32 bit number

  • 8 bit exponent， up to 128
  • $+|-2^{128}\approx1.0 \times 10^{39}\newline$

• Accuracy

  • The effect of changing lsb of mantissa

  • 23 bit mantissa $2^{-23}\approx 1.2 \times 10^{-7}\newline$

  • About 6 decimal places

• Because total bits of floating point numbers is fixed, the range and accuracy are contradictory

---

Density of floating point numbers

• For fixed-point numbers, the numbers are spaced evenly

• For float-point notation, the numbers are not evenly spaced

  • The length of exponent is fixed

  • As the number is getting bigger, the space between two numbers is bigger

IEEE 754

• Standard for floating point storage

• 32 and 64 bit standards

• 32 bits standard

  • 8 bits exponent , 23 bits significand

• 64 bits standard

  • 11 bits exponent , 52 bits significand

• Extended formats (both mantissa and exponent) for intermediate results

Special about IEEE 754 formats

• Extreme value of the exponent to define a particular value

• Exponent after bias is 2047, that is, all 1, indicating infinity

• The actual range is smaller than the ideal range

• For negative, the range is $[-(2-2^{-52}) \times 2^{1023},2^{-1022}]\newline$

• For positive, the range is $[2^{-1022},(2-2^{-52}) \times 2^{1023}]\newline$

Floating-Point Arithmetic

Floating point arithmetic +/-

• Addition and subtraction of floating point numbers must first ensure that the exponent are the same

• How to do this？ Move the binary point position of the valid value of the operand

• Steps for addition and subtraction floating point numbers

  • Check for zeros

  • Align significands (adjusting exponents)

  • Add or subtract significands

  • Normalize result

Example $$ \begin{gather} 1.011 \times 2^5+1.001 \times 2^3\newline Align\ significands \rightarrow 1.001 \times 2^3=0.0101 \times 2^5\newline Add\ or\ subtract\ significands \rightarrow 1.001+0.0101=1.1011\newline Normalize\ result \rightarrow result=1.1011 \times 2^5\newline \end{gather} $$ FP Addition & Subtraction Flowchart

Floating point arithmetic $\times\backslash\div$

• Multiplication and division are simpler than addition and subtraction

• Steps:

  • Check for zero

  • Add/subtract exponents

  • Multiply/divide significands (watch sign)

  • Normalize

  • Round

• All intermediate results should be in double length storage

---

Floating point multiplication

Floating point division

Example: $$ \begin{gather} (1.001 \times 2^5) \times (1.001 \times 2^3)\newline Check\ for\ zeros:no\ zero\newline Add/subtract\ exponents\rightarrow5+3=8=(1000)_2\newline Multiply/divide\ significands\rightarrow1.011\times1.001=1.100011\newline Normalize\ result \rightarrow result=1.100011 \times 2^8\newline Round \rightarrow 1.100011 \times 2^8\approx 1.100 \times 2^8\newline \end{gather} $$