计算机组织与系统结构北大本科07设计过程

1、计算机组织与系统结构设计过程与ALU设计TheDesignProcess&ALUDesign（第七讲）程旭2003.10.21计算机科学技术系计算机系统结构教研室本讲提纲°上一讲复习，本讲介绍°设计过程概述°复习二进制算术运算°设计一个简单的4位ALU°其他 构建 ALU 的技术计算机科学技术系计算机系统结构教研室°性能和技术工艺发展趋势 尽可能保持设计简单充分利用最新技术工艺的优势 CMOS反向器和CMOS逻辑门°延迟建模和门的特征描述 延迟 = 内在延迟 + (负载相关延迟 x 输出负载)°时钟同步方法

2、和定时考虑 最简单的时钟同步方法-所有的单元使用相同的时钟边沿 时钟时间 = CLK-to-Q + 最长延迟路径 + 建立时间 + 时钟扭斜 CLK-to-Q + 最短延迟路径 - 时钟扭斜 > 保持时间计算机科学技术系计算机系统结构教研室时钟扭斜对时钟周期的影响Clk1Clock SkewClk2.SetupHoldSetupHoldD不关心不关心不关心不关心Clock-to-QClock-to-QQ未知SetupHoldD内在延迟 +负载相关延迟时间不关心时钟扭斜最小时钟周期长度计算机科学技术系计算机系统结构教研室时钟扭斜对保持时间的影响Clk1Clock SkewClk2.Setu

3、pHoldSetupHoldD不关心不关心不关心不关心Clock-to-QClock-to-QQ未知HoldHoldDnew?计算机科学技术系计算机系统结构教研室设计过程“设计即描绘（To Design Is To Represent）”设计活动 产生 有关一个对象的 描述/表达 传统的工匠并不区分 概念化（conceptualization） 和 工艺品（artifact） 由于 复杂性 ，这两者才开始分离 概念是用一种或多种 表示语言（representation languages) 描述的 概念化的过程就是设计设计从需求分析开始-功能需求: 性能特征:将要完成的功能速度、功率、面积、成

4、本, . . .计算机系统结构教研室计算机科学技术系设计过程（续）设计以组装结束Design Finishes As Assembly-设计 分解 组成部件，以及如何组装部件-自顶向下 将 复杂的功能（行为）分解为多个基本功能-自底向上将多个基本 功能块为更复杂的组装体设计是一个 “创造性的过程”，而不仅仅是使用某种简单的方法计算机科学技术系计算机系统结构教研室RegsNandGateShifterALUControlDatapathCPU设计求精非形式化的系统需求分析初始规范（Specification）中间规范求精细节逐步增加最终系统结构描述(description)实现的中间规范最终内部

5、规范物理实现计算机科学技术系计算机系统结构教研室设计如同搜寻策略 2策略 1设计包含利用所学知识进行猜测和验证-给定目标, 如何确定这些策略的优劣?给定可选的设计策略, 应该选择那种设计?给定部件和组装体的空间, 哪一部分能够产生最佳解决方案?可行(好)抉择 vs. 最佳抉择计算机科学技术系计算机系统结构教研室子问题 1子问题3子问题2问题 A设计如同陈述（Representation）“VHDL行为"(1)功能描述输入:2 x 16位操作数：A, B;1 位进位输入：Cin.输出:1 x 16位结果：S; 1位进位输出：Co.操作:PASS, ADD (A + B + Cin),

6、AND, XOR, OR, COMPARESUB (A(相等)-B -Cin),性能:现在，还没有详细说明！“VHDL实体"(2)框图理解数据和流16163模式/功能16计算机科学技术系计算机系统结构教研室ABCoALUMSCin二进制数绪论°4位二进制数十进制0123°示例: 3 + 2 = 5二进制0000000100100011十进制4567二进制01000101011001113 + 3 = 610101101101 +0010 +001101010110计算机科学技术系计算机系统结构教研室补码(Twos Complement)表示°负数的补码表

