Microsoft PowerPoint - chx03_org08_Mul&shift

Size: px

Start display at page:

Download "Microsoft PowerPoint - chx03_org08_Mul&shift"

哄晏
5 years ago
Views:

1 计算机组织与系统结构 ALU 设计乘法与移位 ( 第八讲 ) 位 ALU 完成 AND OR 和 ADD 功能的一位 ALU 输入进位 (CarryIn) A 程旭 3..3 B -bit 全加器多路选择器输出进位 (CarryOut) 结果 (Result) 更加细化的框图 LSB 和 MSB 需要进行特殊处理 signed-arith and cin xor co Ovflw A a3 b3 ALU co cin s3 3 B 3 S 3 a b ALU co cin s 4 M C/L to produce select, comp, c-in 先行进位 Carry Look Ahead ( 设计技巧 : 窥探 ) A B A B A B A B G P G P G P G P Cin S S S S C =G + C P C = G + G P + C P P A B C-out Fill C-in Propagate C-in Propagate Generate P = A and B G = A xor B C3 = G + G P + G P P + C P P P G P C4 =...

2 先行进位的理论基础 ( 续 ) 道管 : 先行进位的类比使用新定义的两个术语 : 第 i 位产生的进位 gi = Ai & Bi 通过第 i 位的传播进位 pi = Ai or Bi We can rewrite: Cin = g (p & Cin) Cin = g (p & g) (p & p & Cin) Cin3 = g (p & g) (p & p & g) (p & p & p & Cin) 进入第 3 位的进位是, 如果在第位, 产生了进位 (g) 或者在第位产生了进位 (g) 并且第位传播了这个进位 (p & g) 或者在第位产生了进位 (g) 并且第位和第位都传播了这个进位 (p & p & g) 或者在第位有输入进位 (Cin) 并且第位第位和第位都传播了这个进位 (p & p & p & Cin) g c g c g3 c p g g p g p3 c p g p p p c c4 设计过程的要素分治 Divide and Conquer (e.g., ALU) 针对较简单的部件, 阐明解决方案. 设计每个部件 ( 子问题 ) 产生并测试 Generate and Test (e.g., ALU) 给出一组构件, 如何将它们组装起来, 并满足需求逐步求精 Successive Refinement (e.g., carry lookahead) 解决大多数问题 ( 即, 忽视一些约束或特殊情况 ), 检查并修改不足阐明可供选择的高级方案 Formulate High-Level Alternatives (e.g., carry select) 当选择任何一种方案时, 都要考虑多种策略做已知如何做的事情 Work on the Things you Know How to Do 在不断前进中, 未知的事情将越来越明显设计过程小结采用层次式设计处理复杂性自顶向下 vs. 自底向上 vs. 逐步求精设计表达的重要性 : 基本模块 (Block Diagrams) 分解为位片 ( Bit Slices) 真值表 K-Maps 电路图其他描述 : 状态图时序图, 寄存器传输,... 优化标准 : 门数 [ 封装数 ] 面积管教输出 top down Logic Levels Fan-in/Fan-out Cost Delay Design time Power bottom up mux design meets at TT

3 上讲总结设计过程概述设计是一个不断反复的过程 -- 逐步求精无需等到洞察一切后才开始设计二进制算术绪论使用补码表示, 易于实现减法本讲提纲上一讲复习根据指令系统和移位, 设计 ALU 乘法 ALU 设计设计一个简单的 4 位 ALU 其他构建 ALU 的技术 ISA 驱动的 ALU 设计对 ALU 进行需求分析从指令系统体系结构开始 : 必须能够完成 ISA 中的所有操作根据出现频率和硬件预算, 对成本和性能进行权衡 MIPS ISA MIPS 的算术指令指令示例含义注释 add add $,$,$3 $ = $ + $3 3 operands; exception possible subtract sub $,$,$3 $ = $ -$3 3 operands; exception possible add immediate addi $,$, $ = $ + + constant; exception possible add unsigned addu $,$,$3 $ = $ + $3 3 operands; no exceptions subtract unsigned subu $,$,$3 $ = $ -$3 3 operands; no exceptions add imm. unsign. addiu $,$, $ = $ + + constant; no exceptions multiply mult $,$3 Hi, Lo = $ x $3 64-bit signed product multiply unsigned multu$,$3 Hi, Lo = $ x $3 64-bit unsigned product divide div $,$3 Lo = $ $3, Lo = quotient, Hi = remainder Hi = $ mod $3 divide unsigned divu $,$3 Lo = $ $3, Unsigned quotient & remainder Hi = $ mod $3 Move from Hi mfhi $ $ = Hi Used to get copy of Hi Move from Lo mflo $ $ = Lo Used to get copy of Lo

