計算機組織與系統(tǒng)結(jié)構(gòu)北大本科07設(shè)計過程

1、計算機組織與系統(tǒng)結(jié)構(gòu)設(shè)計過程與ALU設(shè)計TheDesignProcess&ALUDesign（第七講）程旭2003.10.21計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室本講提綱°上一講復(fù)習(xí)，本講介紹°設(shè)計過程概述°復(fù)習(xí)二進制算術(shù)運算°設(shè)計一個簡單的4位ALU°其他 構(gòu)建 ALU 的技術(shù)計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室°性能和技術(shù)工藝發(fā)展趨勢 盡可能保持設(shè)計簡單充分利用最新技術(shù)工藝的優(yōu)勢 CMOS反向器和CMOS邏輯門°延遲建模和門的特征描述 延遲 = 內(nèi)在延遲 + (負(fù)載相關(guān)延遲 x 輸出負(fù)載)°時鐘同步方法

2、和定時考慮 最簡單的時鐘同步方法-所有的單元使用相同的時鐘邊沿 時鐘時間 = CLK-to-Q + 最長延遲路徑 + 建立時間 + 時鐘扭斜 CLK-to-Q + 最短延遲路徑 - 時鐘扭斜 > 保持時間計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室時鐘扭斜對時鐘周期的影響Clk1Clock SkewClk2.SetupHoldSetupHoldD不關(guān)心不關(guān)心不關(guān)心不關(guān)心Clock-to-QClock-to-QQ未知SetupHoldD內(nèi)在延遲 +負(fù)載相關(guān)延遲時間不關(guān)心時鐘扭斜最小時鐘周期長度計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室時鐘扭斜對保持時間的影響Clk1Clock SkewClk2.Setu

3、pHoldSetupHoldD不關(guān)心不關(guān)心不關(guān)心不關(guān)心Clock-to-QClock-to-QQ未知HoldHoldDnew?計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室設(shè)計過程“設(shè)計即描繪（To Design Is To Represent）”設(shè)計活動 產(chǎn)生 有關(guān)一個對象的 描述/表達 傳統(tǒng)的工匠并不區(qū)分 概念化（conceptualization） 和 工藝品（artifact） 由于 復(fù)雜性 ，這兩者才開始分離 概念是用一種或多種 表示語言（representation languages) 描述的 概念化的過程就是設(shè)計設(shè)計從需求分析開始-功能需求: 性能特征:將要完成的功能速度、功率、面積、成

4、本, . . .計算機系統(tǒng)結(jié)構(gòu)教研室計算機科學(xué)技術(shù)系設(shè)計過程（續(xù)）設(shè)計以組裝結(jié)束Design Finishes As Assembly-設(shè)計 分解 組成部件，以及如何組裝部件-自頂向下 將 復(fù)雜的功能（行為）分解為多個基本功能-自底向上將多個基本 功能塊為更復(fù)雜的組裝體設(shè)計是一個 “創(chuàng)造性的過程”，而不僅僅是使用某種簡單的方法計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室RegsNandGateShifterALUControlDatapathCPU設(shè)計求精非形式化的系統(tǒng)需求分析初始規(guī)范（Specification）中間規(guī)范求精細(xì)節(jié)逐步增加最終系統(tǒng)結(jié)構(gòu)描述(description)實現(xiàn)的中間規(guī)范最終內(nèi)部

5、規(guī)范物理實現(xiàn)計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室設(shè)計如同搜尋策略 2策略 1設(shè)計包含利用所學(xué)知識進行猜測和驗證-給定目標(biāo), 如何確定這些策略的優(yōu)劣?給定可選的設(shè)計策略, 應(yīng)該選擇那種設(shè)計?給定部件和組裝體的空間, 哪一部分能夠產(chǎn)生最佳解決方案?可行(好)抉擇 vs. 最佳抉擇計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室子問題 1子問題3子問題2問題 A設(shè)計如同陳述（Representation）“VHDL行為"(1)功能描述輸入:2 x 16位操作數(shù)：A, B;1 位進位輸入：Cin.輸出:1 x 16位結(jié)果：S; 1位進位輸出：Co.操作:PASS, ADD (A + B + Cin),

