分解作多階邏輯合成之研究

Abstract

本篇論文探討以函數分解為導向之多階邏輯合成技術。論文主要分成四部 分。這些技術簡單描述如下：一．二元決策圖之轉換技術：本篇論文提出 一方法來重新建構二元決策樹，使其能從一即定之輸入排序轉至另一輸入 排序。此技術是建立於函數之排列相等性與二元決策圖之結構相等性。同 時提出一轉換運算元以完成此種轉換。這些技術可應用於尋找二元決策圖 之最佳輸入排序；對於以減少連接線數目為主之多階邏輯合，可以找尋一 最佳輸入分割；並可檢測布林函數之對稱性。二．以連接線為取向之多階 合成之研究－重疊分割：以降低連接線為主之技術曾經被提出並應用在多 階邏輯合成。但是在以前的研究中，只考慮了不相交分割。然而對於不同 類型之電路，重疊分割可以減少不用之連接線。在本篇論文中，我們研究 了重疊分割並且探討了以下問題：如何尋找公用變數，如何產生部分函數 ，利用分割產生之隨意集合（don't care set）來改善分割電路品質。三 ．以連接線複雜度為主之布林比對技術：布林比對用於檢查兩個布林函數 在輸入排列與輸入╱輸出狀態設定下是否相等。最直接的作法需要{\em O(n! $2^{n}\cdot$2)} 之時間複雜度，此處 n代表輸入之數目。很多研 究者曾提出各式各樣之記號（signature） 來刪除不可能之排列。在本篇 論文，根據連接線複雜度，我們提出了共同因子記號與相等記號，此二種 記號為現存很多記號之一般式。利用此記號，我們提出一有效之布林比對 演算法，此演算法主要在檢查二決策圖之結構相等性。經由實驗結果證明 ，此演算法的確可有效解決布林比對問題。四．以隨機取記憶體（RAM） 為主之場可程式化閘陣列的技術映成：本篇論文提出一名為「函數映成」 之技術映成工具。本工具利用函數分解原理將一個大函數分割成很多小函 數，使得每一個小函數都可由單一邏輯元件製作。本系統分成二部分。第 一部分設計成能特別處理完全對稱函數，我們提出一個以重量相依性為主 之快速分割演算法。第二部份可處理一般函數，我們提出輸出分割，變數 分割，隨意集合之設定和編碼等技術，以減少部分函數之數目。應用這些 技術，經由實驗結果證明，在映成電路的面積及速度兩方面，均可得到較 佳之結果。 This dissertation attempts to study techniques for multi- level logic synthesis based on functional decomposition. It is mainly divided into four parts. In the first part, we propose a transformation technique for OBDD's. Overlapped decomposition techniques for communication complexity driven multilevel logic synthesis are addressed in the second part. Then we propose a Boolean matching algorithm for technology mapping. Finally, we propose a technology mapping system for RAM-based FPGA's.