4 乘法 ( 无符号数 ) 从纸和笔做乘法 ( 无符号数 ): 被乘数 Multiplicand 乘数 x Multiplier 乘积 Product 如果忽略符号位,m 位 x n 位 = m+n 位乘积二进制, 使得乘法更易实现 : => ( x 被乘数 ) => 被乘数 ( x 被乘数 ) 4 种乘法硬件 / 算法循序渐进无符号组合乘法器 A A A A A A A A P 7 P 6 P 5 P 4 P 3 P P P 如果 B i ==, 那么, 第 i 级累计 A * i 问题 : 3 位乘法器需要多少硬件? 关键路径? B B B B 3 上述乘法器如何工作? A A A A B B 第一种无符号移位 - 加法乘法器 64 位被乘数寄存器 64 位 ALU 64 位乘积寄存器 3 位乘数寄存器 A A B Multiplicand 64 bits Shift Left P 7 P 6 P 5 A P 4 A P 3 P P P B 3 64-bit ALU Multiplier Shift Right 3 bits 每级都对 A 进行左移 ( x ) 使用 B 的下一位来判断是否加上左移后的被乘数 Product 64 bits Write Control 每级都累计 n 位的部分积乘法器 = 数据通路 + 控制

5 第一种乘法算法 Multiplier = Start. Test Multiplier Multiplier = 上述乘法器如何工作? A A A A B B a. Add multiplicand to product & place the result in Product register A A B A A B 3 乘积乘数被乘数. Shift the Multiplicand register left bit. P 7 P 6 P 5 P 4 P 3 P P P 3. Shift the Multiplier register right bit. 3nd repetition? No: < 3 repetitions Yes: 3 repetitions Done 每级都对 A 进行左移 ( x ) 使用 B 的下一位来判断是否加上左移后的被乘数每级都累计 n 位的部分积第一种乘法的启示如何进一步改进? 每个周期个时钟 => 每次乘法大约 (3 3) 个时钟乘法与加法的出现频率比 5: ~ : A A B A A 64 位被乘数中 / 的位数总是为 => 使用 64 位加法器, 太浪费!!! B A A B 在被乘数左移的过程中, 在左边插入 => 一旦产生了乘积的最小位, 它就永远不变!!! A A B 3 用乘积右移替代被乘数左移? P 7 P 6 P 5 被乘数固定不动, 乘积右移 P 4 P 3 P P P

6 第二种乘法硬件第二种乘法算法 Start 3 位被乘数寄存器 3 位 ALU 64 位乘积寄存器 3 位乘数寄存器 Multiplier =. Test Multiplier Multiplier = Multiplicand 3 bits 3-bit ALU Product 64 bits Shift Right Write Multiplier Shift Shift Right Right 3 bits Control a. Add multiplicand to the left half of product & place the result in the left half of Product register Product Multiplier Multiplicand : : 3: : : 3: : : 3: : : 3:. Shift the Product register right bit. 3. Shift the Multiplier register right bit. 3nd repetition? No: < 3 repetitions Yes: 3 repetitions Done 第二种乘法算法仍然浪费很多资源! Multiplier = Start. Test Multiplier Multiplier = 第二种乘法的启示乘积寄存器浪费的空间正好与乘数中无用的空间相同 a. Add multiplicand to the left half of product & place the result in the left half of Product register Product Multiplier Multiplicand : : 3: : : 3: : : 3: : : 3:. Shift the Product register right bit. 3. Shift the Multiplier register right bit. 3nd repetition? No: < 3 repetitions Yes: 3 repetitions Done => 联合使用乘数寄存器和乘积寄存器

