面向共享資源沖突的SoC并發(fā)時(shí)鐘調(diào)度管理

修于杰，黃 凱，林 威，余 慜，莫鵬飛，嚴(yán)曉浪

（1.浙江大學(xué)a.超大規(guī)模集成電路研究所；b.電子信息技術(shù)與系統(tǒng)研究所，杭州310027；2.杭州朔天科技有限公司，杭州310012）

面向共享資源沖突的SoC并發(fā)時(shí)鐘調(diào)度管理

修于杰1a，黃 凱1a，林 威1b，余 慜1a，莫鵬飛2，嚴(yán)曉浪1a

（1.浙江大學(xué)a.超大規(guī)模集成電路研究所；b.電子信息技術(shù)與系統(tǒng)研究所，杭州310027；2.杭州朔天科技有限公司，杭州310012）

片上系統(tǒng)（SoC）的多任務(wù)并發(fā)性使得總線和主存等共享資源的競(jìng)爭(zhēng)日趨頻繁，如何在滿足系統(tǒng)峰值功耗需求的同時(shí)減少資源沖突帶來(lái)的功耗損失是系統(tǒng)級(jí)時(shí)鐘管理的難點(diǎn)。為此，提出一種SoC系統(tǒng)級(jí)時(shí)鐘調(diào)度管理方法，在不影響系統(tǒng)性能的前提下，根據(jù)各計(jì)算單元在共享資源上的競(jìng)爭(zhēng)概率，計(jì)算各單元由于競(jìng)爭(zhēng)沖突導(dǎo)致的等待時(shí)間，進(jìn)而在已知任務(wù)截止時(shí)間的前提下，分析各個(gè)任務(wù)的實(shí)際有效工作時(shí)間，通過(guò)軟件調(diào)配各計(jì)算單元時(shí)鐘頻率調(diào)度共享資源的訪問(wèn)，實(shí)現(xiàn)系統(tǒng)在滿足峰值功率約束下的總功耗最優(yōu)化。實(shí)驗(yàn)結(jié)果表明，該方法可降低3.3%～38.2%的SoC系統(tǒng)總功耗。

片上系統(tǒng)；功耗優(yōu)化；時(shí)鐘調(diào)度；共享資源沖突；沖突時(shí)間；沖突概率

1 概述

隨著片上系統(tǒng)（System on Chip，SoC）規(guī)模的增大，處理器核數(shù)的增多帶來(lái)的功耗開(kāi)銷已經(jīng)成為了一個(gè)急需解決的問(wèn)題。多核系統(tǒng)并發(fā)運(yùn)行多個(gè)不同任務(wù)時(shí)，由于主存總線等共享資源的限制，計(jì)算單元之間存在著資源競(jìng)爭(zhēng)關(guān)系。即便是在單核系統(tǒng)中，處理器與外設(shè)在訪問(wèn)資源等方面也存在著競(jìng)爭(zhēng)關(guān)系，競(jìng)爭(zhēng)引起了延時(shí)等待與能量浪費(fèi)。在一些研究中［1-2］，建立優(yōu)先級(jí)控制器，通過(guò)控制任務(wù)之間的優(yōu)先級(jí)，在滿足系統(tǒng)性能的前提下，實(shí)現(xiàn)各計(jì)算單元最低工作頻率相同，系統(tǒng)功耗最低。這些研究認(rèn)為任務(wù)之間沖突時(shí)間為整個(gè)工作區(qū)間，同時(shí)任務(wù)優(yōu)先級(jí)可控制。

然而，在一些研究中，任務(wù)之間的優(yōu)先級(jí)已經(jīng)確定，任務(wù)之間沖突時(shí)間也可以通過(guò)調(diào)度任務(wù)起始時(shí)間進(jìn)行調(diào)整。在優(yōu)先級(jí)確定的前提下，任務(wù)間沖突時(shí)間為整個(gè)工作區(qū)間時(shí)，系統(tǒng)總功耗并不一定最小。同時(shí)由于供電系統(tǒng)的制約，系統(tǒng)中存在著峰值功率的約束，理論上單一的降低系統(tǒng)總功耗到最低并不一定可以實(shí)現(xiàn)，在滿足峰值功率約束的前提下，降低系統(tǒng)總功耗到最低也是一個(gè)需要解決的問(wèn)題。

