一種減少流處理器片上指令存儲器資源消耗的方法

2023-05-31 21:26:46 1

專利名稱：一種減少流處理器片上指令存儲器資源消耗的方法
技術領域：
本發明涉及減少晶片中指令存儲器資源消耗的方法，尤其指一種減少流處理器片上 指令存儲器資源消耗的方法。
背景技術：
基於流體系結構的流處理器是新一代面向密集計算的高性能微處理器的典型代表， 專門面向流應用。流應用主要分為兩類 一類是媒體應用；另一類是科學計算。流應用 具有以下幾個主要特徵計算密集性，與傳統的桌面應用相比，流式應用對每次從內存 取出的數據都要進行大量的算術運算；並行性，以數據級並行為主，同時存在指令級和 任務級並行；局域性，是指應用中的數據重用局域性。流應用程式通常包含kernel級程 序和流級程序兩部分流級程序負責組織輸入和輸出數據，kernel程序是運算的核心，負 責對這些數據進行運算。
由於流處理器中多以超長指令字(VLIW: Very Long Instruction Word)的方式組織指 令來開發指令級並行，這種結構使得流處理器指令存儲器的寬度很大(因為指令存儲器 每行至少要能容納1條VLIW);另一方面，流處理器的片上指令存儲器大多採用軟體靜 態管理的方式，存儲空間的分配以kernel為粒度，因此，指令存儲器必須有能力同時容 納多個kernel,這使得流處理器指令存儲器的深度很大。對寬度和深度的要求直接導致指 令存儲器的容量增加，從而使得其在晶片中佔用的面積比例增加。如Imagine中核心指 令存儲器的面積佔晶片面積的10%， MASA中核心指令存儲器佔晶片面積的26。/。。編譯 器靜態調度指令碼的管理方式保證了指令存儲器能為計算單元高效地提供指令，然而以 kernel為調度粒度使得在kernel的生命周期中，存在大量的無效指令或不常使用指令長時 間佔用指令存儲空間。這增加了指令存儲器的資源消耗，即增加了構建存儲器所需的硬 件存儲單元的消耗。
對於超長指令字結構的處理器，減少指令存儲器資源消耗主要有指令壓縮、分布式 指令存儲器和指令生命周期分析優化等方法。指令壓縮是通過某種編碼算法對指令碼進 行壓縮，減少指令碼的長度，從而降低指令碼對存儲空間的需求。由於應用程式中有限 的指令級並行使得VLIW中不可避免的含有很多空操作，該方法最大的問題是將壓縮後 的指令還原時會引入額外的指令流出延遲。分布式指令存儲器是將VLIW存儲器分割為多個窄的指令存儲器，每個存儲器分別與一個計算功能單元對應，當VLIW中對應的功 能單元出現空操作時，與該功能單元對應的指令存儲器則可以不存儲指令，從而可以減 少指令存儲空間的需求。這是一種採用修改存儲器硬體結構設計來壓縮指令的方法，它 的主要問題是由於不同應用對各功能單元的需求不同，使得VLIW中空操作出現的比例 不同，會造成部分功能單元對應的局部指令存儲器不夠用，而另一部分指令存儲器則有 多餘的現象。此方法與前一種方法類似，都是通過橫向壓縮指令來減少指令對存儲空間 的需求，從而減少存儲器資源消耗。指令生命周期分析優化是通過縮短指令佔據存儲器 的時間來降低應用程式對存儲空間的需求，從而可通過減少總的存儲容量來減少存儲器 的資源消耗。該方法主要是通過分析程序的局域性，預測程序中各部分指令的生命周期， 通過編譯器控制指令導入存儲器的時機，並指導各指令在其生命周期結束後及時的釋放 存儲空間，從而儘量縮短指令佔據存儲器的時間，在縱向上壓縮指令來減少指令存儲器 的資源消耗。該方法過分依賴軟體編譯器的能力，若編譯器預測錯誤，則會造成程序性 能極為低下。

