一種利用剩餘資源分配寄存器的方法

2023-06-26 06:06:51 2

專利名稱：：一種利用剩餘資源分配寄存器的方法
技術領域：
：本發明涉及高性能處理器中寄存器的分配方法，尤其是採用分布式寄存器文件結構的VLIW處理器中利用剩餘資源分配寄存器的方法。技術背景指令級並行(InstructionLevelParallelism,ILP)是指為了實現多個操作的並行執行而在處理器和編譯器的設計中採用的一系列技術。超長指令字(VeryLongInstructionLevel,VLIW)技術是一種重要的常用指令並行技術，通常VLIW對應多運算單元的處理器體系結構，相應的處理器晶片包括高性能的DSP例如TMS320C6x，方興未艾的流處理器如Imagine,Merrimac,FT64和一些專用處理器Equator'sMAP1000等。其中Imagine包含48個多功能浮點ALU,分成8組每組6個ALU;Merrimac包含80個全功能的浮點ALU,分成16組每組5個ALU,組內的ALU緊密耦合，再加上load/store等功能單元，這對組內寄存器容量和帶寬要求極高，傳統的集中式寄存器文件不能滿足要求，因而這些處理器全部採用分布式寄存器文件結構。採用分布式寄存器文件結構的處理器體系結構中採用分布式的多個寄存器文件代替原來集中式的單一寄存器文件，且所有的功能單元組成的功能單元陣列通常被劃分成多個組，每個組由若千功能單元組成，包括計算型功能單元如加法單元和非計算型功能單元如load"tore單元等。每個功能單元與1至3個本地寄存器文件連接，本地寄存器文件的讀埠直接與對應功能單元的輸入埠連接，每個功能單元只能從其對應的本地寄存器文件中讀取操作數。所有寄存器文件的寫埠同所有功能單元的輸出埠之間通過交叉開關網絡連接，數據可以在不同寄存器文件間通信傳輸。交叉開關網絡保證了每個功能單元的輸出埠通過一個交叉點開關可以無阻塞地與一個空閒的寄存器文件寫埠相連，所有的寄存器文件和功能單元間可以同時傳輸數據。採用分布式寄存器文件的處理器大多面向計算密集型應用，這些應用由於計算的密集性高、並行性好，寄存器文件負載嚴重，從而造成溢出(spill)訪存(由於某個功能單元的寄存器文件被填滿，數據不得不存入存儲器而造成.的存儲器訪問)。而這些處理器性能對存儲器訪問非常敏感，相對於較長的存儲器訪問時間而言，寄存器的極低的存取時間使得它成為一類關鍵的處理器資源。在一些處理器如Imagine中為了優化訪存採用了軟體管理的多級存儲層次，溢出訪存甚至被禁止，一旦寄存器分配失敗，必須由程式設計師修改程序，這給程式設計師帶來很大麻煩，同時還會極大地降低程序性能。因此在採用分布式寄存器文件結構的VLIW處理器中如何減輕分布式寄存器文件壓力，減少溢出訪存是本領域技術人員一直關注的技術難題。
發明內容本發明要解決的技術問題是在採用分布式寄存器文件結構的處理器中，利用剩餘資源分配寄存器，減輕寄存器文件負載，減少溢出訪存。本發明的技術方案是在VLIW的指令調度、通信調度和寄存器預分配完成後，全局統籌分布式寄存器文件負載，使用"負載平移"技術，利用分布式寄存器文件之間負載分配的不均衡，將某個寄存器文件的溢出數據平移到其它未滿的寄存器文件中，當需要時再存回原寄存器文件。本發明包括以下五個步驟第一步，構建剩餘網絡在所有的處理器資源(包括互連總線，寄存器文件，功能單元)都已經分配完畢後，根據編譯器自動生成的對處理器資源的分配表，生成對應的VLIW的調度時空圖，圖中包含所有的指令分配和資源分配的時空關係。將圖中已使用的資源去掉，得到資源分配的剩餘網絡。具體方法是每個時鐘周期，若某個功能單元己被某個操作佔用，將該功能單元從時空圖中刪除；若某個寄存器文件已滿或者寫埠已被佔用，將該寄存器文件及其寫埠從時空圖中刪除；若某條總線已被用來傳輸數據，將該總線從時空圖中刪除，則剩下的時空圖就是剩餘網絡。剩餘網絡標示了指令調度和通信調度後所有的空閒資源，包括功能單元、互連開關、本地寄存器文件。第二步，選擇平移變量為便於說明，令Tup、Tdown:對於某個溢出的寄存器文件，一般只是某一段時間區域內需要用的寄存器數量超過該寄存器文件所能提供的寄存器總量。這一段時間區域成為溢出區間，其起點和終點分別稱為溢出區間的上界、下界。Tup為溢出區間上界，Tdown為溢出區間下界。Toverflow:溢出區間內的任一時刻稱為溢出時刻。Tproduce:變量生命周期起點。Tlastuse:變量生命周期結束點。Tout:將平移變量從源寄存器文件移出的指令周期。Tearly:溢出時刻之前被選擇變量最後一次被使用的時刻，若未被使用，Tearly=Tproduc"Tsbegin、Tsend:平移變量的生命周期割裂的起止時刻(平移變量在移出時，生命周期暫時結束，移回時生命周期又繼續，因此在這段時間，其生命周期處於被割裂狀態)。Tuse:平移變量在溢出時刻之後第一次使用的時刻。Tback:將平移變量向源寄存器文件移回的指令周期。對於溢出的寄存器文件，平移出其溢出區間中的任何變量都可以減輕寄存器壓力，反覆平移多個變量後可使寄存器不溢出。對於任一溢出時刻Toverflow，凡是Tproduce《Toverflow且ToverflowToverflow的條件，移回才有意義。移回時刻可以選擇[Toverflow+1,Tuse]中的任意時刻(Tuse為平移變量在溢出時刻之後第一次使用的時刻)，越靠後被割裂出的生命周期越長。選擇移回功能單元、移回埠移回功能單元、移回埠是指在移回時刻將平移變量從移出目的寄存器文件送到互聯開關的功能單元及其埠，在這裡選擇與移出目的寄存器文件的讀埠直接相連的功能單元以及輸出埠作為移回功能單元、移回埠。確定移回互連開關通路移回互連開關通路是指移回功能單元同源寄存器文件間的開關總線通路，取決於處理器的硬體拓撲結構。採用編譯器原有的通信調度算法即可確定移回互連開關通路。平移路徑的選擇過程就是在剩餘網絡中尋找和選擇移出時刻、移出埠、移出功能單元、移出互連開關、移出目的寄存器文件、移回時刻、移回功能單元、移回互連開關、移回埠，構成一條完整的變量平移迴路，上述元素缺一不可。第四步，在平移路徑中插入copy操作，並指定copy操作的輸入輸出。具體方法是由編譯器在移出功能單元的操作序列中插入一條copy操作，變量產生時不存到需要使用的寄存器文件中，由copy操作直接從變量產生的時刻獲取數據，將變量保存在其它寄存器文件中，在變量需要使用之前與溢出時刻之後將其移回需要使用的源寄存器文件。變量在源寄存器文件中的生命周期變為[Tback，Tlastuse]。若在該變量的產生時刻，移出目的寄存器文件的輸入埠不可用，則在溢出時刻與產生時刻之間插入第二條copy操作，由源寄存器文件所對應的功能單元完成。這條copy操作從變量產生的位置取得數據，變量同樣存放在原來需要使用的寄存器文件中。第一條copy操作從第二條copy操作的輸出獲取數據。設第二條copy操作的輸入時刻為Tincopy2，此時將變量在源寄存器文件中的生命周期分割為兩段，[Tproduce，Tincopy2]禾Q[Tback，Tlastuse]。第五步，對均衡後的寄存器文件重新採用染色圖寄存器分配方法進行分配採用染色圖寄存器分配方法，對發生變化的寄存器文件進行重分配，如果仍然有分配失敗，則返回第一步重新構建剩餘網絡，進行新的負載平移，直到所有的寄存器分配成功或者無法平移為止。採用本發明可以達到以下技術效果1)對於重負載的計算密集型應用，有效避免寄存器分配失敗的問題。在VLIW調度後期通過溢出調度均衡各寄存器文件的負載，減輕分布式寄存器文件壓力，能夠大幅避免單個寄存器文件的溢出，從而使得寄存器分配成功。2)從單個寄存器文件來看，變量的生命周期被割裂，數據暫時存放在其它寄存器文件中，以保證本寄存器文件有足夠的空間存放本地數據；從整個分布式寄存器文件來看，變量的生命周期沒有縮短，從一個寄存器文件移出的數據保存在其它未滿的寄存器文件中，保證不必重新計算而免除增加新的負擔。由於是利用VLIW調度後的剩餘網絡進行負載平移的操作，因此本方法不會帶來性能上的開銷，是無損的。圖1是採用分布式寄存器文件的VLIW處理器系統結構圖；圖2是本發明的總體流程圖；圖3是剩餘網絡構建示意圖；其中圖3.1是VLIW調度時空圖，圖3.2是剩餘網絡；圖4是平移變量選取示意圖；圖5是平移路徑選取示意圖；其中圖5.1是對變量c進行平移的完整平移路徑，圖5.2是進行一次負載平移調度後的VLIW調度時空圖；圖6是平移前後變量的生命周期圖；其中圖6.1是負載平移前的變量生命周期圖，圖6.2是負載平移後的變量生命周期圖。具體實施方式圖1是採用分布式寄存器文件的VLIW處理器系統結構圖。處理器中包含多個運算簇，每個運算簇中含有多個多功能浮點ALU，每個ALU採用了分布式寄存器文件，擁有多個本地寄存器文件。本地寄存器文件的讀埠直接與對應ALU的輸入埠連接，每個ALU只能從自己的本地寄存器文件中讀取操作數。所有寄存器文件的寫埠同所有ALU的輸出埠之間通過交叉開關網絡連接，使得數據可以在不同寄存器文件間通信傳輸。交叉開關網絡保證了每個功能單元ALU的輸出埠通過一個交叉點可以無阻塞地與一個空閒寄存器文件寫埠相連，所有的寄存器文件和ALU間可以同時傳輸數據。圖2是本發明總體流程圖。在寄存器分配失敗後，首先構建剩餘網絡，然後選擇平移變量，再對選定的平移變量選擇合適的平移路徑，並在平移路徑中插入copy操作，然後重新進行寄存器分配，如果成功則結束，否則返回重新構建剩餘網絡，進行新的負載平移直到寄存器分配成功為止。圖3是剩餘網絡構建示意圖。在所有的處理器資源(包括互連總線，寄存器，功能單元)都已經分配完畢後，可以抽取出如圖3.1所示的調度時空圖，圖中包含了所有的指令分配和資源分配的時空關係在第一個指令周期，ADDO對應的寄存器文件存放變量a、b，ADD0執行操作e=a+b，結果e通過輸出埠、總線存放到ADD2對應的寄存器文件中；ADD1對應的寄存器文件存放變量e，ADD1執行操作c=e+e，結果c通過輸出埠、總線存放到ADDO對應的寄存器文件中；ADD2及其對應的寄存器文件空閒；第二個指令周期和第三個指令周期類似。將圖中已使用的資源(斜線部分)去掉，得到如圖3.2所示的剩餘網絡。剩餘網絡標示了VLIW調度後所有的空閒資源，包括ALU、互連開關、本地寄存器文件在第二個指令周期，ADD1禾卩ADD2空閒，ADD1對應的寄存器文件有可用空間、且輸入埠空閒；ADD2對應的寄存器文件有可用空間；有空閒總線。第一個指令周期和第三個指令周期類似。圖4是平移變量選取示意圖。如圖所示，第一次選擇平移變量時，令溢出區間上界Tup=4為溢出時刻Toverflow，根據前文所述平移變量選取方法，變量b的最近前使用距離為4-2=2，最近後使用距離為n-l-4-n-5，取C1二1，C2=2,P-最近前使用距離+2乂最近後使用距離，b的權值為2n-8。同理計算每個變量的平移權值得tableseeoriginaldocumentpage11c、d兩變量在溢出時刻要被使用，因此不能被選作平移變量。因此選擇c變量作為首先平移變量，如果c不能成功依次選取e，a。對於圖3中所示的例子而言，ADDO對應的寄存器文件中，在溢出時刻即第二個指令周期，a、b兩變量都要被使用，不能被選作移出變量，只能選擇變量c作為移出變量。圖5是平移路徑選取圖。在剩餘網絡中，根據前文所述選取平移路徑的方法，為移出變量c尋找平移路徑和插入copy操作的結果如圖5.1所示。在第一個指令周期，變量c直接從產生它的功能單元ADD1的輸出埠通過總線存放到ADD1對應的寄存器文件中去；在第二個指令周期，插入copy操作，由ADD1執行，copy操作從ADDl對應的寄存器文件中獲取變量c，通過ADD1的輸出埠、總線存放到ADDO對應的寄存器文件中。圖5.2是進行一次負載平移調度後的VLIW調度時空圖。原來的將變量c在產生時直接存放到ADD0對應的寄存器文件的路徑被改變為變量c通過copy操作暫時存放在ADD1對應的寄存器文件中去，然後再存回ADD0對應的寄存器文件。圖6是平移前後變量的生命周期圖。圖6.1是平移前變量的生命周期圖，在圖3所示的例子中，所有的寄存器文件容量為2，而在第2個指令周期，ADDO對應的寄存器文件需要同時存放三個變量a、b、c，寄存器溢出，而此時ADD1和ADD2對應的寄存器文件未滿；圖6.2是平移後變量的生命周期圖，變量c通過平移在第二個指令周期存放到ADD1對應的寄存器文件中，在第三個指令周期再存回ADD0對應的寄存器文件，所有的寄存器文件最多同時存放2個變量，寄存器分配成功。權利要求1.一種利用剩餘資源分配寄存器的方法，其特徵在於包括以下步驟第一步，構建剩餘網絡，方法是在所有的互連總線、寄存器文件、功能單元這樣的處理器資源都已經分配完畢後，根據編譯器自動生成的對處理器資源的分配表，生成對應的VLIW的調度時空圖，圖中包含所有的指令分配和資源分配的時空關係，將圖中已使用的資源去掉，得到資源分配的剩餘網絡，具體方法是每個時鐘周期，若某個功能單元已被某個操作佔用，將該功能單元從時空圖中刪除；若某個寄存器文件已滿或者寫埠已被佔用，將該寄存器文件及其寫埠從時空圖中刪除；若某條總線已被用來傳輸數據，將該總線從時空圖中刪除，則剩下的時空圖就是剩餘網絡；第二步，選擇平移變量，方法是令變量的平移權值P＝C1×最近前使用距離+C2×最近後使用距離，其中C1和C2是啟發式參數；最近前使用距離是指在溢出時刻Toverflow之前，變量最後一次被使用的時刻與溢出時刻的距離；最近後使用距離是指在溢出時刻Toverflow之後，變量第一次被使用的時刻與溢出時刻的距離；選擇平移變量的方法是依次選取平移權值最大的變量，若最大平移權值的變量沒有找到平移路徑，則選取平移權值第二大的變量，依此類推；第三步，選擇正確的平移路徑，方法是假定所選擇的變量生命周期為[Tproduce，Tlastuse]，Tproduce是變量生命周期起點，Tlastuse是變量生命周期結束點；平移路徑的物理通路由以下元素來描述移出時刻，移出功能單元，移出埠，移出互連開關通路，移出目的寄存器文件，移回時刻，移回功能單元，移回互連開關通路，移回埠；選擇平移路徑的過程就是在剩餘網絡中尋找和選擇移出時刻、移出埠、移出功能單元、移出互連開關、移出目的寄存器文件、移回時刻、移回功能單元、移回互連開關、移回埠，構成一條完整的變量平移迴路，包括以下步驟a.選擇移出時刻移出時刻選擇[Tproduce，Toverflow]中的任意時刻，越靠前對目的寄存器文件影響越小；b.選擇移出功能單元、移出埠在移出時刻，將變量v送到互連開關的功能單元就是移出功能單元，移出埠是指變量移出需要佔用移出功能單元的輸出埠；當移出時刻某個功能單元的輸出埠的輸出變量是選定的平移變量v時，選擇該功能單元及其輸出埠作為移出功能單元、移出埠；有兩種情況移出功能單元、移出埠是可用的，一是功能單元是源寄存器文件對應的功能單元，且移出時刻該功能單元的輸出埠是空閒的，這時在該功能單元插入一條v＝copy(v)操作，使得其輸出埠的輸出變量為v；二是在移出時刻恰好有某個功能單元的輸出埠輸出v，這時不用插入任何操作；c.確定移出互連開關通路移出互連開關通路是指移出功能單元同目的寄存器文件間的開關總線通路，採用編譯器原有的通信調度算法即可確定移出互連開關通路；d.選擇移出目的寄存器文件移出目的寄存器文件是指平移變量v移出源寄存器文件後用來暫時存放變量v的寄存器文件，適合的目的寄存器文件應滿足兩個條件空閒寄存器和空閒的寫入埠；寄存器文件的剩餘空間和寫入埠通過查尋剩餘網絡獲知，可能有多個滿足條件的移出目的寄存器文件，按照如下規則構成優先選擇隊列選擇在移出時刻寫入埠空閒且有剩餘可用空間的寄存器文件，按照其可用的剩餘空間多少排隊；e.選擇移回時刻移回時刻是指將平移變量向源寄存器文件移回的指令周期Tback，Tback＞Toverflow；移回時刻選擇[Toverflow+1，Tuse]中的任意時刻，Tuse為平移變量在溢出時刻之後第一次使用的時刻；f.選擇移回功能單元、移回埠移回功能單元、移回埠是指在移回時刻將平移變量從移出目的寄存器文件送到互聯開關的功能單元及其埠，選擇與移出目的寄存器文件的讀埠直接相連的功能單元及其輸出埠為移回功能單元、移回埠；g.確定移回互連開關通路移回互連開關通路是指移回功能單元同源寄存器文件間的開關總線通路，採用編譯器原有的通信調度算法即可確定移回互連開關通路；第四步，在平移路徑中插入copy操作，並指定copy操作的輸入輸出，具體方法是由編譯器在移出功能單元的操作序列中插入一條copy操作，變量產生時不存到需要使用的寄存器文件中，由copy操作直接從變量產生的時刻獲取數據，將變量保存在其它寄存器文件中，在變量需要使用之前與溢出時刻之後將其移回需要使用的源寄存器文件；變量在源寄存器文件中的生命周期變為[Tback，Tlastuse]，Tback是指將平移變量向源寄存器文件移回的指令周期；若在該變量的產生時刻，移出目的寄存器文件的輸入埠不可用，則在溢出時刻與產生時刻之間插入第二條copy操作，由源寄存器文件所對應的功能單元完成，這條copy操作從變量產生的位置取得數據，變量同樣存放在原來需要使用的寄存器文件中；第一條copy操作從第二條copy操作的輸出獲取數據；設第二條copy操作的輸入時刻為Tincopy2，此時將變量在源寄存器文件中的生命周期分割為兩段，[Tproduce，Tincopy2]和[Tback，Tlastuse]；第五步，對均衡後的寄存器文件重新採用染色圖寄存器分配方法進行分配，如果仍然有分配失敗，則返回第一步，重新進行新的負載平移，直到所有的寄存器分配成功或者無法平移為止。全文摘要本發明公開了一種利用剩餘資源分配寄存器的方法，要解決的技術問題是在處理器寄存器分配過程中減小寄存器文件壓力過載，減少溢出訪存。技術方案是在寄存器分配失敗後，首先構建剩餘網絡，然後選擇平移變量，再對選定的平移變量選擇合適的平移路徑，並在平移路徑中插入copy操作，然後重新進行寄存器分配，如果成功則結束，否則重新進行新的負載平移，直到寄存器分配成功為止。採用本發明可減輕分布式寄存器文件壓力，大幅避免單個寄存器文件的溢出，有效避免寄存器分配失敗的問題，且本發明不會帶來性能上的開銷，是無損的。文檔編號G06F9/45GK101246434SQ20081003075公開日2008年8月20日申請日期2008年3月6日優先權日2008年3月6日發明者巨任,楠伍,義何,偉吳,張春元,梅文,楊乾明,管茂林,荀長慶申請人:中國人民解放軍國防科學技術大學