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ức Người trình bày: TS. Hoàng Mạnh Thắng TexPoint fonts used in EMF: A A A A A Tổng hợp mạch đa mức Vấ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 logic SOP 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 OR Tương tự, POS có mức thứ nhất là các cổng OR và mức thứ 2 là cổng AND Thự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ào Tổ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ạch Xét cost cho biểu thức SOP dưới đây f(x_1,..x_7)=x_1x_3x_6’+x_1x_4x_5x_6’+x_2x_3x_7+x_2x_4x_5x_7 Tổ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 OR Tổ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ào Có 4 thành phần tích  cần các cổng OR có 3 và 4 đầu vào Fan-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 FPGA Tổ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ức Có 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ào Factoring (đặt thừa số) Các vấn đề của Fan-in Các hạn chế Fan-in ko những chỉ trong PLDs, mà còn trong các cổng logic đơn Nhì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 ra Như 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à 5 Các vấn đề của Fan-in (cont.) Cho một hàm Thự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-in Bài tập Thự c hiện factoring cho biểu thứ c sau với lời giải là chỉ dùng các cổng NA N D /AND và OR hai đầu vào Ảnh hưởng lên mức phức tạp của kết nối Khô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ạch Mối literal tưpưng ứng với 1 dây nối trong mạch, nó mang tín hiệu logic Factoring 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ối Trong 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ây Functional 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ùng Mộ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ức Ví dụ về phân tách hàm Xé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ào COST = 4 cổng + 10 đầu vào = 13. Và COST = 19 nếu cổng NOT được kèm thêm vào Viế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 NOT Cá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ạch Nó 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.