集成電路計算機輔助設(shè)計與驗證算法、實踐總復(fù)習(xí)

1、Verilog總復(fù)習(xí)Verilog設(shè)計部分：一、概念部分1）代碼修改1.端口列表不完整，或者含中間變量2.端口申明不完整（Testbench中無需端口申明）3.變量類型定義錯誤，位寬錯誤，中間變量最好要設(shè)置為寄存器型4.assign只能給線網(wǎng)型變量賦值，只為組合邏輯建模，只包含簡單延時#5.過程賦值語句塊initial、always中被賦值的變量只能是寄存器型6.initial、always這些過程語句中如果包含兩條及兩條以上的語句時，需要用begin end或fork join來封裝7.同一always中阻塞賦值=與非阻塞賦值<=同時存在8.always塊信號敏感列表不完整，會引入不必

2、要的Latch9.if語句結(jié)構(gòu)不完整，且信號未賦初值，組合邏輯描述中if后缺少else時，會產(chǎn)生不必要的Latch10.case語句不完整，分支不完整沒加default，或分支語句中的賦值不完整，且信號未賦初值，都會產(chǎn)生不必要的Latch11.case后的控制表達(dá)式可能與標(biāo)號不符12.case語句后接了兩條或兩條以上的default13.case某一標(biāo)記要執(zhí)行兩條或兩條以上的語句，必須封裝在begin end或fork join14.拼接和復(fù)制時，沒有指定位寬 15.if、if else、if else嵌套只能出現(xiàn)在過程語句塊always、initial或定義函數(shù)function或任務(wù)task

3、中16.位操作符與歸約操作符、邏輯操作符混淆17.標(biāo)點符號出錯 2）語法概念 1.什麼情況下會輸出x值：輸出net上發(fā)生驅(qū)動突變；或一個未知值傳到了net 2.Net與Reg類型的主要區(qū)別：線網(wǎng)型變量類似于導(dǎo)線，不能存儲值，必須受到驅(qū)動源持續(xù)驅(qū)動才有效；寄存器型變量具有記憶功能，在輸入信號消失時他能保持原有值不變，不需要驅(qū)動源 3.Verilog中如何定義一個常數(shù)：使用parameter定義參數(shù)型變量；使用文本宏define定義 4.縮減操作符和位操作符的區(qū)別；與！的區(qū)別；=與=的區(qū)別： 縮減操作符是單目操作符，實現(xiàn)對單一操作數(shù)進(jìn)行操作，并產(chǎn)生一位結(jié)果；位操作符(除了)為雙目操作符，實現(xiàn)對兩個

4、操作數(shù)各位按位操作；位取反是按矢量每位取反；邏輯非！是將操作數(shù)歸約為一位true或false結(jié)果；邏輯等=比較時，操作數(shù)某位不確定時，其結(jié)果也不確定；全等=是比較兩個操作數(shù)是否完全相等，對x和z都要進(jìn)行比較，完全一致時才是1，沒有不定狀態(tài) 5.拼接與復(fù)制操作符在拼接與賦值一個數(shù)據(jù)時，對數(shù)據(jù)有什么要求： 必須指定數(shù)據(jù)位寬，否則會發(fā)生錯誤 6.連續(xù)賦值語句assign通常給組合邏輯建模 7. beginend塊內(nèi)使用非阻塞賦值與forkjoin塊的區(qū)別： 前者可綜合，語句按順序執(zhí)行(但都是按同一起始時刻開始)；后者不可綜合，語句并行執(zhí)行 8. Verilog中posedge、negedge的含義：

