面向共享资源冲突的SoC并发时钟调度管理

修于杰，黄 凯，林 威，余 慜，莫鹏飞，严晓浪

（1.浙江大学a.超大规模集成电路研究所；b.电子信息技术与系统研究所，杭州310027；2.杭州朔天科技有限公司，杭州310012）

面向共享资源冲突的SoC并发时钟调度管理

修于杰1a，黄 凯1a，林 威1b，余 慜1a，莫鹏飞2，严晓浪1a

（1.浙江大学a.超大规模集成电路研究所；b.电子信息技术与系统研究所，杭州310027；2.杭州朔天科技有限公司，杭州310012）

片上系统（SoC）的多任务并发性使得总线和主存等共享资源的竞争日趋频繁，如何在满足系统峰值功耗需求的同时减少资源冲突带来的功耗损失是系统级时钟管理的难点。为此，提出一种SoC系统级时钟调度管理方法，在不影响系统性能的前提下，根据各计算单元在共享资源上的竞争概率，计算各单元由于竞争冲突导致的等待时间，进而在已知任务截止时间的前提下，分析各个任务的实际有效工作时间，通过软件调配各计算单元时钟频率调度共享资源的访问，实现系统在满足峰值功率约束下的总功耗最优化。实验结果表明，该方法可降低3.3%～38.2%的SoC系统总功耗。

片上系统；功耗优化；时钟调度；共享资源冲突；冲突时间；冲突概率

1 概述

随着片上系统（System on Chip，SoC）规模的增大，处理器核数的增多带来的功耗开销已经成为了一个急需解决的问题。多核系统并发运行多个不同任务时，由于主存总线等共享资源的限制，计算单元之间存在着资源竞争关系。即便是在单核系统中，处理器与外设在访问资源等方面也存在着竞争关系，竞争引起了延时等待与能量浪费。在一些研究中［1-2］，建立优先级控制器，通过控制任务之间的优先级，在满足系统性能的前提下，实现各计算单元最低工作频率相同，系统功耗最低。这些研究认为任务之间冲突时间为整个工作区间，同时任务优先级可控制。

然而，在一些研究中，任务之间的优先级已经确定，任务之间冲突时间也可以通过调度任务起始时间进行调整。在优先级确定的前提下，任务间冲突时间为整个工作区间时，系统总功耗并不一定最小。同时由于供电系统的制约，系统中存在着峰值功率的约束，理论上单一的降低系统总功耗到最低并不一定可以实现，在满足峰值功率约束的前提下，降低系统总功耗到最低也是一个需要解决的问题。

研究证明，任务在截止时间前完成然后通过动态电压管理进入低功耗模式，不如降低系统频率，在截止时间点恰好完成任务更省功耗［3-5］。同时在现有工艺下，芯片的功耗开销主要分为动态功耗和静态功耗［6-7］，而动态功耗仍然占据主导作用。综上，采用合适的时钟调度管理技术，找到合适的工作频率，是降低功耗的有效方法。

本文针对已确立优先级的系统，在满足时钟约束、不影响系统性能的情况下，通过理论分析计算得到各任务的实际工作时间以及任务间冲突时间，并采用软硬件协同调度验证理论计算结果，进而实现系统在满足峰值功率约束下的总功耗最优化。

2 功耗优化策略

在系统中，由于总线主存等带宽限制，各计算单元会存在访问竞争，因此导致部分单元产生等待时间。在面向功耗优化的系统中，系统的各个任务并不是越快完成越好，每个任务在截止时间前完成，并消耗最低的能量，才是最优的调度安排。

因为系统中优先级高的单元有更多机会访问总线主存等资源，所以等待时间较少，工作频率也因此较低，功耗浪费少。而优先级低的单元等待时间多，为了满足性能要求，优先级低的计算单元必须提高频率，完成任务，这样就会产生更大的功耗。在这两种情况下，应找到折中的方式，实现系统总功耗最低。

