一種重構高性能目標陣列的方法與流程

2023-10-17 01:49:34 2

本發明涉及重構陣列領域，具體涉及一種重構高性能目標陣列的方法。

背景技術：

處理器雖然能夠通過軟體指令實現不同的算法，可重構處理器利用可重構邏輯器件的動態重構特性，通過不同的配置文件，將特定的指令映射到可重構陣列上運行，由於重構處理器的工作性能通過不同的算法實現，導致工作性能不一，軟體指令無法精確完成。

技術實現要素：

為克服現有技術的不足，本發明公開了一種重構高性能目標陣列的方法，

為實現上述目的本發明採用如下技術方案：

本發明提出了一種重構高性能目標陣列的方法，包括以下步驟：

S1、邏輯列的可滿足性，Bl,Br表示兩條位於大小為m×n的物理陣列中的邏輯列，那麼這兩條邏輯列與物理陣列中的任意一行都存在唯一的交集，且交集中的元素只有一個，其中邏輯列Bl和邏輯列Br之間所有的無故障的處理單元所形成的區域，包括位於邏輯列Bl和邏輯列Br上的正常單元，邏輯列Bl和邏輯列Br分別被稱為這個區域的左邊界和右邊界；

S2、邏輯列重疊區域的可滿足性，邏輯列的產生區域是可以通過左右邊界邏輯列來確定，而邊界邏輯列基於貪心算法得到的，那麼這會造成邏輯列的產生區域之間彼此重疊，形成重疊區域；

S3、可滿足性模型變量約束規則，區域A[Bl,Br]，對於任意的i(1≤i≤m)，已知E′i＝Ri∩A[Bl,Br]，E′i+1＝Ri+1∩A[Bl,Br]，如果對於任意的e(e∈E′i)，都存在對應的e′(e′∈E′i+1)使得col(e)＝col(e′)；對於任意的e′(e′∈E′i+1)，存在對應e(e∈E′i)使得col(e′)＝col(e)，那麼稱E′i和E′i+1是等價的。如果E′i和E′i+1是等價的，那麼E′i+1中的處理單元就不需要使用新的布爾變量來表示，可以使用Ei中的布爾變量來表示，其對應關係如下：對於任意的布爾變量u(u∈Ei)，v(v∈Ei+1)，如果col(u)＝col(v)，u和v則表示同一個布爾變量，並將其稱為變量約束規則；

S4、目標陣列可滿足性模型生成算法，物理陣列的大小為m×n，記為H，Generate_CNF算法能夠根據物理陣列H得出該目標陣列的可滿足性的合取範式F，通過GCR算法和GCR′算法確定物理陣列H中每條邏輯列的邊界；

S5、基於目標陣列可滿足性模型的高性能目標陣列完備算法，物理陣列的大小為m×n，合取範式是Generate_CNF算法根據變量約束和陣列重構的可滿足性約束生成的，那麼合取範式就可以用於描述為目標陣列的可滿足性模型；

S6、基於目標陣列可滿足性模型的高性能目標陣列非完備算法，大小為m×n的物理陣列H，系統對重構的目標陣列的長連結總數的期望值為l，T1和T2是分別表示由GCR算法和GCR算法重構的目標陣列，函數CNF(T1,T2)表示目標陣列的可滿足性模型的合取公式的產生函數，其返回值為可滿足性模型由Generate_CNF算法產生。

優選的，所述步驟1中R1,R2,...,Rm分別表示給定的物理陣列的第一行、第二行、……、第m行，且目標陣列中的行也是從物理行R1,R2,...,Rm中選擇，Bl,Br表示兩條位於大小為m×n的物理陣列中的邏輯列，那麼這兩條邏輯列與物理陣列中的任意一行都存在唯一的交集，且交集中的元素只有一個。

優選的，所述步驟2中假設處理單元e(e∈Ri∩A[Bl,Br]∩A[Bl+1,Br-1])，已知處理單元e在區域A[Bl,Br]中對應的布爾變量為x，處理單元e在區域A[Bl+1,Br-1]中對應的布爾變量x′。

優選的，所述步驟3中對於邏輯列的產生區域A[Bl,Br]，對於任意的i(1≤i≤m)，已知E′i＝Ri∩A[Bl,Br]，E′i+1＝Ri+1∩A[Bl,Br]，如果對於任意的e(e∈E′i)，都存在對應的e′(e′∈E′i+1)使得col(e)＝col(e′)，對於任意的e′(e′∈E′i+1)，也存在對應e(e∈E′i)使得col(e′)＝col(e)，那麼稱E′i和E′i+1是等價的，對於任意的布爾變量u(u∈Ei)，v(v∈Ei+1)，如果col(u)＝col(v)，那麼u和v表示同一個布爾變量，並將其稱為變量約束規則。

