Computer Organization - Ch3 Arithmetic for Computers

Chapter 3   Arithmetic for Computers

3.1   Arithmetic Logic Unit

• One-bit ALUs with Set Less Than 

• 32-bit ALU with Set Less Than
• Set less than：Set less than instruction requires a subtraction and then sets all but the least significant bit to 0, with the lsb set to 1 if a < b  (lsb – signed bit)
• Overflow：要兩數同號才有可能overflow，overflow時正負會和原來兩數相反，用邏輯式表示為overflow = a31' * b31' * result31 + a31 * b31 * result31’

• Carry look-ahead adder
• 在ALU中，加法器與乘法器有最長的delay path。carry-look-ahead logic就是預先將 Carry 預知送到下一級去運算，減少等待各級間 Carry 運算的時間來增加速度。
• 要預先得到 Carry 的情況就需要藉助 Carry Generate Block 的處理，我們定義 Propagate bit 與 Generate bit如下：
• P(i) = A(i) XOR B(i)
• G(i) = A(i) * B(i) 
• 因此而得Carry和Sum為
• C(i) = G(i) + P(i)G(i-1) + P(i)P(i-1)G(i-2) + … + P(i)…P(1)C(0)
• SUM(i) = A(i) XOR B(i) XOR C(i-1) = P(i) XOR C(i-1)
• 又因此而4 bit carry look-ahead adder的carry分別為
• C1 = P0C0 + G0
• C2 = P1C1 + G1 = P1(P0C0 + G0) + G1 = P1P0C0 + P1G0 + G1
• C3 = P2C2 + G2 = P2(P1P0C0 + P1G0 + G1) + G2 = P2P1P0C0 + P2P1G0 + P2G1 + G2
• C4 = P3C3 + G3 = P3(P2P1P0C0 + P2P1G0 + P2G1+ G2) + G3
  = P3P2P1P0C0 + P3P2P1G0 + P3P2G1 + P3G2 + G3

• 再定義group generate (g0-3) and group propagate (p0-3) 
• g0-3 = g3 + p3g2 + p3p2g1 + p3p2p1g0
• p0-3 = p3p2p1p0
• 因此得 2 level 16 bit carry look-ahead adder的carry分別為
• c4 = g0-3 + p0-3c0
• c8 = g4-7 + p4-7c4 = g4-7 + p4-7(g0-3 + p0-3c0) = g4-7 + p4-7g0-3 + p4-7p0-3c0

3.2   乘法

• 傳統改良乘法
• 先加上部分積
• 乘數和積向右shift一位 (都是在乘積暫存器裡同時做)：同時“讀乘數的下一bit" 並減少目前product的位數 “讓之後算出的部分積相對增加”

• Booth演算法
• 概念
• Booth演算法是一種較簡潔的有號數字相乘的方法，即利用位元掃描方式，跳過00、11以增快速度，因此，當乘數中的連續1比較多時(形成比較長的1串時)，booth演算法較一般的乘法演算法執行的加減法運算少。
• 舉例來說...
  A * 0011 1110
  = A * (0100 0000 - 0000 0010)
  = A * 0100 0000 - A * 0000 0010
  = (A<<6) - (A<<1)
  因此在booth演算法中有加法與減法。
• 注意起始狀態時乘數(與積共用)最右側要加上mythical bit = 0
• 演算法
• 依照目前與先前位元的不同，執行下面工作：
1. 00： 字串0的中間部份，不需要算術運算
2. 01： 字串1的結尾，所以將被乘數加到乘積的左半部
3. 10： 字串1的開端，所以從乘積的左半部減去被乘數
4. 11： 字串1的中間部份，所以不需要算術運算

3.3   浮點數

• IEEE二進位浮點數算術標準（IEEE 754）
• 浮點數儲存格式
• S：最高有效位為符號位
• Exponent：儲存指數
• Fraction：儲存尾數的小數部份(在非規約形式下整數部份默認為0，其他情況下一律默認為1)

• 正規形式與非正規形式
• 如果浮點數中指數部分的編碼值在0 < exponent < 2^(e)-1之間，且尾數部分最高有效位（即整數位）是1，那麼這個浮點數將被稱為正規形式的浮點數。
• 實際上非正規形式的浮點數仍然是有效可以使用的，只是它們的絕對值已經小於所有的規約浮點數的絕對值；即所有的非規約浮點數比規約浮點數更接近0
• 指數偏移值 (exponent bias)
• 浮點數表示法中的指數域的編碼值為指數的實際值加上某個固定的值，IEEE 754標準規定該固定值為2^(e-1) - 1，其中的e為儲存指數的位元的長度。以單精度浮點數為例，它的指數域是8個位元，固定偏移值是128-1 = 127。
• 採用這種方式表示的目的是簡化比較。因為指數的值可能為正也可能為負，如果採用補碼表示的話，全體符號位S和Exp自身的符號位將導致不能簡單的進行大小比較。正因為如此，指數部分通常採用一個無符號的正數值存儲。單精度的指數部分是−126～+127加上偏移值127，指數值的大小從1～254（0和255是特殊值）。浮點小數計算時，指數值減去偏正值將是實際的指數大小。