每个系统任务存在一个实际的工作时间，保证这个时间结束点不超过截止时间就满足系统性能要求。在系统工作中，各个任务之间存在竞争资源的时间段，本文称之为冲突时间。图1给出了系统功耗优化方法的工作流程。

图1 系统功耗优化流程

具体步骤如下：

（1）建立模型。根据实际系统建立计算单元与主存间的访问模型，并从实际系统中获取模型所需常量，模型需要从实际系统中获得的常量有：任务的截止时间，任务的指令数量，计算单元访问主存次数，计算单元每秒处理的指令数量，无访问冲突时芯片负载电容及存在冲突时芯片负载电容，任务间优先级关系，系统工作电压。

（2）计算任务间冲突概率、等待时间与冲突时间、任务实际工作时间的映射关系。在冲突时间内，根据任务访问资源的方式及优先级大小，可以获得每个任务冲突概率模型及其等待时间长度。

（3）计算每个任务最低工作频率与冲突时间、任务实际工作时间的映射关系。计算得到任务由于冲突而导致的等待时间后，可以推知每个任务真正运行指令的实际有效工作时间，从而得到任务最低工作频率。

（4）计算系统总功耗、峰值功率与冲突时间、任务实际工作时间的映射关系。在得到系统任务的最低工作频率后，根据CMOS反相器的平均动态公式求得系统峰值功率、系统最低总功耗与任务工作时间、冲突时间的映射关系。

（5）通过软件优化，得出满足系统峰值功率约束下，系统总功耗最低时任务间的冲突时间及每个任务实际运行时间。

（6）软件调度任务实际工作时间及工作频率，保证满足优化后的任务冲突时间，即可实现满足系统峰值功率约束下的系统总功耗最低。

最后可根据实测系统功耗结果，进行误差范围内调整或重新执行以上步骤。下文将以已知常量为基础，建立2个计算单元的系统模型进行功耗优化方法的论证。并在此基础上进行延伸，分析多个计算单元独立运行多个独立任务时系统功耗优化方法。

本文的建模方法、任务冲突概率及等待时间的计算方法参考已有研究成果［1-2］，在此基础上，增加冲突时间变量和任务实际工作时间变量，且固定任务之间优先级，建立冲突时间变量、任务实际工作时间变量与系统功耗之间的映射关系。

3 模型建立及优化方案

本节将建立SoC系统模型，分析各计算单元之间主存资源竞争情况，通过优化各单元时钟频率，降低由于访问主存冲突而引起的无用功耗，在保证系统性能及满足系统峰值功率约束的前提下，优化系统总功耗。

3.1 模型建立及假设

假设SoC系统中有2个计算单元，忽略总线的限制，只考虑主存访问限制，只允许一个计算单元单独访问主存，在被访问过程中，后来的访问发起者将处于等待状态。其他外设单元暂不考虑。图2给出了模型架构。

图2 模型架构

模型使用的常量定义如下，其中，i表示0或者1。

CUi：计算单元；

Ti：应用任务；

D：整个系统任务截止时间；

tsi：CUi由于器件本身特性造成的时间损耗；

P：系统额定峰值功率。

以上常量通过其他方法获得，本文不做分析。假设2个CUi运行的任务Ti完全独立，同时运行一个任务期间，CUi工作频率不变。

每个CUi需要在截止时间D前完成任务，完成每个任务时间可以为截止时间D内任意时间段，用Li表示任务实际运行时间。每个任务有Ii条指令，由于CUi在访问主存时可能产生资源竞争冲突，导致处于等待状态，因此使用ti表示任务实际有效运行时间，tcon表示CUi间冲突时间，tdelayi表示由于冲突引起的等待时间。

所以：

CUi的运行频率与指令数量Ii以及实际有效运行时间ti有关［8］，在模型中可以按照下列公式给出每个计算单元的运行最低频率fi，式中采用一个常数因子c，它是计算单元每秒处理指令数量。