7 第三种乘法硬件第三种乘法算法 Start 3 位被乘数寄存器 3 位 ALU 64 位乘积寄存器 ( 没有乘数寄存器 ) Multiplicand Product Product =. Test Product Product = Multiplicand a. Add multiplicand to the left half of product & place the result in the left half of Product register 3 bits 3-bit ALU Product Multiplicand. Shift the Product register right bit. Product (Multiplier) 64 bits Shift Right Write Control 3nd repetition? No: < 3 repetitions Yes: 3 repetitions Done 第三种乘法的启示由于乘数和乘积结合在一起, 每位需要步 MIPS 中寄存器 Hi 和 Lo 是乘积的左半部和右半部提供了 MIPS 指令 MultU 如何进一步改进该算法的速度? 有符号数乘法如何? 简单地策略是假设两个源操作数都位正数, 在运算结束时在对乘积进行修正 ( 不算符号位, 运算 3 步 ) 使用补码 - 需要对部分乘积进行符号扩展, 在最后再进行减法 Booth 算法是一种利用上述硬件进行有符号数乘法的优秀算法 - 可同时处理多位 Booth 算法的动机示例 : x 6 = x : x 移位 ( 乘数运算位为 ) + 加法 ( 乘数运算位为 ) + 加法 ( 乘数运算位为 ) + 移位 ( 乘数运算位为 ) 具有加法或减法的 ALU 可以采用多种方式计算相同的结果 : 6= 或者 = -+ 乘数中的串可以用看到第一个时, 进行一次减法, 在处理完最后一个后, 再加! x 移位 ( 乘数运算位为 ) - sub ( 乘数中的第一个 ) + shift ( 串的中部 ) + add ( 最后的前步 )

Booth 算法探奥运行尾部 (end of run) 运行中部 (middle of run) 运行首部 (beginning of run) 当前位右边位解释示例串运行的首部串运行的中部 Booth 算法. 依赖于当前和以前的位, 进行下述步骤之一 : : a. 串的中部, 不进行任何运算操作. : b. 串的结束, 将被乘数加到乘积的左半部. : c.