研究證明，任務(wù)在截止時(shí)間前完成然后通過(guò)動(dòng)態(tài)電壓管理進(jìn)入低功耗模式，不如降低系統(tǒng)頻率，在截止時(shí)間點(diǎn)恰好完成任務(wù)更省功耗［3-5］。同時(shí)在現(xiàn)有工藝下，芯片的功耗開(kāi)銷主要分為動(dòng)態(tài)功耗和靜態(tài)功耗［6-7］，而動(dòng)態(tài)功耗仍然占據(jù)主導(dǎo)作用。綜上，采用合適的時(shí)鐘調(diào)度管理技術(shù)，找到合適的工作頻率，是降低功耗的有效方法。

本文針對(duì)已確立優(yōu)先級(jí)的系統(tǒng)，在滿足時(shí)鐘約束、不影響系統(tǒng)性能的情況下，通過(guò)理論分析計(jì)算得到各任務(wù)的實(shí)際工作時(shí)間以及任務(wù)間沖突時(shí)間，并采用軟硬件協(xié)同調(diào)度驗(yàn)證理論計(jì)算結(jié)果，進(jìn)而實(shí)現(xiàn)系統(tǒng)在滿足峰值功率約束下的總功耗最優(yōu)化。

2 功耗優(yōu)化策略

在系統(tǒng)中，由于總線主存等帶寬限制，各計(jì)算單元會(huì)存在訪問(wèn)競(jìng)爭(zhēng)，因此導(dǎo)致部分單元產(chǎn)生等待時(shí)間。在面向功耗優(yōu)化的系統(tǒng)中，系統(tǒng)的各個(gè)任務(wù)并不是越快完成越好，每個(gè)任務(wù)在截止時(shí)間前完成，并消耗最低的能量，才是最優(yōu)的調(diào)度安排。

因?yàn)橄到y(tǒng)中優(yōu)先級(jí)高的單元有更多機(jī)會(huì)訪問(wèn)總線主存等資源，所以等待時(shí)間較少，工作頻率也因此較低，功耗浪費(fèi)少。而優(yōu)先級(jí)低的單元等待時(shí)間多，為了滿足性能要求，優(yōu)先級(jí)低的計(jì)算單元必須提高頻率，完成任務(wù)，這樣就會(huì)產(chǎn)生更大的功耗。在這兩種情況下，應(yīng)找到折中的方式，實(shí)現(xiàn)系統(tǒng)總功耗最低。

每個(gè)系統(tǒng)任務(wù)存在一個(gè)實(shí)際的工作時(shí)間，保證這個(gè)時(shí)間結(jié)束點(diǎn)不超過(guò)截止時(shí)間就滿足系統(tǒng)性能要求。在系統(tǒng)工作中，各個(gè)任務(wù)之間存在競(jìng)爭(zhēng)資源的時(shí)間段，本文稱之為沖突時(shí)間。圖1給出了系統(tǒng)功耗優(yōu)化方法的工作流程。

圖1 系統(tǒng)功耗優(yōu)化流程

具體步驟如下：

（1）建立模型。根據(jù)實(shí)際系統(tǒng)建立計(jì)算單元與主存間的訪問(wèn)模型，并從實(shí)際系統(tǒng)中獲取模型所需常量，模型需要從實(shí)際系統(tǒng)中獲得的常量有：任務(wù)的截止時(shí)間，任務(wù)的指令數(shù)量，計(jì)算單元訪問(wèn)主存次數(shù)，計(jì)算單元每秒處理的指令數(shù)量，無(wú)訪問(wèn)沖突時(shí)芯片負(fù)載電容及存在沖突時(shí)芯片負(fù)載電容，任務(wù)間優(yōu)先級(jí)關(guān)系，系統(tǒng)工作電壓。

（2）計(jì)算任務(wù)間沖突概率、等待時(shí)間與沖突時(shí)間、任務(wù)實(shí)際工作時(shí)間的映射關(guān)系。在沖突時(shí)間內(nèi)，根據(jù)任務(wù)訪問(wèn)資源的方式及優(yōu)先級(jí)大小，可以獲得每個(gè)任務(wù)沖突概率模型及其等待時(shí)間長(zhǎng)度。