6、AND, XOR, OR, COMPARESUB (A(相等)-B -Cin),性能:現(xiàn)在，還沒有詳細(xì)說明！“VHDL實體"(2)框圖理解數(shù)據(jù)和流16163模式/功能16計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室ABCoALUMSCin二進制數(shù)緒論°4位二進制數(shù)十進制0123°示例: 3 + 2 = 5二進制0000000100100011十進制4567二進制01000101011001113 + 3 = 610101101101 +0010 +001101010110計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室補碼(Twos Complement)表示°負(fù)數(shù)的補碼表

7、示 每位取反,并加 負(fù)數(shù)的最大位(1MSB)總是為1=>符號位 最大的4位二進制數(shù):7最小的4位二進制數(shù):-8十進制01234567二進制00000001001000110100010101100111十進制0-1-2-3-4-5-6-7-8每位取反111111101101110010111010100110000111補碼000011111110110111001011101010011000計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室無效的正數(shù)!81000計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)

8、教研室計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室補碼算術(shù)十進制01234567二進制00000001001000110100010101100111十進制0-1-2-3-4-5-6-7-8補碼000011111110110111001011101010011000°示例:7-6=7+(-6)=13-5=3+(- 5)=-2110111010011111100111+00011110計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室ALU的功能描述ALUop3AN零(Zero)結(jié)果(Result)N溢出(Overflow)BN輸出進位(CarryOut)°ALU 000 001 010 110

9、111線 (ALUop)功能And Or AddSubtractSet-on-less-than計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室ALU1位 ALU°該 1位 ALU將完成 AND、OR和 ADD輸入進位（CarryIn）A結(jié)果（Result）B輸出進位（CarryOut）計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室多路選擇器1-bit全加器1位全加器°又稱為 “ (3, 2) adder”CarryInACB°半加器: 沒有CarryIn 和 CarryOutCarryOut°真值表:計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室輸入輸出注釋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計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室輸入輸出注釋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)計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室輸入輸出注釋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、（續(xù)）°Sum = (!A & !B & CarryIn) | (!A & B & !CarryIn)|(A & !B & !CarryIn)|(A & B & CarryIn)°Sum = A XOR BXORCarryIn°XOR的真值表:計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室XYX XORY000011101110CarryOut和Sum的邏輯圖°CarryOut = B & CarryIn|A & CarryIn|A & BCarryInABCarryOut&#

14、176;Sum = AXORB XORCarryInCarryInABSum計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室4位ALU1位ALU4位ALUCarryIn0CarryInA0B0Result0ACarryOut0CarryIn1A1B1Result1結(jié)果CarryOut1CarryIn2A2B2Result2CarryOut2CarryIn3A3B3BResult3CarryOutCarryOut3計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室多路選擇器1-bit ALU1-bit全加器1-bit ALU1-bit ALU1-bit ALU任務(wù): 為MIPS ISA設(shè)計一個快速ALU°需求分

15、析?°必須支持算術(shù)/邏輯操作°基于出現(xiàn)頻率和硬件預(yù)算 在成本和速度之間進行權(quán)衡計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室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)=> 帶反向器的補碼加法器, 可檢查結(jié)果的符號位計算機科學(xué)技術(shù)系計

16、算機系統(tǒng)結(jié)構(gòu)教研室MIPS31算術(shù)指令的格式25201550R-type:I-Type:°帶符號的算術(shù)運算產(chǎn)生溢出，而不是進位計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室Typeopfunct00500051SLT0052SLTU0053Typeopfunct ADD0040ADDU 0041SUB0042SUBU 0043AND0044OR0045XOR0046NOR0047Typeopfunct ADDI10xxADDIU11xxSLTI12xxSLTIU13xxANDI14xxORI15xxXORI16xxLUI17xxopRsRtImmed 16opRsRtRdfunct設(shè)計訣竅1:

17、分治(divide&conquer)° 將整個問題分解為較簡單的小問題，在各個擊破后，綜合起來得到整個問題的解決方案。° 例如：假設(shè)在設(shè)計我們的ALU之前，已經(jīng)妥善處理了立即數(shù)問題 10 個操作類型 (4 位)計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室00 add01 addU02 sub03 subU04 and05 or06 xor07 nor12 slt13 sltU逐步求精后的需求情況(1) 功能描述輸入:輸出:操作:2 x 32位操作數(shù) A, B, 4位模式選擇(mode)32位結(jié)果S, 1位進位, 1位溢出add, addu, sub, subu, and,

