基于PID動態(tài)調節(jié)亂序處理器指令吞吐量的方法

武漢工程大學電氣信息學院　戴璐平　李繼林

0　引言

同時多線程（Simultaneous multithreading）這個概念是由美國加州大學Tullsen提出，并提出SMT處理器模型。同時多線程處理器可以并行執(zhí)行多條指令，其系統(tǒng)效能較普通處理器高，但也使處理器的計算時間難以預測。對于預測處理程序的時間預測主要有兩種方式：靜態(tài)時序預測和動態(tài)時序預測。靜態(tài)時序預測是依據編譯階段對程序信息的采集，來預測處理器執(zhí)行程序的時間。動態(tài)時序預測是在程序運行階段，對程序子系統(tǒng)進行合理調配，實現實時預測處理器的執(zhí)行時間的[1]。

最壞情況下執(zhí)行時間（WCET）分析是最典型的靜態(tài)時序方式。它是通過對程序的編譯階段的分析，得出程序在最壞執(zhí)行路徑下的最大指令數。但是，由于SMT的指令吞吐量具有很大的可變性，特別是在指令吞吐量發(fā)生非平穩(wěn)變化時，即使能夠確定程序的最壞執(zhí)行路徑，也難以得到精確的執(zhí)行時間等信息。解決這個問題的一種方案是想辦法對處理器的指令吞吐量進行平穩(wěn)控制。本文提出通過將變速積分PID反饋控制與動態(tài)電壓頻率調節(jié)技術結合起來的控制機制，用于穩(wěn)定SMT中的指令吞吐量非平穩(wěn)變化時的情況。這種方法不僅減少處理器的功耗，還可以將平穩(wěn)化后的處理器用于實時系統(tǒng)中，達到預測處理器計算時間的目的[2-4]。

1　SMT指令吞吐量突變的特征分析

處理器的指令吞吐量即單位時間內的數據輸出數量，也等于處理器的頻率除以程序執(zhí)行一條指令所需要的平均時鐘周期（CPI）。本文選用廣泛使用于嵌入式實時系統(tǒng)的Mibench測試基準中的qsort標準測試程序，使用simplescalar模擬器執(zhí)行，采樣分析測試程序在處理器上的指令吞吐量。這里將標準測試程序呈現任務平穩(wěn)變化及非平穩(wěn)變化兩種情況分別進行測試：

首先，將標準測試程序分成若干子程序，每個程序40百萬條命令構成，以任務為單位，采樣標準測試程序中當任務平穩(wěn)變化時，一段時間內亂序處理器的動態(tài)指令吞吐量。我們參照解碼一幀MPEG-4壓縮視頻在simplescalar中運行指令數取子程序窗口的大小為40百萬條指令數。圖1中，橫坐標采樣時間段，縱坐標代表同時多線程處理器吞吐量信息，單位是MIPS。測試結果如圖1所示。

圖1　qsort標準測試程序中平穩(wěn)變化任務

由圖1可以看出當標準測試程序中任務平穩(wěn)變化時指令吞吐量的變化范圍在1200MIPS～1700MIPS。

如果將標準測試程序分成 3個任務，每個任務指令數隨機設置時，采樣得到的qsort標準測試程序中非平穩(wěn)變化任務的指令吐量如圖2所示。

圖2　qsort標準測試程序中非平穩(wěn)變化任務

由圖2可以看出當標準測試程序中任務非平穩(wěn)變化時指令吞吐量的變化范圍在750MIPS～2000MIPS之間。序處理器的指令吞吐量呈現出高度可變性，具有平穩(wěn)或者非平穩(wěn)變化特征。

2　SMT指令吞吐量的動態(tài)調節(jié)

由于SMT同時處理指令的數目巨大，勢必會導致處理器運行程序時間的不可預測。因此，本項目引入動態(tài)電壓頻率調節(jié)機制和變速積分PID控制算法對處理器指令吞吐量進行動態(tài)調節(jié)。