5、前者指敏感信號上升沿；后者指下降沿 9. Verilog中有哪些條件結(jié)構(gòu)：if、ifelse、ifelse嵌套、case casex casez、? : 條件語句與分支語句比較：條件語句帶優(yōu)先級，二選一，更具一般性；分支語句可選擇帶與不帶優(yōu)先級，多選一，其分支表達(dá)式要求與控制表達(dá)式形式相同 10. Verilog中什么結(jié)構(gòu)能產(chǎn)生一個新范圍，那些結(jié)構(gòu)能被禁止： 模塊、任務(wù)、函數(shù)、有名塊能產(chǎn)生一個新范圍，其中有名塊和任務(wù)可被禁止 11.如何向存儲器加載數(shù)據(jù)：通過將其申明為2維寄存器陣列；通過使用系統(tǒng)任務(wù)$readmen或$readmenb或使用過程語句賦值 3）綜合概念 1.什麼是綜合：檢查RTL

6、代碼質(zhì)量的重要手段；RTL語言到門級網(wǎng)表的過程；前端與后端的交叉點；翻譯+優(yōu)化+映射 2.定義時鐘：dc_shell-t> creat_clock period 2 get_ports clk（2ns時鐘周期） dc_shell-t> set_dont_touch_network get_clocks clk （阻止優(yōu)化時鐘） 3.模塊內(nèi)部，寄存器到寄存器的路徑約束： 4.輸入路徑延時：dc_shell-t> set_input_delay max 0.5 clock clk get_ports A（輸入路徑延時即輸入端口的外部邏輯用了0.5ns） 5.輸出路徑延時：dc_s

