[發明專利]集成電路邏輯優化并行處理方法

有效

• 申請號: 201210525602.X
• 申請日: 2012-12-07
• 公開（公告）號: CN103034758A
• 公開（公告）日: 2013-04-10
• 發明（設計）人: 邱建林;陳建平;顧翔;陳莉;潘陽;楊娜
• 申請（專利權）人: 南通大學
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 南通市永通專利事務所 32100
• 代理人: 葛雷

技術領域

本發明涉及一種集成電路邏輯優化并行處理方法。?

背景技術

由于在國內外期刊、會議論文、著作等中對集成電路邏輯優化并行處理中的任務調度的研究幾乎是沒有出現過的，因此就需要在研究并行處理調度算法和邏輯優化兩個領域的基礎上，結合邏輯優化中的特點，形成適用于邏輯優化的并行處理調度算法。?

隨著EDA的發展，集成電路的邏輯函數變量數及狀態數越來越多，而傳統的邏輯函數化簡方法，比如公式法、卡諾圖法，已不再能滿足優化集成電路的工作。公式法的不直觀，導致難以確定化簡思路和判定函數是否最簡；而卡諾圖法雖較比較直觀，但它只是比較適合五個以下變量的函數，是以畫圖為基礎的，因此不便于計算機的實現。近幾年，隨著VLSI芯片集成度的大大提高，一些優化方法被相繼提出，其中具有代表性的算法大致可以分為兩類：一類是先對最小項集合進行化簡，從而獲得本源蘊涵項(prime?implicant)集合，然后再進行求解最小覆蓋。另一類則不必求出全部實質蘊涵項，而是直接構建函數的最小覆蓋。?

在邏輯問題研究領域中，美國加里福尼亞大學伯克利分校的Brayton與日本九州（Kyushu）大學的Sasao的研究是極具代表性的，而在邏輯優化領域中，日本的J.Butler和Shinobu?Nagayama、臺灣師?大資訊工程研究所S.-S.Lin以及捷克斯洛伐克捷克科技大學的Petr?Fiser的研究頗多。而在國內，中科院、清華大學、北京大學、浙江大學、上海交通大學、復旦大學、北京理工大學等著名高校的專家、學者也在邏輯設計自動化方面進行了大量的應用與研究，并且取得了引人注目的成果，從而在理論和應用方面推動了我國集成電路設計、加工和制造事業的發展。?

1952年Quine-McCluskey首次提出了最小化布爾函數的方法—Q-M法，其在功能上等同卡諾圖法，但是該方法是根據真值表逐層逐項地比較并合并的表格法化簡，這樣可以有效地利用計算機處理問題。當邏輯變量變多時，最小項的數目也急劇增加，則需占用的內存就變多，朱幼蓮提出用星積運算求質蘊涵素項，而用選擇極值法求最小覆蓋的方法，通過采用靈活的數據結構來重新組合化簡步驟，進而大大節省存儲空間，加快邏輯化簡的速度。王忠林則介紹了一種可以化簡復雜邏輯函數的方法——列表法，該方法是利用邏輯函數的最小項對相鄰最小項進行合并，消去多余的變量因子，從而得到邏輯函數的最簡式。管致錦提出的適合大變量邏輯函數最佳覆蓋的改進Beister算法，是針對對最小列覆蓋算法的相關規則，優先考慮含有效1多的列和含1較少的行。基于變換化簡法，呂宗偉給出了一種改進的適用于局部邏輯網絡優化的多級邏輯優化算法，該算法通過計算邏輯網絡中門或連線處的無關項，迅速地獲得最大允許函數集合，從而降低計算時間，并提高原算法的適用性。管致錦等人提出一種新的本源蘊涵項的生成算法，生成過程中遵循“最小孤立點優先”的原則，僅產生?本源項子集來形成覆蓋，使冗余項減少，從而有效地提高運算速度。在分析多輸出邏輯函數最小化覆蓋選拔算法的基礎上，葉靜提出了針對大規模邏輯函數優化的改進選拔算法，此算法利用相交迭代的思想，而大大提高處理速度，同時利用局部搜索的思想解決分支處理時內存占用率高、處理時間長等問題。?