（3）計(jì)算每個(gè)任務(wù)最低工作頻率與沖突時(shí)間、任務(wù)實(shí)際工作時(shí)間的映射關(guān)系。計(jì)算得到任務(wù)由于沖突而導(dǎo)致的等待時(shí)間后，可以推知每個(gè)任務(wù)真正運(yùn)行指令的實(shí)際有效工作時(shí)間，從而得到任務(wù)最低工作頻率。

（4）計(jì)算系統(tǒng)總功耗、峰值功率與沖突時(shí)間、任務(wù)實(shí)際工作時(shí)間的映射關(guān)系。在得到系統(tǒng)任務(wù)的最低工作頻率后，根據(jù)CMOS反相器的平均動(dòng)態(tài)公式求得系統(tǒng)峰值功率、系統(tǒng)最低總功耗與任務(wù)工作時(shí)間、沖突時(shí)間的映射關(guān)系。

（5）通過(guò)軟件優(yōu)化，得出滿足系統(tǒng)峰值功率約束下，系統(tǒng)總功耗最低時(shí)任務(wù)間的沖突時(shí)間及每個(gè)任務(wù)實(shí)際運(yùn)行時(shí)間。

（6）軟件調(diào)度任務(wù)實(shí)際工作時(shí)間及工作頻率，保證滿足優(yōu)化后的任務(wù)沖突時(shí)間，即可實(shí)現(xiàn)滿足系統(tǒng)峰值功率約束下的系統(tǒng)總功耗最低。

最后可根據(jù)實(shí)測(cè)系統(tǒng)功耗結(jié)果，進(jìn)行誤差范圍內(nèi)調(diào)整或重新執(zhí)行以上步驟。下文將以已知常量為基礎(chǔ)，建立2個(gè)計(jì)算單元的系統(tǒng)模型進(jìn)行功耗優(yōu)化方法的論證。并在此基礎(chǔ)上進(jìn)行延伸，分析多個(gè)計(jì)算單元獨(dú)立運(yùn)行多個(gè)獨(dú)立任務(wù)時(shí)系統(tǒng)功耗優(yōu)化方法。

本文的建模方法、任務(wù)沖突概率及等待時(shí)間的計(jì)算方法參考已有研究成果［1-2］，在此基礎(chǔ)上，增加沖突時(shí)間變量和任務(wù)實(shí)際工作時(shí)間變量，且固定任務(wù)之間優(yōu)先級(jí)，建立沖突時(shí)間變量、任務(wù)實(shí)際工作時(shí)間變量與系統(tǒng)功耗之間的映射關(guān)系。

3 模型建立及優(yōu)化方案

本節(jié)將建立SoC系統(tǒng)模型，分析各計(jì)算單元之間主存資源競(jìng)爭(zhēng)情況，通過(guò)優(yōu)化各單元時(shí)鐘頻率，降低由于訪問(wèn)主存沖突而引起的無(wú)用功耗，在保證系統(tǒng)性能及滿足系統(tǒng)峰值功率約束的前提下，優(yōu)化系統(tǒng)總功耗。

3.1 模型建立及假設(shè)

假設(shè)SoC系統(tǒng)中有2個(gè)計(jì)算單元，忽略總線的限制，只考慮主存訪問(wèn)限制，只允許一個(gè)計(jì)算單元單獨(dú)訪問(wèn)主存，在被訪問(wèn)過(guò)程中，后來(lái)的訪問(wèn)發(fā)起者將處于等待狀態(tài)。其他外設(shè)單元暫不考慮。圖2給出了模型架構(gòu)。

圖2 模型架構(gòu)

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

CUi：計(jì)算單元；

Ti：應(yīng)用任務(wù)；

D：整個(gè)系統(tǒng)任務(wù)截止時(shí)間；

tsi：CUi由于器件本身特性造成的時(shí)間損耗；

P：系統(tǒng)額定峰值功率。