18、or, xor, nor, slt, sltU(2) 框圖(Block Diagram)(powerview symbol, VHDL entity)3232AB4ALUS32c ovfm計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室行為表現(xiàn):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;計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室VHSIC: Very High Speed Integrated CircuitVHDL: VHSIC Hardware Description Language設(shè)計抉擇ALUbit slice7-to-2 C/L7 3-to-2 C/LPLDmux°簡片(bit-slice)C/L:組合邏輯 大規(guī)模組合邏輯的問題 許多小規(guī)模組合邏輯的問題 劃分成2-step的問題°具有先行進位的位片處理計算. 機.科學(xué)技術(shù)系計算

20、機系統(tǒng)結(jié)構(gòu)教研室GatesCL6CL0細(xì)化的框圖:位片ALU32AB324M32S計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室Ovflwa31b31 ALU31mcocin s31a0b0ALU0mcocin s07-to-2組合邏輯°設(shè)計起步 . . .0127計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室FunctionInputsOutputsK-MapM0M1M2M3ABCinS Coutadd0000000007個輸入 + 一個MUX ?° 設(shè)計訣竅2: 從你知道的 (或 可以)局部方案開始設(shè)計,并努力將它們整合起來° 設(shè)計訣竅3: 先解決部分問題, 再逐步擴充S-sel

21、ectCarryInandAorResultaddBCarryOut計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室Mux1-bit Full Adder其他操作°A - B = A + (-B) 通過 取反 再 加 1 獲得負(fù)數(shù)的補碼S-selectinvertCarryInandAorResultaddBCarryOutSet-less-than? 課后思考計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室Mux1-bit Full Adder減法°記住: (A - B) 可以看作: A + (-B) 補碼: 每位取反，末位加一°對B每位取反，即 !B: A + !B + 1 = A

22、+ (!B + 1) = A + (-B) = A - B減法CarryInA4零結(jié)果4B444!BCarryOut計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室ALU2x1 MuxSel 01進一步細(xì)化的框圖°LSB 和 MSB 需要進行特殊處理32AB324MC/L to produce select, comp,c-inOvflw32S計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室?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計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室溢出檢測°溢出: 結(jié)果超出了正常的表示范圍（太大 和 太小） 例如: - 8 < = 4位二進制數(shù) <= 7°當(dāng)對具有不同符號的操作數(shù)進行加法運算時，出現(xiàn)溢出！°當(dāng)進行下列加法時，出現(xiàn)溢出: 兩個正數(shù)相加，結(jié)果為負(fù) 兩個負(fù)數(shù)相加，結(jié)果為正°溢出可以用如下方法檢測: 輸入到最大位的進位

24、!= 從最大位輸出的進位（Carry into MSB ! =Carryoutof MSB）11111100- 4 - 5 0173 +1011 +0011 011171010-6計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室0110溢出檢測邏輯輸入到最大位的進位 != 從最大位輸出的進位對于N位ALU: 溢出 = CarryInN - 1XORCarryOutN - 1CarryIn0A0B0Result0CarryOut0CarryIn1A1B1Result1CarryOut1CarryIn2A2B2Result2CarryIn3 OverflowA3B3Result3CarryOut3計算機科學(xué)技

25、術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室1-bit ALU1-bit ALU1-bit ALU1-bit ALUXYXXORY000011101110更加細(xì)化的框圖°LSB 和 MSB 需要進行特殊處理32AB32signeand ci4MC/L to produce select, comp,c-inOvflw32S計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室d-arithn xor coa31b31 ALU0co s31cina0b0 ALU0co s0 cin行波進位的缺點°行波進位加法器（Ripple Carry Adder） 加位將從最小位(LSB)到最大位(MSB) N位加法器在最壞情

26、況下的延遲: 2N個門延遲CarryIn0A0B0Result0CarryOut0CarryIn1CarryInA1B1Result1ACarryOut1CarryIn2A2B2Result2CarryOut2CarryIn3BCarryOutA3B3Result3CarryOut3計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室1-bit ALU1-bit ALU1-bit ALU1-bit ALU但是，性能如何呢?° n位行波進位加法器的關(guān)鍵路徑為 n´CPCarryIn0A0B0Result0CarryOut0CarryIn1A1B1Result1CarryOut1CarryIn