7、hell-t> set_output_delay max 0.6 clock clk get_ports A（輸出路徑延時即輸出端口的內(nèi)部邏輯需要用0.5ns） 6.時鐘周期： 7.保持時間： 8.綜合工具四大庫：綜合庫synthetic、鏈接庫link、符號庫symbol、目標(biāo)庫target二、代碼優(yōu)化（組合邏輯電路） 1）模塊復(fù)用 引用模塊名 當(dāng)前模塊名 (.引用模塊引腳(當(dāng)前模塊引腳), .clk(clk), .reset(reset); 節(jié)約面積，減少功耗，但犧牲了速度2）香濃擴(kuò)展 該方法是增加一個多路選擇器，以縮短某個優(yōu)先級高但路徑長的信號路徑延時，提高關(guān)鍵路徑的工作頻率，但會

8、犧牲面積數(shù)據(jù)信號晚到處理將晚到數(shù)據(jù)信號移至靠近輸出，新的控制信號邏輯的一般形式為：control=被移動信號的控制信號 & ( (比被移動信號優(yōu)先級高的控制信號 相或)控制信號晚到處理 將晚到控制信號移至靠近輸出，新的控制信號邏輯的一般形式為：control=被移動信號的控制信號 & ( (比被移動信號優(yōu)先級高的控制信號 相或) 3）流水線時序 關(guān)鍵是均勻劃分邏輯，保證信號同步，確保功能正確三、模塊設(shè)計熟練RTL級描述與門級描述之間的轉(zhuǎn)換；熟知RTL級描述中各種條件語句的轉(zhuǎn)換1）組合邏輯電路：多路器設(shè)計四選一多路選擇器1.門級描述 module mux4_1(A, B, C,

9、D, sel, out); input A, B, C, D; input 1:0 sel; output out; wire sa, sb, sc, sd; wire ns0, ns1, sab, scd; wire out1, out2, out; not (ns0, sel 0); and (sa, a, ns0 ); and (sb, b, sel 0);or (out1, sa, sb); and (sc, c, ns0); and (sd, d, sel 0); or (out2, sc, sd);not (ns1, sel 1); and (sab, out1, ns1); an

10、d (scd, out2, sel 1); or (out, sab, scd); endmodule2.RTL級描述：條件操作符module mux4_1 (A, B, C, D, sel, out);input A, B, C, D;input 1:0 sel;output out;assign out = (sel1 = 0) ? (sel0 = 0) ? A : B) : (sel0 = 0) ? C : D);endmodule3.RTL級描述：ifelse嵌套 (一般不采用單if結(jié)構(gòu)，因為會產(chǎn)生Latch)module mux4_1 (A, B, C, D, sel, out);i

11、nput A, B, C, D;input 1:0 sel;output out;reg out;always (sel or A or B or C or D) if (sel = 2b00) out = A; else if (sel = 2b01) out = B; else if (sel = 2b10) out = C; else out = D;endmodule4.RTL級描述：case語句 (多選一結(jié)構(gòu)時建議常用)module mux4_1 (A, B, C, D, sel, out);input A, B, C, D;input 1:0 sel;output out;reg

12、out;always (sel or A or B or C or D) case(sel) 2b00 : out=A; 2b01 : out=B; 2b10 : out=C; 2b11 : out=D; default : out=A; endcase endmodule編碼器 8-3優(yōu)先級編碼器 1.casex語句module pri_8_3encoder (a, valid, y); input 7:0 a; output 2:0 y; output valid; reg 2:0 y; reg valid; always (a) begin valid = 1; casex(a) 8b1

13、xxxxxxx: y=3b111; 8b01xxxxxx: y=3b110; 8b001xxxxx: y=3b101; 8b0001xxxx: y=3b100;8b00001xxx: y=3b011; 8b000001xx: y=3b010; 8b0000001x: y=3b001; 8b00000001: y=3b000; default: y, valid = 4b0; endcase endmodule 2.for循環(huán)語句module pri_8_3encoder (a, valid, y); input 7:0 a; output 2:0 y; output valid; reg 2:

14、0 y; reg valid; integer i; always (a) begin valid = 0; y = 3b0; for (i=0; i<8; i=i+1) if (ai) begin valid = 1; y=i; end end endmodule譯碼器 3-8譯碼器索引法描述 module decoder _3_8(in, out); parameter N=8, log2N=3; input log2N-1:0 in; output N-1:0 out; reg N-1:0; always (in) begin out= 0 ; out in = 1; end en

15、dmoduleALU單元（略）2）時序邏輯電路：串行移位器 8位帶加載、復(fù)位、和左右移位功能的串入并出移位寄存器 module shift_reg (data, clk, load, rst, left_right, s_in, q); input 7:0 data; input clk, rst, load, left_right, s_in; output 7:0 q; reg 7:0 q; always (posedge clk) if (!rst) q<=8b0; else if (load) q<=data; else if (left_right) q<=q6:0

16、, s_in; else q<=s_in, q7:1; endmodule計數(shù)器 加法計數(shù)器，每10個時鐘有效沿輸出一個脈沖 module sync_counter_10(clk, c); input clk; output c; reg c; reg 3:0 counter; always (posedge clk) begin if (counter=9) begin counter<=0; c<=1; end else if (counter<9) begin counter<=counter+1; c<=0; endendendmodule分頻器 3

17、分頻器，占空比為50% module clk_3div (clk,reset,clk_out); input clk, reset; output clk_out; parameter A=2b00, B=2b01, C=2b11; reg 1:0 state; reg clk1; always (posedge clk or negedge reset); if (!reset) state<=2b00; else case (state) A: state<=B; B: state<=C; C: state<=A; default: state<=A; end

18、case always (negedge clk or negedge reset) if (!reset) clk1<=0; else clk1<=state0; assign clk_out = state0 & clk1;endmoduleLFSR線性反饋移位寄存器 LFSR：它是一種特殊的時序移位寄存器，能利用組合反饋邏輯生成相應(yīng)的偽隨機二進(jìn)制數(shù)列（2n-1個偽隨機數(shù)），按反饋回路的不同分為內(nèi)異或結(jié)構(gòu)（一對多）和外異或結(jié)構(gòu)（多對一），應(yīng)用于計數(shù)器、偽隨機數(shù)產(chǎn)生器、數(shù)據(jù)壓縮、數(shù)據(jù)加解密、數(shù)據(jù)完整性檢查等 如何構(gòu)造LFSR：1.位數(shù)n：決定了觸發(fā)器的個數(shù)n，也確定了偽隨

19、機數(shù)序列長度2n-1；2.特征向量（hn-1, hn-2, h1, h0）：決定了特征值Taps（hi=1表示觸發(fā)器Di的輸出與Dn-1的輸出進(jìn)行異或(也可取同或)，再將其反饋給Di+1，hi=0表示觸發(fā)器Di直接輸出給Di+1）；3.反饋邏輯：異或與同或兩種，異或時LFSR值不能為全0，同或時不能為全1，避免進(jìn)入死循環(huán)LFSR特征向量表位數(shù)循環(huán)長度反饋節(jié)點特征向量4153, 010015314, 1100106635, 010000171276, 0100000182557, 3, 2, 1100011101010239, 2100000010013819112, 3, 2, 0100000

20、000110116216-115, 4, 2, 11000000000010110 13時鐘分頻器，每隔13個時鐘周期輸出一個脈沖 module CNT_LFSR_DIV13 (clk, reset, Y); input clk, reset; output Y; reg Y; integer i; parameter Taps = 4b1001, StartCount = 4b1111, EndCount = 4b1010; reg 3:0 Count; always (posedge clk or negedge reset) begin if (!reset) begin Y<=0

21、; Count<=StartCount; end else if (Count=EndCount) begin Count<=StartCount; Y<=1; end else begin for (i=0; i<=2; i=i+1) if (Tapsi) Counti+1<=Counti Count3; else Counti+1<=Counti; Count0<=Count3; Y<=0; end end endmoduleFSM有限狀態(tài)機1.Moore狀態(tài)機(略) 二段式定義：采用同步時序描述當(dāng)前狀態(tài)遷移邏輯；采用組合邏輯描述狀態(tài)轉(zhuǎn)移規(guī)律

22、，二段比一段要短，代碼比一段清晰，利于維護(hù)和修改，其形式如下： always (posedge clk or negedge reset) /第一段 if (!reset) CS <= Initial_State; else CS <=NS; always (CS or IN) /第二段 begin case (CS) ST0: . ST1: . . default: . endcase end2.序列檢測器（二段式）檢測序列為10010，x輸入，z輸出（高電平有效）（1）狀態(tài)圖idleABCDE0/00/10/00/00/01/01/01/00/01/01/01/0（2）veri

23、log模塊module FSM(clock, reset, x, z);input clock, reset, x;output z;reg z;reg 4:0 NS, CS;parameter idle=5b00000, A=5b00001, B=5b00010, C=5b00100, D=5b01000, E=5b10000;always (posedge clock or negedge reset)if(!reset) CS<=idle; else CS<=NS;always (CS or x) begin NS<=idle; z<=0; case (CS) i

24、dle: if (x) beginNS<=A;z<=0; end else begin NS<=idle; z<=0; endA: if (x) beginNS<=B;z<=0;end else begin NS<=A; z<=0; endB: if (x) beginNS<=C;z<=0;end else begin NS<=A; z<=0; endC: if (x) beginNS<=D;z<=0;end else begin NS<=idle; z<=0; endD: if (x) begin

25、NS<=E;z<=1; end else begin NS<=A; z<=0; endE: if (x) beginNS<=C;z<=0;end else begin NS<=A; z<=0; end default: begin NS<=idle; z<=0; end endcase endendmodule （3）Testbench模塊module FSM_test( );reg clock, reset;reg x;parameter N=20, IN=20b11001001000010010100;reg N-1:0 data

26、;integer iinitialbeginclock=0; reset=1; #2 reset=0; #10 reset=1; data=IN; x=data0endalways #10 clock=clock;always (posedge clock); begin for(i=0; i<=N-2; i=i+1) x=dataiendFSM FSM_INST (.clock(clock), .reset(reset), .x(x);endmodule Verilog驗證與算法部分：一、選擇、填空、簡答：1） 哪些語言是專門用于驗證的高級語言：SystemVerilog、e語言、Ve

27、ra、PSL、System C2) 用于低功耗設(shè)計驗證的描述規(guī)范是：CPF, UPF3） 驗證分類：功能驗證（確保集成電路功能的正確性）、時序驗證（確保芯片達(dá)到性能指標(biāo)）、物理驗證（包含LVS、ERC、DRC、信號完整性驗證等）4） 斷言的優(yōu)點：提高錯誤的可觀察性和提高代碼可調(diào)試性；斷言成分：信號存儲、激活條件、斷言、行動；斷言工具包括：OVL、SMV、PSL、SVA、Oin Checkware5） 屬于低功耗設(shè)計驗證規(guī)范中描述的內(nèi)容：DVFS、狀態(tài)保持器件使用規(guī)則6） 驗證與測試的區(qū)別：驗證是確保設(shè)計滿足功能目標(biāo)，發(fā)現(xiàn)在制造前的設(shè)計錯誤；測試是確保制造過程的正確性，確定是否存在制造故障7）

