(19)國家知識產(chǎn)權(quán)局(71)申請人寧波大學(xué)(74)專利代理機(jī)構(gòu)寧波奧圣專利代理有限公司專利代理師謝瀟(54)發(fā)明名稱一種基于矩陣半張量積的數(shù)字電路邏輯優(yōu)化方法本發(fā)明公開了一種基于矩陣半張量積的數(shù)的重收斂驅(qū)動(dòng)切割以及最大扇出自由錐并得到除數(shù)集；對節(jié)點(diǎn)n的最大扇出自由錐的內(nèi)部節(jié)點(diǎn)及除數(shù)集中的節(jié)點(diǎn)進(jìn)行仿真，再對除數(shù)集進(jìn)行精簡操作；使用半張量積計(jì)算節(jié)點(diǎn)n關(guān)于剔除冗余的除數(shù)集的所有可行的依賴函數(shù)；基于邏輯網(wǎng)絡(luò)實(shí)現(xiàn)規(guī)模較小的依賴函數(shù)綜合出節(jié)點(diǎn)n的新的實(shí)現(xiàn)；若節(jié)點(diǎn)n的新的實(shí)現(xiàn)中邏輯門的數(shù)量小于其最大扇出自由錐的內(nèi)部節(jié)點(diǎn)的數(shù)量，則以其新的實(shí)現(xiàn)替換掉最大扇出自由錐；遍歷完邏輯網(wǎng)絡(luò)中的所有目標(biāo)節(jié)點(diǎn)，完成電路尺寸優(yōu)化。本發(fā)明優(yōu)化方法建立在嚴(yán)密的數(shù)學(xué)框架之上，其核心為矩21.一種基于矩陣半張量積的數(shù)字電路邏輯優(yōu)化方法，其特征在于，該方法為：按拓?fù)漤樞虮闅v待優(yōu)化的數(shù)字電路的邏輯網(wǎng)絡(luò)，選定邏輯網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)n作為待優(yōu)化的目標(biāo)節(jié)點(diǎn)，計(jì)算節(jié)點(diǎn)n的重收斂驅(qū)動(dòng)切割以及最大扇出自由錐，再收集除數(shù)，得到除數(shù)集；對節(jié)點(diǎn)n的最大扇出自由錐的內(nèi)部節(jié)點(diǎn)及除數(shù)集中的節(jié)點(diǎn)進(jìn)行仿真，再根據(jù)仿真結(jié)果對除數(shù)集進(jìn)行精簡操作，得到剔除冗余的除數(shù)集；然后使用半張量積計(jì)算節(jié)點(diǎn)n關(guān)于剔除冗余的除數(shù)集的所有可行的依賴函數(shù)；從所有可行的依賴函數(shù)中選擇邏輯網(wǎng)絡(luò)實(shí)現(xiàn)規(guī)模較小的一個(gè)依賴函數(shù)，基于該依賴函數(shù)綜合出節(jié)點(diǎn)n的新的實(shí)現(xiàn)；若節(jié)點(diǎn)n的新的實(shí)現(xiàn)中邏輯門的數(shù)量小于節(jié)點(diǎn)n的最大扇出自由錐的內(nèi)部節(jié)點(diǎn)的數(shù)量，則以節(jié)點(diǎn)n的新的實(shí)現(xiàn)替換掉節(jié)點(diǎn)n的最大扇出自由錐；按上述方法遍歷完邏輯網(wǎng)絡(luò)中的所有目標(biāo)節(jié)點(diǎn)，完成電路尺寸優(yōu)化。2.根據(jù)權(quán)利要求1所述一種基于矩陣半張量積的數(shù)字電路邏輯優(yōu)化方法，其特征在于，該方法具體包括以下步驟：步驟1、按拓?fù)漤樞虮闅v待優(yōu)化的數(shù)字電路的邏輯網(wǎng)絡(luò)，選定邏輯網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)n作為待優(yōu)化的目標(biāo)節(jié)點(diǎn)，計(jì)算節(jié)點(diǎn)n的重收斂驅(qū)動(dòng)切割以及最大扇出自由錐，再收集除數(shù)，得到除數(shù)集；節(jié)點(diǎn)n的重收斂驅(qū)動(dòng)切割和除數(shù)構(gòu)成邏輯網(wǎng)絡(luò)中的一個(gè)子網(wǎng)絡(luò)，將節(jié)點(diǎn)n的重收斂驅(qū)動(dòng)切割的q個(gè)葉子節(jié)點(diǎn)視為該子網(wǎng)絡(luò)的原始輸入，將節(jié)點(diǎn)n的最大扇出自由錐的內(nèi)部節(jié)點(diǎn)及收集到的除數(shù)集中的節(jié)點(diǎn)表征為該q個(gè)葉子節(jié)點(diǎn)的布爾函數(shù)，對節(jié)點(diǎn)n的最大扇出自由錐的內(nèi)部節(jié)點(diǎn)及收集到的除數(shù)集中的節(jié)點(diǎn)進(jìn)行仿真，再根據(jù)仿真結(jié)果對收集到的除數(shù)集進(jìn)行精簡步驟2、使用半張量積計(jì)算節(jié)點(diǎn)n關(guān)于剔除冗余的除數(shù)集的所有可行的依賴函數(shù)；步驟3、使用開源邏輯綜合工具Espresso進(jìn)行求解，根據(jù)求解結(jié)果從所有可行的依賴函數(shù)中選擇邏輯網(wǎng)絡(luò)實(shí)現(xiàn)規(guī)模較小的一個(gè)依賴函數(shù)，如果得到的依賴函數(shù)的支持不大于4,則命令將得到的依賴函數(shù)分解為一個(gè)由4-LUTs組成的LUT網(wǎng)絡(luò)，并對該LUT網(wǎng)絡(luò)中的每一個(gè)若節(jié)點(diǎn)n的新的實(shí)現(xiàn)中邏輯門的數(shù)量小于節(jié)點(diǎn)n的最大扇出自由錐的內(nèi)部節(jié)點(diǎn)的數(shù)量，則以節(jié)點(diǎn)n的新的實(shí)現(xiàn)替換掉節(jié)點(diǎn)n的最大扇出自由錐；步驟4、重復(fù)步驟1~步驟3,直至遍歷完邏輯網(wǎng)絡(luò)中的所有目標(biāo)節(jié)點(diǎn)，完成電路尺寸優(yōu)3.根據(jù)權(quán)利要求2所述一種基于矩陣半張量積的數(shù)字電路邏輯優(yōu)化方法，其特征在于，所述步驟1中，對收集到的除數(shù)集進(jìn)行精簡操作的方法為：步驟1.1、給定定理，基于該定理將精簡除數(shù)集的問題轉(zhuǎn)換為覆蓋集合的問題，該定理的具體描述如下：定義變量X={x?,x?,..,×。,基于該變量X給定布爾函數(shù)f(X)和初始除數(shù)集{z?,Z?,..,z},其中p,q為正整數(shù)，該初始除數(shù)集中的p個(gè)除數(shù)都是關(guān)于X的布爾函數(shù)：8?1(X),g?2(X),...,gzn(X),當(dāng)且僅當(dāng)不存在一對最小項(xiàng)(M:,M)使得f(M.)≠8zk(M),則布爾函數(shù)f(X)被初始除數(shù)集{z?,Z?,.,z}重新表達(dá)為f(X)=h(8?1(X),822(X),...,8zp(X)),其中布爾函數(shù)h被定義為依賴函數(shù)；3步驟1.2、由節(jié)點(diǎn)n所區(qū)分的最小項(xiàng)對構(gòu)成一個(gè)集合M,從節(jié)點(diǎn)n的初始除數(shù)集中迭代地4.根據(jù)權(quán)利要求3所述一種基于矩陣半張量積的數(shù)字電路邏個(gè)葉子節(jié)點(diǎn)記為(x,X?,…,x。),進(jìn)入步驟2.2,通過結(jié)構(gòu)矩陣描述節(jié)點(diǎn)n以及剔除冗余其中m∈M2×2?,m,中的每一列f,都是一個(gè)二元列向量，取值于集合的等式：將m?x?X?…xqm?X?X?…xa…mpX?X?…Xq規(guī)范化為myx?X?…xq,其中my∈M2P×29,此時(shí)等式(4)轉(zhuǎn)換為：mfX?X?…xq=mxmyx?X?…由于在計(jì)算節(jié)點(diǎn)n關(guān)于除數(shù)集的所有可行的依賴函數(shù)過程中遇到的每個(gè)矩陣的每一列4fr()=f;(7);則f既可以為,又可以為,它們都會滿足等式(5),因此，通過等式(7)單次計(jì)算求得節(jié)點(diǎn)n關(guān)于除數(shù)集的所有可行的依賴函數(shù)。5替換(BooleanResubstitution)是一種經(jīng)典的數(shù)字電路邏輯優(yōu)化方法現(xiàn)有網(wǎng)絡(luò)中的節(jié)點(diǎn)(稱為除數(shù))來重新表達(dá)目標(biāo)節(jié)點(diǎn)的功能，并以新的實(shí)現(xiàn)替換原有實(shí)現(xiàn)，[0003]傳統(tǒng)布爾重替換算法采用啟發(fā)式枚舉策略實(shí)現(xiàn)目標(biāo)節(jié)點(diǎn)重構(gòu)，其標(biāo)準(zhǔn)流程包插入量約束i≤min{m-1,3}下，從i=0起始執(zhí)行漸進(jìn)式枚舉搜索，逐級遞增枚舉新實(shí)現(xiàn)方=3)未獲解時(shí)，觸發(fā)啟發(fā)式分解：選取j個(gè)除數(shù)(j∈{1,2})對目標(biāo)函數(shù)進(jìn)行分解，因需插入j個(gè)邏輯門，約束條件同步更新為i≤{m-1-j歸執(zhí)行核心處理流程直至滿足約束條件。當(dāng)現(xiàn)首個(gè)成本降低解時(shí)即終止迭代，僅能遍歷解空間的有限子集；2)數(shù)學(xué)框架的系統(tǒng)性缺性顯著提升的基于矩陣半張量積(Semi-TensorProduct,STP)的數(shù)字電路邏輯優(yōu)化方法。按拓?fù)漤樞虮闅v待優(yōu)化的數(shù)字電路的邏輯網(wǎng)絡(luò)，選定邏輯網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)n作大扇出自由錐的內(nèi)部節(jié)點(diǎn)及除數(shù)集中的節(jié)點(diǎn)進(jìn)行仿真，再6可行的依賴函數(shù)；從所有可行的依賴函數(shù)中選擇邏輯網(wǎng)絡(luò)實(shí)現(xiàn)規(guī)模較小的一個(gè)依賴函數(shù)，基于該依賴函數(shù)綜合出節(jié)點(diǎn)n的新的實(shí)現(xiàn)；若節(jié)點(diǎn)n的新的實(shí)現(xiàn)中邏輯門的數(shù)量小于節(jié)點(diǎn)n的最大扇出自由錐的內(nèi)部節(jié)點(diǎn)的數(shù)量，則以節(jié)點(diǎn)n的新的實(shí)現(xiàn)替換掉節(jié)點(diǎn)n的最大扇出自由錐；按上述方法遍歷完邏輯網(wǎng)絡(luò)中的所有目標(biāo)節(jié)點(diǎn)，完成電路尺寸優(yōu)化。[0007]作為優(yōu)選，本發(fā)明基于矩陣半張量積的數(shù)字電路邏輯優(yōu)化方法具體包括以下步步驟1、按拓?fù)漤樞虮闅v待優(yōu)化的數(shù)字電路的邏輯網(wǎng)絡(luò)，選定邏輯網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)n作為待優(yōu)化的目標(biāo)節(jié)點(diǎn)，計(jì)算節(jié)點(diǎn)n的重收斂驅(qū)動(dòng)切割以及最大扇出自由錐，再收集除節(jié)點(diǎn)n的重收斂驅(qū)動(dòng)切割和除數(shù)構(gòu)成邏輯網(wǎng)絡(luò)中的一個(gè)子網(wǎng)絡(luò)，將節(jié)點(diǎn)n的重收斂驅(qū)動(dòng)切割的q個(gè)葉子節(jié)點(diǎn)視為該子網(wǎng)絡(luò)的原始輸入，將節(jié)點(diǎn)n的最大扇出自由錐的內(nèi)部節(jié)點(diǎn)及收集到的除數(shù)集中的節(jié)點(diǎn)表征為該q個(gè)葉子節(jié)點(diǎn)的布爾函數(shù)，對節(jié)點(diǎn)n的最大扇出自由錐的內(nèi)部節(jié)點(diǎn)及收集到的除數(shù)集中的節(jié)點(diǎn)進(jìn)行仿真，再根據(jù)仿真結(jié)果對收集到的除數(shù)集進(jìn)行步驟2、使用半張量積計(jì)算節(jié)點(diǎn)n關(guān)于剔除冗余的除數(shù)集的所有可行的依賴函數(shù)；步驟3、使用開源邏輯綜合工具Espresso進(jìn)行求解，根據(jù)求解結(jié)果從所有可行的依賴函數(shù)中選擇邏輯網(wǎng)絡(luò)實(shí)現(xiàn)規(guī)模較小的一個(gè)依賴函數(shù)，如果得到的依賴函數(shù)的支持不大于4,則直接對其精確綜合，從而得到節(jié)點(diǎn)n的新的實(shí)現(xiàn)，否則，調(diào)用開源邏輯綜合工具also中的dec命令將得到的依賴函數(shù)分解為一個(gè)由4-LUTs組成的LUT網(wǎng)絡(luò)，并對該LUT網(wǎng)絡(luò)中的每一個(gè)LUT進(jìn)行精確綜合，從而得到節(jié)點(diǎn)n的新的實(shí)現(xiàn)；若節(jié)點(diǎn)n的新的實(shí)現(xiàn)中邏輯門的數(shù)量小于節(jié)點(diǎn)n的最大扇出自由錐的內(nèi)部節(jié)點(diǎn)的數(shù)量，則以節(jié)點(diǎn)n的新的實(shí)現(xiàn)替換掉節(jié)點(diǎn)n的最大扇出自由錐；步驟4、重復(fù)步驟1~步驟3,直至遍歷完邏輯網(wǎng)絡(luò)中的所有目標(biāo)節(jié)點(diǎn)，完成電路尺寸[0008]作為優(yōu)選，所述步驟1中，對收集到的除數(shù)集進(jìn)行精簡操作的方法為：步驟1.1、給定定理，基于該定理將精簡除數(shù)集的問題轉(zhuǎn)換為覆蓋集合的問題，該定理的具體描述如下：定義變量X={x?,X?,…,x。},基于該變量X給定布爾函數(shù)f(X)和初始除數(shù)集{z?,Z?,..,zp},其中p,q為正整數(shù)，該初始除數(shù)集中的p個(gè)除數(shù)都是關(guān)于X的布爾函數(shù)：8?1(X),g?2(X),...,gzn(X),當(dāng)且僅當(dāng)不存在一對最小項(xiàng)(M:,M)使得f(M.)≠8zk(M;),則布爾函數(shù)f(X)被初始除數(shù)集{Z?,Z?,.,z,}重新表達(dá)為f(X)=h(g?1(X),822(X),...,8zp(X)),其中布爾函數(shù)h被定義為依賴函數(shù)；步驟1.2、由節(jié)點(diǎn)n所區(qū)分的最小項(xiàng)對構(gòu)成一個(gè)集合M,從節(jié)點(diǎn)n的初始除數(shù)集中迭代地選擇除數(shù)，在每次迭代中選擇能夠覆蓋集合M中未被覆蓋的最小項(xiàng)對數(shù)量最多的除數(shù)，[0009]作為優(yōu)選，所述步驟2中，使用半張量積計(jì)算節(jié)點(diǎn)n關(guān)于剔除冗余的除數(shù)集的所有可行的依賴函數(shù)的方法為：步驟2.1、將剔除冗余的除數(shù)集記為{d?,d?,..,d},將節(jié)點(diǎn)n的重收斂驅(qū)動(dòng)切割7的q個(gè)葉子節(jié)點(diǎn)記為(x?,X?,..,x。),進(jìn)入步驟2.2,通過結(jié)構(gòu)矩陣描述節(jié)點(diǎn)n以及剔除冗其中mf∈M2×29,m中的每一列f,都是一個(gè)二元列向量，取值于集合mfx?x?…×q=mxm?x?x?…xqm?x?X?…xa…mpx?X?將m?x?X?…xqm?X?X?…xq…mpx?X?…Xq規(guī)范化為myx?X?…Xq,其中my∈M22×24,此時(shí)等式(4)轉(zhuǎn)換為：mfX?X?…xq=mxmyx?X?…由于在計(jì)算節(jié)點(diǎn)n關(guān)于除數(shù)集的所有可行的依賴函數(shù)過程中遇到的每個(gè)矩陣的每fr()=f;(7);輯優(yōu)化方法是一種新的重替換算法，該數(shù)字電路邏輯優(yōu)化方法建立在嚴(yán)密的數(shù)學(xué)框架之8個(gè)葉子節(jié)點(diǎn)x?,X?,X?,x?,收集的除數(shù)為x?,X?,X?,x?,Z5,Z?,Z?,Zg,其中x,X?,X?:0xaaaa,9其中mg∈M2×16,m中的每一列都是一個(gè)二元列向量，取值于集合0mx=[f1f2…f4];mfX?X?X?X4=mxm?x?X?X?X4m?x?將m?X1X?X?X4mzX?XzX3X4規(guī)范化為myX1X?X?X4,其中my∈M?×16,此時(shí)[0016]步驟3、使用開源邏輯綜合工具Espresso進(jìn)行求解，根據(jù)求解結(jié)果從所有可行的依賴函數(shù)中選擇邏輯網(wǎng)絡(luò)實(shí)現(xiàn)規(guī)模較小的一個(gè)依賴函數(shù)。由于本實(shí)施例中節(jié)點(diǎn)n關(guān)于剔除冗余的除數(shù)集的所有可行的依賴函數(shù)是唯一的，并且該依賴函數(shù)的支持大小為3,可以直接對依賴函數(shù)進(jìn)行精確綜合，得到節(jié)點(diǎn)n關(guān)新的實(shí)現(xiàn)。其中，對依賴函數(shù)精確綜合的結(jié)果如圖2所[0017]由于節(jié)點(diǎn)n的新的實(shí)現(xiàn)中邏輯門的數(shù)量為1,小于節(jié)