基于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.