28、測試方法：全掃描Full Scan、邊界掃描Boundary Scan、內(nèi)建自測試BIST；驗證方法：模擬驗證（包含事件驅(qū)動模擬slowest、基于周期模擬、硬件仿真fastest（FPGA原型驗證、硬件加速器、仿真器）等方法）、形式化驗證（包括模型檢驗（三步走：系統(tǒng)建模、規(guī)范描述、驗證）、等價性檢驗（分為組合等價性與時序等價性）、定理證明、屬性檢查等方法）8） 模擬驗證與形式化驗證的區(qū)別：模擬驗證方法是通過加載輸入激勵動態(tài)驗證設(shè)計描述的正確性，是目前主流方法，適合范圍廣，工具成熟，缺點是運行時間長，需要大量的測試模擬向量，而且不能保證驗證的完整性；形式化驗證方法是使用數(shù)學(xué)方法形式化地證明設(shè)計

29、是否滿足描述的要求，不需要測試向量，能夠進(jìn)行完備的驗證，可靠，將系統(tǒng)和屬性分類分隔，驗證時間短，缺點是其驗證規(guī)模有限，而且在過程中容易引入人為錯誤9） 基于周期模擬方法與基于事件模擬方法的區(qū)別：兩者都是模擬驗證工具的實現(xiàn)方法，事件模擬更通用，能夠模擬電路內(nèi)部細(xì)節(jié)，缺點是運行速度慢，依賴內(nèi)部時間與事件輪轉(zhuǎn)調(diào)度機制；周期模擬運行速度較快，但不能模擬異步邏輯，沒有時序信息10）各種驗證方法中比較：事件驅(qū)動模擬、模型驗證、靜態(tài)時序分析既能驗證功能，又能驗證時序；基于周期模擬、等價性檢查、只能驗證功能，不能驗證時序；事件驅(qū)動模擬速度最慢；等價性檢查、模型驗證、靜態(tài)時許分析不需要模擬激勵，其余的都是模擬驗

