分簇vliw處理器上統(tǒng)一的指令調(diào)度和寄存器分配方法
【專利摘要】本發(fā)明公開了一種分簇VLIW處理器上統(tǒng)一的指令調(diào)度和寄存器分配方法，指令調(diào)度器將程序中所有基本塊按照相反后序進(jìn)行調(diào)度，并將每個基本塊中的指令按照優(yōu)先級調(diào)度；即，每次選取可調(diào)度指令中優(yōu)先級最高的指令，給它分配簇及簇上的功能部件，并且使用寄存器分配器給該指令的虛擬寄存器分配物理寄存器。本發(fā)明具有可最大程度地減少程序的基本塊中指令執(zhí)行時間、有效降低寄存器壓力等優(yōu)點。
【專利說明】分簇VLIW處理器上統(tǒng)一的指令調(diào)度和寄存器分配方法

【技術(shù)領(lǐng)域】
[0001]本發(fā)明主要涉及到處理器的編譯優(yōu)化【技術(shù)領(lǐng)域】，特指一種適用于分簇VLIW處理器的指令調(diào)度和寄存器分配方法。

【背景技術(shù)】
[0002]隨著各種應(yīng)用程序?qū)SP (數(shù)字信號處理器)的性能要求不斷提高，當(dāng)前的高端DSP通常采用VLIW體系結(jié)構(gòu)來挖掘指令級并行性，從而提高DSP處理器的性能。VLIW處理器由多個功能部件組成，其中每個功能部件可以執(zhí)行多種指令。所有的功能部件共享一個寄存器文件。在每個時鐘周期，多個指令可以在多個功能部件上并行執(zhí)行。然而，單個寄存器文件極大地阻礙了 VLIW處理器的可擴(kuò)展性，在增加功能部件數(shù)目的同時想要保持或加速時鐘頻率，對于單個簇的體系結(jié)構(gòu)來說是不可能的。分簇VLIW體系結(jié)構(gòu)通過將單個簇的體系結(jié)構(gòu)劃分為多個較小的簇來獲得更高的性能和較低的功耗，每個簇有自己的功能部件和本地寄存器文件，簇間由通信網(wǎng)絡(luò)進(jìn)行通信。
[0003]指令調(diào)度和寄存器分配是編譯器優(yōu)化的兩個重要問題，對程序的執(zhí)行時間有很大影響。傳統(tǒng)方法將寄存器分配和指令調(diào)度分兩個階段執(zhí)行，從而會導(dǎo)致階段順序問題，使得編譯代碼不夠優(yōu)化。若寄存器分配在指令調(diào)度前執(zhí)行，同一個寄存器可能被分配給不同的變量，導(dǎo)致偽依賴關(guān)系，因此降低代碼的指令級并行性。若指令調(diào)度在寄存器分配之前執(zhí)行，增加的指令級并行性可能極大地增加寄存器壓力，導(dǎo)致寄存器溢出。
[0004]分簇VLIW處理器使得指令調(diào)度和寄存器分配更具挑戰(zhàn)性。首先，指令調(diào)度需要將指令分配到不同的簇，不當(dāng)?shù)姆峙鋾?dǎo)致不必要的簇間通信，從而增加基本塊的執(zhí)行時間。第二，簇間的指令分配對不同簇上的寄存器壓力有很大影響。不當(dāng)?shù)姆峙錂C制可能導(dǎo)致各簇的寄存器壓力不均勻而增加寄存器溢出。第三，當(dāng)變量被從一個簇傳遞到其它簇的時候，會動態(tài)地產(chǎn)生的新的活躍區(qū)間，并且需要其它簇上的多個寄存器來保存同一個變量的副本。第四，一個變量的精確的活躍區(qū)間取決于它的第一個定義和最后一個使用的相關(guān)指令在何時被調(diào)度，而無法由傳統(tǒng)的針對靜態(tài)代碼的活躍區(qū)間分析來決定。


【發(fā)明內(nèi)容】

