Bài giảng Tổng hợp luận lý vi mạch - Chương 3: Tổng hợp mạch 2 mức

Nội dung text: Bài giảng Tổng hợp luận lý vi mạch - Chương 3: Tổng hợp mạch 2 mức

1. dce dce 2008 2008 Tốigiản đạisố Bool mạch 2 mức • Two-level Boolean minimization đượcsử dụng để tìm dạng tổng các tích (sum-of- products) cho hàm số Bool đólàtối ưu theo Chương 3: Tổng hợpmạch 2 mức một hàm chi phí cho trước. •2 bước trong quá trình tốigiảnlà: ¾ Tốigiản đạisố Bool mạch 2 mức –Sinhtập prime implicant ¾ Phương pháp Quine-McCluskey BK –Chọntậpmộttập prime implicant tốithiểu TP.HCM ¾ Luậtsuydiễn2 mức (Two-Level Tautology) ¾ Bù (complementation) ¾ Phương pháp tốigiản chính xác (Exact Minization) ¾ Phương pháp tốigiảntối ưu (Heuristic Minimization) Logic Synthesis 2 dce dce 2008 Phương pháp Quine-McCluskey 2008 Sinh Prime Implicant •Cácbướcthựchiện •Liệtkêtậpcácminterm củahàm E (biểudiễn ở dạng các số nhị phân). 0 0000 0, 8 _000 – Sinh Prime Implicant •Trộncáccặp minterm. Các cặp 5 0101 5, 7 01_1 D minterm chỉ khác nhau 1 bit để tạo 7 0111 7, 15 _111 C – Thành lậpbảng Prime Implicant thành 1 cube. 8 1000 8, 9 100_‘ •Tiếptụctrộncáccặp cube thành 9 1001 8, 10 10_0‘ – Tìm Essential Prime Implicant 10 1010 9, 11 10_1‘ một cube mớichođên khi không 11 1011 10, 11 101_‘ – Tìm Dominated Column thể trộntiếp. 14 1110 10, 14 1_10‘ – Tìm Dominating Row • Đánh đấucáccube đã đượctrộn 15 1111 11, 15 1_11‘ •Tậpcáccube không được đánh 14, 15 111_‘ –Tối ưu các Dominated Comlumn và các dấulàtập prime implicant của hàm. dominating Row. B • Trong trường hợp hàm không đầy 8, 9, 10, 11 10_ _ –Tómtắt quy trình 10, 11, 14, 15 1_1_ đủ thì các minterm sẽ bao gồm A trong cả tập ON-set và DC-set của hàm đó. Logic Synthesis 3 Logic Synthesis 4
2. dce dce 2008 Dominated Columns 2008 Dominating Rows •Chọn C và G, do đây là • Hàng i củabảng prime implicant C D E F G cặp Relatively Essential đượcgọilàdominate một hàng j 0101 X D E F G Prime Implicant C D E F G khác nếu i có x tạitấtcả những cột 0111 X X E F G •ChọnE 0101 X D E F G mà trong đój được đánh dấux 1000 C D E F X •Kếtquả f = {A, C, E, G} 0111 X X E F G •Ta cóthể lượtbỏ những cột 1010 C D E X X •Vìviệcchọnngẩu nhiên A 1000 C D E F X dominating 1110 C D X X G ban đầu nên kếtquả 1010 C D E X X •Vídụ: 1111 C X X F G không đán tin cậy. 1110 C D X X G – Hàng 0111 dominate hàng 0101 – Hàng 1010 dominate hàng 1000 C D E F G •Cầnphảithựchiệnviệc 1111 C X X F G 0101 X D E F G backtrack và bỏ A khỏi bảng, tiếptụcthựchiện 1000 C D E F X •Mộtkếtquả khác f = {B, 1110 C D X X G D, F, H} 1111 C X X F G Logic Synthesis 9 Logic Synthesis 10 dce dce 2008 Tóm tắt 2008 Luậtsuydiễn2 mức - Tautology •Cácbướcthựchiện •Hàmf làtautology nếuvàchỉ nếutập ON-set củaf –Xâydựng bảng prime implicant là tậpvũ trụ. Ký hiệuf ≅1 – Xóa những cột dominated và những hàng dominating •f(x) = 1, ∀x∈Bn ⇔ f ≅1 –Tìmhếtnhững essential prime. Đưa chúng vào tậplựa •Hàmf đượcgọilàmonotone increasing chọn (decreasing) theo biếnxi nếuviệcchuyểnxi từ 0 lên –Nếutậplựachọn các prime này lớnhơnhoặcbằng lờigiải 1 làm cho f chuyểntừ 0 lên 1 hoặcgiữ nguyên giá trị tốtnhấtthìdừng lại. (1 xuống 0 hoặcgiữ nguyên) –Chọnmột prime mộtcáchtối ưu – Thêm prime vào tậplựachọnvàquay trở lạivớibảng đã đượctốigiảntừ việcchọn prime. –Loại prime đórakhỏitậplựachọnvàquay trở lạivớibảng đã đượctốigiảnnàyđể thựchiệnlại quy trình. Logic Synthesis 11 Logic Synthesis 12
3. dce dce 2008 Tautology 2008 Tautology • Quy trình xác định tính tautology củahàmf: • Định lý: f có ma trậnnhư hình sau: ⎛ A D D ⎞ Tautology(F){ ⎜ 1 ⎟ ⎜ D A2 D ⎟ T = SPECIAL_CASE(F); M = f ⎜ ⎟ ⎜ ⎟ if(T ≅ -1) (T, F) = UNATE_REDUCTION(F); ⎜ ⎟ ⎝ D D AP ⎠ if(T ≅ -1) (T, F) = COMP_REDUCTION(F); if(T ≅ -1) return(T); VớiD làmộtkhối toàn x. Mf là một tautology khi và chỉ khi có k, với1 ≤ k ≤ P, mà A ≅ 1 j = BINATE_INPUT_SELECT(F); k if(TAUTOLOGY(Fxj) ≅ 0) return(T=0); if(TAUTOLOGY(Fx’j) ≅ 0) return(T=0); Return (T = 1); } Logic Synthesis 17 Logic Synthesis 18 dce dce 2008 Bù 2008 Bù • Quy trình tính bù: • Bù của hàm f đượckýhiệulà: f COMPLEMENT(F){ if (row of all 2’s) return(φ); f = x j f x + x j f j x j if (F is a unate cover in all variables) NếuF làmonotone increasing theo x thì: return(UNATE_COMPLEMENT(F)); j c = first cube in F; f = x j f + f x for(i=1; i≤ N; i=i+1){ x j j if(c[i] not equal to d[i] for any cube d∈F) c[i]=2; NếuF làmonotone decreasing theo xj thì: } R = UNATE_COMPLEMENT(c); f = x j f x + f j x j F = Fc; j = BINATE_INPUT_SELECT(F); R = R ∪ (xj. COMPLEMENT(Fxj)); R = R ∪ (x’j. COMPLEMENT(Fx’j)); Return(R); } Logic Synthesis 19 Logic Synthesis 20
4. dce dce 2008 2008Recursive Complement – termination COMPLEMENT Operation rules Algorithm COMPLEMENT(List_of_Cubes C) { if(C contains single cube c) { Cres = complement_cube(c) // generate one cube per return Cres // literal l in c with ^l } else { xi = SELECT_VARIABLE(C) C0 = COMPLEMENT(COFACTOR(C,^xi)) Ù ^xi C1 = COMPLEMENT(COFACTOR(C,xi)) Ù xi return OR(C0,C1) } } dce dce 2008Recursive Complement – example 2008Recursive Complement – example (split) (merge)
5. dce dce 2008 Ví dụ 2008 Rút gọnbảng Prime Implicant • Cho hàm f gồm các implicant •Biểudiễn hàm f dướidạng các tập: •Tập OFF-Set R của f là R={001_, 00_1, 01_0, – ON-set: F 110_} – DC-set: D 0 0000 – OFF-set: R 1 1 0 5 0101 c + c + c 1 2 3 1 1 0 0 •GọiQ: tập các prime implicant cho hàm f cần 7 0111 c1 + c2 + c3 c4 1 1 1 0 0 1 1 1 1 0 8 1000 c1 c3 + c1 c2 + c1 c2 c4 c1 + c2 + c4 phảitốithiểu hoá. 9 1001 1 1 1 0 0 0 10 1010 1 0 1 + c2 c3 c4 + c2 c3 c4 c + c + c 0 1 1 1 0 1 1 • Chia Q thành 2 tập: 11 1011 1 2 4 c1 c4 + c1 c3 + c2 + c3 c4 14 1110 c0 + c0 + c1 – Relatively essential: Er 15 1111 1 2 3 So sánh kếtquả với – Relatively redundant: Rr {}1−1−,10 − −,01−1,−111,− 000 phương pháp trước (slide 4) Logic Synthesis 33 Logic Synthesis 34 dce dce 2008 Rút gọnbảng Prime Implicant 2008 Rút gọnbảng Prime Implicant •Vớic làmột cube thuộcF •Rt :có thể loạibỏ hoàn toàn –c E nếuQ D –c khôngchứac. ∈ r ∪ •Rp: mộtphầnsẽ thuộc cover tốithiểucủaf –c ∈ Rr nếuQ ∪ D – c chứac. •XétH = Er ∪ Rp –c, vớic ∈ Rp •Ersẽ nằmtrongmọi cover của hàm f •Rrsẽđược chia thành 2 tập –Rt: tậpdư thừa toàn phần (totally) –Rp: tậpdư thừa bán phần(partially) •Vớic làmột cube thuộcRr –c ∈ Rt nếuEr ∪ D chứac. –c ∈ Rp nếuEr ∪ D không chứac. Logic Synthesis 35 Logic Synthesis 36
6. dce dce 2008 Phương pháp tốigiảntối ưu 2008 Tối ưudựa trên Exact Minimization •Hailoại chính: •Mộttập các prime implicant mà chứamột – Các phương pháp tối ưumàtheochiếnlược particular cube c có thểđượcsinhrasử dụng exact minimizer nhưng không cầnthiếtsinhtoàn mộtsự thay đổi đơngiảnmàđã đượctrình bộ tập các prime implicant và giảiquyếtvấn đề bày ở phầntrước (sinh prime implicant). covering mộtcáchtối ưu – Các phương pháp tối ưudựatrênmở rộng lặp, giảm (reduction), và reshaping các implicant trong một cover Logic Synthesis 41 Logic Synthesis 42 dce dce 2008 Tối ưudựa trên Exact Minimization 2008 Tối ưudựa trên Iterative Improvement •Vídụ: •Babướchiệuchỉnh cơ bản: 0 –Nếumột cube c có 1 tạivị trí j thì ta thiếtlậpbiếnC j là 0 trong biểu thức I (xem slide 27). –Mỗi implicant đượcrútgọnvớikíchthướcnhỏ 0 1 –Nếumột cube c có _ tạivị trí j thì ta thiếtlậpcả c j và c j là 0 trong biểu nhấtcóthể thứcI – Các implicant đượckiểmtratừng cặp để xem liệu – Các prime implicant củaI sẽ tương ứng với các prime implicant của hàm f nó có thểđược reshape bằng cách rút gọnmột – Các prime implicant có thểđượcsinhmàchứamộttậphợp các cube cái và làm lớncáicònlại. đượcchọnmộtcáchtối ưu trong cover của hàm f –Giảithuật covering tối ưu (mà không quay lui) có thểđượcsử dụng –Với các implicant đượclàmlớn(đếnmứclớnnhất trong bảng prime implicant sinh ra từ tập con này của các prime. của nó) thì phảibỏđinhững implicant khác mà bị nó chứa. Logic Synthesis 43 Logic Synthesis 44
7. dce dce 2008 Espresso: Why Iterate on Reduce, Irredundant Cover, Expand? 2008 Espresso Iteration (Continued) A A A A AB AB AB AB CD 00 01 11 10 CD 00 01 11 10 CD 00 01 11 10 CD 00 01 11 10 00 1 1 0 0 00 1 1 0 0 00 1 1 0 0 00 1 1 0 0 01 1 1 1 1 01 1 1 1 1 01 1 1 1 1 01 1 1 1 1 D D D D 11 0 0 1 1 11 0 0 1 1 11 0 0 1 1 11 0 0 1 1 C C C C 10 1 1 1 1 10 1 1 1 1 10 1 1 1 1 10 1 1 1 1 B B B B Second EXPAND generates a IRREDUNDANT COVER found by Initial Set of Primes found by different set of prime implicants final step of espresso Steps1 and 2 of the Espresso Result of REDUCE: Method Shrink primes while still covering the ON-set Only three prime implicants! 4 primes, irredundant cover, Choice of order in which but not a minimal cover! to perform shrink is important dce dce 2008 2008 Expand ESPRESSO Illustrated • Expand the cubes that are unlikely to be covered by other cubes REDUCE • Selection: – Compute vector of column sums Local minimum – Weight: inner product of cube and vector EXPAND – Sort implicants in ascending order of weight • Rationale: – Low weight correlates to having few 1s in densely IRREDUNDANT populated columns Local minimum
8. dce dce 2008 Example (4) 2008 Reduce 11 11 10 • Sort implicants 10 10 01 – Heuristics: sort by descending weight • Expand 10 10 01: – Opposite to the heurstic sorting for expand – 11 10 01 invalid. • Maximal reduction can be determine exactly – 10 11 01 invalid. • Theorem: – 10 10 11 valid. –Let α be in F and Q = F U D – { α } • Expand cover: Then, the maximally reduced cube is: α = α ∩ supercube (Q’ ) 11 11 10 α 10 10 11 dce dce 2008 Example 2008 Irredundant cover Q = F U D – { α } • Expand cover: α = α∩supercube (Q’α) α 11 11 10 α 10 10 11 β 10 10 11 β 11 10 01 • Select first implicant: γ 01 11 01 –Q’= 01 11 11 δ 01 01 11 11 01 11 ε 11 01 10 – Supercube= 11 11 11 – Cannot be reduced. • Select second implicant: Q’= 11 11 01 c – β = β∩supercube (Q’β) = 10 10 01 b • Reduced cover: a 11 11 10 10 10 01