基于PID動態調節亂序處理器指令吞吐量的方法

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

0　引言

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

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

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

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

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

圖1　qsort標準測試程序中平穩變化任務

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

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

圖2　qsort標準測試程序中非平穩變化任務

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

2　SMT指令吞吐量的動態調節

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

2.1　動態電壓頻率調節

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

圖3　PID反饋控制動態調節流程圖

2.2　PID反饋調節

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

其中KP、KI和KD分別是比例系數、積分系數和微分系數，E為系統誤差，U是閉環系統的凈輸入。

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

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

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

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

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

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

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

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

圖4　變速積分PID反饋控制的動態流程圖

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

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

3　結論

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

不僅亂序處理器的指令吞吐量具有可變性，即使是對于順序型的處理器，由于多核化的結果，多個核間會共享片上存儲及片上網絡等資源，也將不可避免地導致指令吞吐量具有高度可變性。所以，本文提出的方法也可以擴展利用于多核順序處理器運行子程序大小的平穩化，以提高運行程序執行時間的可預測性[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]張文波,苑凌嬌,譚小波,等.嵌入式多線程處理器的執行控制設計方法的研究[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系統的實時進程調度算法的研究[J].計算機應用與軟件,2014,31(12):278-282.

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