發明內容
本發明要解決的技術問題是提供一種減少流處理器片上指令存儲器資源消耗的方 法。該方法基於現有成熟的硬體存儲器結構，增加少量的指令讀取延遲，不增加複雜的 編譯算法，能有效的減少指令存儲器的資源消耗。
本發明的方案是將流處理器中純軟體管理的指令存儲器修改為軟硬體混合指令存
儲器，根據流應用中kernel程序的特徵，定義kernel熱代碼；根據kernel熱代碼的定義， 得到三個判定kernel熱代碼的定理；在編譯器中增加kernel熱代碼查找模塊，由kernel 熱代碼査找模塊根據三個判定定理査找流應用中的kernel熱代碼；採用軟體管理靜態存 儲器存儲kernel熱代碼以保證其高命中率，採用硬體管理的cache存儲其他指令，通過 縮短指令佔用指令存儲器的時間來減少程序對存儲空間的需求，從而可以縮減總存儲容 量，從而減少指令存儲器的資源消耗。 本發明技術方案是
為說明本發明技術方案，先給出如下定義和定理
定義1:循環LOOP1是循環LOOP2的外層循環，若LOOP2不失效能保證80%以上 的LOOP1指令不失效，則稱LOOP2是LOOP1的熱代碼。
定義2:如果kernel中某個循環的所有指令不失效能保證kernel中最外層循環80% 以上的指令不失效，則稱這個循環是"kernel熱代碼"，稱kernel中其他指令為"kernel涼代碼"。
在kernel中，最外層循環之外的指令在整個kernel的執行過程中只會執行一次，而 對於沒有預取功能的指令存儲器來說，這些指令都存在不可避免的強制失效，即在首次 使用這些指令(也是唯一的一次)時，它們沒有裝載進指令存儲器中而引發的失效。而 對於循環內部的指令，由於它們都需要被反覆多次執行，若指令存儲器有足夠的能力捕 捉其時間局域性，即存儲器有足夠的容量或高效的替換策略使得它們在反覆執行的過程 中一直存於存儲器中，那麼就能極大保證循環內部指令的命中率，從而提高整個kernel 的命中率。因此，kernel熱代碼定義主要考慮了 kernel最外層循環內指令的命中率，而忽 略外層循環之外的指令的影響，在指令存儲器的硬體設計中再對外層循環之外的指令進 行優化。
根據熱代碼和kernel熱代碼的定義，得到判定熱代碼的三個定理。 定理1:循環LOOP1長度為LI ， LOOP2長度為L2，循環次數為C2， LOOP1是LOOP2 的外層循環。若滿足(CW(L2/L0〉4，貝lj LOOP2是LOOP1的"熱代碼"。
證明考慮最壞的情況存儲器僅有能力捕捉LOOP2的時間局域性，而完全不能捕 捉LOOPl的時間局域性。也就是說，每次LOOPl執行一次新的循環時，LOOP1中的所 有指令都會失效一次，即LOOP1每開始一輪新循環，其中LOOP2的第一遍循環會全部 失效，但本次LOOPl的循環中LOOP2的後續循環將全部命中。可以計算出，在這種情 況下，LOOP1的失效指令數(Ml, Miss Instructions)和失效率(MR， Miss Rate)分別 為
Ci[Zi +- "] d[l + ^(C2 —1)]
若LOOP2在LOOP1每一輪新循環中都存在強制失效的情況下，都能保證LOOP1 的命中率大於80%，那麼LOOP2的指令不失效就更加能保證80%以上的LOOP1指令不 失效，艮卩LOOP2是LOOPl的熱代碼。因此有如下推導
LOOP2是LOOP1的熱代碼G 1 — AO > 80%
formula see original document page 8formula see original document page 9
定理2: LOOPl是kernel中的最外層循環，若LOOPl沒有熱代碼，則LOOPl是kernel 熱代碼；若LOOP2是LOOPl的熱代碼，則LOOP2為kernel熱代碼。 證明由定義1和定義2顯然得證。
由於kernel結構不同，在進行kernel熱代碼分析時，多層循環嵌套進行kernel熱代 碼分析比較複雜。因此，提出三層循環嵌套的kernel熱代碼判定定理-
定理3 (三層嵌套循環kernel熱代碼判定定理)LOOPl、 LOOP2、 LOOP3是kernel 中的由外到內三層嵌套循環，Ll、 L2、 L3分別為三個循環的長度，Cl、 C2、 C3分別為 對應的循環次數。LOOP3是kernel熱代碼，若且唯若命題1和命題2同時成立 命題l: LOOP3是LOOP2的熱代碼；
丄一
命題2: _k_*c2>~^^其中/7 = ~~AC2(C3-1)_ (h表示當LOOP3 丄i一丄2 125 —丄 C2(^2—A) + ^3C3C2
一S
中指令的不失效時，LOOP2的最低命中率)； 證明
1. 若LOOP3不是LOOP2的熱代碼，也就是說，LOOP3指令不失效時，LOOP2的 命中率小於80%，那麼LOOP2的外層循環LOOP1的命中率會更低，從而可知LOOP3 不是kernel熱代碼；
2. 若LOOP3是LOOP2的熱代碼，LOOP1的最低命中率(HR， HitRate)為
服=_zag(c廣i)_formula see original document page 9A —丄 C2(￡2 — i3) + ￡3C3C2 丄2 3
丄、—+丄
。i z 1 i——f>80%
, 丄-i
/ - /2 1
丄i厶2 1.25 _丄
本發明最多只對3層嵌套循環進行kernel熱代碼分析，因為kernel作為流應用中的 計算核心，通常不會含有多層循環嵌套的程序結構。3層嵌套循環的情況已經很少見，多 於3層循環的kernel基本上沒有。對於超過3層循環的kernel也按照3層循環的情況來 處理。
本發明的具體步驟是
第一步，將流處理器中純軟體管理的指令存儲器修改為軟硬體混合指令存儲器。軟 硬體混合指令存儲器由軟體管理靜態存儲器和硬體管理的cache兩部分組成。設計方法 如下
l丄軟體管理靜態存儲器與地址產生控制器、片外存儲器和計算簇相連，它從片外存 儲器獲得程序中的kernel熱代碼，即流控制器根據從地址產生控制器獲得的寫地址將各 kernel熱代碼由片外存儲器寫入軟體管理靜態存儲器；程序執行時，軟體管理靜態存儲器 給計算簇提供數據，即計算簇根據地址產生控制器中的讀地址從軟體管理靜態存儲器中 讀取kernel熱代碼。
軟體管理靜態存儲容量設定為流處理器中原有的靜態指令存儲器容量的一半。通過 查找典型應用中的kernel熱代碼，發現kernel熱代碼量通常為原程序指令代碼量的一半 左右，所以靜態指令存儲器的容量減小為原來容量的一半。
1.2.硬體管理的cache是一個直接映射的經典cache,包括存儲體、Tag存儲器和cache 控制器三個部分，它從片外存儲器獲得程序中的kernel涼代碼。
存儲體與cache控制器、片外存儲器和計算簇相連。存儲體從片外存儲器獲得程序 中的kernel涼代碼，即流控制器將kernel涼代碼從片外存儲器寫入cache控制器指定的 存儲體的地址；程序執行時，硬體管理的cache向計算簇提供kernel涼代碼，即計算簇根據cache控制器產生的kernel涼代碼的讀地址，從存儲體中讀取kernel涼代碼。
Tag存儲器與cache控制器相連。在kernel涼代碼導入存儲體時，cache控制器根據 涼代碼中指令的寫地址解析出對應的Tag位和Tag存儲器寫地址，根據Tag存儲器寫地 址將Tag位寫入Tag存儲器；在計算簇從存儲體中讀取kernel涼代碼中的指令時，cache 控制器根據指令讀地址解析出與其對應的Tag存儲器讀地址，根據該讀地址從Tag存儲 器讀取對應Tag位。
cache控制器與地址產生控制器、Tag存儲器和存儲體相連。當計算簇從存儲體讀取 指令時，cache控制器從地址產生控制器獲取指令讀地址，根據指令讀地址解析出存儲體 讀地址、指令對應的Tag位和Tag存儲器讀地址。根據存儲體讀地址從存儲體中讀出指 令，根據Tag存儲器讀地址從Tag存儲器中讀取對應的Tag位。將指令對應的Tag位與 從Tag存儲器中讀出的Tag位進行比較，若二者相等，則表示cache命中，存儲體中讀取 的指令有效；若二者不相等，則表示cache失效，存儲體中讀取的指令無效。cache控制 器中包含一個硬體預取部件，當cache失效時，硬體預取部件向片外存儲器發cache取指 令請求，請求將失效指令以及失效指令後續的若干條指令(即涼代碼) 一併寫入存儲體。 硬體預取有很多種方式，最常見的是採用cache行預取，即一次cache寫操作寫入一個 cache行， 一個cache行內包含多條指令。當cache取指令請求被片外存儲器響應後，地 址產生控制器將cache寫地址送入cache控制器，cache控制器根據指令寫地址解析出該 指令對應的存儲體寫地址、Tag存儲器寫地址和指令對應的Tag位，根據存儲體寫地址將 指令寫入存儲體，根據Tag存儲器寫地址將Tag位寫入Tag存儲器。
硬體管理的cache的存儲體大小通常為2的整數次冪(cache訪問地址是由片外存儲 器地址截位而得，所以2的整數次冪方便地址變換)。因為kernel大小一般不會超過1024 條VUW， kernel涼代碼通常不會超過kernel大小的一半，所以存儲體的容量通常為512 條VLIW。若流處理器是專門面向某類應用，也可以根據該類應用的特徵對其容量進行 定製。
第二步，在編譯器中增加kernel熱代碼查找模塊，由kernel熱代碼査找模塊查找kernel 熱代碼。對於含有n個kernel的應用程式，kernel熱代碼査找模塊的流程是 2丄令i的初始值為1;
2.2.提取第i個kernel中各層循環的長度和除最外層循環外所有循環的循環次數，即 "、L2、 L3、 C2、 C3的值。
Lj、 L2和L3的值為由外到內三層循環的長度，由編譯器通過解析循環指令的循環跳轉的範圍得到，C2、 C3為第二、第三層的循環次數，其值根據應用的特徵而定。在流應 用中，循環的次數與輸入數據流的長度密切相關。對於典型的流應用(如視頻編碼、圖 像搜索等)，輸入流的大小在絕大多數情況下是可預知的(如一幀圖像的大小是確定的)， 因此C2、 C3的值通過kernel的輸入流的長度除以每次循環處理數據的個數來確定。在極 少數特殊應用中，少數kernel的輸入流的不定長會造成<:2或<:3不可預知。對Cz或C3 不可預知的情況要分別進行處理；
2.3.若C2不可預知，標記第一層循環為kernel熱代碼，轉步驟2.5;若(32可預知但 C3不可預知，轉步驟2.4;若C2和C3都可預知，利用定理3判斷第三層循環是否為kernel 熱代碼，方法如下
計算P屍(C3-1)氣L3/L2)、 P2=~^*C2、 丄3(C廣1)
丄-i
1.25」
/7
則將第三層循環標記為kernel熱代碼，轉步驟2.5;否則轉
步驟2.4;
2.4.利用定理1和定理2査找kernel熱代碼，方法如下
計算P氣CW(L2/L0;
若P〉4，則將第二層循環標記為kernel熱代碼，轉步驟2.5;否則標記第一層循環為
kernel熱代碼，轉步驟2.5;
2.5.i=i+l，若i〉n，則kernel熱代碼查找完畢，轉入第三步；否則轉步驟2.2。 第三歩，在流級編譯時，在各個kernel熱代碼之前添加指令流加載指令，該指令通
常為如下格式
浙e鵬丄o^/〈啟動瓶若泣巖成#丄位魔長度潛爭源關;^> 啟動標誌位表示該指令是否已經啟動， 一般0表示未啟動，l表示已啟動；完成標誌 位表示該指令是否已經完成， 一般0表示未完成，l表示已完成。起始地址和流長度信息 指定了 kernel熱代碼在軟體管理靜態存儲器中的空間分配；指令相關性包含了本條指令 與它之前其他指令的相關性信息，當所有相關性都得到滿足，本條指令流加載指令才能 被啟動執行，也就是說，指令相關性確定了 kernel熱代碼導入軟體管理靜態存儲器的時 機。
第四步，將應用程式裝載到軟硬體混合指令存儲器，啟動程序運行，程序運行過程
12如下
4丄令j的初始值等於l;
4.2. 査詢第j個kernel的kernel熱代碼對應的指令流加載指令的狀態，若啟動標誌位 為未啟動則轉步驟4.3;若己啟動但完成標誌位指示為未完成則轉步驟4.5;若完成標誌 位為已完成則轉步驟4.6;
4.3. 判斷第j個kernel的kernel熱代碼對應的指令流加載指令的指令相關性是否滿 足，若滿足則轉步驟4.4,否則程序執行終止，輸出"系統異常"。
當輪到第j個kernel執行時，它的kernel熱代碼對應的指令流加載指令的相關性必 須得到滿足，這是由編譯器保證的。若得不到滿足，則表示出現了系統異常。
4.4. 啟動第j個kernel的指令流加載指令，修改該指令的啟動標誌位為已啟動。由地 址產生控制器執行該指令流加載指令，獲取軟體管理靜態存儲器起始地址和指令流的長 度，將第j個kernel的kernel熱代碼從外部存儲器寫入軟體管理靜態存儲器；
4.5. 等待第j個kernel的kernel熱代碼寫入軟體管理靜態存儲器，當第j個kernel的 kernel熱代碼全部寫入軟體管理靜態存儲器，將第j個kernel的指令流加載指令的完成標 志位修改為已完成；
4.6. 令k=j+l，啟動第j個kernel運行，執行步驟4.7 4.8;同時導入後續kernel的 kernel熱代碼，執行步驟4.9 4.11;
在第j個kernel執行時，同時導入後續kernel的kernel熱代碼，實現計算和存儲操 作的重疊執行，從而提高程序執行的效率。
4.7. 若l^n，轉步驟4.12;若k^n，判斷第k個kernel的kernel熱代碼對應的指令流 加載指令的指令相關性是否滿足，若滿足則啟動第k個kernel的指令流加載指令，修改 該指令的啟動標誌位為已啟動，轉步驟4.8;若不滿足則直接轉步驟4.8;
4.8. k=k+l;轉步驟4.7;
4.9. 若第j個kernel執行完畢，轉步驟4.12;否則執行步驟4.10;
4.10. 根據地址產生控制器中的地址訪問軟硬體混合指令存儲器。若地址產生控制器 中的地址是軟體管理靜態存儲器的地址，則計算簇從軟體管理靜態存儲器中讀取對應的 指令；若是硬體管理的cache地址，則轉步驟4.11;
4.11. 若cache失效，則硬體預取部件請求從片外存儲器中加載涼代碼，寫入硬體管 理的cache;若cache命中，計算簇從硬體管理的cache存儲體中讀取對應的指令；轉步 驟4.9;4.12Jon且第j個kernel執行完畢，轉步驟4.13，否則轉步驟4.12; 4.13.j=j+l;若j〉n，則程序執行結束；否則轉步驟4.2。
採用本發明可以達到以下技術效果
1. 採用硬體管理的cache存儲當前執行kernel的kernel涼代碼，相對於純軟體管理的 指令存儲器，減少了其他非活躍kernel (非當前執行的kernel)的涼代碼對存儲空間的長 期佔用，從而減少了存儲器容量的需求，減少了指令存儲器在晶片中的面積消耗；
2. 本發明採用硬體管理的cache存儲當前執行kernel的kernel涼代碼，並通過硬體預 取等方法提高了涼代碼的命中率。這是因為程序有順序執行的特性，當某條指令被執行 之後，若不出現跳轉指令，則後續指令肯定被執行。因此，當某條指令發生失效，將其 後續的若干條指令一併取入cache中，可以減少後續指令失效。由於流處理器中運算單 元很多，分支操作通常會被轉化為選擇操作執行，即將分支操作的兩條路徑都執行，然 後對根據分支條件對二者的結果進行選擇。這樣減少了流應用程式中的跳轉指令；另外， kernel涼代碼中的循環跳轉要遠少於整個kernel中的循環跳轉，因此在cache中增加硬體 預取功能對提高kernel的命中率有明顯的效果。
3. 本發明採用軟體管理靜態存儲器保證了 kernel熱代碼不失效，帶預取功能的硬體管 理的cache提高了涼代碼的命中率，從而保證了整個kernel指令的高命中率；對kernel 熱代碼和kernel涼代碼的分別存儲減少了非活躍kernel的涼代碼對存儲空間的長期佔用， 從而減少了存儲器容量的需求；因此，本發明在保證指令高命中率的情況下降低了對指 令存儲器容量的需求，從而提高了指令存儲器的利用率，減少了存儲器的資源消耗。


圖l是本發明總體流程圖。
圖2是本發明第一步設計的軟硬體混合指令存儲器結構圖。
圖3是本發明第二步對含有n個kernel的應用程式kernel熱代碼査找方法流程圖。 圖4是本發明第四步採用本發明時含n個kernel的應用程式運行過程示意圖。 圖5是本發明指令在存儲器中空間佔用示意圖。 圖6是採用本發明後kernel運行時間及指令存儲器資源消耗比較。
具體實施例方式
圖l是本發明的總體流程圖。
第一步，將流處理器中純軟體管理的指令存儲器修改為軟硬體混合指令存儲器。軟 硬體混合指令存儲器由軟體管理靜態存儲器和硬體管理的cache兩部分組成。如圖2所7K。
第二步，在編譯器中增加kernel熱代碼查找模塊，由kernel熱代碼查找模塊査找kernel 熱代碼，査找方法流程如圖3所示。
第三步，在流級編譯時，在各個kernel熱代碼之前添加指令流加載指令。 第四步，將程序指令裝載到軟硬體混合指令存儲器，啟動程序運行。程序運行過程 和軟硬體混合指令存儲器讀/寫操作的流程如圖4所示。
圖2是本發明第一步設計的軟硬體混合指令存儲器結構圖。設計方法如下 l丄軟體管理靜態存儲器與地址產生控制器、片外存儲器和計算簇相連，它從片外存 儲器獲得程序中的kernel熱代碼，即流控制器根據從地址產生控制器獲得的寫地址將各 kernel熱代碼由片外存儲器寫入軟體管理靜態存儲器；程序執行時，軟體管理靜態存儲器 給計算簇提供數據，即計算簇根據地址產生控制器中的讀地址從軟體管理靜態存儲器中 讀取kernel熱代碼。
軟體管理靜態存儲容量設定為流處理器中原有的靜態指令存儲器容量的一半。通過 査找典型應用中的kernel熱代碼，發現kernel熱代碼量通常為原程序指令代碼量的一半 左右，所以靜態指令存儲器的容量減小為原來容量的一半。
1.2.硬體管理的cache是一個直接映射的經典cache,包括存儲體、Tag存儲器和cache 控制器三個部分。
存儲體與cache控制器、片外存儲器和計算簇相連。存儲體從片外存儲器獲得程序 中的kernel涼代碼，即流控制器將kernel涼代碼從片外存儲器寫入cache控制器指定的 存儲體的地址；程序執行時，硬體管理的cache向計算簇提供kernel涼代碼，即計算簇 根據cache控制器產生的kernel涼代碼的讀地址，從存儲體中讀取kernel涼代碼。
Tag存儲器與cache控制器相連。在kernel涼代碼導入存儲體時，cache控制器根據 涼代碼中指令的寫地址解析出對應的Tag位和Tag存儲器寫地址，根據Tag存儲器寫地 址將Tag位寫入Tag存儲器；在計算簇從存儲體中讀取kernel涼代碼中的指令時，cache 控制器根據指令讀地址解析出與其對應的Tag存儲器讀地址，根據該讀地址從Tag存儲 器讀取對應Tag位。
cache控制器與地址產生控制器、Tag存儲器和存儲體相連。當計算簇從存儲體讀取 指令時，cache控制器從地址產生控制器獲取指令讀地址，根據指令讀地址解析出存儲體 讀地址、指令對應的Tag位和Tag存儲器讀地址。根據存儲體讀地址從存儲體中讀出指 令，根據Tag存儲器讀地址從Tag存儲器中讀取對應的Tag位。將指令對應的Tag位與從Tag存儲器中讀出的Tag位進行比較，若二者相等，則表示cache命中，存儲體中讀取 的指令有效；若二者不相等，則表示cache失效，存儲體中讀取的指令無效。cache控制 器中包含一個硬體預取部件，當cache失效時，硬體預取部件向片外存儲器發cache取指 令請求，請求將失效指令以及失效指令後續的若干條指令一併寫入存儲體。硬體預取有 很多種方式，最常見的是採用cache行預取，即一次cache寫操作寫入一個cache行，一 個cache行內包含多條指令。當cache取指令請求被片外存儲器響應後，地址產生控制器 將cache寫地址送入cache控制器，cache控制器根據指令寫地址解析出該指令對應的存 儲體寫地址、Tag存儲器寫地址和指令對應的Tag位，根據存儲體寫地址將指令寫入存儲 體，根據Tag存儲器寫地址將Tag位寫入Tag存儲器。
硬體管理的cache的存儲體大小通常為2的整數次冪(cache訪問地址是由片外存儲 器地址截位而得，所以2的整數次冪方便地址變換)。因為kernel大小一般不會超過1024 條VLIW， kernel涼代碼通常不會超過kernel大小的一半，所以存儲體的容量通常為512 條VLIW。若流處理器是專門面向某類應用，也可以根據該類應用的特徵對其容量進行 定製。
圖3是本發明第二步對含有n個kernel的應用程式kernel熱代碼査找方法流程圖。。 對於含有n個kernel的應用程式，kernel熱代碼查找模塊的流程是 2丄令i的初始值為1;
2.2. 提取第i個kernel中各層循環的長度和除最外層循環外所有循環的循環次數，即 Li、 L2、 L3、 C2、 C3的值。
L2和L3的值為由外到內三層循環的長度，由編譯器通過解析循環指令的循環跳 轉的範圍得到，C2、 C3為第二、第三層的循環次數，其值根據應用的特徵而定。在流應 用中，循環的次數與輸入數據流的長度密切相關。對於典型的流應用(如視頻編碼、圖 像搜索等)，輸入流的大小在絕大多數情況下是可預知的(如一幀圖像的大小是確定的)， 因此C2、 C3的值通過kernel的輸入流的長度除以每次循環處理數據的個數來確定。在極 少數特殊應用中，少數kernel的輸入流的不定長會造成C2或C3不可預知。對<:2或<:3 不可預知的情況要分別進行處理；
2.3. 若C2不可預知，標記第一層循環為kernel熱代碼，轉步驟2.5;若C2可預知但 C3不可預知，轉步驟2.4;若C2和C3都可預知，利用定理3判斷第三層循環是否為kernel 熱代碼，方法如下計算P屍(CrlHL3/L2)、 P2:
*C, 、
(丄2—Z3) + ￡3C:
若P!>4且P2>
，則將第三層循環標記為kernel熱代碼，轉步驟2.5;否則轉
步驟2.4;
2.4.利用定理1和定理2査找kernel熱代碼，方法如下
計算P-((W(L2/Lj);
若P〉4，則將第二層循環標記為kernel熱代碼，轉步驟2.5;否則標記第一層循環為 kernel熱代碼，轉步驟2.5;
i=i+l，若i〉n，則kernel熱代碼查找完畢，轉入第三步；否則轉步驟2.2。 圖4是本發明第四步採用本發明時含n個kernel的應用程式運行過程示意圖。 4丄令j的初始值等於l;
4.2. 查詢第j個kernel的kernel熱代碼對應的指令流加載指令的狀態，若啟動標誌位 為未啟動則轉步驟4.3;若已啟動但完成標誌位指示為未完成則轉步驟4.5;若完成標誌 位為已完成則轉步驟4.6;
4.3. 判斷第j個kernel的kernel熱代碼對應的指令流加載指令的指令相關性是否滿 足，若滿足則轉步驟4.4，否則程序執行終止，輸出"系統異常"。
當輪到第j個kernel執行時，它的kernel熱代碼對應的指令流加載指令的相關性必 須得到滿足，這是由編譯器保證的。若得不到滿足，則表示出現了系統異常。
4.4. 啟動第j個kernel的指令流加載指令，修改該指令的啟動標誌位為已啟動。由地 址產生控制器執行該指令流加載指令獲取軟體管理靜態存儲器起始地址和指令流的長 度，將第j個kernel的kernel熱代碼從外部存儲器寫入軟體管理靜態存儲器；
4.5. 等待第j個kernel的kernel熱代碼寫入軟體管理靜態存儲器，當第j個kernel的 kernel熱代碼全部寫入軟體管理靜態存儲器，將第j個kernel的指令流加載指令的完成標 志位修改為已完成；
4.6. 令k,+l，啟動第j個kernel運行，執行步驟4.7 4.8;同時導入後續kernel的 kernel熱代碼，執行步驟4.9 4.11;
在第j個kernel執行時，同時導入後續kernel的kernel熱代碼，實現計算和存儲操 作的重疊執行，從而提高程序執行的效率。4.7. 若k>n，轉步驟4.12;若k^n，判斷第k個kernel的kernel熱代碼對應的指令流 加載指令的指令相關性是否滿足，若滿足則啟動第k個kernel的指令流加載指令，修改 該指令的啟動標誌位為己啟動，轉步驟4.8;若不滿足則直接轉步驟4.8;
4.8. k=k+l;轉步驟4.7;
4.9. 若第j個kernel執行完畢，轉步驟4.12;否則執行步驟4.10;
4.10. 根據地址產生控制器中的地址，訪問軟硬體混合指令存儲器。若地址產生控制 器中的地址是軟體管理靜態存儲器的地址，則計算簇從軟體管理靜態存儲器中讀取對應 的指令；若是硬體管理的cache地址，則轉步驟4.11;
4.11. 若cache失效，則啟動硬體預取機制，從片外存儲器中加載涼代碼，寫入硬體 管理的cache;若cache命中，計算簇從硬體管理的cache存儲體中讀取對應的指令；轉 步驟4.9;
4.12. k〉n且第j個kernel執行完畢，轉步驟4.13，否則轉步驟4.12;
4.13. j=j+l;若j〉n，則程序執行結束；否則轉步驟4.2。
圖5是本發明指令在存儲器中空間佔用示意圖。左圖是指令在現有大多數流處理器 採用的純軟體指令存儲器中的空間佔用示意圖，右圖是指令在本發明的軟硬體混合指令 存儲器中空間佔用示意圖。可以看出，在純軟體指令存儲器中，多個kernel的所有指令 都同時存儲於指令存儲器中，所有的kernel涼代碼在kernel的整個生命周期中都會一直 佔用存儲空間，直到kernel結束才會釋放存儲空間。由於kernel涼代碼在kernel的整個 生命周期中很少被訪問，這使得指令存儲器的利用率降低。在本發明的軟硬體混合指令 存儲器中，kernel熱代碼都存儲於軟體管理靜態存儲器，以保證其命中率。硬體管理的 cache中只存儲當前執行kernel的kernel涼代碼，這種設計減少了 kernel涼代碼對片上指 令存儲器存儲空間的佔用，減少了應用對存儲器容量的需求，減少了存儲器的資源消耗。
圖6是採用本發明後kernel運行時間及指令存儲器資源消耗比較。以MASA流處理 器為平臺，分別採用本發明軟硬體混合管理指令存儲器、純軟體管理靜態存儲器和純硬 件管理的cache作為指令存儲器，比較6個應用程式在這三種結構下kernel運行時間及 指令存儲器資源消耗。純軟體管理的靜態存儲器和純硬體管理的cache容量都為2048條 VLIW，本發明的存儲器容量由兩部分組成軟體管理靜態存儲器為1024條VLIW,硬 件管理的cache為512條VLIW，比純軟體管理的靜態存儲器和純硬體管理的cache的容 量小512條VLIW。
分別採用上述三種存儲器作為MASA流處理器的指令存儲器，將RS、 SUSAN、LUCAS、 Ygx2、 MPEG和H264等六個應用程式分別在MASA流處理器上執行，統計個 應用程式的執行時間，並將所有的執行時間對釆用純軟體管理靜態存儲器作為指令存儲 器的MASA的執行時間進行歸一操作，即所有的執行時間都除以在純軟體管理的靜態存 儲器下對應的執行時間，得到如圖6中的柱狀圖。.
利用HP公司公布的存儲器評測軟體cacti獲得三種存儲器的資源消耗，並將所有資 源消耗值對採用純軟體管理靜態存儲器作為指令存儲器的資源消耗進行歸一操作，得到 如圖6中的折線圖。
可以看出，採用本發明，雖然有些應用的執行時間增加了少許，但指令存儲器的資 源消耗減少了很多。
權利要求
1.一種減少流處理器片上指令存儲器資源消耗的方法，其特徵在於包括以下步驟第一步，將流處理器中純軟體管理的指令存儲器修改為軟硬體混合指令存儲器，軟硬體混合指令存儲器由軟體管理靜態存儲器和硬體管理的cache兩部分組成，設計方法如下1.1.軟體管理靜態存儲器與地址產生控制器、片外存儲器和計算簇相連，它從片外存儲器獲得程序中的kernel熱代碼，並在程序執行時給計算簇提供數據；1.2.硬體管理的cache包括存儲體、Tag存儲器和cache控制器三個部分，它從片外存儲器獲得程序中的kernel涼代碼；第二步，在編譯器中增加kernel熱代碼查找模塊，kernel熱代碼查找模塊的流程是2.1.令i的初始值為1；2.2.由編譯器通過解析循環指令的循環跳轉的範圍得到第i個kernel中由外到內三個循環的長度L1、L2、L3，根據應用的特徵確定第二、第三層的循環次數C2、C3當kernel的輸入流的大小預知時，C2、C3的值通過輸入流的長度除以每次循環處理數據的個數來確定；當kernel的輸入流不定長時C2或C3不可預知；2.3.若C2不可預知，標記第一層循環為kernel熱代碼，轉步驟2.5；若C2可預知但C3不可預知，轉步驟2.4；若C2和C3都可預知，判斷第三層循環是否為kernel熱代碼，方法是計算P1＝(C3-1)*(L3/L2)、<![CDATA[ P 2= L2 L 1- L 2 * C 2 ]]> top= "179" left = "135"/>、<![CDATA[ h= L 3 ( C3 - 1 ) ( L2 - L3 )+ L 3 C 3 , ]]> top= "198" left = "24"/>若P1＞4且<![CDATA[ P 2> 1 h-1 1.25- 1 h , ]]> top= "193" left = "84"/>則將第三層循環標記為kernel熱代碼，轉步驟2.5；否則轉步驟2.4；2.4.查找kernel熱代碼，方法是計算P＝(C2-1)*(L2/L1)，若P＞4，則將第二層循環標記為kernel熱代碼，轉步驟2.5；否則標記第一層循環為kernel熱代碼，轉步驟2.5；2.5.i＝i+1，若i＞n，n為應用程式中含有的kernel個數，轉第三步；否則轉步驟2.2；第三步，在流級編譯時，在各個kernel熱代碼之前添加指令流加載指令，該指令格式為StreamLoad啟動標誌位 完成標誌位 起始地址 流長度 指令相關性啟動標誌位表示該指令是否已經啟動，完成標誌位表示該指令是否已經完成，起始地址和流長度信息指定了kernel熱代碼在軟體管理靜態存儲器中的空間分配，指令相關性包含了本條指令與它之前其他指令的相關性信息，當所有相關性都得到滿足，本條指令流加載指令才能被啟動執行；第四步，將應用程式裝載到軟硬體混合指令存儲器，啟動程序運行，程序運行過程和軟硬體混合指令存儲器讀/寫操作的流程如下4.1.令j的初始值等於1；4.2.查詢第i個kernel的kernel熱代碼對應的指令流加載指令的狀態，若未啟動則轉步驟4.3，若未完成則轉步驟4.5，若已完成則轉步驟4.6；4.3.判斷kernel j的kernel熱代碼對應的指令流加載指令的相關性是否滿足，若滿足則轉步驟4.4，否則程序執行終止，輸出「系統異常」；4.4.啟動第j個kernel的指令流加載指令，修改該指令的啟動標誌位為已啟動，由地址產生控制器執行該指令流加載指令，獲取軟體管理靜態存儲器起始地址和指令流的長度，將第j個kernel的kernel熱代碼從外部存儲器寫入軟體管理靜態存儲器；4.5.等待第j個kernel的kernel熱代碼寫入軟體管理靜態存儲器，當第j個kernel的kernel熱代碼全部寫入軟體管理靜態存儲器，將第j個kernel的指令流加載指令的完成標誌位修改為已完成；4.6.令k＝j+1，啟動第j個kernel運行，執行步驟4.7～4.8；同時導入後續kernel的kernel熱代碼，執行步驟4.9～4.11；4.7.若k＞n，轉步驟4.12；若k≤n，判斷第k個kernel的kernel熱代碼對應的指令流加載指令的指令相關性是否滿足，若滿足則啟動第k個kernel的指令流加載指令，修改該指令的啟動標誌位為已啟動，轉步驟4.8；若不滿足則直接轉步驟4.8；4.8.k＝k+1；轉步驟4.7；4.9.若第j個kernel執行完畢，轉步驟4.12；否則執行步驟4.10；4.10.若地址產生控制器中的地址是軟體管理靜態存儲器的地址，則計算簇從軟體管理靜態存儲器中讀取對應的指令；若是硬體管理的cache地址，則轉步驟4.11；4.11.若cache失效，則硬體預取部件請求從片外存儲器中加載涼代碼，寫入硬體管理的cache；若cache命中，計算簇從硬體管理的cache存儲體中讀取對應的指令，轉步驟4.9；4.12.k＞n且第j個kernel執行完畢，轉步驟4.13，否則轉步驟4.12；4.13.j＝j+1；若j＞n，則程序執行結束；否則轉步驟4.2。
2. 如權利要1所述的一種減少流處理器片上指令存儲器資源消耗的方法，其特 徵在於所述軟體管理靜態存儲容量設定為流處理器中原有的靜態指令存儲器 容量的一半。
3. 如權利要1所述的一種減少流處理器片上指令存儲器資源消耗的方法，其特 徵在於如果kernel中某個循環的所有指令不失效能保證kernel中最外層循環 80%以上的指令不失效，則這個循環為kernel熱代碼，kernel中其他指令為 kernel涼代碼。
4. 如權利要1所述的一種減少流處理器片上指令存儲器資源消耗的方法，其特 徵在於所述硬體管理的cache中的存儲體與cache控制器、片外存儲器和計算 簇相連，存儲體從片外存儲器獲得程序中的kernel涼代碼，並在程序執行時 向計算簇提供kernel涼代碼；Tag存儲器與cache控制器相連，在kernel涼代 碼導入存儲體時，cache控制器根據涼代碼中指令的寫地址解析出對應的Tag 位和Tag存儲器寫地址，根據Tag存儲器寫地址將Tag位寫入Tag存儲器； 在計算簇從存儲體中讀取kernel涼代碼中的指令時，cache控制器根據指令讀 地址解析出與其對應的Tag存儲器讀地址，根據該讀地址從Tag存儲器讀取 對應Tag位；cache控制器與地址產生控制器、Tag存儲器和存儲體相連，當 計算簇從存儲體讀取指令時，cache控制器從地址產生控制器獲取指令讀地 址，根據指令讀地址解析出存儲體讀地址、指令對應的Tag位和Tag存儲器 讀地址，根據存儲體讀地址從存儲體中讀出指令，根據Tag存儲器讀地址從 Tag存儲器中讀取對應的Tag位；將指令對應的Tag位與從Tag存儲器中讀出的Tag位進行比較，若二者相等，則表示cache命中，存儲體中讀取的指 令有效；若二者不相等，則表示cache失效，存儲體中讀取的指令無效；cache 控制器中包含一個硬體預取部件，當cache失效時，硬體預取部件向片外存 儲器發cache取指令請求，請求將失效指令以及失效指令後續的若干條指令 一併寫入存儲體；當cache取指令請求被片外存儲器響應後，地址產生控制 器將cache寫地址送入cache控制器，cache控制器根據指令寫地址解析出該 指令對應的存儲體寫地址、Tag存儲器寫地址和指令對應的Tag位，根據存 儲體寫地址將指令寫入存儲體，根據Tag存儲器寫地址將Tag位寫入Tag存 儲器。
全文摘要
本發明公布了一種減少流處理器片上指令存儲器資源消耗的方法，要解決的技術問題基於現有成熟的硬體存儲器結構，不增加複雜的編譯算法，有效減少指令存儲器的資源消耗。技術方案是將流處理器中純軟體管理的指令存儲器修改為軟硬體混合指令存儲器；在編譯器中增加kernel熱代碼查找模塊，根據判定熱代碼的定理查找流應用中的kernel熱代碼；且在流級編譯時，在各個kernel熱代碼之前添加指令流加載指令；採用軟體管理靜態存儲器存儲kernel熱代碼以保證其高命中率，採用硬體管理的cache存儲其他指令，通過縮短指令佔用指令存儲器的時間來減少指令存儲器對存儲器容量的需求，從而可以減少指令存儲器的容量。採用本發明能減少指令存儲器在晶片中的資源消耗。
文檔編號G06F9/38GK101620526SQ200910043828
公開日2010年1月6日 申請日期2009年7月3日 優先權日2009年7月3日
發明者巨 任, 楠 伍, 義 何, 偉 吳, 張春元, 梅 文, 李京旭, 楊乾明, 俊 柴, 管茂林, 荀長慶 申請人:中國人民解放軍國防科學技術大學