(19)國家知識產(chǎn)權(quán)局(10)申請公布號CN120218011A(71)申請人寧波大學(xué)地址315211浙江省寧波市江北區(qū)風(fēng)華路818號(72)發(fā)明人儲著飛汪艷珍邱成楷夏銀水王倫耀(74)專利代理機(jī)構(gòu)寧波奧圣專利代理有限公司專利代理師謝瀟(54)發(fā)明名稱一種GPU加速的基于矩陣半張量積的電路仿真方法本發(fā)明公開了一種GPU加速的基于矩陣半張量積的電路仿真方法，包括步驟：解析電路信息并轉(zhuǎn)換成半張量積矩陣；將電路中的節(jié)點表示為矩陣鏈表達(dá)式；隨機(jī)選定一個節(jié)點，對其矩陣鏈表達(dá)式進(jìn)行規(guī)范化處理；引入半張量積矩陣編碼方法和CUDA并行計算架構(gòu)進(jìn)行GPU加速，得到矩陣鏈表達(dá)式的運算結(jié)果；提取臨時真值表，將臨時真值表中的數(shù)值按照變量的排列順序進(jìn)行對應(yīng)位置的交換，得到該節(jié)點的實際真值表，提取出該節(jié)點的仿真信息；重復(fù)上述步驟，得到電路性能最優(yōu)的半張量積電路仿真器的仿真方法，本發(fā)明電路仿真方法在計算速度方面提升了約7.79倍。SS011711117106011031015110100040100101130011600102001040001110012000001000022.根據(jù)權(quán)利要求1所述一種GPU加速的基于矩陣半張量積的電路仿真方法，其特征在于，將所述步驟1中轉(zhuǎn)換得到的半張量積矩陣記為M,其滿足如下公式(1或(5):3.根據(jù)權(quán)利要求1所述一種GPU加速的基于矩陣半張量積的電路仿真方法，其特征在34.根據(jù)權(quán)利要求3所述一種GPU加速的基于矩陣半張量積的電路仿真方法，其特征在1的變量移到矩陣鏈表達(dá)式的最右邊，并計算出所有邏輯矩陣和所有變量矩陣進(jìn)行半張量5.根據(jù)權(quán)利要求1所述一種GPU加速的基于矩陣半張量積的電路仿真方法，其特征在陣A∈M(m×n)編碼為一個形如[x(0),x(1),...,x(n)]的行向量X,其中x(0)的值等于m,表示矩陣A的行數(shù)，而根據(jù)半張量積矩陣中每一列中只有一個元素為1、其余元素都為0的特6.根據(jù)權(quán)利要求1所述一種GPU加速的基于矩陣半張量積的電路仿真方法，其特征在4技術(shù)領(lǐng)域[0001]本發(fā)明涉及計算機(jī)技術(shù)領(lǐng)域，具體涉及一種GPU加速的基于矩陣半張量積的電路仿真方法。背景技術(shù)[0002]快速高效的邏輯仿真器是現(xiàn)代邏輯綜合工具的關(guān)鍵組成部分，在組合電路等價性驗證、技術(shù)無關(guān)優(yōu)化中的等價類分類和重映射函數(shù)提取等任務(wù)中發(fā)揮著重要作用。隨著電路規(guī)模的增長，仿真執(zhí)行時間變得越來越關(guān)鍵。此外，隨著先進(jìn)技術(shù)的發(fā)展，邏輯綜合中涌輯仿真方法將具備更好的可擴(kuò)展性。[0003]近年來，電路仿真方法的發(fā)展與邏輯綜合領(lǐng)域緊密交織，尤其在提升設(shè)計效率、優(yōu)化算法以及整合智能化技術(shù)方面取得了顯著進(jìn)展。為了滿足大規(guī)模電路仿真的需求，現(xiàn)有方法在降低計算復(fù)雜度方面取得了顯著進(jìn)展，例如利用稀疏矩陣求解和模型降階技術(shù)。例如，KLU算法能夠加速矩陣求解并顯著減少門級網(wǎng)表仿真時間。此外，并行計算和異構(gòu)硬件加速(如GPU和FPGA)使得矩陣計算可以分布式執(zhí)行，從而進(jìn)一步提高仿真速度。盡管取得了這些進(jìn)展，但一個關(guān)鍵瓶頸仍然存在：傳統(tǒng)仿真方法難以充分利用矩陣?yán)碚摰挠嬎銉?yōu)勢，因為邏輯表示與矩陣表示之間存在鴻溝。[0004]近年來，基于半張量積(Semi-TensorProduct,STP)的仿真方法在邏輯電路建模、狀態(tài)空間分析和自動設(shè)計優(yōu)化領(lǐng)域受到了廣泛關(guān)注。STP作為一種數(shù)學(xué)工具，通過將布爾邏輯運算轉(zhuǎn)化為矩陣操作，能夠高效處理高維邏輯系統(tǒng)，為復(fù)雜電路的分析與綜合提供了新的思路。利用STP仿真方法的核心優(yōu)勢在于，它將邏輯函數(shù)表示為矩陣，并通過矩陣乘法執(zhí)行布爾運算。這種方法能夠高效處理高維系統(tǒng)，但隨著電路規(guī)模的增長，會導(dǎo)致指數(shù)級的內(nèi)存開銷。內(nèi)部矩陣的持續(xù)擴(kuò)展不僅會引發(fā)內(nèi)存短缺問題，還會導(dǎo)致計算時間顯著增加。發(fā)明內(nèi)容[0005]為了解決STP在邏輯綜合應(yīng)用時因矩陣規(guī)模過大而效率低下甚至無法計算的問題，本發(fā)明提供一種在保證仿真結(jié)果正確的情況下在速度方面提升明顯的GPU加速的基于矩陣半張量積的電路仿真方法，該方法極大地提高了電路仿真效率。[0006]本發(fā)明解決上述技術(shù)問題所采用的技術(shù)方案為：一種GPU加速的基于矩陣半張量步驟1、解析蘊含電路信息的bench文件，定義數(shù)據(jù)集mtx用來表示bench文件中各節(jié)點之間的關(guān)系，并將電路信息轉(zhuǎn)換成半張量積矩陣；步驟2、按照電路中的節(jié)點之間的關(guān)系，并根據(jù)表示電路信息的半張量積矩陣，將電路中的節(jié)點表示為由數(shù)據(jù)集mtx和電路原始輸入PI組成的矩陣鏈表達(dá)式；步驟3、隨機(jī)選定bench文件中的一個節(jié)點，對該節(jié)點表示的矩陣鏈表達(dá)式進(jìn)行規(guī)范化處理，得到規(guī)范化的矩陣鏈表達(dá)式；5臨時真值表中的數(shù)值按照變量的排列順序進(jìn)行對應(yīng)位置的交換，得到該節(jié)點的實際真值[0007]作為優(yōu)選，將所述步驟1中轉(zhuǎn)換得到的半張量積矩陣記為M,其滿足如下公式(1)運算“與”、“或”、“蘊含”和“等價”。6量為1的變量移到矩陣鏈表達(dá)式的最右邊，并計算出所有邏輯矩陣和所有變量矩陣進(jìn)行半為m×n的邏輯矩陣A∈M(m×n)編碼為一個形如[x(0),x(1),...,x(n)]的行向量X,其中x矩陣的半張量積計算和常規(guī)矩陣乘法的特點，將規(guī)范化的矩陣鏈表達(dá)式中的矩陣分布在7附圖說明圖4為本發(fā)明方法進(jìn)行規(guī)范化處理得到的矩陣鏈表達(dá)式；示為“?”。如果A∈M(m×n)且B∈M(p×q),其定義式為,其中aj表示矩陣A的第i行第j列的元素。通過克羅內(nèi)克積可以將兩個維度不匹配的矩陣膨脹到節(jié)點之間的關(guān)系，并將電路信息轉(zhuǎn)換成半張量積矩(4)或(5):8[0017]步驟2、按照電路中的節(jié)點之間的關(guān)系，并根據(jù)表示電路信息的半張量積矩陣，將電路中的節(jié)點表示為由數(shù)據(jù)集mtx和電路原始輸入PI組成的矩陣鏈表達(dá)式，如圖2中的(b)所示。[0018]步驟3、隨機(jī)選定bench文件中的一個節(jié)點，對該節(jié)點表示的矩陣鏈表達(dá)式進(jìn)行規(guī)步驟3.1、現(xiàn)有的半張量積規(guī)范型是將所有變量直接移至矩陣鏈表達(dá)式的最右邊，然后按照變量的排序，通過插入交換矩陣交換變量之間的位置，同時用降冪矩陣將變量降冪，得到的結(jié)果如圖3所示；區(qū)別于現(xiàn)有的半張量積規(guī)范型，我們在矩陣鏈表達(dá)式中找到第一個變量的第一個同名變量，并確定第一個同名變量的位置，之后從第一個同名變量的位置往后查找第二個同名變量，若查找到第二個同名變量，則在矩陣鏈表達(dá)式中刪除第一個同名變量，同時在第二個同名變量前的位置插入降冪矩陣Mr,進(jìn)入步驟3.2;若未查找到第二個同名變量，則重復(fù)上述操作，直至在矩陣鏈表達(dá)式中找到某一個變量的第一個同名變量和第二個同名變量，進(jìn)入步驟3.2;步驟3.2、處理同一個變量的第一個同名變量和第二個同名變量之間的矩陣，根據(jù)半張量積的偽交換性，若該矩陣是邏輯矩陣，對于與單位矩陣進(jìn)行克羅內(nèi)克積的邏輯矩陣，將該單位矩陣的維度乘2,若邏輯矩陣前沒有單位矩陣與其進(jìn)行克羅內(nèi)克積的運算，則在邏輯矩陣前增加維度為2的單位矩陣I2;若該矩陣是變量矩陣，則在矩陣鏈表達(dá)式的中間插入換位矩陣Mw;步驟3.3、重復(fù)步驟3.1~步驟3.2,直到矩陣鏈表達(dá)式中沒有同名變量之后，即所有變量在矩陣鏈表達(dá)式中的數(shù)量均為1之后，按照現(xiàn)有的半張量積規(guī)范型的過程，將所有的數(shù)量為1的變量移到矩陣鏈表達(dá)式的最右邊，并計算出所有邏輯矩陣和所有變量矩陣進(jìn)行半張量積的最終結(jié)果，得到如圖4所示的規(guī)范化的矩陣鏈表達(dá)式。[0019]圖4中，第一行為合并同名變量得到的結(jié)果，第二行為將所有的數(shù)量為1的變量移到矩陣鏈表達(dá)式的最右邊的最終結(jié)果。將圖4中第二行的結(jié)果與圖3對比，可以明顯看出，采用本發(fā)明方法后，最大的單位矩陣維度從32減小為8,極大地縮小了在計算時的矩陣維度，避免進(jìn)行過大規(guī)模的矩陣計算。[0020]步驟4、引入半張量積矩陣編碼方法，其編碼規(guī)則為：將一個維度為m×n的邏輯矩陣A∈M(m×n)編碼為一個形如[x(0),x(1),...,x(n)]的行向量X,其中x(0)的值等于m,表示矩陣A的行數(shù)，而根據(jù)半張量積矩陣中每一列中只有一個元素為1、其余元素都為0的特積矩陣編碼方法的示例。對于一個維度為m×n的邏輯矩陣A∈M(m×n)來說，采用本發(fā)明方法引入的半張量積矩陣編碼方法編碼后的矩陣可以完全包含原矩陣的全部信息，并且空間復(fù)雜度縮小了n倍。[0021]矩陣運算是一個常見的計算密集型任務(wù)，通過將矩陣分割成小塊或子矩陣，不僅可以優(yōu)化內(nèi)存使用，減少重復(fù)數(shù)據(jù)訪問，還可提高內(nèi)存帶寬的利用率和計算的并行度，這使得GPU成為執(zhí)行大規(guī)模矩陣乘法的理想選擇。而STP計算過程中存在大量的矩陣運算如克羅內(nèi)克積和常規(guī)矩陣乘法，這使得STP計算成為GPU友好型計算，利用多核心來分布式的計算STP可以有效提升計算速度，引入GPU可以有效的降低電路仿真所需的時間。因此，在上述編9分布在GPU的多個線程進(jìn)行半張量積矩陣并行運算，根據(jù)矩陣鏈表達(dá)式中的矩陣的行列數(shù)，動態(tài)地在GPU內(nèi)部的基本單元之間分配子矩陣計算任務(wù)，進(jìn)行半張量積矩陣并行運算，得到矩陣鏈表達(dá)式的運算結(jié)果，該運算結(jié)果表示為一個邏輯矩陣，根據(jù)半張量積的運算特性，該運算結(jié)果表示的邏輯矩陣的第一行數(shù)值表示的即為步驟3中隨機(jī)選定的節(jié)點的真值表。上述GPU加速方法可提高STP計算過程的效率。在克羅內(nèi)克積運算和矩陣乘法等大規(guī)模矩陣運中的所有矩陣稀疏度較高，采用編碼可以極大減少內(nèi)存和GPU開辟的線程數(shù)；另一方面，參與運算的矩陣都具有一定特性，而傳統(tǒng)的矩陣壓縮方式(如CSR、CO0等)不能很好地體現(xiàn)這些特性。所以我們提出將矩陣編碼后用GPU進(jìn)行STP計算，這種方法更具有內(nèi)存和速度上的[0022]步驟5、提取該運算結(jié)果表示的邏輯矩陣的第一行數(shù)值作為臨時真值表，獲取臨時真值表中不同變量的權(quán)重，計算臨時真值表中的數(shù)值與不同變量的權(quán)重的對應(yīng)關(guān)系，并將臨時真值表中的數(shù)值按照變量的排列順序進(jìn)行對應(yīng)位置的交換，得到該節(jié)點的實際真值表，根據(jù)實際真值表提取出該節(jié)點的仿真信息。[0023]步驟5的具體過程為：提取該運算結(jié)果表示的邏輯矩陣的第一行數(shù)值作為臨時真值表，獲取臨時真值表中的每個變量與該臨時真值表中原始變量的位置的二進(jìn)制關(guān)系，之后對于每個變量按照給定的索引進(jìn)行重新排列，再根據(jù)排列后的變量順序，將臨時真值表中的數(shù)值按照所述二進(jìn)制關(guān)系進(jìn)行排序，最終得到與現(xiàn)有的半張量積規(guī)范型的計算結(jié)果相同的真值表。[0024]通過本發(fā)明步驟5的方法，直接通過臨時真值表和變量的對應(yīng)關(guān)系重新排列得到最終結(jié)果，避免了復(fù)雜的矩陣運算，大大節(jié)省了資源的消耗。通過上述步驟5的方法得到的臨時真值表和最終得到的真值表見圖6,圖6中，左表為交換前的臨時真值表，右表為交換后a、b、c分別代表變量x1、x2、x3交換后得到的真值表結(jié)果，該交換后得到的有的半張量積規(guī)范型的計算結(jié)果相同。[0025]步驟6、重復(fù)步驟3~步驟5,直至遍歷完bench文件中的所有節(jié)點，獲取整個bench文件的仿真信息，即得到電路仿真結(jié)果。[0026]目前性能最優(yōu)的半張量積電路仿真器的仿真方法為LS(H.Pan,R.Zhang,Y.Xia,L.Wang,F.Yang,X.Zeng,andZ.Chu,"Asemi-tensorproductcircuitsimulationforsat-sweeping,"in2024Design,Autom真方法(即有GPU的方法)以及不進(jìn)行GPU加速的方法(即無GPU的方法，該方法與本發(fā)明電路仿真方法的區(qū)別在于未采用GPU加速)進(jìn)行性能測試，測試這三種電路仿真方法對不同測試案例的仿真時間。三種電路仿真方法的性能測試對比結(jié)果見表一。由表一可知，相比于目前性能最優(yōu)的半張量積電路仿真器的仿真方法，本發(fā)明所提出的GPU加速的基于矩陣半張量積的電路仿真方法在計算速度方面提升了約7.79倍。CN120218011A測試案例LS(秒)無GPU的方法(秒)有GPU的方法(秒)11=MnMMnMcI?MnI?MI?MnI?McI=MnMMnMcI?MnI?MI?M