[0005]本發(fā)明要解決的技術(shù)問題就在于:針對現(xiàn)有技術(shù)存在的技術(shù)問題，本發(fā)明提供一種可最大程度地減少程序的基本塊中指令執(zhí)行時間、有效降低寄存器壓力的分簇VLIW處理器上統(tǒng)一的指令調(diào)度和寄存器分配方法。
[0006]為解決上述技術(shù)問題，本發(fā)明采用以下技術(shù)方案:
[0007]—種分簇VLIW處理器上統(tǒng)一的指令調(diào)度和寄存器分配方法，指令調(diào)度器將程序中所有基本塊按照相反后序進(jìn)行調(diào)度，并將每個基本塊中的指令按照優(yōu)先級調(diào)度；8卩，每次選取可調(diào)度指令中優(yōu)先級最高的指令，給它分配簇及簇上的功能部件，并且使用寄存器分配器給該指令的虛擬寄存器分配物理寄存器。
[0008]作為本發(fā)明的進(jìn)一步改進(jìn):所述寄存器分配器為一個遞增寄存器分配器，所述遞增寄存器分配器根據(jù)指令調(diào)度器的調(diào)度情況給每條指令依次分配物理寄存器。
[0009]作為本發(fā)明的進(jìn)一步改進(jìn):所述指令優(yōu)先級在調(diào)度前根據(jù)指令間延遲和處理器資源限制來確定，并且在調(diào)度過程中根據(jù)寄存器壓力來動態(tài)更新。
[0010]作為本發(fā)明的進(jìn)一步改進(jìn):所述簇的選擇取決于指令在各簇上可能的調(diào)度時間及寄存器壓力。
[0011]作為本發(fā)明的進(jìn)一步改進(jìn):在指令調(diào)度和寄存器分配過程中，對程序的控制流圖中的變量進(jìn)行生命周期分析；首先根據(jù)控制流圖，對變量進(jìn)行靜態(tài)的生命周期分析；然后在調(diào)度過程中，所述遞增寄存器分配器根據(jù)部分調(diào)度信息動態(tài)地分析變量的生命周期；即，根據(jù)已有的部分調(diào)度，進(jìn)一步對變量的生命周期進(jìn)行動態(tài)的分析。
[0012]作為本發(fā)明的進(jìn)一步改進(jìn):對于有η個變量的程序，靜態(tài)生命周期分析的時間復(fù)雜度在最壞情況下為O (η4)，在通常情況下為O (η)或0(η2);動態(tài)生命周期分析的時間復(fù)雜度為ο(|Β|*η),其中|βI為控制流圖中的基本塊數(shù)目。
[0013]與現(xiàn)有技術(shù)相比，本發(fā)明的優(yōu)點在于:
[0014]1、本發(fā)明的分簇VLIW處理器上統(tǒng)一的指令調(diào)度和寄存器分配方法，將指令調(diào)度和寄存器分配結(jié)合在一個階段完成，從而避免了傳統(tǒng)方法將兩者分別執(zhí)行而帶來的階段順序問題。
[0015]2、本發(fā)明的分簇VLIW處理器上統(tǒng)一的指令調(diào)度和寄存器分配方法，在計算指令優(yōu)先級時不僅考慮指令間延遲，也考慮處理器資源限制，而傳統(tǒng)方法不考慮處理器資源限制，因此本發(fā)明的方法所計算的指令優(yōu)先級更加精確，更能精確反映指令的相對重要性。此夕卜，本發(fā)明在具體應(yīng)用的調(diào)度過程中動態(tài)更新指令優(yōu)先級，可以有效降低寄存器壓力。
[0016]3、本發(fā)明的分簇VLIW處理器上統(tǒng)一的指令調(diào)度和寄存器分配方法，在調(diào)度指令時，指令調(diào)度器考慮了多個因素:指令的最早調(diào)度時間和其后續(xù)指令的最早調(diào)度時間，以及各簇的寄存器壓力，從而能夠更加有效地調(diào)度指令。

【專利附圖】

【附圖說明】
[0017]圖1是本發(fā)明的流程示意圖。

