# 計組第二章 計算機算術
[TOC]
### 重點一:數的表示
[1]
sign magnitude:第一bit是正負號
1's complement:負數計算方法就是看要加多少才會全部都變成11111
2's complement:負數計算方法就是看要加多少才會進位
<font color="red">現在計算機用2's complement居多</font>

[2]
n bit的表示range:-2^n-1^~2^n-1^-1(正數比負數少1,因為有一個要代表0)

[3]sign extension(符號拓展)
少bit換到多bit的暫存器中,則此時看資料的第1bit是0還是1,決定前面多餘的空位是補0或1

### 重點二:加法與減法
[1]
減法也是用加法運算,只不過是要先取一個2'complement再相加

[2]溢位偵測
有號數溢位偵測=>
查看A跟B之正負號以及運算元
ex;正+正,正-負,負+負,負-正

無號數溢位常忽略,要自行偵測

### 重點三:多媒體算數
[1]Vector或SIMD
同時對某些短向量做特別運算(可能同時對2個32位元...)

[2]飽和運算
當運算溢位,則將結果設為最大或最小值

### 重點四:算術邏輯運算單元
[1]one bit Adder

<font color="red">CarryOut = ab + aCarryIn + bCarryIn(2個gate delay)
sum = a⊕b⊕CarryIn(3個gate delay)
</font>

[2]one bit ALU

| Function| Ainvert | Binvert |CarryIn|Operation1|Operation2|
| -------- | -------- | -------- |----|----|----|
| and | 0 | 0 | X | 0 | 0 |
| or | 0 | 0 | X | 0 | 1 |
| add | 0 | 0 | 0 | 1 | 0 |
| sub | 0 | 1 | 1 | 1 | 0 |
| nor | 1 | 1 | X | 0 | 0 |
| slt | 0 | 1 | 1 | 1 | 1 |

[3]溢位偵測
<font color="red">如果前兩位位元 一個有進位 一個沒有進位 則overflow</font>

### 重點五:前瞻進位加法器
[1]定義
critical path:CarryOut算完之所需總時間
sum path:sum算完之所需總時間

#### 漣波進位加法器(ripple carry adder)
critical path = 2N(gate delay)
sum path = 2N + 1(gate delay)

#### 無限硬體快速進位加法器
基本想法:
任何問題都可以用<font color="red">兩層邏輯</font>表示
缺點:
當式子到較高位元時會變成非常複雜,雖然延遲時間短,但硬體成本消耗太高,會呈指數型成長

#### 前瞻進位加法器(carry lookahead adder,CLA)=>前兩者的折衷版
決定進位之兩要素:
Generate:gi = ai * bi
Propagate:pi = ai + bi

四位元前瞻進位加法器
(1)
c1 = g0 + (p0 * c0)
c2 = g1 + (p1 * g0) + (p1 * p0 * c0)
c3 = g2 + (p2 * g1) + (p2 * p1 * g0) + (p2 * p1 * p0 * c0)
c4 = g3 + (p3 * g2) + (p3 * p2 * g1) + (p3 * p2 * p1 * g0) + (p3 * p2 * p1 * p0 * c0)

(2)
critical delay = 算pi,gi delay時間 + 算cn delay 時間 =1 + 2 = 3
sum delay = critical delay + 3delay = 3 + 3 = 6

十六位元前瞻進位加法器
(1)
critical delay = 算pi,gi delay時間 + 算Pi,Gi delay時間 + 算cn delay 時間 = 1 + 2 + 2 = 5 delays
sum delay = critical delay + Cn帶入求出小c + 求sum = 5 + 2 + 3 = 10 delays

### 重點六:進位儲存加法器
設經過一加法器需要2T延遲
傳統加法器:2T * 7 = 14T延遲
進位儲存加法器:2T * 6 = 12T延遲

### 重點七:無號數乘法
傳統乘法器
[1]
initial:被乘數放置於被乘數暫存器右半部

for loop:
step1:multiplier向右shift 1 bit被拿來跟multiplicand相乘加入product中
step2:multiplicand向左shift 1 bit

#### [1]硬體最佳化乘法器
initial:將乘數放置於被乘數暫存器右半部

for loop:
step1:multiplier向右shift 1 bit被拿來跟multiplicand相乘加入product的左半部

### 重點八:有號數乘法
#### [1]布斯演算法
跟執行硬體最佳化乘法演算法的硬體很像,<font color="red">差別在於一次檢查乘數的兩位元</font>

| 抓的數字 | 動作 |
| -------- | -------- |
| 00 | 不執行運算 |
| 01 | 將被乘數加到乘積的左半部 |
| 10 | 將乘積的左半部減去被乘數 |
| 11 | 不執行運算 |

inital:最右邊的1bit(mythical bit)放0
for loop:
steps1:一次檢查兩位元看是否需要做動作
steps2:將乘積暫存器向右移1位元

#### [2]布斯演算法優點
(1)可算有號數乘法
(2)平均運算速度比一般乘法器快,因他只處理01跟10的狀況,若連續1或0不需處理

#### [3]快速乘法硬體

比較快的原因:
(1)序向電路對乘積的每一位元都必須消耗一個時脈週期,但加法器陣列的乘法器不用
(2)容易被最佳化
(3)較容易pipeline,可同時運算(可以到log(n)等級)