以上常量通過(guò)其他方法獲得，本文不做分析。假設(shè)2個(gè)CUi運(yùn)行的任務(wù)Ti完全獨(dú)立，同時(shí)運(yùn)行一個(gè)任務(wù)期間，CUi工作頻率不變。

每個(gè)CUi需要在截止時(shí)間D前完成任務(wù)，完成每個(gè)任務(wù)時(shí)間可以為截止時(shí)間D內(nèi)任意時(shí)間段，用Li表示任務(wù)實(shí)際運(yùn)行時(shí)間。每個(gè)任務(wù)有Ii條指令，由于CUi在訪問(wèn)主存時(shí)可能產(chǎn)生資源競(jìng)爭(zhēng)沖突，導(dǎo)致處于等待狀態(tài)，因此使用ti表示任務(wù)實(shí)際有效運(yùn)行時(shí)間，tcon表示CUi間沖突時(shí)間，tdelayi表示由于沖突引起的等待時(shí)間。

所以：

CUi的運(yùn)行頻率與指令數(shù)量Ii以及實(shí)際有效運(yùn)行時(shí)間ti有關(guān)［8］，在模型中可以按照下列公式給出每個(gè)計(jì)算單元的運(yùn)行最低頻率fi，式中采用一個(gè)常數(shù)因子c，它是計(jì)算單元每秒處理指令數(shù)量。

在現(xiàn)有工藝下，系統(tǒng)功耗主要來(lái)源于動(dòng)態(tài)功耗，而動(dòng)態(tài)功耗的主要部分為開(kāi)關(guān)功耗，根據(jù)CMOS反相器的平均動(dòng)態(tài)公式可推知系統(tǒng)功率與頻率關(guān)系：

因?yàn)楸疚闹环治鱿到y(tǒng)時(shí)鐘調(diào)度，所以模型建立在電壓恒定的基礎(chǔ)上，Vdd為常量。a為常數(shù)因子，CL為芯片負(fù)載電容，由于計(jì)算單元內(nèi)部實(shí)現(xiàn)時(shí)插入門控單元，當(dāng)與其他設(shè)備發(fā)生資源沖突產(chǎn)生競(jìng)爭(zhēng)等待時(shí)，將關(guān)閉計(jì)算單元內(nèi)部部分電路時(shí)鐘節(jié)省功耗，因此在沖突時(shí)間內(nèi)，CL將減小到C′L。

通過(guò)任務(wù)調(diào)度，2個(gè)任務(wù)可能同時(shí)進(jìn)行，也可能完全沒(méi)有沖突，當(dāng)2個(gè)計(jì)算單元發(fā)生沖突時(shí)，有一個(gè)計(jì)算單元會(huì)關(guān)閉內(nèi)部部分電路時(shí)鐘，另一個(gè)正常工作，所以系統(tǒng)峰值功率及功耗為：

當(dāng)tcon≠0時(shí)：

當(dāng)tcon=0時(shí)：

3.2 競(jìng)爭(zhēng)分析及頻率優(yōu)化

在CUi分別運(yùn)行不同的任務(wù)Ti時(shí)，系統(tǒng)可以通過(guò)軟件調(diào)度控制任務(wù)的起始時(shí)間，在運(yùn)行時(shí)，任務(wù)間在沖突時(shí)間tcon中存在競(jìng)爭(zhēng)沖突，通過(guò)優(yōu)化，調(diào)整任務(wù)起始時(shí)間以及沖突時(shí)間的長(zhǎng)度，在保證系統(tǒng)性能的前提下，盡可能地降低競(jìng)爭(zhēng)發(fā)生的概率及其引起的等待時(shí)間。

由于不同的系統(tǒng)中，CUi之間沖突方式及數(shù)量不同，概率計(jì)算方法不盡相同，本文重點(diǎn)在于提出系統(tǒng)功耗的整體優(yōu)化方法并證明其有效性及可行性，因此對(duì)于不同的概率計(jì)算方法不做詳細(xì)討論。針對(duì)本文提出模型，用lins表示每條指令從主存讀取所需時(shí)間mi表示CUi訪問(wèn)主存次數(shù)，兩者由應(yīng)用及硬件架構(gòu)決定。