30、證方法需要施加測試激勵向量；事件驅(qū)動模擬、基于周期模擬只能用于門極設(shè)計，不能用于RTL級設(shè)計11）等價性檢查的中間表達(dá)式包括：布爾函數(shù)（真值表、布爾表達(dá)式、卡諾圖、決策圖（BDDOBDDROBDD占空間最小）12）硬件仿真加速器的驗證工具包括：Palladium、EVE zebu、Veloce13）模擬器三個部件組成：編譯前端、編譯后端、模擬引擎/控制14）屬于System Verilog 在Verilog 之上增加的數(shù)據(jù)類型包括：enum, logic15）根據(jù)對內(nèi)部信號進(jìn)行直接控制和觀測的不同，與驗證工程師對設(shè)計的理解和介入劃分驗證方法：黑盒驗證、白盒驗證、灰盒驗證16）在模擬驗證中，如何

31、判斷驗證已經(jīng)完成（提交sign-off或tape-out）：覆蓋率數(shù)據(jù)要滿足質(zhì)量要求，結(jié)構(gòu)與功能覆蓋率接近100%，錯誤產(chǎn)生的概率與速度呈現(xiàn)下降趨勢，沒有尚未解決的設(shè)計錯誤，驗證與設(shè)計通過評審，完成無錯誤的回歸驗證17）模擬驗證環(huán)境四要素：待驗證設(shè)計代碼DUT、驗證測試環(huán)境代碼Testbench、設(shè)計激勵與參考輸出、結(jié)果比較機制18）劃分過程：系統(tǒng)級劃分（系統(tǒng)PCB板）、板級劃分（PCB板芯片）、芯片級劃分（芯片子電路）19）劃分、布圖規(guī)劃與布局的區(qū)別：將復(fù)雜的系統(tǒng)分解成若干個子系統(tǒng)的過程就是劃分，其目標(biāo)是確保功能一致性、模塊獨立性、劃分有效性；為了確定每個模塊的形狀，并根據(jù)互連情況確定各模塊

