Abstract
在本篇論文中，我們提出一個以編碼方式來傳遞邏輯訊息的電路邏輯分割 法。我們的演算法會將所輸入的電路分割成兩個新的區塊，這兩個區塊之 間有訊息彼此傳遞；而且其整體的功能與原先未分割前是相同的。我們的 方法是在電路進行邏輯合成與映成之前進行的，整個演算法的主要目的在 於使分割區塊之總接腳數越少越好；亦即使兩個區塊之間的相互連接線降 低。在此，我們是利用(1)編碼與(2)變數複製的技巧來達到此一目標。在 這一篇論文中，我們同時也提出了多終端節點的二元決策圖(英文簡寫為: MTBDD)之資料結構。利用多終端節點的二元決策圖，我們可以很容易的求 得多輸出函數(multi-output function )的等類項(equivalence class) 進而算出區塊間最少的連接線個數。在兩區塊間相互溝通的訊息可視為一 些符號的集合，欲得到這些符號，可使用以下所列之兩個方法：(1) 求多 終端節點的二元決策圖之等類項；(2) 求真值表的列型態。我們所提的邏 輯分割法包含了：輸出函數分割法與輸入變數分割法。在輸出函數分割這 一步驟，我們利用多終端節點二元決策圖的節點個數做為價值函數。而輸 入變數分割法可分為四個子步驟：尋找固定變數；決定初始的輸入變數分 割；利用變數對調運算子對初始變數分割進行變數的對調，以期使等類項 的個數減少；選取重疊變數加以複製，以減少等類項的個數。經由我們的 方法得到之實驗結果，可有以下的結論：(1) 我 們的方法可在較短的 時間內執行完成；(2) 雖然我們的方法是針對於分割電路成兩個區塊，但 是其亦適用於分割電路成為多個區塊。 We consider communication based circuit partitioning in this thesis. We operate on the logic specification before the synthesis and mapping steps have been performed. The main goal of our algorithm is to minimize the number of pins needed to implement the resultant output partitions. This is accomplished by adding logic to reduce the number of pins, and by minimizing the number of pins needed for inter- partition communication by encoding the signals that flow between partitions. Counting the number of equivalence classes is an important task in the communication based logic partitioning. We propose the Multiple-Terminal- Node BDD (abbreviate as MTBDD) to count the number of equivalence classes of a multiple output function. The MTBDD is an extension from Ordered Binary Decision Diagrams. Based on the MTBDD, we can count the number of equivalence classes of a multiple output function easily.