8 Booth 算法探奥运行尾部 (end of run) 运行中部 (middle of run) 运行首部 (beginning of run) 当前位右边位解释示例串运行的首部串运行的中部 Booth 算法. 依赖于当前和以前的位, 进行下述步骤之一 : : a. 串的中部, 不进行任何运算操作. : b. 串的结束, 将被乘数加到乘积的左半部. : c. 串的首部, 从乘积的左半部减去被乘数. : d. 串的中部, 不进行任何运算操作.. 象第三种乘法算法一样, 将乘积算术右移位. 串运行的尾部串运行的中部早期, 由于移位比加法速度更快, 采用该算法主要为了速度将乘数中间的串用在第一次看见时的一次初始减法和在最后一个后的一次加法代替被乘数乘积 ( x 3) 被乘数乘积 ( x -3) Booth 算法探奥 Booth 算法探奥 a i a i- Operation Do Nothing Add b Subtract b Do Nothing 对于 a i- -a i: ( a + ( a + ( a ( a a 3 a a a ) b 3 ) b ) b ) b 3 : do nothing +: add b - : subtract b a b (( a = b a i i+ i i i i + ai = ( ai + ai ) = ( ai ai ) = ai 3 3 ) + ( a a = 3 3 ) ( a ) + ( a )

9 Booths 示例 ( x 7) Operation Multiplicand Product next?. initial value sub a. P = P - m + shift P (sign ext) b. nop, shift. nop, shift 3. add 4a. + shift 4b. done Booths 示例 ( x -3) Operation Multiplicand Product next?. initial value sub a. P = P - m + shift P (sign ext) b. add + a. shift P b. sub + 3a. shift 3b. nop 4a shift 4b. done MIPS 的逻辑指令指令示例含义注释 and and $,$,$3 $ = $ & $3 3 reg. operands; Logical AND or or $,$,$3 $ = $ $3 3 reg. operands; Logical OR xor xor $,$,$3 $ = $ $3 3 reg. operands; Logical XOR nor nor $,$,$3 $ = ~($ $3) 3 reg. operands; Logical NOR and immediate andi $,$, $ = $ & Logical AND reg, constant or immediate ori $,$, $ = $ Logical OR reg, constant xor immediate xori $, $, $ = ~$ &~ Logical XOR reg, constant shift left logical sll $,$, $ = $ << Shift left by constant shift right logical srl $,$, $ = $ >> Shift right by constant shift right arithm. sra $,$, $ = $ >> Shift right (sign extend) shift left logical sllv $,$,$3 $ = $ << $3 Shift left by variable shift right logical srlv $,$, $3 $ = $ >> $3 Shift right by variable shift right arithm. srav $,$, $3 $ = $ >> $3 Shift right arith. by variable 比较并转移比较并转移 BEQ rs, rt, offset if R[rs] == R[rt] then PC-relative branch BNE rs, rt, offset <> 与零比较并转移 BLEZ rs, offset if R[rs] <= then PC-relative branch BGTZ rs, offset > BLT < BGEZ >= BLTZAL rs, offset If R[rs] < then branch and link (into R 3) BGEZAL >= 几乎所有的比较都是与进行比较!

10 MIPS 对 ALU 的需求 Add, AddU, Sub, SubU, AddI, AddIU => 带溢出检测和反向器的补码加法器 SLTI, SLTIU (set less than) => 带反向器的补码加法器, 检测结果的符号 BEQ, BNE (branch on equal or not equal) => 带反向器的补码加法器, 检测结果是否为零 And, Or, AndI, OrI => 逻辑或逻辑与上一讲介绍的 ALU 支持这些操作 MIPS 对 ALU 的其他需求 Xor, Nor, XorI => 逻辑异或逻辑或非或者两步策略 : (A OR B) XOR... Sll, Srl, Sra => 需要进行 ~3 位的左移右移算术右移运算 Mult, MultU, Div, DivU => 需要有符号无符号的 3 位乘法和除法对 ALU 增加异或功能三种移位器扩展多路选择器 CarryIn 逻辑 (logical) 移入的数值总是 "" "" msb lsb "" A 算术 (arithmetic) 在右移时, 进行符号扩展 B -bit 全加器 CarryOut 多路选择器结果 left msb lsb msb lsb "" 循环 (rotating) 移出的位又从另一端移入 ( 在 MIPS 中不支持 ) right msb lsb 注 : 需要一位移动特定指令可能要求进行 3 位移动!

11 使用多路选择器的组合移位器基本单元 8 位右移器 A 7 A B sel D A 6 A 5 A 4 A A S S S SHR: Q Q Q 多路选择器 / 移位器 D3 D D D SHR/ don't shift ( 5 inputs) Q Q Q SHR,,, 3 bits: D3 D D D Q Q Q x x 8 x : Mux stages D3 D D D R 7 R 6 R 5 R 4 R 3 MSBs 的输入如何? 3 位移位器需要多少级? 如果使用 4- 多路选择器, 结果如何? R R R 算术右移如何做? shift amount (,,,3) 4 x 4: Mux stage 通用右移策略 (6 位 ) S (,) S (, ) S (, 4) 3 位移位器使用上述配置对 3 位数据进行 ~3 位移位将导致 : 如果使用 : 多路选择器, 那么需要 5 级多路选择器 (x, x, x4, x8, x6) 3 位 x 5 级 = 6 个 : 多路选择器! 如果使用级 4: 多路选择器和级 : 多路选择器, 那么需要 3 级多路选择器 3 x 4: + 3 x 4: + 3 x : S 3 (, 8) 如果增加自右至左的连接, 就可以支持循环移位如果使用级 8: 多路选择器和级 4: 多路选择器, 那么需要级多路选择器 3 x 8: + 3 x 4:

12 多位移位复合策略, 每次循环完成多位的多重控制循环 3 位移位 : 使用位移位器 3 次迭代使用 3 位移位器次迭代使用位移位器 5 次迭代使用 5 位移位器 3 次迭代实际上, 大多数移位都比较短 ( 通常, 实现 -3) 漏斗移位器 (Funnel Shifter) 代替从 64 位中抽取 3 位. Y X 右移 R A 右移 i 位 (sa = shift right amount ) 3 3 逻辑 : Y =, X=A, sa=i 非常复杂 : 目前, 只能进行右移算术 : Y = sign(a), X=A 循环 : Y=A, X=A 右移 3 左移 : Y=A, X=, sa= 3 - i 桶式移位器 (Barrel Shifter) 依赖于技术工艺的解决方案 : 每个开关一个晶体管总结 SR3 SR SR SR D3 指令系统驱动 ALU 设计移位器 : 从每次位到桶式移位器逐步完善 A6 A5 D D 乘法 : 逐步完善 3 位加法器 64 位移位寄存器 3 被乘数寄存器可处理有符号数的 Booth 算法 A4 D 可以设计出每次运算多位的乘法算法移位器 : 每次位的寄存器桶式移位器 A3 A A A

Microsoft PowerPoint - chap3.ppt

Microsoft PowerPoint - chap3.ppt 微算機系統第三章 Arithmetic for Computers 陳伯寧教授電信工程學系國立交通大學 chap3-1 Arithmetic Where we've been: Abstractions: Instruction Set Architecture Assembly Language and Machine Language What's up ahead: Implementing