#### [3]parallel fast multipier
32個bit只要經過celing(log~2~32 = 5個add delay即可完成)

### 重點九:除法
#### [1]傳統除法器:
(1)32位元除數會先被放置在左半部(xxxx0000),每次循環右移一位
(2)餘數暫存器一開始設定為被除數的值
<font color="red">注意第一回合可以不理會(因不會有交集),故4個bit相除要做5個回合</font>
=>不會有交集的意思,可以帶1111除0001試試看就明白了

#### [2]硬體最佳化除法:
initial:
divisor 32位元
remainder 64位元(左半部補0,右半部放被除數)

:::warning
<font color="green">sop流程:</font>
initial:
先將remainder左移1bit(讓divisor跟dividend有交集)

for loop (0,32)://共做了32bit
step1:dividor除remainder左半部,將0或1結果插入到remainder最右邊(因此remainder左移1bit)
step:2檢查是否超過32次了

end:
remainder左半部要往右移1bit(不能影響右半部的值)

:::

結果:
商數=remainder右半部
餘數=remainder左半部

<font color="red">此方法4bit只會做4回合 因為有先initial向左移動了1bit</font>
<font color="red">此方法divisor完全不需要動,商數就是remainder右半部</font>

#### [3]mips乘、除法
有兩種指令:mfhi,mflo各將64bit的左右半部存入暫存器中
(1)
乘法:存乘積
除法:Hi存放餘數,Lo存放商數

(2)使用方法

mfhi $s0   #$s0<-Hi

### 重點十一:浮點數的表示
#### [1]IEEE754浮點數標準

(1)單精度(32bit):
1位元表示正負號,8位元表示指數,23位元表示有效數字

(2)倍精度(64bit)
1位元表示正負號,11位元表示指數,52位元表示有效數字

(3)
公式=(-1)^sign^x(1+fraction)x2^(exponent-bias)^
<font color="red">bias = 2^(指數個數-1)^-1</font>
ex:32bit=>8個指數個數=>bias=2^8-1^-1 = 127
ex:excess-15 => bias=15

(4)非正規化數
公式=(-1)^sign^x(<font color="red">0.</font>fraction)x2^-126^

此數之存在是因為IEEE754range只能從
1.0x2^-126^-1.11...x2^127^以及(-1.0x2^-126^)-(-1.11...x2^127^)
0~+-1.0x2^-126^沒辦法被表示,因此為了能夠表示更小的數,才有此數之出現
故range最小可以到0.000000000....x2^-126^ = 1.02^-149^,此數以下的仍無法表示

(5)0~0.00000.....1x2^-126^此區間稱為gradual underflow(除了0):精確值逐漸遞減為0

(6)0~0.11111...1x2^-126^此區間稱為underflow(除了0)(正規浮點數表示法無法表達到的區間)

(7)浮點數表示法的range為+-2x2^bias^~2x2^-bias^

<font color="red">(8)重要表格</font>

### 重點十二:浮點數的加法
(1)相加時,指數的大小要遵從較大的
### 重點十三:浮點數的乘法
### 重點十四:精確的算術運算
(1)
Guard bit:mantissa之外的第1bit
Round bit:mantissa之外的第2bit
sticky bit:mantissa之外的第3~n bits是否都為0,若不是都為0,則為1

### 重點十五:浮點數加法的結合律
<font color="red">浮點數加法並不符合結合律
當一個(15000000 - 15000000) + 1.0 = 1.0,
但15000000 - (15000000 + 1.0) = 0
故 (x+y)+z ≠ x+(y+z)</font>

### 重點十六:右移與2的幕次方除法運算
<font color="red">一個數*4可以直接左移2bit,
但當是除法時則不行使用右移的方法 當除數與被除數異號時會有問題</font>
<font color="gree">解決方法:加2^n^-1判斷被捨棄的兩個數字是否非0,如果是零除4則加3,除8則+7,非0的話會進位</font>

### 重點十七:軟體偵測溢位
[1]有號數加法之溢位偵測
=>前四行判斷兩運算元是否異號
=>後三行判斷結果跟運算元是否異號

addu $t0,$t1,$t2               #$t0=sum,but don't trap 
xor  $t3,$t1,$t2               #check if signs differ
slt  $t3,$t3,$zero             #$t3 = 1 if signs differ  
bne  $t3,$zero,$No_overflow    #t1,t2 signs ≠,so no overflow
xor  $t3,$t0,$t1               #signs=;sign of sum match too? 
                               #$t3 negative if sum sign different
slt  $t3,$t3,$zero             #$t3 = 1 if sim sign different
bne  $t3,$zero,Overflow        #All three signs≠;goto overflow

[2]有號數加法之溢位偵測
=>看t2的補數是否大於t1
=>移項之後代表檢查t1+t2是否會大於1

addu $t0,$t1,$t2               #$t0=sum
nor  $t3,$t1,$zero             #$t3=NOT$t1
                               #(2's comp-1:2^32^-$t1-1)
sltu $t3,$t3,$t2               #(2^32-$t1-1)<$t2
                               #(2^32-1)<$t2+$t1
bne  $t3,$zero,Overflow        #if(2^32-1<$t2+$t1)go to overlow

###### tags: `computer architecture` `chp2` `tips` `bit computer`