在沖突時(shí)間段tcon中，由于CU1占用主存資源，CU0訪問(wèn)主存時(shí)發(fā)生沖突的概率為：

在tcon中，CU0訪問(wèn)主存的指令數(shù)量約為：

由于CU1占用主存資源，CU0每次取指時(shí)CU1已占用時(shí)間不確定，假設(shè)χ為其已完成進(jìn)度，因此CU0需要等待的平均時(shí)間為：

綜上，在沖突時(shí)間tcon內(nèi)，CU0需要等待的總時(shí)間為：

同理可得，CU1需要等待的時(shí)間為：

根據(jù)式（1）可以推知任務(wù)Ti的實(shí)際有效工作時(shí)間，根據(jù)式（2）可以求得任務(wù)Ti的最低工作頻率fi：

根據(jù)式（4）～式（7）可推知系統(tǒng)峰值功率及總功耗：

當(dāng)tcon≠0時(shí)：

當(dāng)tcon=0時(shí)：

這樣，得到系統(tǒng)峰值功率及總功耗與Ti實(shí)際運(yùn)行時(shí)間Li以及沖突時(shí)間tcon的映射關(guān)系，通過(guò)式（18）對(duì)變量加以約束，結(jié)合式（14）～式（17）即可獲得在滿足系統(tǒng)峰值功率約束下，系統(tǒng)總功耗最低時(shí)任務(wù)實(shí)際運(yùn)行時(shí)間及沖突時(shí)間，進(jìn)而可以求得系統(tǒng)各任務(wù)的工作頻率：

其中，fmaxi為CUi的最大工作頻率；fmini為CUi的最低工作頻率。

求得任務(wù)之間的沖突時(shí)間及實(shí)際運(yùn)行時(shí)間后，通過(guò)調(diào)整任務(wù)起始時(shí)間及時(shí)鐘暫停操作，使各個(gè)任務(wù)的實(shí)際運(yùn)行時(shí)間及沖突時(shí)間滿足約束，從而使系統(tǒng)總功耗最低。

3.3 多計(jì)算單元的優(yōu)化

上述模型同樣可以擴(kuò)展支持多計(jì)算單元的SoC系統(tǒng)。n個(gè)CUi分別運(yùn)行n個(gè)獨(dú)立的應(yīng)用任務(wù)Ti，由式（4）～式（7）可推知系統(tǒng)峰值功率及總功耗。

當(dāng)所有任務(wù)有共同沖突時(shí)間時(shí)：

當(dāng)部分任務(wù)存在沖突時(shí)：

在多個(gè)任務(wù)中，任務(wù)之間的沖突時(shí)間分別為2個(gè)任務(wù)之間沖突、3個(gè)任務(wù)之間沖突以至n個(gè)任務(wù)之間同時(shí)沖突，沖突時(shí)間tconij（i＜j且i，j∈｛0，1，…，n-1｝），tconijK（i＜j＜K且i，j，K∈｛0，1，…，n-1｝），以此類推。

在這些沖突時(shí)間中，每個(gè)任務(wù)由于沖突導(dǎo)致等待時(shí)間根據(jù)任務(wù)取指令方式確定。每個(gè)任務(wù)總的沖突時(shí)間為：

通過(guò)確定每個(gè)任務(wù)等待總時(shí)間與任務(wù)實(shí)際運(yùn)行時(shí)間、沖突時(shí)間的映射關(guān)系，就可以確定任務(wù)工作頻率、峰值功率、系統(tǒng)總功耗與任務(wù)實(shí)際運(yùn)行時(shí)間、沖突時(shí)間的映射關(guān)系，結(jié)合約束條件，求得各任務(wù)間的沖突時(shí)間及實(shí)際工作時(shí)間，進(jìn)一步求得每個(gè)任務(wù)的工作頻率，通過(guò)系統(tǒng)軟件調(diào)度任務(wù)工作起始時(shí)間，在截止時(shí)間內(nèi)合理分配任務(wù)工作時(shí)間，即可優(yōu)化系統(tǒng)功耗。

4 實(shí)驗(yàn)結(jié)果及分析

