時(shí)序功能塊的提取.doc

-專(zhuān)業(yè)文檔，值得下載!-專(zhuān)業(yè)文檔，值得珍藏！-時(shí)序功能塊的提取潘日華童家榕唐璞山（復(fù)旦大學(xué)電子工程系ICCAD實(shí)驗(yàn)室，上海200433）【摘要】文章介紹了基于功能塊提取器（DLFE）工具的時(shí)序功能塊提取工具和方法。整套工具用于從版圖中構(gòu)造層次化電路，以利于電路的驗(yàn)證和理解。時(shí)序功能塊提取通過(guò)時(shí)序功能塊的普遍特征來(lái)定位時(shí)序功能塊，避免了手工定位的盲目性，大大加快了構(gòu)造層次化電路的速度。實(shí)驗(yàn)證明，工具對(duì)時(shí)序模塊的提取是十分有效的。關(guān)鍵詞：功能塊提取時(shí)序功能塊邏輯驗(yàn)證1引言通常的集成電路驗(yàn)證中，在大規(guī)模生產(chǎn)之前，必須檢驗(yàn)版圖和設(shè)計(jì)電路圖的一致性。一般的方法是將設(shè)計(jì)電路圖打碎至最底層，然后與版圖比較1。驗(yàn)證方法基于圖的同構(gòu)，雖然有很多優(yōu)化，其復(fù)雜性仍然是非多項(xiàng)式的。在電路的規(guī)模比較小時(shí)，這樣的算法可以勝任。但是隨著電路規(guī)模的不斷增長(zhǎng)，驗(yàn)證耗費(fèi)的時(shí)間和成本逐漸變得不能忍受。層次化驗(yàn)證的方法2，雖然每一個(gè)子電路仍然采取同構(gòu)的驗(yàn)證方法，但是通過(guò)對(duì)電路的劃分，可以將時(shí)間復(fù)雜性由非多項(xiàng)式向多項(xiàng)式轉(zhuǎn)化。例如對(duì)較大的N來(lái)說(shuō)，若分為a塊，exp(N)遠(yuǎn)大于a*exp(N/a)。因此，如果能從版圖中構(gòu)造出層次化的電路圖，將大大加快驗(yàn)證過(guò)程。另一方面，設(shè)計(jì)的電路圖是按功能劃分的，若要將提取出的電路圖和設(shè)計(jì)電路圖比較，必須按功能從版圖中提取層次化電路圖?，F(xiàn)有的軟件中還沒(méi)有按功能提取層次化電路的工具。不同的電路由于應(yīng)用領(lǐng)域不同，各自的功能塊截然不同，很難用一個(gè)算法來(lái)自動(dòng)識(shí)別，或者是算法只能識(shí)別某一類(lèi)型的功能塊。本文所介紹的工具也不試圖設(shè)計(jì)一個(gè)能自動(dòng)識(shí)別任何功能塊的算法，而是采用人機(jī)結(jié)合的方法。分別利用人腦的識(shí)別能力和計(jì)算機(jī)的計(jì)算能力，共同完成功能塊的提取。在此之前，我們已經(jīng)設(shè)計(jì)了交互式的功能塊提取器（DLFE）工具3，實(shí)現(xiàn)了電路的可視化和層次化的基本機(jī)制。用戶可以通過(guò)可視化工具瀏覽電路，制作功能塊的樣本，然后用工具在整個(gè)電路中搜尋并替換所有同構(gòu)的樣本的實(shí)例。自下而上的逐步構(gòu)造出層次化的電路圖，同時(shí)完成對(duì)電路的功能分析。但是DLFE工具在功能塊尋找和定位方面有所欠缺，很大程度上依賴于用戶自己通過(guò)瀏覽去搜-專(zhuān)業(yè)文檔，值得下載!-專(zhuān)業(yè)文檔，值得珍藏！-尋樣本，有一定的偶然性，與用戶的經(jīng)驗(yàn)也有很大關(guān)系。因此我們?cè)贒LFE的基礎(chǔ)上開(kāi)發(fā)了幫助用戶尋找和定位時(shí)序功能塊的工具。它根據(jù)時(shí)序模塊的普遍特征來(lái)搜尋可能的功能塊，具有很高的準(zhǔn)確性。且不依賴于已有的模塊庫(kù)，不受模塊實(shí)現(xiàn)方式的影響，可以應(yīng)用于各種電路。在工具輔助下，避免了手工查找的盲目性和隨機(jī)性，大大加快了構(gòu)造層次化電路圖的速度。文章第2節(jié)介紹了時(shí)序模塊的普遍特征，第3節(jié)介紹如何根據(jù)這些特征來(lái)定位時(shí)序模塊，第4節(jié)介紹算法的實(shí)現(xiàn)和復(fù)雜性，第5節(jié)列舉了具體的例子和效果。2時(shí)序功能塊的特征通過(guò)對(duì)大量時(shí)序功能塊的總結(jié)歸納，我們發(fā)現(xiàn)時(shí)序功能塊具有一些共同的特征。圖1所示的電路是一個(gè)典型的時(shí)序功能塊，下面以它為例介紹時(shí)序功能塊的基本特征。DQQSETCLRDQQSETCLRDQQSETCLRDQQSETCLRQ0Q1Q2Q3CP圖1一個(gè)典型的時(shí)序功能塊核心器件在模塊中起核心作用的器件。如圖1中用深灰色表示的的觸發(fā)器。另外如十六位定時(shí)器中的四位計(jì)數(shù)器等等都屬于核心器件。全局線網(wǎng)在功能上控制器件的行為的線網(wǎng)，在連接關(guān)系上它連接了所有的核心器件。如圖1中用粗線表示的時(shí)鐘信號(hào)。又如復(fù)位信號(hào)和雙向計(jì)數(shù)器的計(jì)數(shù)方向信號(hào)都是全局線網(wǎng)。相關(guān)和相關(guān)路徑一個(gè)模塊中，核心器件A到核心器件B之間存在一條數(shù)據(jù)通路，那么A和B是相關(guān)的，這條路徑稱為相關(guān)路徑。如圖1中的虛線就是其中的一條相關(guān)路徑。關(guān)系特征如果相關(guān)路徑用連線來(lái)表示，核心器件用圓來(lái)表示，模塊中所有相關(guān)路徑就構(gòu)成了模塊的關(guān)系特征。如圖2是四位計(jì)數(shù)器的觸發(fā)器之間的關(guān)系圖，圖3是四位移位寄存器的觸發(fā)器關(guān)系圖。-專(zhuān)業(yè)文檔，值得下載!-專(zhuān)業(yè)文檔，值得珍藏！-ABCD圖2四位同步計(jì)數(shù)器關(guān)系圖ABCD圖3四位移位計(jì)數(shù)器關(guān)系圖關(guān)系特征可以用作功能塊的特征和辨別功能塊的依據(jù)，雖然不能保證具有某種特征的模塊一定是實(shí)現(xiàn)某種功能的模塊，但可以肯定不具有這種特征的模塊不是實(shí)現(xiàn)某種功能的模塊。如不具有圖2特征的模塊肯定不是四位同步計(jì)數(shù)器。根據(jù)以上這些特點(diǎn)，我們可以假定：核心器件和所有相關(guān)路徑包含的器件（如圖1中淺灰色器件）構(gòu)成模塊的主體。經(jīng)驗(yàn)表明，對(duì)大部分時(shí)序功能塊來(lái)說(shuō)，這個(gè)假定是成立的。工具將基于這個(gè)假定來(lái)提取時(shí)序功能塊。以上的幾個(gè)概念和假定，雖然比較模糊，而且不一定在任何情況下都成立，但是它們?cè)诖蟛糠智闆r下都是很有效的。3時(shí)序功能塊的提取時(shí)序功能塊的提取根據(jù)上一節(jié)介紹的時(shí)序功能塊的普遍特征來(lái)定位功能塊。提取工作分三步完成：核心器件和全局線網(wǎng)的提取、核心器件之間的關(guān)系分析、功能塊主體的提取。這里要說(shuō)明的是，此后所說(shuō)的“核心器件”、“全局線網(wǎng)”等都應(yīng)是“可能的核心器件”、“可能的全局線網(wǎng)”，并不是嚴(yán)格意義上的核心器件、全局線網(wǎng)。“可能的”核心器件和全局線網(wǎng)將覆蓋真正的核心器件和全局線網(wǎng)，判斷和區(qū)分工作由用戶完成。3.1核心器件和全局線網(wǎng)的提取核心器件和全局線網(wǎng)的提取將建立功能塊的框架，以排除大量的無(wú)關(guān)器件，縮小處理范圍。由于工具自己不能分別核心器件和普通器件，用戶需要輸入核心器件類(lèi)型集合。另外還要引入一個(gè)定義：關(guān)鍵引腳核心器件連接全局線網(wǎng)的引腳。引入關(guān)鍵引腳是要從核心器件找到全局線網(wǎng)。一般來(lái)說(shuō)，全局線網(wǎng)不僅連接了所-專(zhuān)業(yè)文檔，值得下載!-專(zhuān)業(yè)文檔，值得珍藏！-有的核心器件，而且都連接著相同的引腳。如時(shí)鐘信號(hào)連接了CP引腳，復(fù)位信號(hào)連接了RZ引腳。核心器件和全局線網(wǎng)的提取基于這樣一個(gè)假設(shè)：功能塊的全局線網(wǎng)所連的核心器件包含且僅包含該功能塊的核心器件。即不包含其它功能塊里的核心器件。對(duì)實(shí)際版圖上的電路來(lái)說(shuō)，這個(gè)假定是合理的。由于驅(qū)動(dòng)能力的限制，雖然一個(gè)線網(wǎng)可以在邏輯上連接了很多模塊的核心器件，但在實(shí)際電路中，必須加多個(gè)驅(qū)動(dòng)器件。一般地，這些驅(qū)動(dòng)器件都位于模塊的輸入位置，從而隔離了不同模塊之間的核心器件。如在圖4中，N1和N2分別是功能塊B和C的全局線網(wǎng)，雖然在邏輯上是相同的，但在實(shí)際電路中，它們并不直接相連。AAAABCDN1N2N3圖4驅(qū)動(dòng)器件的隔離作用3.2核心器件關(guān)系分析分析核心器件關(guān)系采用窮舉的方法，在一定范圍內(nèi)，若兩個(gè)核心器件之間存在通路，則這兩個(gè)器件存在關(guān)系。核心器件關(guān)系分析就是要找出功能塊內(nèi)所有的這樣的關(guān)系。通過(guò)這些核心器件關(guān)系信息，用戶可以初步判斷功能塊的功能。如果模塊的輸出在模塊外部反饋回模塊本身，分析出的關(guān)系不僅包含模塊內(nèi)核心器件之間的關(guān)系，還包括模塊外的關(guān)系。由此定位出的功能塊將包含模塊外部的器件，影響到提取的準(zhǔn)確性。解決這一問(wèn)題的辦法是繞開(kāi)它，如果電路中有多個(gè)這種功能塊，那么最好的解決辦法是找一個(gè)不受反饋干擾的功能塊實(shí)例的關(guān)系圖，然后利用工具的匹配和替換功能3來(lái)找出所有實(shí)例，反饋的連線自然會(huì)被排除在外。另一種辦法是逐步縮小遍歷深度（算法中的可控參數(shù)），使得反饋線路不在遍歷范圍內(nèi)。3.3功能塊主體的提取功能塊主體的提取把某個(gè)關(guān)系圖對(duì)應(yīng)的子電