[發明專利]利用堆棧深度進行多線程預測的動態功耗控制方法

有效

• 申請號: 200810019344.1
• 申請日: 2008-01-04
• 公開（公告）號: CN101216725A
• 公開（公告）日: 2008-07-09
• 發明（設計）人: 戚隆寧;黃少珉;胡晨
• 申請（專利權）人: 東南大學
• 主分類號: G06F1/32
• 分類號: G06F1/32;G06F9/46
• 代理公司: 南京經緯專利商標代理有限公司
• 代理人: 葉連生

1.一種利用堆棧深度進行多線程預測的動態功耗控制方法，其特征在于：

第一步：通過操作請求的簇集模式RCM來描述單個線程對部件或設備的操作請求序列Φ的特征，其計算方法如下；

RCMΦ=mod232(Σri∈ΦRA(ri)),Φ={ri|TRI(ri,ri-1)<TBE(s2)}]]>

式中：

r_i——系統對部件(或設備)的操作請求；

RA(r_i)——產生操作請求r_i的函數的返回地址；

mod_x(y)——以為基數x對y進行模運算；

T_RI(r_i，r_i-1)——操作請求r_i與r_i-1之間的空閑時間；

s_i——第i級低功耗空閑模式；

T_BE(s_i)——進入第i級低功耗空閑模式的損益平衡時間，即進入低功耗空閑模式能夠節約能耗的最短空閑時間；

第二步：采用兩級哈希表來預測單線程下請求間隔時間的概率分布，第一級哈希表是根據mod₃₇[RA(r_i)]構建的函數返回地址哈希表，用鏈表解決哈希沖突，該哈希表的索引結點包含對具有相同函數返回地址的操作請求后空閑時間分布的統計結果F_RA，以及第二級哈希表：根據mod₁₇[SD(r_i)]和mod₁₇[RCM]分別構建的棧深哈希表和請求簇集模式哈希表，其中SD(r_i)表示產生操作請求r_i時的堆棧深度，即堆棧頂部與堆棧底部之差；棧深哈希表的索引結點包含了具有相同函數返回地址和堆棧深度的操作請求之后的空閑時間分布F_SD；而請求簇集模式哈希表的索引結點則包含了具有相同函數返回地址和請求簇集模式的操作請求之后的空閑時間分布F_RCM；單線程下請求間隔時間，即請求之后的空閑時間的概率分布F_predict可以根據哈希表的命中情況進行預測，當僅函數返回地址哈希表命中時F_predict＝F_RA；當僅棧深哈希表命中時F_predict＝F_SD；當僅請求簇集模式哈希表命中時F_predict＝F_RCM；當棧深哈希表和請求簇集模式同時命中，F_predict＝F_SD×F_RCM；

第三步：以線程為獨立的請求源，并根據線程所屬任務以及入口地址對請求源進行分組，屬于同一任務并且執行入口地址相同的線程歸入同一個分組，在同組請求源產生的請求服從相同分布的假設條件下，綜合各請求源對請求間隔時間的預測結果，計算出部件或設備進入低功耗空閑模式s_i的概率P(s_i)；計算方法如下，

P(si)=Πj=1NTPj(si,Δtj)-Πj=1NTPj(si+1,Δtj),(i<n)Πj=1NTPj(si,Δtj),(i=n)]]>

Pj(si,Δtj)=1-Fpredict(TBE(si)+Δtj)-Fpredict(Δtj)1-Fpredict(Δtj)]]>

式中

N_T——當前正在使用部件或設備的線程總數，即請求源總數；

n——部件或設備的空閑模式總數；

t_j——請求源j當前的延時；

P_j(s_i，Δt_j)——請求源j在空閑Δt_j時間后繼續空閑的時間超過空閑模式s_i損益平衡時間的概率；

第四步：根據部件或設備空閑時間的概率分布，計算出多功耗模式單門限下的最優超時門限k_opt和最優功耗模式s_opt，計算方法如下，

Etotal(rΔt,si)=Σj=1r(a1Tj+njb1)+Σj=r+1q(aiTj+nj((a1-ai)rΔt+bi))]]>

Eopt=min1≤i≤m1≤r≤q{Etotal(rΔt,si)}=Etotal(roptΔt,sopt)]]>

k_opt＝r_optΔt

式中

Δt——候選超時門限的間隔時間；

E_total(rΔt，s_i)——部件或設備在經過rΔt超時時間后，進入空閑模式s_i的能耗期望；

q——候選超時門限的總數；

T_i——空閑時間分布統計中，落在第i個區間內的空閑時間的長度總和；

n_i——空閑時間分布統計中，空閑時間落在第i個區間內的請求的總數；在請求處理結束后啟動定時器，一旦部件空閑時間超過計算出的最優超時門限k_opt，則立刻控制部件進入對應的最優功耗模式s_opt。