在现有工艺下，系统功耗主要来源于动态功耗，而动态功耗的主要部分为开关功耗，根据CMOS反相器的平均动态公式可推知系统功率与频率关系：

因为本文只分析系统时钟调度，所以模型建立在电压恒定的基础上，Vdd为常量。a为常数因子，CL为芯片负载电容，由于计算单元内部实现时插入门控单元，当与其他设备发生资源冲突产生竞争等待时，将关闭计算单元内部部分电路时钟节省功耗，因此在冲突时间内，CL将减小到C′L。

通过任务调度，2个任务可能同时进行，也可能完全没有冲突，当2个计算单元发生冲突时，有一个计算单元会关闭内部部分电路时钟，另一个正常工作，所以系统峰值功率及功耗为：

当tcon≠0时：

当tcon=0时：

3.2 竞争分析及频率优化

在CUi分别运行不同的任务Ti时，系统可以通过软件调度控制任务的起始时间，在运行时，任务间在冲突时间tcon中存在竞争冲突，通过优化，调整任务起始时间以及冲突时间的长度，在保证系统性能的前提下，尽可能地降低竞争发生的概率及其引起的等待时间。

由于不同的系统中，CUi之间冲突方式及数量不同，概率计算方法不尽相同，本文重点在于提出系统功耗的整体优化方法并证明其有效性及可行性，因此对于不同的概率计算方法不做详细讨论。针对本文提出模型，用lins表示每条指令从主存读取所需时间mi表示CUi访问主存次数，两者由应用及硬件架构决定。

在冲突时间段tcon中，由于CU1占用主存资源，CU0访问主存时发生冲突的概率为：

在tcon中，CU0访问主存的指令数量约为：

由于CU1占用主存资源，CU0每次取指时CU1已占用时间不确定，假设χ为其已完成进度，因此CU0需要等待的平均时间为：

综上，在冲突时间tcon内，CU0需要等待的总时间为：

同理可得，CU1需要等待的时间为：

根据式（1）可以推知任务Ti的实际有效工作时间，根据式（2）可以求得任务Ti的最低工作频率fi：

根据式（4）～式（7）可推知系统峰值功率及总功耗：

当tcon≠0时：

当tcon=0时：

这样，得到系统峰值功率及总功耗与Ti实际运行时间Li以及冲突时间tcon的映射关系，通过式（18）对变量加以约束，结合式（14）～式（17）即可获得在满足系统峰值功率约束下，系统总功耗最低时任务实际运行时间及冲突时间，进而可以求得系统各任务的工作频率：

其中，fmaxi为CUi的最大工作频率；fmini为CUi的最低工作频率。

求得任务之间的冲突时间及实际运行时间后，通过调整任务起始时间及时钟暂停操作，使各个任务的实际运行时间及冲突时间满足约束，从而使系统总功耗最低。

3.3 多计算单元的优化

上述模型同样可以扩展支持多计算单元的SoC系统。n个CUi分别运行n个独立的应用任务Ti，由式（4）～式（7）可推知系统峰值功率及总功耗。

当所有任务有共同冲突时间时：

当部分任务存在冲突时：

在多个任务中，任务之间的冲突时间分别为2个任务之间冲突、3个任务之间冲突以至n个任务之间同时冲突，冲突时间tconij（i＜j且i，j∈｛0，1，…，n-1｝），tconijK（i＜j＜K且i，j，K∈｛0，1，…，n-1｝），以此类推。

在这些冲突时间中，每个任务由于冲突导致等待时间根据任务取指令方式确定。每个任务总的冲突时间为：

通过确定每个任务等待总时间与任务实际运行时间、冲突时间的映射关系，就可以确定任务工作频率、峰值功率、系统总功耗与任务实际运行时间、冲突时间的映射关系，结合约束条件，求得各任务间的冲突时间及实际工作时间，进一步求得每个任务的工作频率，通过系统软件调度任务工作起始时间，在截止时间内合理分配任务工作时间，即可优化系统功耗。