7、示 每位取反,并加 负数的最大位(1MSB)总是为1=>符号位 最大的4位二进制数:7最小的4位二进制数:-8十进制01234567二进制00000001001000110100010101100111十进制0-1-2-3-4-5-6-7-8每位取反111111101101110010111010100110000111补码000011111110110111001011101010011000计算机科学技术系计算机系统结构教研室无效的正数!81000计算机科学技术系计算机系统结构教研室计算机科学技术系计算机系统结构教研室计算机科学技术系计算机系统结构教研室计算机科学技术系计算机系统结构

8、教研室计算机科学技术系计算机系统结构教研室补码算术十进制01234567二进制00000001001000110100010101100111十进制0-1-2-3-4-5-6-7-8补码000011111110110111001011101010011000°示例:7-6=7+(-6)=13-5=3+(- 5)=-2110111010011111100111+00011110计算机科学技术系计算机系统结构教研室ALU的功能描述ALUop3AN零(Zero)结果(Result)N溢出(Overflow)BN输出进位(CarryOut)°ALU 000 001 010 110

9、111线 (ALUop)功能And Or AddSubtractSet-on-less-than计算机科学技术系计算机系统结构教研室ALU1位 ALU°该 1位 ALU将完成 AND、OR和 ADD输入进位（CarryIn）A结果（Result）B输出进位（CarryOut）计算机科学技术系计算机系统结构教研室多路选择器1-bit全加器1位全加器°又称为 “ (3, 2) adder”CarryInACB°半加器: 没有CarryIn 和 CarryOutCarryOut°真值表:计算机科学技术系计算机系统结构教研室输入输出注释ABCarryInCarr

10、yOutSum000000 + 0 + 0 = 00001010 + 0 + 1 = 01010010 + 1 + 0 = 01011100 + 1 + 1 = 10100011 + 0 + 0 = 01101101 + 0 + 1 = 10110101 + 1 + 0 = 10111111 + 1 + 1 = 111-bit全加器CarryOut的逻辑方程式°CarryOut = (!A & B & CarryIn) | (A & !B & CarryIn) | (A & B & !CarryIn)|(A & B &

11、CarryIn)°CarryOut = B & CarryIn|A & CarryIn|A & B计算机科学技术系计算机系统结构教研室输入输出注释ABCarryInCarryOutSum000000 + 0 + 0 = 00001010 + 0 + 1 = 01010010 + 1 + 0 = 01011100 + 1 + 1 = 10100011 + 0 + 0 = 01101101 + 0 + 1 = 10110101 + 1 + 0 = 10111111 + 1 + 1 = 11Sum的逻辑方程式°Sum = (!A & !B &

12、; CarryIn)| (!A & B & !CarryIn) | (A & !B & !CarryIn)|(A & B & CarryIn)计算机科学技术系计算机系统结构教研室输入输出注释ABCarryInCarryOutSum000000 + 0 + 0 = 00001010 + 0 + 1 = 01010010 + 1 + 0 = 01011100 + 1 + 1 = 10100011 + 0 + 0 = 01101101 + 0 + 1 = 10110101 + 1 + 0 = 10111111 + 1 + 1 = 11Sum的逻辑方程式

13、（续）°Sum = (!A & !B & CarryIn) | (!A & B & !CarryIn)|(A & !B & !CarryIn)|(A & B & CarryIn)°Sum = A XOR BXORCarryIn°XOR的真值表:计算机科学技术系计算机系统结构教研室XYX XORY000011101110CarryOut和Sum的逻辑图°CarryOut = B & CarryIn|A & CarryIn|A & BCarryInABCarryOut&#

14、176;Sum = AXORB XORCarryInCarryInABSum计算机科学技术系计算机系统结构教研室4位ALU1位ALU4位ALUCarryIn0CarryInA0B0Result0ACarryOut0CarryIn1A1B1Result1结果CarryOut1CarryIn2A2B2Result2CarryOut2CarryIn3A3B3BResult3CarryOutCarryOut3计算机科学技术系计算机系统结构教研室多路选择器1-bit ALU1-bit全加器1-bit ALU1-bit ALU1-bit ALU任务: 为MIPS ISA设计一个快速ALU°需求分