2.1　動態(tài)電壓頻率調節(jié)

由于處理器結構以及設計技術的不斷提高，現代很多處理器具有變頻功能。即根據當前運行程序的大小，動態(tài)地調節(jié)處理器的頻率和運行電壓，在達到應用程序的所需性能的同時，降低系統(tǒng)的功耗。在調節(jié)機制中，當測得的處理器提供的吞吐量大于目標吞吐量時，降低處理器運行頻率和運行電壓，當測得的處理器提供的吞吐量小于目標吞吐量時，升高處理器運行頻率和供給電壓。這種動態(tài)調節(jié)機制不僅能調節(jié)處理器吞吐量，縮小其變化幅度，還能降低功耗，提高處理器的運行能力利用率[5,6]。對于具有復雜特性的亂序處理器而言，僅僅依靠DVFS調節(jié)是遠遠不夠的，所以將引進調節(jié)收斂性更好的PID反饋調節(jié)。

圖3　PID反饋控制動態(tài)調節(jié)流程圖

2.2　PID反饋調節(jié)

PID控制器的比例單元(P)、積分單元(I)和微分單元(D)分別對應目前誤差、過去累計誤差及未來誤差。借由調整PID控制器的三個參數，可以有效調節(jié)多線程處理器的指令吞吐量PPID控制公式如下：

其中KP、KI和KD分別是比例系數、積分系數和微分系數，E為系統(tǒng)誤差，U是閉環(huán)系統(tǒng)的凈輸入。

根據程序的需求，設定處理器的目標吞吐量，通過定期采樣得到當前處理器的指令吞吐量，將當前目標值與當前吞吐量的誤差反饋給PID控制器，待誤差經過比例系數的放大、積分系數的累加運算后得到下一次處理器的輸入控制值。

對于SMT而言，其子程序運行的多少與處理器工作頻率直接相關.由局部性原理，程序執(zhí)行過程中平均時鐘周期在相鄰的階段是基本相同的。所以，我們可以通過子程序運行的多少與處理器工作頻率的對應關系，推算出下一次處理器的輸入頻率，依此不斷地反饋調節(jié)，直至系統(tǒng)的誤差為零。吞吐量到頻率的對應關系為：

其中，Fnext是處理器下一次的運行頻率，Fcurrent是處理器當前的運行頻率，(MIPS)target是設定的目標吞吐量，(MIPS)current是當前采樣得到的吞吐量[7]。

對于平穩(wěn)變化的指令吞吐量，采用定值PID反饋控制器即可實現指令吞吐量的基本穩(wěn)定。經過反復的實驗得出當P=0.4，I=0.20和D=0.1即可滿足處理器運行程序平穩(wěn)化[8-10]。但對于指令吞吐量非平穩(wěn)變化時，利用上述參數的調節(jié)結果并不收斂于目標值。

2.3　自適應調速積分PID控制算法

對于非平穩(wěn)化的指令吞吐量而言，希望能達到隨著系統(tǒng)偏差的變化，積分作用與之成反比變化的效果。假如偏差大，積分作用加強，則會產生超調，使得處理器吞吐量更大，反而會加大了系統(tǒng)偏差。因此，對于突變后非平穩(wěn)化變化的指令吞吐量，本文引入自適應調速積分PID控制算法，根據系統(tǒng)偏差自適應調節(jié)積分值以達到調節(jié)非平穩(wěn)變化的指令吞吐量對的目的。

自適應調節(jié)積分PID控制算法的基本思想是設法改變積分項的累加速度，使其與偏差的大小相對應：偏差越大，積分越慢，積分作用減弱；偏差越小，積分越快，積分作用增強。

A、B為設定區(qū)間，f在[0，1]范圍內，當系統(tǒng)偏差大于A+B時，系數f為零，此時不對積分項進行累加，當系統(tǒng)偏差落在B和A+B之間時，對積分項的累積隨著誤差的較小而增大，當系統(tǒng)偏差小于B時，對積分項的累加達到最大。當合理地選擇A、B區(qū)間時，變速積分PID反饋算法可以將非平穩(wěn)化變化的指令吞吐量收斂于目標值。系統(tǒng)控制流程圖如圖4所示：

