Bài giảng Thiết kế số - Thực hiện tối ưu hóa hàm logic: Phân tích và tổng hợp mạch đa mức - Hoàng Mạnh Thắng

Thiết kế số Thực hiện tối ưu hóa hàm logic:Phân tích và tổng hợp mạch đa mứcNgười trình bày: TS. Hoàng Mạnh ThắngTexPoint fonts used in EMF: AAAAATổng hợp mạch đa mứcVấn đề tối ưu hóa là đi tìm dạng tối thiểu dưới dạng POS hoặc SOP cho hàm logicSOP hay POS thuộc loại hai mức:Dạng SOP có mức thứ nhất chỉ gồm các cổng AND với các đầu ra nối đến các đầu vào của mức thứ 2 là cổng ORTương tự, POS có mức thứ nhất là các cổng OR và mức thứ 2 là cổng ANDThực hiện tổng hợp mạch 2 lớp thường hiệu quả cho các hàm có vài đầu vàoTổng hợp mạch đa mức (cont.)Khi số đầu vào tăng thì vấn đề xảy ra ở chỗ đầu vào (fan-in problems)Fan-in: tổng số đầu vào đi đến một cổng hay một phần tử của mạchXét cost cho biểu thức SOP dưới đâyf(x_1,..x_7)=x_1x_3x_6’+x_1x_4x_5x_6’+x_2x_3x_7+x_2x_4x_5x_7Tổng hợp mạch đa mức (cont.)Xét việc thực hiện hàm f hai lớp với các PLD như CPLD hay FPGA .Với CPLD thì không sao bởi có đủ đầu vào, đủ cổng AND và cả cổng ORTổng hợp mạch đa mức (cont.)Với FPGA có các LUTs 2 đầu vào thì hàm này ko thể thực hiện được trực tiếp vì:Dạng SOP có 3 và 4 thành phần (literals)  yêu cầu các cổng AND có 3 và 4 đầu vàoCó 4 thành phần tích  cần các cổng OR có 3 và 4 đầu vàoFan-in để thực hiện mạch này là lớn hơn so với các LUTs 2 đầu vào của FPGATổng hợp mạch đa mức (cont.)Để giải quyết, hàm phải được biểu diễn ở dạng có số mức logic lớn hơn 2. Nó được gọi là biểu thứ logic đa mứcCó 2 kỹ thuật tổng hợp các hàm logic đa mức là: factoring và functional decomposition (đặt thừa số và phân tách hàm)Factoring (đặt thừa số)Sử dụng tính chất phân bố để viết lại biểu thức dưới dạng có ít thành phần biến (literals) trong một nhóm hơn.Ví dụỞ dạng này, hàm có ko quá 2 thành phần biến cho mỗi nhóm và có thể thực hiện với LUTs hai đầu vàoFactoring (đặt thừa số)Các vấn đề của Fan-inCác hạn chế Fan-in ko những chỉ trong PLDs, mà còn trong các cổng logic đơnNhìn chung, khi số đầu vào đến 1 cổng logic tăng dẫn đến trễ lan truyền tăng.Trễ lan truyền là tổng trễ cần thiết cho sự thay đổi ở đầu vào tạo ra thay đổi ở đầu raNhư vậy, mong muốn là hạn chế số đầu vào tới một phần tử. Thông thường tối đa là 5Các vấn đề của Fan-in (cont.)Cho một hàmThực hiện trực tiếp yêu cầu 2 cổng AND 6 đầu vào và 1 cổng OR 2 đầu vàoĐặt thừa số cho hàm này cóHàm này giải quyết được vấn đề Fan-inBài tậpThực hiện factoring cho biểu thức sau với lời giải là chỉ dùng các cổng NAND/AND và OR hai đầu vàoẢnh hưởng lên mức phức tạp của kết nốiKhông gian của IC được chiếm bởi mạch và các dây dẫn tạo nên kết nối cho các mạchMối literal tưpưng ứng với 1 dây nối trong mạch, nó mang tín hiệu logicFactoring làm giảm tổng số literal và cũng giúp giảm mức phức tạp của kết nốiTrong khi tổng hợp mạch logic, CAD tôls xem xét các tham số như: chi phí của mạch, fan-in, tốc độ của mạch và mức phức tạp của dâyFunctional decomposition (phân tách hàm)Mức phức tạp của mạch logic (cổng logic và kết nối) thường có thể được giảm bằng cách phân tách (decomposing) biểu thứ 2 mức thành nhiều mạch nhỏ hơn.Mạch nhỏ này có thể đuwocj dùng một số nơi trong mạch cuối cùngMột biểu thức 2 mức có thể được thay thế bởi 2 hay nhiều biểu thức mới.Các biểu thức mới được tổ hợp để hình thành mạch nhiều mứcVí dụ về phân tách hàmXét biểu thức:Hàm này yêu cầu 1 cổng AND 3 đầu vào, 2 cổng AND 2 đầu vào và 1 cổng OR 3 đầu vàoCOST = 4 cổng + 10 đầu vào = 14. Và COST = 20 nếu cổng NOT được kèm thêm vàoViết lại hàm f: Gọi  Ví dụ về phân tách hàm (cont.)Hàm trở thành Mạch được xây dựng như sau với COST=16 bao gồm cả cổng NOTCác vấn đề thực tếPhân tách hàm là công cụ mạnh để giảm mức độ phức tạp cho mạchNó có thể được dùng để thực hiện hàm logic với các ràng buộc. Ví dụ: thực hiện với PLD cụ thể.CAD tools dùng nhiều khái niệm này.