程式電羊: Chapter 3 Arithmetic for Computers

Chapter 3 Arithmetic for Computers

一切都是從這張圖開始,想當初修計組這門課對於前面的組語概念都不甚了解,最有印象的內容大概就是這章節,因為他實作起來比較簡單,總之32bit加法器,非常適合新手入門!

在實作32bit加法器之前,我想大家都有一個必經的過程先個別實作出1bit的加法器,如下圖,還記得大家在實作實都會照著一張表來作,當時也沒有想太多就照著寫就對了

Function	Ainvert	Binvert	CarryIn	Operation1	Operatopn2
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

bit operation比較直觀,我想大家會有疑問的應該會是對sub與slt,這個問題也是每次遇到都要再查一遍,屢試不爽.

Sub

A - B = A + (2's comp B)

= A + (B' + 1). note: +1的部分可以從carry in借來

Slt 中心思想為A,B兩數相減

Result reg is 1 if a < b

Result reg is 0 if a >= b

最後還必須判斷是否溢位(overflow)

Recall the simpler overflow detection:

An overflow occurs if and only if the carry in to the HOB differs from the carry out of the HOB. (直接檢查最高位的carry_in與carry_out是否相同,不同的話則溢位)

額外補充:

Implementing Zero Detection

To see if all bits are zero just need the NOR of all the bits
Conceptually trivially but does require some wiring

note: 這可以在branch condition時,快速判斷兩暫存器內容是否相同

花了一些篇幅介紹簡單的加法器,然而往往最簡單的想法可能步驟是簡單而多的.

這種加法器又稱為漣波進位加法器(Ripple Carry Adder ,RCA),漣波進位加法器必須從最小有效位傳輸至最大有效位,因此會有很長的電路延遲,就N位元漣波進位加法器,最長延遲路徑(Critical path delay)為2N個邏輯閘延遲(must wait for input A and B),而得到正確結果須2N+1

這種加法器相較於其他加法器算是延遲時間最長的一種.

前詹進位加法器 (Carry Lookahead Adder, CLA)

先定義兩個名詞

propagate is that p is true if the current bit will propagate a carry from its input to its output. note: 是否會傳遞進位?

It is easy to see that p = (a OR b), i.e.

if and only if (a OR b)

then if there is a carry in

then there is a carry out

generate is that g is true if the current bit will generate a carry out (independent of the carry in). note:是否會產生進位?

It is easy to see that g = (a AND b), i.e.

if and only if (a AND b)

then the must be a carry-out independent of the carry-in

to generate a carry: gi = ai bi
to propagate a carry: pi = ai+bi

四位元前瞻進位加法器

c1 = g0 + p0 c0

c2 = g1 + p1 c1 = g1 + p1 g0 + p1 p0 c0

c3 = g2 + p2 c2 = g2 + p2 g1 + p2 p1 g0 + p2 p1 p0 c0

c4 = g3 + p3 c3 = g3 + p3 g2 + p3 p2 g1 + p3 p2 p1 g0 + p3 p2 p1 p0 c0

無號數乘法 Multiplication

第一次看這邊總是搞不懂到底是multiplicand 還是multiplier該往右,在這之前必須知道multiplicand是被乘數,multiplier是乘數,在進行乘法時,都會先選定乘數的最小位乘上一個被乘數,在選乘數的第二位乘上一個被乘數,依序下去,所以從這個過程可以看出直覺得想法該如何時作乘法器.

首先要知道(n bit)乘上(m bit),所乘結果,最多只有n+m bit,所以product與被乘數的部分為64bit,傳統的乘法為每次檢查multipler的LSB如果為1就在product累加並將multiplicand左移,muliplier右移(試想乘法的過程每次都會對齊目前的乘數位置),這個方法的缺點是被乘數總有一半的位元數為零(wasted),所以有改良版

Hardware-friendly multiplication

之前提到有一半浪費的空間,加強版的的要旨就是要好好的利用這部分,首先固定不動被乘數,並將乘數放在product這個register(意味著不需要額外的空間來儲存multiplier),基本步驟與傳統乘法相似,差別在判斷乘數的LSB為1時,將multiplicand累加至product的左半邊,反之為0則no operation,最後右移product,這舉動相當漂亮,將傳統的一左一右合併成一個動作.

有號數乘法

第一種方法為直接將乘數與被乘數用二的補數方式改成正數

第二種方法為

Booth’s Alogrithm

這個演算法的硬體與硬體最佳化的硬體大致相同,這個演算法多了一個mythiccal bit的register

布斯演算法的核心在於他對數字中間部分的1字串進行頭,中,尾三段的處理. 0字串的部分由於本身就無須進行運算,所以不必理會,布斯演算法一次檢查乘數的連續兩個位元,所以依據這兩個位元的值會有四種狀況

依照目前與先前位元(右邊)的不同，執行下面工作：

00：字串0的中間部份，不需要算術運算
01：字串1的結尾，所以將被乘數加到乘積的左半部
10：字串1的開端，所以從乘積的左半部減去被乘數
11：字串1的中間部份，所以不需要算術運算

如同前面的演算法，將乘積暫存器右移1位元

note:

1.一開始 mythical bit值為0

2.將乘積右移時，因為我們是處理有號數字，必須保留中間過程結果的正負符號，所以當乘積向右移時，擴展其符號。因此第一次重覆迴圈的乘積暫存器右移1位元時，將(111001110)2轉換成(111100111)2，不是(011100111)2，這種移位稱為算術右移(arithemetic right shift)，有別於邏輯右移。

重覆次數	步驟	被乘數暫存器	乘積暫存器
0	起始值	0010	0000 1101 0
1	10=>乘積暫存器=乘積暫存器-被乘數暫存器	0010	1110 1101 0
1	乘積暫存器右移	0010	1111 0110 1
2	01=>乘積暫存器=乘積暫存器+被乘數暫存器	0010	0001 0110 1
2	乘積暫存器右移	0010	1111 1011 0
3	10=>乘積暫存器=乘積暫存器-被乘數暫存器	0010	1110 1011 0
3	乘積暫存器右移	0010	1111 0101 1
4	11=>不做任何事	0010	1111 0101 1
4	乘積暫存器右移	0010	1111 1010 1