對(duì)上文所述的優(yōu)化方法驗(yàn)證時(shí)，本文所采用的SoC實(shí)驗(yàn)平臺(tái)集成了2個(gè)CK610 32位嵌入式處理器［9-10］、單路或多路64-bit AHB總線和SDRAM主存等。測(cè)試程序采用業(yè)界主流的嵌入式多核Benchmark：EEMBC multibench［11-13］。優(yōu)化前系統(tǒng)時(shí)鐘采用20 MHz。

本文實(shí)驗(yàn)使用Matlab工具。在使用Matlab優(yōu)化最優(yōu)解時(shí)，考慮到目標(biāo)函數(shù)不是線性的，方法有2種：第1種方法采用Matlab的非線性規(guī)劃函數(shù)，但這種方法有時(shí)求得的為局部最優(yōu)解；第2種方法通過(guò)取點(diǎn)方式計(jì)算，是一種離散算法，滿足前提是函數(shù)不會(huì)在一定局域內(nèi)突變，以一定步長(zhǎng)在變量約束范圍內(nèi)取值，遍歷所有可能的值，步長(zhǎng)越小，結(jié)果越準(zhǔn)確?？紤]到實(shí)驗(yàn)平臺(tái)中目標(biāo)函數(shù)和約束條件比較簡(jiǎn)單，因此，本文采用第2種方法進(jìn)行求解。

為驗(yàn)證本文提出的方法對(duì)系統(tǒng)功耗的優(yōu)化效果，進(jìn)行以下3組實(shí)驗(yàn)。

實(shí)驗(yàn)1 忽略峰值功率的約束。表1給出了實(shí)驗(yàn)結(jié)果，其中，fi為優(yōu)化前CUi工作頻率；f′i為優(yōu)化后CUi工作頻率。

在沖突時(shí)間為0時(shí)，系統(tǒng)總功耗最低，這個(gè)結(jié)果在式（21）中也可以得以驗(yàn)證，沖突時(shí)間為0，則沖突等待時(shí)間為0，式中的第2項(xiàng)最小，系統(tǒng)總功耗最低。

表1 系統(tǒng)總功耗最低時(shí)的實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)2 不考慮系統(tǒng)總功耗，使峰值功率最低。表2給出了實(shí)驗(yàn)結(jié)果。由表中數(shù)據(jù)可知，沖突時(shí)間只有2種情況：0或D，因此，軟件上僅存在2種優(yōu)化的可能性。圖3給出了模型在獲得任務(wù)實(shí)際運(yùn)行時(shí)間及沖突時(shí)間后，通過(guò)軟件調(diào)度任務(wù)前后的進(jìn)度對(duì)比。分析這種現(xiàn)象的原因，圖4為存在沖突時(shí)間的假設(shè)優(yōu)化結(jié)果，其中，Loldi為優(yōu)化前任務(wù)完成時(shí)間；tstarti為任務(wù)起始運(yùn)行時(shí)間。

表2 系統(tǒng)峰值功率最低時(shí)的實(shí)驗(yàn)數(shù)據(jù)

圖3 優(yōu)化前后任務(wù)調(diào)度對(duì)比

圖4 假設(shè)的任務(wù)調(diào)度優(yōu)化結(jié)果

假設(shè)任務(wù)之間存在一段沖突時(shí)間0＜tcon_x＜D時(shí)系統(tǒng)峰值功率最低，則系統(tǒng)的峰值功率肯定是2個(gè)任務(wù)沖突時(shí)間段內(nèi)，也就是兩者峰值功率之和，同時(shí)降低2個(gè)任務(wù)峰值功率，才可能降低系統(tǒng)峰值功率，每個(gè)任務(wù)的功率與其工作頻率相關(guān)，而工作頻率又與其實(shí)際有效工作時(shí)間有關(guān)，實(shí)際有效工作時(shí)間越長(zhǎng)，頻率越低，峰值功率也越低。任務(wù)1的工作時(shí)間為t1+t2，如果在t2內(nèi)，任務(wù)1存在部分有效工作時(shí)間，沖突是概率事件，所以在t3時(shí)間內(nèi)，即使存在沖突，任務(wù)1仍然可以獲得實(shí)際有效工作時(shí)間，所以任務(wù)一的實(shí)際工作時(shí)間可以延長(zhǎng)為D，這樣系統(tǒng)峰值功率更小，同理，任務(wù)2的工作時(shí)間也可以延長(zhǎng)為D，進(jìn)一步降低系統(tǒng)峰值功率，從而使得任務(wù)沖突時(shí)間tcon_x也為D。如果在t2內(nèi)，任務(wù)1不存在實(shí)際有效工作時(shí)間，則任務(wù)1在t2內(nèi)不能完成任何工作，也沒(méi)有存在的必要，所以沖突時(shí)間tcon_x為0。2種優(yōu)化的可能性與實(shí)際任務(wù)的指令數(shù)量、沖突概率、取指周期相關(guān)，實(shí)際系統(tǒng)優(yōu)化方法選擇需要通過(guò)上文介紹方法進(jìn)行計(jì)算得知。