4 实验结果及分析

对上文所述的优化方法验证时，本文所采用的SoC实验平台集成了2个CK610 32位嵌入式处理器［9-10］、单路或多路64-bit AHB总线和SDRAM主存等。测试程序采用业界主流的嵌入式多核Benchmark：EEMBC multibench［11-13］。优化前系统时钟采用20 MHz。

本文实验使用Matlab工具。在使用Matlab优化最优解时，考虑到目标函数不是线性的，方法有2种：第1种方法采用Matlab的非线性规划函数，但这种方法有时求得的为局部最优解；第2种方法通过取点方式计算，是一种离散算法，满足前提是函数不会在一定局域内突变，以一定步长在变量约束范围内取值，遍历所有可能的值，步长越小，结果越准确。考虑到实验平台中目标函数和约束条件比较简单，因此，本文采用第2种方法进行求解。

为验证本文提出的方法对系统功耗的优化效果，进行以下3组实验。

实验1 忽略峰值功率的约束。表1给出了实验结果，其中，fi为优化前CUi工作频率；f′i为优化后CUi工作频率。

在冲突时间为0时，系统总功耗最低，这个结果在式（21）中也可以得以验证，冲突时间为0，则冲突等待时间为0，式中的第2项最小，系统总功耗最低。

表1 系统总功耗最低时的实验数据

实验2 不考虑系统总功耗，使峰值功率最低。表2给出了实验结果。由表中数据可知，冲突时间只有2种情况：0或D，因此，软件上仅存在2种优化的可能性。图3给出了模型在获得任务实际运行时间及冲突时间后，通过软件调度任务前后的进度对比。分析这种现象的原因，图4为存在冲突时间的假设优化结果，其中，Loldi为优化前任务完成时间；tstarti为任务起始运行时间。

表2 系统峰值功率最低时的实验数据

图3 优化前后任务调度对比

图4 假设的任务调度优化结果

假设任务之间存在一段冲突时间0＜tcon_x＜D时系统峰值功率最低，则系统的峰值功率肯定是2个任务冲突时间段内，也就是两者峰值功率之和，同时降低2个任务峰值功率，才可能降低系统峰值功率，每个任务的功率与其工作频率相关，而工作频率又与其实际有效工作时间有关，实际有效工作时间越长，频率越低，峰值功率也越低。任务1的工作时间为t1+t2，如果在t2内，任务1存在部分有效工作时间，冲突是概率事件，所以在t3时间内，即使存在冲突，任务1仍然可以获得实际有效工作时间，所以任务一的实际工作时间可以延长为D，这样系统峰值功率更小，同理，任务2的工作时间也可以延长为D，进一步降低系统峰值功率，从而使得任务冲突时间tcon_x也为D。如果在t2内，任务1不存在实际有效工作时间，则任务1在t2内不能完成任何工作，也没有存在的必要，所以冲突时间tcon_x为0。2种优化的可能性与实际任务的指令数量、冲突概率、取指周期相关，实际系统优化方法选择需要通过上文介绍方法进行计算得知。

这样得出结论：在任务截止时间相同的情况下2个任务之间的冲突，只有完全冲突，或者完全不冲突，才能实现系统峰值功率最低。结论可以进一步扩展为多个任务的系统中，任务两两之间完全不冲突，或者排除其他任务与之冲突部分，其余部分必须完全冲突，才能实现系统峰值功率最小。

实验3 考虑在系统峰值功率满足约束的情况下，系统功耗最低。表3给出了实验结果。任务X 264-4M q与Rotate-4M s1w1虽然在冲突时间为0时系统总功耗最低，但是由于峰值功率的约束，无法实现冲突时间为0，在满足峰值功率约束下，冲突时间为D时系统总功耗最低。