32、之間的相對位置該階段叫布圖規(guī)劃，輸入包括由劃分產(chǎn)生的模塊、每個面積、可能形狀、管腳數(shù)及網(wǎng)表；在布圖規(guī)劃基礎(chǔ)上，確定每個模塊及其管腳的具體位置叫布局，要求在面積最小的情況下，無覆蓋地分配完各個模塊，并留布線空間20）布線過程：全局布線（區(qū)域定義、區(qū)域分配、引腳分配三階段）、詳細(xì)布線（通道布線、二維開關(guān)盒布線、三維布線）、特殊布線（時鐘布線、電源地布線）二、分析論述題：1）為IEEE-754標(biāo)準(zhǔn)雙精度浮點加法器設(shè)計撰寫驗證計劃：（指出基本功能點，先進(jìn)功能點，Corner功能點，指出可使用的驗證方法） 答：1.基本功能點驗證：（采用定向模擬） 32b模式下，兩個32位浮點加法器的每一個端口的操作數(shù)正

33、確性；64b模式下，64位浮點運算加操作正確性；SIMD模式下，兩個32位浮點加法器并行運算操作正確性。 2.先進(jìn)功能點驗證：（初期采用定向模擬，后期采用隨機模擬） 測試32b模式下，每個浮點加法器流水化運行操作正確性；三種模式混合運行時操作正確性 3.Corner功能驗證：（采用定向模擬和斷言） 32b、64b模式下，加法和減法的溢出；特殊數(shù)據(jù)的加法和減法0+0，0-0，獲得結(jié)果數(shù)OxFFFFFFFF；在Reset信號有效期間，打入數(shù)據(jù)和操作進(jìn)行驗證；在運算過程中，打入Reset信號進(jìn)行驗證。2）以4位加法器驗證環(huán)境為例，簡述VLSI模擬驗證環(huán)境的主要構(gòu)成要素及實現(xiàn)方法；簡述類似OpenSP

34、ARC針對CPU設(shè)計的復(fù)雜驗證環(huán)境的構(gòu)成要素及實現(xiàn)方法；對比兩種驗證環(huán)境 答： 1.簡單驗證環(huán)境：單文件Verilog4位加法器(adder4b)其DUT為4位加法器，通過Verilog實例化1位或4位加法器或者底層編碼來實現(xiàn)；Testbench是整個Verilog代碼(t_adder4b)；設(shè)置激勵通過initial語句塊對stim進(jìn)行延遲賦值實現(xiàn)；參考輸出是預(yù)先計算的結(jié)果；結(jié)果對比是通過波形或者$monitor語句的輸出與預(yù)先計算結(jié)果進(jìn)行人工對比 2.復(fù)雜驗證環(huán)境：OpenSPARC的整個DUT位于代碼的design/iop目錄下；tastbench是在Verif/env目錄下；測試激勵是

