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
	乘積暫存器右移	0010	1111 0110 1
2	01=>乘積暫存器=乘積暫存器+被乘數暫存器	0010	0001 0110 1
	乘積暫存器右移	0010	1111 1011 0
3	10=>乘積暫存器=乘積暫存器-被乘數暫存器	0010	1110 1011 0
	乘積暫存器右移	0010	1111 0101 1
4	11=>不做任何事	0010	1111 0101 1
	乘積暫存器右移	0010	1111 1010 1

floating point

就如科學記號為了一致性會對數字進行標準化,blabla  ,總之稱為 IEEE 754浮點數標準

single precision

double precision

note:

1.exponent 有正負號

2.這是給2進位的標準,通常都會要求轉換成十進位制的科學記號

note:

Normalize significand(規約數):

1.

1.0 ≤ |significand| < 2.0(e.g  1.xxxxxx 與科學記號的概念相同)

2.

expoent 介於   0 < exponent < 2e-1

至於非正規數可以參照維基定義,非正規數是為了能表示更接近零的數

非规约形式的浮点数

如果浮点数的指數部分的编码值是0，尾数为非零，那么这个浮点数將被稱為非规约形式的浮点数。IEEE 754标准规定：非规约形式的浮点数的指数偏移值比规约形式的浮点数的指数偏移值大1.例如，最小的规约形式的单精度浮点数的指数部分编码值为1，指数的实际值为-126；而非规约的单精度浮点数的指数域编码值为0，对应的指数实际值也是-126而不是-127。实际上非规约形式的浮点数仍然是有效可以使用的，只是它们的绝对值已经小于所有的规约浮点数的绝对值；即所有的非规约浮点数比规约浮点数更接近0。规约浮点数的尾数大于等于1且小于2，而非规约浮点数的尾数小于1且大于0.

總的來說可以得到下圖的規則

最後附上一個 轉IEEE_754的方法

note:  小數轉二進位可以不斷的乘二直到小數位都為零的方法

參考資料:

對於1bit alu有很好的解釋

https://cs.nyu.edu/courses/fall01/V22.0436-001/lectures/lecture-09.html

booth algorithm

http://alex9ufoexploer.blogspot.tw/2013/12/8-bit-booths-multiplier-booth.html

significand mantissa  傻傻分不清楚?

https://en.wikipedia.org/wiki/Significand

uf 大學op講義

https://www.cise.ufl.edu/~mssz/CompOrg/CDA-arith.html

中文版的維基  對於IEEE_754得講解非常清楚,有點像補習班老師的fu

https://zh.wikipedia.org/wiki/IEEE_754

Chapter2 Instructions: Language of the Computer

Chapter2 Instructions: Language of the Computer

There are four design princinple in MIPS

1. Simplicity favors regularity.

2. Smaller is faster.

3. Good design demands good compromises.

4. Make the common case fast.

simplicity favors regularity

e.g.

C code:

A = B + C + D;

E = F - A;

MIPS code:

add $t0, $s1, $s2    # $t0 = $s1 + $s2, put result “temporarily” in $t0

add $s0, $t0, $s3    # $s0 = $t0 + $s3, now we can use the “temporary” result from $t0

sub $s4, $s5, $s0   # $s4 = $s5 - $s0

--->加減乘除必須遵照R-format  

--->Operands must be registers — only 32 registers provided  (MIPS arithmethic)

smaller is faster

Clock cycle faster vs. More registers  

The amount of time it takes to get a value from a register into the ALU, or from the ALU into a register, is proportional to the exponent of 2. That is, the time for 32 registers is twice the time of 16 registers and 1/2 the time of 64 registers.

總的來說,發現32個register是比較適當的

----->

那如果暫存器不夠用呢?

ans:

Must move values between memory and registers

Load and Store instruction

C or Java code:

A[8] = h + A[8];

MIPS code:

la $t3, A                       # load address of start of array A

lw $t0, 32($t3)             # load contents of A[8]

add $t0, $s2, $t0

sw $t0, 32($t3)

從這兩個準則可以發現

MIPS的兩大特性

• loading words but addressing bytes

• arithmetic performed on registers only

Machine languague

R-format

   6                       5               5               5                5                  6    bit

• op — basic operation of the instruction, the opcode