在结果中，进一步发现任务间冲突时间仍然为完全冲突或者为0，分析原因，与上文的只考虑峰值功率时的现象原因不同，在这种情况下，出现冲突时间为D或者0是因为在冲突时间为0，系统峰值功率如果小于额定峰值功率，此时系统总功耗肯定为最小，实验1中已经分析原因，这样冲突时间就为0，如果冲突时间为0时，系统峰值功率大于额定峰值功率，则只有增加冲突时间才有可能降低峰值功率，实验系统冲突时间增大，也增加了实际有效工作时间，实际有效工作时间的增加降低了系统任务工作频率，本文实验平台中工作频率降低对系统的影响恰好大于等待时间增加对系统的影响，这样冲突时间为D时结果最优，所以才出现了满足峰值功率约束下系统功耗最低时，冲突时间为0或者D。

表3 系统满足额定峰值功率约束且功耗最低时的实验数据

理论优化频率在实验中并不完全适用，存在误差，理论结果偏小，这是由于冲突模型分析只考虑主存竞争，实际系统中还存在核间架构、总线竞争等，同时计算过程中，为了方便计算，取指周期采用一个较小的固定值，而实际中它与系统频率有关，计算单元完成任务时需要访问主存次数采用经验统计值，其访问次数与实际应用的程序结构有关。以上导致计算的优化频率存在误差，但实际最优值存在于理论值附近，可以通过实际软件调整实现，即可保证在截止时间前完成任务并降低功耗。

通过实验结果与文献［1-2］对比，结果表明，文献［1-2］中的系统任务冲突时间为整个任务周期，在此基础上控制系统各任务的优先级，优化系统功耗。基于功耗、功率、时间三者的关系，功耗等于时间乘以功率，如果将时间确定为整个任务周期，则导致功耗和功率变化关系线性统一，而有的系统只要求总功耗最低，有的系统要求在一定的峰值功率约束下总功耗最低，固定冲突时间的体系方法并不能适应所有系统的要求。本文提出的方法不是在已有研究上的优化，而是提出可以在确定系统各任务优先级的情况下，通过控制任务之间的冲突时间长度，优化系统功耗，并可以根据系统总功耗最低、系统峰值功率最低、系统峰值功率约束下总功耗最低3种情况下给出不同的优化方法及依据，对于系统的功耗优化更为灵活。

综合实验结果及理论分析可知，本文所建立的分析模型可以实现系统在满足峰值功率约束下的总功耗最小化。

5 结束语

本文根据目标计算单元的相关参数建立功耗分析模型，通过分析计算单元间竞争主存资源的概率，得到冲突时间以及由于竞争而导致的延时，继而分析每个计算单元的实际有效工作时间，求得在截止时间约束下的工作最低频率，实现系统总功耗最低。由实验结果可知，任意2个计算单元间冲突时间为0或者排除其他任务与之冲突部分，其余部分必须完全冲突，系统峰值功率最低。在实际实验平台中，当满足峰值功率约束时，本文方法可使系统总功耗优化3.3%～38.2%。

［1］ Watanabe R，Kondo M，Nakamura H，et al.Power Reduction of Chip Multi-processors Using Shared Resource Control Cooperating with DVFS［C］// Proceedings of the 25 th International Conference on Computer Design.Washington D.C.，USA：IEEE Press，2007：615-622.

［2］ Takagi N，Sasaki H，Kondo M，et al.Cooperative Shared Resource Access Control for Low-pow er Chip Multiprocessors［C］//Proceedings of the 14th ACM/ IEEE International Symposium on Low Power Electronics and Design.New York，USA：ACM Press，2009：177-182.

［3］ Weiser M，Welch B，Dem er S A，et al.Scheduling for Reduced CPU Energy［C］//Proceedings of the 1st USENIX Symposium on Operating System s Design and Implementation.New York，USA：USENIX，1996：449-471.

［4］ Zhuravlev S，Saez J C，Blagodurov S，et al.Survey of Energy-cognizant Scheduling Techniques［J］.IEEE Transactions on Parallel and Distributed System s，2013，24（7）：1447-1464.