圖4　變速積分PID反饋控制的動態(tài)流程圖

在相同的實驗環(huán)境下，通過反復測試，當P=0.6，I=0.3，D=0.1，A=80，B=20時，可以滿足有效調節(jié)亂序處理器指令吞吐量的需求。突變后非平穩(wěn)變化的指令吞吐量的調節(jié)曲線如圖5所示：

對突變非平穩(wěn)變化的指令吞吐量后，經過變速積分調節(jié)，實際吞吐量收斂于目標吞吐量1000MIPS。通過上圖，可以看到，加入變速積分PID反饋控制算法后，對突變后非平穩(wěn)變化的程序，通過動態(tài)自適應調節(jié)，能很好地實現指令吞吐量的平穩(wěn)化。

3　結論

本文提出了利用PID平穩(wěn)化亂序處理器指令吞吐量的一些初步結果。在分析亂序處理器指令吞吐量的高度可變特征的基礎上，通過引入PID反饋控制動態(tài)自適應調節(jié)處理器的頻率，來獲得相對平穩(wěn)的指令吞吐量。針對指令吞吐量突變后非平穩(wěn)變化的程序，加入變速積分PID反饋控制，來實現指令吞吐量的平穩(wěn)化調節(jié)，從而使得運行于亂序處理器上程序的執(zhí)行時間具有可預測性。

不僅亂序處理器的指令吞吐量具有可變性，即使是對于順序型的處理器，由于多核化的結果，多個核間會共享片上存儲及片上網絡等資源，也將不可避免地導致指令吞吐量具有高度可變性。所以，本文提出的方法也可以擴展利用于多核順序處理器運行子程序大小的平穩(wěn)化，以提高運行程序執(zhí)行時間的可預測性[11]。

[1]Eggers S J,Emer J S,Levy H M,et al.Simultaneous Multithreading:aplatform or next-generation rocessors[J].IEEE Micro,1997,17(5):12-19.

[2]Rotenberg E.Using Variable-MHz Microprocessors to E ciently Handle Uncertainty in Real-Time Systems.In Proceedings of the 34th International Symposium on Microarchitecture,2001.

[3]Brun N,Collengs S S,Diamos G.Simultaneous branch and warp interweaving for sustained GPU performance[J].Acm sigarch Computer architecture news,2012,40(40):49-60.

[4]張文波,苑凌嬌,譚小波,等.嵌入式多線程處理器的執(zhí)行控制設計方法的研究[J].沈陽理工大學學報,2012,31(4):1-5.

[5]Suh Jinho,Dubois Michel.Dynamic MIPS Stabilization in Outof-Order Processors.ISCA’09,2009:20-24.

[6]須田信英.PID控制理論與實務[M].臺北:全華科技圖書股份有限公司,1992.

[7]馬雪.嵌入式硬件多線程處理器設計與多線程機制[J].電子技術與軟件工程,2015(21):204.

[8]Varma A,Ganesh B,Sen M,Choudhury S R,Srinivasan L，Bruce J.A control-theoretic approach to dynamic voltage scheduling.In Proceedings of the 2003 international Conference on Compilers,Architecture and Synthesis For Embedded Systems(CASES ‘03),2003:255-266.

[9]Matsumoto K,UmeoH,Yamasaki N.A Thread Speed Control Scheme for Real-Time Microprocessors.IEEE 17th International Conference Embedded and Real-Time Computing Systems and Applications(RTCSA),2011:16-21.

[10]馮川放,馬季.基于嵌入式LINUX系統(tǒng)的實時進程調度算法的研究[J].計算機應用與軟件,2014,31(12):278-282.

[11]李剛,金蓓弘.基于線程的并發(fā)控制技術研究與應用[J].計算機工程,2007,30(14):43-45.