• rs — first register source operand

• rt — second register source operand

• rd — register destination operand, it gets the result

• shamt — shift amount (e.g sll $d, $t, h  note: t*2^h )

• funct — Function. Selects the specific variant of the opcode.

I-format

------->

Good design demands good compromises.

Where’s the compromise?

Keep all instructions at 32 bits Offset limited to 16-bits, ± 32K

Immediate Operands

1.Constant data specified in an instruction

 addi $s3, $s3, 4

2.

No subtract immediate instruction

Just use a negative constant

 addi $s2, $s1, -1

Small constants are common

Immediate operand avoids a load instruction

--->  Make the common case fast

j-format

e.g.

J -- Jump

JAL -- Jump and link

介紹完四大原則,這邊介紹一些常用到的指令與標示符號和格式

Unsigned Binary integers

Range: 0 to +2^n  – 1

2s-Complement Signed Integers

Range: –2^(n – 1)  to +2^(n – 1)  – 1

二元數與二的補數轉換

Logical Operations

shift operation

R-type

Shift left logical

Shift left and fill with 0 bits

sll by i bits multiplies by 2^i

Shift right logical

Shift right and fill with 0 bits

srl by i bits divides by 2 i  (unsigned only)

AND OR NOT operation

這三種指令基本上大同小異

nor $t0, $t1 $zero

Condition operation

Branch to a labeled instruction if a  condition is true. Otherwise, continue sequentially

beq rs, rt, L1

if (rs == rt) branch to instruction labeled L1;

bne rs, rt, L1

if (rs != rt) branch to instruction labeled L1;

j L1

unconditional jump to instruction labeled L1

Basic Block

A basic block is a sequence of instructions

with

No embedded branches (except at end)

No branch targets (except at beginning)

note: compiler 可以對一個block進行優化

Branch Instruction Design

why MIPS don’t use bge or blt ?

--->Hardware for <, ≥, … slower than =, ≠

--->beq and bne are the common case This is a good design compromise

Procedure Calling

Steps required

1. Place parameters in registers

2. Transfer control to procedure

3. Acquire storage for procedure

4. Perform procedure’s operations

5. Place result in register for caller

6. Return to place of call

有兩種procedure

leaf-procedure  

function不會在call subroutine所以callee不需要push return adress到stack裡

e.g

Non-leaf procedure

步驟:

For nested call, caller needs to save on the

stack:

Its return address

Any arguments and temporaries needed after

the call

Restore from the stack after the call

e.g.

新增說明文字

-->return adress是情況,要自己push進stack裡

-->callee若需要要自己push進stack裡

Byte/Halfword Operations

lb rt, offset(rs)     lh rt, offset(rs)

Sign extend to 32 bits in rt   e.g.

00 1010         --->0000 0000 0000 1010

11 1111 0001 --->1111 1111 1111 0001

lbu rt, offset(rs)    lhu rt, offset(rs)

Zero extend to 32 bits in rt

sb rt, offset(rs)     sh rt, offset(rs)

Store just rightmost byte/halfword (解題目時,要記得MIPS是big-endian~~)

暫存器最右邊的寫入MSB

載入上半部,且右半部清為零

載入下半部

Branch addressing

forward or backward

PC-relative addressing

Target address = PC + offset*4

PC already incremented by 4 by this time

e.g.

參考資料:

交大吳凱強 計算機組織上課講義

對於MIPS的四大原則有很好的例子

http://mescal.imag.fr/membres/vania.marangozova-martin/TEACHING/NACHOS/NACHOS_DOC/04-MIPSintro.pdf

lb sb 之題目

https://www.ptt.cc/bbs/Grad-ProbAsk/M.1262840536.A.8F0.html

https://www.ptt.cc/bbs/Grad-ProbAsk/M.1344535203.A.5CE.html

額外補充之big-endian與little-endian

http://cywu.blogspot.tw/2006/08/endianness-endiannessendiannessbig.html

int到底有幾個btyes呢?

http://www.programmer-club.com.tw/ShowSameTitleN/c/30428.html

某op學校講義(英文版  還未看完)

https://www.cise.ufl.edu/~mssz/CompOrg/CDA-arith.html

wiki sign extension

https://en.wikipedia.org/wiki/Sign_extension