15、析?°必须支持算术/逻辑操作°基于出现频率和硬件预算 在成本和速度之间进行权衡计算机科学技术系计算机系统结构教研室MIPS ALU的需求°Add,AddU,Sub,SubU, AddI, AddIu=> 具有溢出检测功能的补码加法器/减法器°And,Or, AndI, OrI, Xor, Xori, Nor=> 逻辑与(Logical AND)、逻辑或(logical OR)、异或(XOR)、或非(nor)°SLTI, SLTIU (set less than)=> 带反向器的补码加法器, 可检查结果的符号位计算机科学技术系计

16、算机系统结构教研室MIPS31算术指令的格式25201550R-type:I-Type:°带符号的算术运算产生溢出，而不是进位计算机科学技术系计算机系统结构教研室Typeopfunct00500051SLT0052SLTU0053Typeopfunct ADD0040ADDU 0041SUB0042SUBU 0043AND0044OR0045XOR0046NOR0047Typeopfunct ADDI10xxADDIU11xxSLTI12xxSLTIU13xxANDI14xxORI15xxXORI16xxLUI17xxopRsRtImmed 16opRsRtRdfunct设计诀窍1:

17、分治(divide&conquer)° 将整个问题分解为较简单的小问题，在各个击破后，综合起来得到整个问题的解决方案。° 例如：假设在设计我们的ALU之前，已经妥善处理了立即数问题 10 个操作类型 (4 位)计算机科学技术系计算机系统结构教研室00 add01 addU02 sub03 subU04 and05 or06 xor07 nor12 slt13 sltU逐步求精后的需求情况(1) 功能描述输入:输出:操作:2 x 32位操作数 A, B, 4位模式选择(mode)32位结果S, 1位进位, 1位溢出add, addu, sub, subu, and,

18、or, xor, nor, slt, sltU(2) 框图(Block Diagram)(powerview symbol, VHDL entity)3232AB4ALUS32c ovfm计算机科学技术系计算机系统结构教研室行为表现:VHDLEntityALU isgeneric (c_delay:integer:=20ns;S_delay: integer := 20 ns);port(signal signal signal signal signalA,B:m:S:in in out out outvlbit_vector vlbit_vector vlbit_vector vlbit;

19、 vlbit)(0(0(0to to to31);3);31);c: ovf:. . .ALU;endS<=A +B;计算机科学技术系计算机系统结构教研室VHSIC: Very High Speed Integrated CircuitVHDL: VHSIC Hardware Description Language设计抉择ALUbit slice7-to-2 C/L7 3-to-2 C/LPLDmux°简片(bit-slice)C/L:组合逻辑 大规模组合逻辑的问题 许多小规模组合逻辑的问题 划分成2-step的问题°具有先行进位的位片处理计算. 机.科学技术系计算

20、机系统结构教研室GatesCL6CL0细化的框图:位片ALU32AB324M32S计算机科学技术系计算机系统结构教研室Ovflwa31b31 ALU31mcocin s31a0b0ALU0mcocin s07-to-2组合逻辑°设计起步 . . .0127计算机科学技术系计算机系统结构教研室FunctionInputsOutputsK-MapM0M1M2M3ABCinS Coutadd0000000007个输入 + 一个MUX ?° 设计诀窍2: 从你知道的 (或 可以)局部方案开始设计,并努力将它们整合起来° 设计诀窍3: 先解决部分问题, 再逐步扩充S-sel

21、ectCarryInandAorResultaddBCarryOut计算机科学技术系计算机系统结构教研室Mux1-bit Full Adder其他操作°A - B = A + (-B) 通过 取反 再 加 1 获得负数的补码S-selectinvertCarryInandAorResultaddBCarryOutSet-less-than? 课后思考计算机科学技术系计算机系统结构教研室Mux1-bit Full Adder减法°记住: (A - B) 可以看作: A + (-B) 补码: 每位取反，末位加一°对B每位取反，即 !B: A + !B + 1 = A