優選的，所述步驟4中採用數字作為布爾變量的名字，假設給定的物理陣列的大小為m×n，記為H，Generate_CNF算法能夠根據物理陣列H得出該目標陣列的可滿足性的合取範式F。

優選的，所述步驟5中假設布爾表達式表示根據前面步驟所提到的可滿足性編碼約束規則所得到的目標陣列的合取範式，那麼任何一組關於合取範式的真值指派都有可能是高性能目標陣列，但是在沒有得到合取範式的所有真值指派之前，是沒有辦法確定哪一個或者哪幾個真值指派所表示目標陣列就是高性能目標陣列。

優選的，所述步驟6中假設給定大小為m×n的物理陣列H，系統對重構的目標陣列的長連結總數的期望值為l，T1和T2是分別表示由GCR算法和GCR算法重構的目標陣列，函數CNF(T1,T2)表示目標陣列的可滿足性模型的合取公式的產生函數，其返回值為可滿足性模型由Generate_CNF算法產生。

與現有技術相比，本發明的有益效果是：該重構高性能目標陣列的方法，實驗通過算法CMTA得到的目標陣列的長連結總數(nlis)的值作為GNPTASAT算法中l的初始值，即在實際的實驗中，先計算CMTA算得到的目標陣列的長連結數量，並將該值賦值給GNPTASAT算法中的輸入參數l，GNPTASAT算法至少要找到與CMTA算法求得的目標陣列相互等價的目標陣列時才會終止，極大的提高了重構目標陣列的性能，算法GNPTASAT的精確性優越於算法CMTA和算法DP_GCR，實驗數據證明對於重構高性能的目標陣列具有極大的益處。

具體實施方式

為了使本發明的目的、技術方案及優點更加清楚明白，以下結合具體實施例，對本發明進行進一步詳細說明，此處所描述的具體實施例僅僅用以解釋本發明，並不用於限定本發明。

一種重構高性能目標陣列的方法，包括以下步驟：

S1、邏輯列的可滿足性，Bl,Br表示兩條位於大小為m×n的物理陣列中的邏輯列，那麼這兩條邏輯列與物理陣列中的任意一行都存在唯一的交集，且交集中的元素只有一個，其中邏輯列Bl和邏輯列Br之間所有的無故障的處理單元所形成的區域，包括位於邏輯列Bl和邏輯列Br上的正常單元，邏輯列Bl和邏輯列Br分別被稱為這個區域的左邊界和右邊界；

S2、邏輯列重疊區域的可滿足性，邏輯列的產生區域是可以通過左右邊界邏輯列來確定，邊界邏輯列基於貪心算法得到的，那麼這造成了邏輯列的產生區域之間可能存在彼此重疊，形成重疊區域；

S3、可滿足性模型變量約束規則，區域A[Bl,Br]，對於任意的i(1≤i≤m)，已知E′i＝Ri∩A[Bl,Br]，E′i+1＝Ri+1∩A[Bl,Br]，如果對於任意的e(e∈E′i)，都存在對應的e′(e′∈E′i+1)使得col(e)＝col(e′)，對於任意的e′(e′∈E′i+1)，也存在對應e(e∈E′i)使得col(e′)＝col(e)，那麼稱E′i和E′i+1是等價的，那麼如果E′i和E′i+1是等價的，那麼E′i+1中的處理單元就不需要使用新的布爾變量來表示，可以使用Ei中的布爾變量來表示，其對應如下對於任意的布爾變量u(u∈Ei)，v(v∈Ei+1)，如果col(u)＝col(v)，那麼u和v表示同一個布爾變量，並將其稱為變量約束規則；

S4、目標陣列可滿足性模型生成算法，物理陣列的大小為m×n，記為H，Generate_CNF算法能夠根據物理陣列H得出該目標陣列的可滿足性的合取範式F，通過GCR算法和GCR′算法確定物理陣列H中每條邏輯列的邊界；

S5、基於目標陣列可滿足性模型的高性能目標陣列完備算法，物理陣列的大小為m×n，合取範式是Generate_CNF算法根據變量約束和陣列重構的可滿足性約束生成的，那麼合取範式就可以用於描述為目標陣列的可滿足性模型；

S6、基於目標陣列可滿足性模型的高性能目標陣列非完備算法，大小為m×n的物理陣列H，系統對重構的目標陣列的長連結總數的期望值為l，T1和T2是分別表示由GCR算法和GCR算法重構的目標陣列，函數CNF(T1,T2)表示目標陣列的可滿足性模型的合取公式的產生函數，其返回值為可滿足性模型由Generate_CNF算法產生。

儘管已經示出和描述了本發明的實施例，對於本領域的普通技術人員而言，可以理解在不脫離本發明的原理和精神的情況下可以對這些實施例進行多種變化、修改、替換和變型，本發明的範圍由所附權利要求及其等同物限定。