這樣得出結(jié)論：在任務(wù)截止時(shí)間相同的情況下2個(gè)任務(wù)之間的沖突，只有完全沖突，或者完全不沖突，才能實(shí)現(xiàn)系統(tǒng)峰值功率最低。結(jié)論可以進(jìn)一步擴(kuò)展為多個(gè)任務(wù)的系統(tǒng)中，任務(wù)兩兩之間完全不沖突，或者排除其他任務(wù)與之沖突部分，其余部分必須完全沖突，才能實(shí)現(xiàn)系統(tǒng)峰值功率最小。

實(shí)驗(yàn)3 考慮在系統(tǒng)峰值功率滿足約束的情況下，系統(tǒng)功耗最低。表3給出了實(shí)驗(yàn)結(jié)果。任務(wù)X 264-4M q與Rotate-4M s1w1雖然在沖突時(shí)間為0時(shí)系統(tǒng)總功耗最低，但是由于峰值功率的約束，無(wú)法實(shí)現(xiàn)沖突時(shí)間為0，在滿足峰值功率約束下，沖突時(shí)間為D時(shí)系統(tǒng)總功耗最低。

在結(jié)果中，進(jìn)一步發(fā)現(xiàn)任務(wù)間沖突時(shí)間仍然為完全沖突或者為0，分析原因，與上文的只考慮峰值功率時(shí)的現(xiàn)象原因不同，在這種情況下，出現(xiàn)沖突時(shí)間為D或者0是因?yàn)樵跊_突時(shí)間為0，系統(tǒng)峰值功率如果小于額定峰值功率，此時(shí)系統(tǒng)總功耗肯定為最小，實(shí)驗(yàn)1中已經(jīng)分析原因，這樣沖突時(shí)間就為0，如果沖突時(shí)間為0時(shí)，系統(tǒng)峰值功率大于額定峰值功率，則只有增加沖突時(shí)間才有可能降低峰值功率，實(shí)驗(yàn)系統(tǒng)沖突時(shí)間增大，也增加了實(shí)際有效工作時(shí)間，實(shí)際有效工作時(shí)間的增加降低了系統(tǒng)任務(wù)工作頻率，本文實(shí)驗(yàn)平臺(tái)中工作頻率降低對(duì)系統(tǒng)的影響恰好大于等待時(shí)間增加對(duì)系統(tǒng)的影響，這樣沖突時(shí)間為D時(shí)結(jié)果最優(yōu)，所以才出現(xiàn)了滿足峰值功率約束下系統(tǒng)功耗最低時(shí)，沖突時(shí)間為0或者D。

表3 系統(tǒng)滿足額定峰值功率約束且功耗最低時(shí)的實(shí)驗(yàn)數(shù)據(jù)