【具體實施方式】
[0018]以下將結(jié)合說明書附圖和具體實施例對本發(fā)明做進(jìn)一步詳細(xì)說明。
[0019]如圖1所示，本發(fā)明的分簇VLIW處理器上統(tǒng)一的指令調(diào)度和寄存器分配方法，為:指令調(diào)度器將程序中所有基本塊按照相反后序進(jìn)行調(diào)度，并將每個基本塊中的指令按照優(yōu)先級調(diào)度。每次選取可調(diào)度指令中優(yōu)先級最高的指令，給它分配簇及簇上的功能部件，并且使用遞增寄存器分配器給該指令的虛擬寄存器分配物理寄存器。即，在給每個指令分配簇和功能部件的同時，給每個指令的虛擬寄存器分配物理寄存器。
[0020]在上述過程中，寄存器分配工作由一個遞增寄存器分配器實現(xiàn)，它根據(jù)指令調(diào)度器的調(diào)度情況給每條指令依次分配物理寄存器。
[0021]本實施例中，指令優(yōu)先級可以在調(diào)度前根據(jù)指令間延遲和處理器資源限制來確定，并且在調(diào)度過程中根據(jù)寄存器壓力來動態(tài)更新。
[0022]本實施例中，簇的選擇需要考慮指令在各簇上可能的調(diào)度時間及寄存器壓力。
[0023]在上述過程中，本發(fā)明進(jìn)一步對程序的控制流圖中的變量進(jìn)行生命周期分析；在具體應(yīng)用時，可以采用傳統(tǒng)的遞歸算法來進(jìn)行生命周期分析。
[0024]在上述過程中根據(jù)已有的部分調(diào)度，進(jìn)一步對變量的生命周期進(jìn)行動態(tài)的分析。對于有η個變量的程序，靜態(tài)生命周期分析的時間復(fù)雜度在最壞情況下為0(η4)，在通常情況下為O (η)或O (η2)。動態(tài)生命周期分析的時間復(fù)雜度為0( |Β I *η)，其中|Β|為控制流圖中的基本塊數(shù)目。
[0025]由上可知，本發(fā)明的關(guān)鍵就在于將指令調(diào)度和寄存器分配放在同一階段完成，其目的是:最小化所有指令的總體執(zhí)行時間。對每一個可調(diào)度指令，指令調(diào)度器在分配簇和功能部件的同時，調(diào)用遞增寄存器分配器給該指令分配物理寄存器。遞增寄存器分配器還要考慮簇間通信帶來的寄存器之間的數(shù)據(jù)拷貝問題，在不同簇上用相應(yīng)的寄存器保存一個變量的多個副本。遞增寄存器分配器根據(jù)變量生命周期和當(dāng)前調(diào)度信息來決定分配或釋放一個物理寄存器。由于本發(fā)明將指令調(diào)度和寄存器分配結(jié)合在同一階段執(zhí)行，只有當(dāng)相關(guān)的指令被調(diào)度時才能決定變量生命周期的開始和結(jié)束。所以，遞增寄存器分配器根據(jù)部分調(diào)度信息動態(tài)地分析變量的生命周期。
[0026]因此，本發(fā)明將寄存器分配和指令調(diào)度集成在同一個階段來執(zhí)行，以產(chǎn)生性能優(yōu)化的編譯代碼。
[0027]在具體應(yīng)用過程中，本發(fā)明在調(diào)度當(dāng)前優(yōu)先級最高的可執(zhí)行指令Vi時，給Vi選擇簇取決于Vi在各簇上可能的最早執(zhí)行時間或它的直接后續(xù)指令\的最早執(zhí)行時間。為Vi選擇的簇是使得\可以盡早執(zhí)行的。若不能評估\的執(zhí)行時間，則為Vi選擇一個簇使得\可以盡早執(zhí)行。此外，各簇的寄存器壓力也在考慮范圍內(nèi)，以避免各簇的寄存器壓力不均衡而引發(fā)不必要的寄存器溢出。
[0028]與傳統(tǒng)的圖著色寄存器分配方法不同，遞增寄存器分配器按照指令調(diào)度的順序給逐條指令分配寄存器。當(dāng)調(diào)度一條可執(zhí)行指令Vi時，如果需要另外一條指令Vk產(chǎn)生的結(jié)果a并且a已經(jīng)被溢出，或者Vk和Vi不在同一個簇上，則需要為a在Vi所在的簇上分配一個寄存器。隨后，為指令Vi的目標(biāo)寄存器分配一個物理寄存器，如果此時沒有空閑的物理寄存器，需要選擇一個物理寄存器的值溢出并將該物理寄存器分配給Vi的目標(biāo)寄存器。
[0029]以上僅是本發(fā)明的優(yōu)選實施方式，本發(fā)明的保護(hù)范圍并不僅局限于上述實施例，凡屬于本發(fā)明思路下的技術(shù)方案均屬于本發(fā)明的保護(hù)范圍。應(yīng)當(dāng)指出，對于本【技術(shù)領(lǐng)域】的普通技術(shù)人員來說，在不脫離本發(fā)明原理前提下的若干改進(jìn)和潤飾，應(yīng)視為本發(fā)明的保護(hù)范圍。
【權(quán)利要求】
1.一種分簇VLIW處理器上統(tǒng)一的指令調(diào)度和寄存器分配方法，其特征在于，指令調(diào)度器將程序中所有基本塊按照相反后序進(jìn)行調(diào)度，并將每個基本塊中的指令按照優(yōu)先級調(diào)度；即，每次選取可調(diào)度指令中優(yōu)先級最高的指令，給它分配簇及簇上的功能部件，并且使用寄存器分配器給該指令的虛擬寄存器分配物理寄存器。
2.根據(jù)權(quán)利要求1所述的分簇VLIW處理器上統(tǒng)一的指令調(diào)度和寄存器分配方法，其特征在于，所述寄存器分配器為一個遞增寄存器分配器，所述遞增寄存器分配器根據(jù)指令調(diào)度器的調(diào)度情況給每條指令依次分配物理寄存器。
3.根據(jù)權(quán)利要求1所述的分簇VLIW處理器上統(tǒng)一的指令調(diào)度和寄存器分配方法，其特征在于，所述指令優(yōu)先級在調(diào)度前根據(jù)指令間延遲和處理器資源限制來確定，并且在調(diào)度過程中根據(jù)寄存器壓力來動態(tài)更新。
4.根據(jù)權(quán)利要求1所述的分簇VLIW處理器上統(tǒng)一的指令調(diào)度和寄存器分配方法，其特征在于，所述簇的選擇取決于指令在各簇上可能的調(diào)度時間及寄存器壓力。
5.根據(jù)權(quán)利要求1?4中任意一項所述的分簇VLIW處理器上統(tǒng)一的指令調(diào)度和寄存器分配方法，其特征在于，在指令調(diào)度和寄存器分配過程中，對程序的控制流圖中的變量進(jìn)行生命周期分析；首先根據(jù)控制流圖，對變量進(jìn)行靜態(tài)的生命周期分析；然后在調(diào)度過程中，所述遞增寄存器分配器根據(jù)部分調(diào)度信息動態(tài)地分析變量的生命周期；即，根據(jù)已有的部分調(diào)度，進(jìn)一步對變量的生命周期進(jìn)行動態(tài)的分析。
6.根據(jù)權(quán)利要求5所述的分簇VLIW處理器上統(tǒng)一的指令調(diào)度和寄存器分配方法，其特征在于，對于有η個變量的程序，靜態(tài)生命周期分析的時間復(fù)雜度在最壞情況下為O (η4)，在通常情況下為0(η)或0(η2);動態(tài)生命周期分析的時間復(fù)雜度為0(|Β|*η)，其中|Β|為控制流圖中的基本塊數(shù)目。
【文檔編號】G06F9/45GK104461471SQ201410798231
【公開日】2015年3月25日 申請日期:2014年12月19日 優(yōu)先權(quán)日:2014年12月19日
【發(fā)明者】張雪萌, 吳輝, 孫海燕, 王霽, 陽柳, 郭陽, 扈嘯 申請人:中國人民解放軍國防科學(xué)技術(shù)大學(xué)