35、預(yù)先寫好的匯編代碼；參考輸出內(nèi)嵌在匯編激勵中，也可以用協(xié)同模擬Co-sim體系結(jié)構(gòu)模擬器做參考輸出；內(nèi)嵌匯編的比較機制是通過匯編代碼自動比較，而協(xié)同模擬的比較機制是通過鎖步執(zhí)行，對結(jié)構(gòu)狀態(tài)變化進(jìn)行比較 3.兩種環(huán)境對比：簡單驗證環(huán)境易于書寫，能夠快速獲得測試結(jié)果并進(jìn)行對比，在小型設(shè)計驗證和驗證初期常用，不適用于大型設(shè)計和可控制的驗證進(jìn)度；復(fù)雜驗證環(huán)境構(gòu)成要素眾多，需要大量資源，但適合于復(fù)雜設(shè)計，并可以通過覆蓋率等方法控制并判斷驗證進(jìn)度。三、算法大題：1）劃分：KL算法 ， 屬于迭代算法，初始劃分得對稱，每次成對的交換節(jié)點，并計算每次交換的代價與增益，選取最大增益的交換對進(jìn)行交換，每次交換后的已

36、交換對互鎖，不再進(jìn)入下一輪計算，前一次迭代的結(jié)果為下一次迭代計算的初始值，當(dāng)在新的過程中切口大小不再降低，算法將停止該算法有較好的魯棒性，但缺點是由于計算中增益不再增加或為負(fù)時，就停止了算法，所以很容易掉入局部最優(yōu)解的陷阱，不適合超圖，不能處理有權(quán)重的圖形，且分區(qū)大小在劃分前需指定，復(fù)雜度較高，較慢FM算法，屬于迭代算法，初始劃分可不對稱，但要滿足平衡約束，每一次只移動一個節(jié)點，移動后鎖住該點該算法優(yōu)點是他能夠帶權(quán)重劃分，可以處理非平衡劃分，復(fù)雜度比KL要低，較快，但缺點是由于計算中增益不再增加或為負(fù)時，就停止了算法，所以很容易掉入局部最優(yōu)解的陷阱退火算法該算法屬于概率迭代算法，算法隨機選擇某

37、一種劃分作為起始狀態(tài)，然后從該劃分的不同分區(qū)中選擇元件進(jìn)行交換，從而產(chǎn)生新的劃分，并計算出增益s，如果s<0，則接受此次交換，如果s>0，就以的概率接受此次交換這種以概率接受惡化解的能力可以使算法跳出局部最優(yōu)解的陷阱，從而尋找全局最優(yōu)解，且具有并行性Algorithm: Simulated_Annealing begin get an initial solution S; get an initial temperature T >0; while not yet “frozen” do for 1iP do pick a random neighbor S of S; c

38、ost(S) cost(S); if 0 then S S; else then S S with probability ; T rT; return Send遺傳算法該算法屬于概率迭代算法，它是以某些初始布局為基礎(chǔ)，這些初始布局可以隨機產(chǎn)生，我們稱之為種群，這個種群中的個體表現(xiàn)為能實現(xiàn)的某種布局，用一個符號串表示，我們稱之為染色體，這些串中的符號我們稱之為基因，遺傳算法是迭代進(jìn)行的，每次迭代生成一代，在每次迭代期間，種群中新產(chǎn)生的個體會被賦予一定的適應(yīng)度值，在中群眾的兩個個體可以被新選擇成為父母，且其適應(yīng)度越高，越可能被選中，然后通過交叉、變異、反轉(zhuǎn)等操作，將父代基因融合并傳給子代，然后子代作為新一代，就其在種群中的適應(yīng)性被評估，高適應(yīng)性個體被選擇，低適應(yīng)性的被淘汰，中群大小保持不變因為一些壞的基因仍有小概率被遺傳下來，從而避免了算法陷入局部最優(yōu)解中2）布圖規(guī)劃：基于約束Slicing算法a, b兩模塊形狀都為，a固定，b可旋轉(zhuǎn)a模塊： b模塊：橫切：豎切：3）布局： 退火算法模擬退火算法四要素：解空間、鄰解表示方法、評價方法、退火模式該類算法特點：是通過定義代價函數(shù)對每個解的可行性和優(yōu)劣進(jìn)行計算，在定義一組移動操作來對組間元件