22、+ (!B + 1) = A + (-B) = A - B减法CarryInA4零结果4B444!BCarryOut计算机科学技术系计算机系统结构教研室ALU2x1 MuxSel 01进一步细化的框图°LSB 和 MSB 需要进行特殊处理32AB324MC/L to produce select, comp,c-inOvflw32S计算机科学技术系计算机系统结构教研室?a31b31 ALU0cocin s31a0b0 ALU0cocin s0溢出二进制00000001001000110100010101100111十进制0-1-2-3-4-5-6-7-8十进制01234567补码00

23、0011111110110111001011101010011000°示例: 7+3 =10但是 .- 4-5 =- 9.但是01001101111117311100101- 4 - 5 +1010- 6 01117计算机科学技术系计算机系统结构教研室溢出检测°溢出: 结果超出了正常的表示范围（太大 和 太小） 例如: - 8 < = 4位二进制数 <= 7°当对具有不同符号的操作数进行加法运算时，出现溢出！°当进行下列加法时，出现溢出: 两个正数相加，结果为负 两个负数相加，结果为正°溢出可以用如下方法检测: 输入到最大位的进位

24、!= 从最大位输出的进位（Carry into MSB ! =Carryoutof MSB）11111100- 4 - 5 0173 +1011 +0011 011171010-6计算机科学技术系计算机系统结构教研室0110溢出检测逻辑输入到最大位的进位 != 从最大位输出的进位对于N位ALU: 溢出 = CarryInN - 1XORCarryOutN - 1CarryIn0A0B0Result0CarryOut0CarryIn1A1B1Result1CarryOut1CarryIn2A2B2Result2CarryIn3 OverflowA3B3Result3CarryOut3计算机科学技

25、术系计算机系统结构教研室1-bit ALU1-bit ALU1-bit ALU1-bit ALUXYXXORY000011101110更加细化的框图°LSB 和 MSB 需要进行特殊处理32AB32signeand ci4MC/L to produce select, comp,c-inOvflw32S计算机科学技术系计算机系统结构教研室d-arithn xor coa31b31 ALU0co s31cina0b0 ALU0co s0 cin行波进位的缺点°行波进位加法器（Ripple Carry Adder） 加位将从最小位(LSB)到最大位(MSB) N位加法器在最坏情

26、况下的延迟: 2N个门延迟CarryIn0A0B0Result0CarryOut0CarryIn1CarryInA1B1Result1ACarryOut1CarryIn2A2B2Result2CarryOut2CarryIn3BCarryOutA3B3Result3CarryOut3计算机科学技术系计算机系统结构教研室1-bit ALU1-bit ALU1-bit ALU1-bit ALU但是，性能如何呢?° n位行波进位加法器的关键路径为 n´CPCarryIn0A0B0Result0CarryOut0CarryIn1A1B1Result1CarryOut1CarryIn

27、2A2B2Result2CarryOut2CarryIn3A3B3Result3CarryOut3设计技巧: 减少关键路径上的硬件延迟计算机科学技术系计算机系统结构教研室1-bit ALU1-bit ALU1-bit ALU1-bit ALUCarry Propagation进位选择（Carry°设计一个 8位 ALUSelectHeader） 简单方案: 将两个4位ALU串联A3:0CarryIn4Result3:04B3:04A7:44Result7:44B7:44CarryOut计算机科学技术系计算机系统结构教研室ALUALU进位选择（续）°设计一个 8位 ALU 快