27、2A2B2Result2CarryOut2CarryIn3A3B3Result3CarryOut3設(shè)計技巧: 減少關(guān)鍵路徑上的硬件延遲計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室1-bit ALU1-bit ALU1-bit ALU1-bit ALUCarry Propagation進位選擇（Carry°設(shè)計一個 8位 ALUSelectHeader） 簡單方案: 將兩個4位ALU串聯(lián)A3:0CarryIn4Result3:04B3:04A7:44Result7:44B7:44CarryOut計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室ALUALU進位選擇（續(xù)）°設(shè)計一個 8位 ALU 快

28、速、昂貴: 使用3個 4位 ALUA3:04CarryInResult3:040B3:04A7:44C4X7:441B7:44A7:44Result7:44C0Y7:44B7:44C1C4CarryOut計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室ALU2 - 1多路選擇器ALUALU02 到 1多路選擇器1SelSel01先行進位（CarryLookahead）的理論基礎(chǔ)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 定義兩個新術(shù)語:第i位產(chǎn)生的進位通過第i位的gi pi=Ai Ai& Bi or Bi進位(Propagate Carry)計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室Cout0Cin1Cout11-bit ALU1-bit ALU先行進位的理論基礎(chǔ)（續(xù)）°使用新定義的兩個術(shù)語:第i位產(chǎn)生的進位通過第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位，產(chǎn)生了進位 (g2)在第1位產(chǎn)生了進位 (g1)并且或者第2位了這個進位 (p2 & g1)在第0位產(chǎn)生了進位 (g0)并且或者第1位和第2位都了這個進位 (p2 & p1 & g0)在第0位有輸入進位(Cin0) 并且或者第0位、第1位和第2位都了這個進位 (p2 & p1 & p0 & Cin0)計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室局部先行進位加法器（Partial C

32、arry Lookahead Adder）°實現(xiàn)進位加法器的成本太高 想象 Cin31的邏輯方程的長度°一般性經(jīng)驗:連接一些N位先行進位加法器，形成一個大加法器例如: 連接4個8位進位先行加法器，形成1個 32位局部先行進位加法器A31:24B31:24A23:168B23:168A15:88B15:88A7:08B7:0888C24C16C8C08888Result31:24計算機科學(xué)技術(shù)系Result23:16Result15:8Result7:0計算機系統(tǒng)結(jié)構(gòu)教研室8位 先行進位加法器8位 先行進位加法器8位 先行進位加法器8位 先行進位加法器先行進位CarryLoo

33、kAhead(設(shè)計技巧:窺探)CinA0B0· P0ABP = A and B G = A xor BG0 · P1 + C0 · P0 · P1AB· P2 + G0 · P1 · P2 + C0 · P0 · P1 · P2ABGPC4 = . . .計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室SC1 =G0 + C0C2 = G1 +C3 = G2 + G1SG PSG PSG PG PABC-out000Fill0 1C-inPropagate1 0C-inPropagate111Generat

34、e道管：先行進位的類比c0g0p0c1c0g0p0c0g1g0p1p0c2g1p1g2p2g3p3c4計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室層疊式先行進位 (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 = . . .計算機科學(xué)技術(shù)系計

35、算機系統(tǒng)結(jié)構(gòu)教研室第進位、的管道類比g0p0p1g1p1p2p3g2p2P0g3p3G0計算機科學(xué)技術(shù)系計算機系統(tǒng)結(jié)構(gòu)教研室設(shè)計訣竅:猜測CP(2n) = 2*CP(n)CP(2n) = CP(n) + CP(mux)01Carry-select adderAssumes: mux is faster than adder計算機系統(tǒng)結(jié)構(gòu)教研室Cout計算機科學(xué)技術(shù)系n-bit addern-bit addern-bit addern-bit addern-bit adder進位跳躍加法器（CarrySkipAdder）:減少最壞情況的延遲B A4B A04-bit Ripple Adder4-bit Ripple AdderP3SP3SP2