理論優(yōu)化頻率在實(shí)驗(yàn)中并不完全適用，存在誤差，理論結(jié)果偏小，這是由于沖突模型分析只考慮主存競(jìng)爭(zhēng)，實(shí)際系統(tǒng)中還存在核間架構(gòu)、總線競(jìng)爭(zhēng)等，同時(shí)計(jì)算過(guò)程中，為了方便計(jì)算，取指周期采用一個(gè)較小的固定值，而實(shí)際中它與系統(tǒng)頻率有關(guān)，計(jì)算單元完成任務(wù)時(shí)需要訪問(wèn)主存次數(shù)采用經(jīng)驗(yàn)統(tǒng)計(jì)值，其訪問(wèn)次數(shù)與實(shí)際應(yīng)用的程序結(jié)構(gòu)有關(guān)。以上導(dǎo)致計(jì)算的優(yōu)化頻率存在誤差，但實(shí)際最優(yōu)值存在于理論值附近，可以通過(guò)實(shí)際軟件調(diào)整實(shí)現(xiàn)，即可保證在截止時(shí)間前完成任務(wù)并降低功耗。

通過(guò)實(shí)驗(yàn)結(jié)果與文獻(xiàn)［1-2］對(duì)比，結(jié)果表明，文獻(xiàn)［1-2］中的系統(tǒng)任務(wù)沖突時(shí)間為整個(gè)任務(wù)周期，在此基礎(chǔ)上控制系統(tǒng)各任務(wù)的優(yōu)先級(jí)，優(yōu)化系統(tǒng)功耗。基于功耗、功率、時(shí)間三者的關(guān)系，功耗等于時(shí)間乘以功率，如果將時(shí)間確定為整個(gè)任務(wù)周期，則導(dǎo)致功耗和功率變化關(guān)系線性統(tǒng)一，而有的系統(tǒng)只要求總功耗最低，有的系統(tǒng)要求在一定的峰值功率約束下總功耗最低，固定沖突時(shí)間的體系方法并不能適應(yīng)所有系統(tǒng)的要求。本文提出的方法不是在已有研究上的優(yōu)化，而是提出可以在確定系統(tǒng)各任務(wù)優(yōu)先級(jí)的情況下，通過(guò)控制任務(wù)之間的沖突時(shí)間長(zhǎng)度，優(yōu)化系統(tǒng)功耗，并可以根據(jù)系統(tǒng)總功耗最低、系統(tǒng)峰值功率最低、系統(tǒng)峰值功率約束下總功耗最低3種情況下給出不同的優(yōu)化方法及依據(jù)，對(duì)于系統(tǒng)的功耗優(yōu)化更為靈活。

綜合實(shí)驗(yàn)結(jié)果及理論分析可知，本文所建立的分析模型可以實(shí)現(xiàn)系統(tǒng)在滿足峰值功率約束下的總功耗最小化。

5 結(jié)束語(yǔ)

本文根據(jù)目標(biāo)計(jì)算單元的相關(guān)參數(shù)建立功耗分析模型，通過(guò)分析計(jì)算單元間競(jìng)爭(zhēng)主存資源的概率，得到?jīng)_突時(shí)間以及由于競(jìng)爭(zhēng)而導(dǎo)致的延時(shí)，繼而分析每個(gè)計(jì)算單元的實(shí)際有效工作時(shí)間，求得在截止時(shí)間約束下的工作最低頻率，實(shí)現(xiàn)系統(tǒng)總功耗最低。由實(shí)驗(yàn)結(jié)果可知，任意2個(gè)計(jì)算單元間沖突時(shí)間為0或者排除其他任務(wù)與之沖突部分，其余部分必須完全沖突，系統(tǒng)峰值功率最低。在實(shí)際實(shí)驗(yàn)平臺(tái)中，當(dāng)滿足峰值功率約束時(shí)，本文方法可使系統(tǒng)總功耗優(yōu)化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嵌入式系統(tǒng)開(kāi)發(fā)教程［M］.北京：科學(xué)出版社，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并發(fā)時(shí)鐘調(diào)度管理［J］.計(jì)算機(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

國(guó)家自然科學(xué)基金資助項(xiàng)目（61100074）；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)基金資助項(xiàng)目（2013QNA5008）；國(guó)家科技重大專項(xiàng)基金資助項(xiàng)目（2009ZX 01030-001-002）。

修于杰（1989-），男，碩士研究生，主研方向：片上系統(tǒng)設(shè)計(jì)；黃 凱（通訊作者），副教授；林 威，碩士研究生；余 慜，博士；莫鵬飛，碩士；嚴(yán)曉浪，教授。

2014-09-04

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