［5］ Chandrakasan A P，Sheng S，Brodersen R W.Low-power CMOS Digital Design［J］.IEEE Journal of Solid-state Circuits，1992，27（4）：473-484.

［6］ Zhu D，Melhem R，Childers B.Scheduling with dynamic Voltage/speed Adjustment Using Slack Reclamation in Multiprocessor Real-time System s［J］.IEEE Transactions on Parallel and Distributed System s，2003，14（7）：686-700.

［7］ Yao F，Demers A，Shenker S.A Scheduling Model for Reduced CPU Energy［C］//Proceedings of the 36th Annual Symposium on Foundations of Computer Science.Washington D.C.，USA：IEEE Press，1995：374-382.

［8］ Ishihara T，Yasuura H.Voltage Scheduling Problem for Dynamically Variable Voltage Processors［C］//Proceedings of International Symposium on Low Power Electronics and Design.Washington D.C.，USA：IEEE Press，1998：197-202.

［9］ 潘 赟.CK-CPU嵌入式系统开发教程［M］.北京：科学出版社，2011.

［10］ CK610 Introduction［EB/OL］.［2014-08-15］.http：// www.c-sky.com/product.php？typeid=103.

［11］ Gal-On S，Levy M.Measuring Multicore Performance［J］.Com puter，2008，41（11）：99-102.

［12］ Poovey JA，Conte T M，Levy M，et al.A Benchmark Characterization of the EEMBC Benchmark Suite［J］. IEEE Micro，2009，29（5）：18-29.

［13］ MultiBenchTM1.0 Benchmark Software［EB/OL］.［2014-08-15］.http：//www.eembc.org/benchmark/multi_sl.php.

编辑 金胡考

SoC Concurrent Clock Scheduling Management Oriented to Shared Resource Conflict

XIU Yujie1a，HUANG Kai1a，LIN W ei1b，YU M in1a，MO Pengfei2，YAN Xiaolang1a
（1a.Institute of VLSIDesign；1b.Institute of Electronic Information Technology and System，Zhejiang University，Hangzhou 310027，China；2.Hangzhou Sec-Chip Technology Co.，Ltd.，Hangzhou 310012，China）

System on Chip（SoC）multi-task concurrency leads to more frequent com petitions on shared resources like bus and main memory.How to reduce the power consumption caused by resource conflicts while meeting peak power requirements of the system has become amajor challenge on system-level clock management.In this paper，a system-level SoC clock scheduling management method is proposed to achieve optimal total power consumption under the peak power constraint.Without any im pact on system performance，it calculates the waiting time of each unit caused by resource conflicts according to their competition probabilities on shared resources，and further analyzes the effective working time of each task as the finishing time of tasks is known.The optimization target is then reached by using software to deploy the clock frequency of each unit to schedule shared resource access.Experimental results show that total power consumption can be reduced from 3.3%to 38.2%With this method.

System on Chip（SoC）；power consumption optimization；clock scheduling；shared resource conflict；conflict time；conflict probability

修于杰，黄 凯，林 威，等.面向共享资源冲突的SoC并发时钟调度管理［J］.计算机工程，2015，41（9）：108-114，119.

英文引用格式：Xiu Yujie，Huang Kai，Lin Wei，et al.SoC Concurrent Clock Scheduling Management Oriented to Shared Resource Conflict［J］.Computer Engineering，2015，41（9）：108-114，119.

1000-3428（2015）09-0108-07

A

TN47

10.3969/j.issn.1000-3428.2015.09.019

国家自然科学基金资助项目（61100074）；中央高校基本科研业务费专项基金资助项目（2013QNA5008）；国家科技重大专项基金资助项目（2009ZX 01030-001-002）。

修于杰（1989-），男，硕士研究生，主研方向：片上系统设计；黄 凯（通讯作者），副教授；林 威，硕士研究生；余 慜，博士；莫鹏飞，硕士；严晓浪，教授。

2014-09-04

2014-10-16 E-m ail：huangk@vlsi.zju.edu.cn