28、速、昂贵: 使用3个 4位 ALUA3:04CarryInResult3:040B3:04A7:44C4X7:441B7:44A7:44Result7:44C0Y7:44B7:44C1C4CarryOut计算机科学技术系计算机系统结构教研室ALU2 - 1多路选择器ALUALU02 到 1多路选择器1SelSel01先行进位（CarryLookahead）的理论基础B1A1B0A0Cin2Cin0°回忆: CarryOut = Cin2 = Cout1 Cin1 = Cout0(B & CarryIn)= (B1 & Cin1)= (B0 & Cin0)|(A

29、 & CarryIn)| (A & B)(A1 & B1)(A1 & Cin1)(A0 & Cin0)| (A0 & B0)°将Cin1 代入 Cin2: Cin2 = (A1 & A0 & B0) | (A1 & A0 & Cin0) |(A1 & B0 & Cin0)|(B1 & A0 & B0) | (B1 & A0 & Cin0) | (B1 & A0 & Cin0) | (A1 & B1) Cin2 NOT depend o

30、f Cout0 定义两个新术语:第i位产生的进位通过第i位的gi pi=Ai Ai& Bi or Bi进位(Propagate Carry)计算机科学技术系计算机系统结构教研室Cout0Cin1Cout11-bit ALU1-bit ALU先行进位的理论基础（续）°使用新定义的两个术语:第i位产生的进位通过第i位的gi = Ai & Bipi = Aior BiWe can rewrite:进位Cin1 Cin2Cin3=g0 g1g2|(p0 & Cin0)(p1 & g0) | (p1 & p0 & Cin0) (p2 &

31、g1) | (p2 & p1 & g0) |(p2 & p1 & p0 & Cin0)°进入第3位的进位是1， 如果在第2位，产生了进位 (g2)在第1位产生了进位 (g1)并且或者第2位了这个进位 (p2 & g1)在第0位产生了进位 (g0)并且或者第1位和第2位都了这个进位 (p2 & p1 & g0)在第0位有输入进位(Cin0) 并且或者第0位、第1位和第2位都了这个进位 (p2 & p1 & p0 & Cin0)计算机科学技术系计算机系统结构教研室局部先行进位加法器（Partial C

32、arry Lookahead Adder）°实现进位加法器的成本太高 想象 Cin31的逻辑方程的长度°一般性经验:连接一些N位先行进位加法器，形成一个大加法器例如: 连接4个8位进位先行加法器，形成1个 32位局部先行进位加法器A31:24B31:24A23:168B23:168A15:88B15:88A7:08B7:0888C24C16C8C08888Result31:24计算机科学技术系Result23:16Result15:8Result7:0计算机系统结构教研室8位 先行进位加法器8位 先行进位加法器8位 先行进位加法器8位 先行进位加法器先行进位CarryLoo

33、kAhead(设计技巧:窥探)CinA0B0· P0ABP = A and B G = A xor BG0 · P1 + C0 · P0 · P1AB· P2 + G0 · P1 · P2 + C0 · P0 · P1 · P2ABGPC4 = . . .计算机科学技术系计算机系统结构教研室SC1 =G0 + C0C2 = G1 +C3 = G2 + G1SG PSG PSG PG PABC-out000Fill0 1C-inPropagate1 0C-inPropagate111Generat

34、e道管：先行进位的类比c0g0p0c1c0g0p0c0g1g0p1p0c2g1p1g2p2g3p3c4计算机科学技术系计算机系统结构教研室层叠式先行进位 (16位):抽象C L AC0G0P0C1 =G0 + C0 · P04-bit AdderC2 = G1 + G0 · P1 + C0 · P0 · P14-bit AdderC3 = G2 + G1 · P2 + G0 · P1 · P2 + C0 · P0 · P1 · P2GP4-bit AdderC4 = . . .计算机科学技术系计

35、算机系统结构教研室第进位、的管道类比g0p0p1g1p1p2p3g2p2P0g3p3G0计算机科学技术系计算机系统结构教研室设计诀窍:猜测CP(2n) = 2*CP(n)CP(2n) = CP(n) + CP(mux)01Carry-select adderAssumes: mux is faster than adder计算机系统结构教研室Cout计算机科学技术系n-bit addern-bit addern-bit addern-bit addern-bit adder进位跳跃加法器（CarrySkipAdder）:减少最坏情况的延迟B A4B A04-bit Ripple Adder4-bit Ripple AdderP3SP3SP2