夏開建，任曉剛，吳 玥

(常熟市第一人民醫(yī)院 信息科，江蘇 常熟 215500)

0 引言

移動電話的普適性、便攜性以及連通性使得它們成為連續(xù)感知應(yīng)用的理想平臺。移動電話含有多種傳感器，可以在連續(xù)感知任務(wù)中感知用戶不同類型的上下文[1]。移動電話采用電池供電，電池的容量決定著移動電話的使用時(shí)間。在連續(xù)移動感知應(yīng)用中，如何節(jié)約電量的消耗從而提高連續(xù)感知應(yīng)用的時(shí)間是最具研究挑戰(zhàn)的內(nèi)容之一[2-3]。

為了解決上述問題，研究人員提出在平臺中加入低功耗處理器，用于控制移動設(shè)備的傳感器。TI OMAP[4]平臺中除了含有應(yīng)用處理器內(nèi)核，還包含芯片級的低功耗處理器內(nèi)核。其基本原則是：低功耗處理器在活躍狀態(tài)消耗很小的能量，并且從睡眠狀態(tài)到活躍狀態(tài)的喚醒開銷幾乎可以忽略不計(jì)，因此可以有效率地執(zhí)行重復(fù)的感知任務(wù)。在感知任務(wù)中，應(yīng)用處理器處于睡眠模式，低功耗處理器感知傳感器的數(shù)據(jù)并在進(jìn)行計(jì)算密集型任務(wù)時(shí)喚醒應(yīng)用處理器。

Reflex平臺[5]為用戶在多處理器移動平臺上提供了一種簡單的編程體驗(yàn)。該平臺通過共享內(nèi)存技術(shù)將復(fù)雜的底層開發(fā)問題集成到低功耗處理器中，程序員可以使用標(biāo)準(zhǔn)的程序開發(fā)技術(shù)來設(shè)計(jì)應(yīng)用。X等人提出了一種概念驗(yàn)證原型系統(tǒng)LittleRock[6]，該系統(tǒng)強(qiáng)調(diào)了低功耗處理器在任務(wù)劃分中的有效性。區(qū)別于上述兩種方法，本文針對連續(xù)的感知應(yīng)用提出了一種任務(wù)劃分指導(dǎo)方法以及適當(dāng)?shù)倪\(yùn)行環(huán)境設(shè)計(jì)原則。本文提出的方法可以在上述兩個(gè)平臺中實(shí)現(xiàn)，是對這兩個(gè)平臺的補(bǔ)充。為了將工作負(fù)載劃分到異構(gòu)的平臺上，CUERVO E等人[7]和GORACAKO M等人[8]提出了基于整數(shù)線性規(guī)劃的任務(wù)劃分方法。前者研究任務(wù)在移動設(shè)備與云平臺之間的劃分，后者研究任務(wù)在兩個(gè)處理器之間的劃分。區(qū)別于上述兩個(gè)工作，本文采用基于模擬的方法以得到更接近真實(shí)值的準(zhǔn)確結(jié)果。

本文從能量有效的角度研究如何在應(yīng)用處理器和低功耗處理器上進(jìn)行任務(wù)的劃分，對任務(wù)劃分期間跨不同處理器的能源消耗和傳輸開銷進(jìn)行了量化，提出了一種應(yīng)用組件分析方法，并基于該方法對組件進(jìn)行最有效的劃分。

1 能量消耗比例

給定平臺P和應(yīng)用程序集合A，在P中運(yùn)行A中所有應(yīng)用消耗的能量為理想能耗。平臺P的理想平臺P^的定義為：P^與P有著相同的性能和能耗特征，P^的休眠能耗為0，并且從休眠狀態(tài)喚醒的時(shí)間和能耗都為0。在平臺P中運(yùn)行A的理想能耗為在理想平臺P^的應(yīng)用處理器上運(yùn)行A中所有應(yīng)用所消耗的能量。事實(shí)上，所有處理器在休眠時(shí)都有微弱的能量損耗，并且都有少量的喚醒時(shí)間和能耗。本文用EPA表示應(yīng)用集合A在平臺P上的真實(shí)能耗，那么有EPA＞。

在理想平臺中，當(dāng)應(yīng)用程序的執(zhí)行存在間隙時(shí)，系統(tǒng)進(jìn)入休眠狀態(tài)。然而在真實(shí)平臺中，系統(tǒng)是否進(jìn)入休眠狀態(tài)取決于程序的運(yùn)行間隙是否大于系統(tǒng)狀態(tài)轉(zhuǎn)換所需的時(shí)間[2，8]。給定 P和 A，為了量化真實(shí)能耗與理想能耗之間的差異，本文定義能量比例因子為：

當(dāng)所有的應(yīng)用程序都運(yùn)行在應(yīng)用處理器上時(shí)，因?yàn)檎鎸?shí)平臺的喚醒能耗大于0，故EPAPA＞1；當(dāng)應(yīng)用程序在應(yīng)用處理器和低功耗處理器上共享時(shí)，可以將應(yīng)用進(jìn)行任務(wù)劃分，使部分任務(wù)高效地運(yùn)行在低功耗處理器上降低EPA，從而使得 EPAPA＜1。給定平臺P，本文的任務(wù)是通過對應(yīng)用進(jìn)行任務(wù)劃分，從而最小化EPAPA。

2 處理器的能量消耗優(yōu)化

2.1 假設(shè)前提

為了簡化問題的分析，本文做如下假設(shè)：(1)假設(shè)感知應(yīng)用通過傳感器對數(shù)據(jù)進(jìn)行抽樣，并周期性的運(yùn)行。(2)假設(shè)那些對輸入數(shù)據(jù)進(jìn)行計(jì)算的特殊任務(wù)片段的運(yùn)行時(shí)間是常數(shù)，并不依賴于輸入數(shù)據(jù)。實(shí)際上，一些特殊的輸入數(shù)據(jù)，如全0輸入，可能會簡化計(jì)算，從而加快任務(wù)片段的運(yùn)行，此處假設(shè)這種差別并不顯著。(3)假設(shè)兩個(gè)處理器間的通信開銷相對于執(zhí)行時(shí)間和采樣周期可以忽略不計(jì)。在大多數(shù)處理器平臺中，應(yīng)用處理器和低功耗處理器在同一芯片中，因此通信開銷很低。此外，即使應(yīng)用處理器和低功耗處理器在不同的芯片中，也可以通過高速總線互聯(lián)，從而大大降低它們之間的通信開銷。(4)由于將感知負(fù)載轉(zhuǎn)移到低功耗處理器上，本文假設(shè)低功耗處理器的休眠與活躍狀態(tài)之間的狀態(tài)轉(zhuǎn)換開銷和休眠時(shí)的空閑能耗相對于其他能耗可以忽略不計(jì)。(5)假設(shè)所有的任務(wù)片段在這兩個(gè)處理器上都是可調(diào)度的。這意味著通過將任務(wù)片段劃分在不同的處理器上，可以降低應(yīng)用程序總的運(yùn)行時(shí)間。

由于傳感器的數(shù)據(jù)是連續(xù)的，而處理器處理的數(shù)據(jù)往往是離散的，采樣方法作為基本的傳感器數(shù)據(jù)處理方法不僅能很好地描述傳感器數(shù)據(jù)，還可以大大壓縮數(shù)據(jù)總量，因此假設(shè)(1)是合理的。假設(shè)(2)、(3)和(4)對問題的分析進(jìn)行了簡化，該假設(shè)會對分析結(jié)果產(chǎn)生微小的誤差，在對系統(tǒng)的整體性能進(jìn)行評估時(shí)，這些誤差可以忽略不計(jì)。通過對應(yīng)用程序的任務(wù)進(jìn)行分配，可以使任務(wù)在不同的處理器間進(jìn)行調(diào)度，因此假設(shè)(5)是合理的。

2.2 總的能量消耗

本文采用的符號的含義如表1所示。令應(yīng)用程序的調(diào)用包含N個(gè)任務(wù)片段，并且部分任務(wù)片段可能重復(fù)多次運(yùn)行，該應(yīng)用程序的每個(gè)周期的持續(xù)時(shí)間為d。令M表示應(yīng)用處理器，那么應(yīng)用程序的理想能耗為：

表1 符號含義表

事實(shí)上，應(yīng)用處理器的狀態(tài)轉(zhuǎn)換能耗和休眠能耗并不能忽略不計(jì)，于是真實(shí)能耗為：

其中Etrans·K表示處理器模式轉(zhuǎn)換的能耗。由于周期d遠(yuǎn)遠(yuǎn)大于應(yīng)用程序運(yùn)行時(shí)總共的模式轉(zhuǎn)換時(shí)間，因此本文忽略了處理器狀態(tài)的轉(zhuǎn)換時(shí)間。

當(dāng)平臺中含有M和L兩個(gè)處理器時(shí)，應(yīng)用程序可以按照比例被分割為若干個(gè)連續(xù)的活躍能耗和模式轉(zhuǎn)換能耗，于是能耗為：

由于將部分任務(wù)轉(zhuǎn)移到L上運(yùn)行，因此M上的模式轉(zhuǎn)換次數(shù)K′與 K不同。對比 EMulti與 EM，由于EMulti將部分任務(wù)轉(zhuǎn)移到低功耗處理器L上運(yùn)行，M上的模式轉(zhuǎn)換次數(shù)K′減小了，因此式(1)定義的能量消耗比例減小了。

2.3 任務(wù)片段劃分

為了確定最優(yōu)的能量比例因子，本文應(yīng)用了移動連續(xù)感知應(yīng)用的一些典型的特征。在這些應(yīng)用中，每個(gè)任務(wù)片段的輸出率會隨著計(jì)算管道明顯的降低。例如，采樣和緩沖任務(wù)片段在100 Hz頻率下采集和緩沖傳感器的采樣數(shù)據(jù)，而對緩沖數(shù)據(jù)進(jìn)行分類的操作會在更低的頻率(如1 Hz)下工作。此外，管道開始的任務(wù)片段是輕量級的，往往進(jìn)行簡單的數(shù)據(jù)緩沖和過濾，而管道的后續(xù)任務(wù)片段往往是計(jì)算密集的。

在確定任務(wù)片段的處理器時(shí)，由于任務(wù)是可調(diào)度的，其唯一決定因素為兩個(gè)處理器之間的相對能量消耗比例差異。如果i被劃分到L上時(shí)，其能量消耗比例相對于M減少了，那么將任務(wù)片段i劃分到L上。相對能量消耗比例差異Δi依賴于任務(wù)片段i的劃分，其計(jì)算方法為：

其中，D[i→M]表示任務(wù)片段 i被劃分到 M上，D[i→L]表示任務(wù)片段i被劃分到L上。

如果應(yīng)用式(4)作為應(yīng)用程序的能耗，那么當(dāng) Δi＞0時(shí)，將任務(wù)片段i劃分到低功耗處理器L上。式(5)中的參數(shù)si=TLi/TMi為任務(wù)片段i的減速因子。在給定的包含應(yīng)用處理器和低功耗處理器的平臺中，式(5)中的大多數(shù)參數(shù)都可以預(yù)先確定，其中與具體的計(jì)算任務(wù)片段相關(guān)的參數(shù)是 si。 由于 K′≤Fi，取最壞情況，即 K′≈Fi，可得如下公式：

應(yīng)用式(6)可以得到一條曲線，曲線的橫坐標(biāo)為TMi，縱坐標(biāo)為si。當(dāng)坐標(biāo)點(diǎn)落到曲線的右上方時(shí)，該任務(wù)在應(yīng)用處理器上運(yùn)行；當(dāng)坐標(biāo)點(diǎn)落到曲線的左下方時(shí)，該任務(wù)在低功耗處理器上運(yùn)行。

3 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

3.1 模擬器設(shè)計(jì)

本文分析多個(gè)應(yīng)用程序下所有應(yīng)用的計(jì)算時(shí)間、模式轉(zhuǎn)換次數(shù)以及程序的喚醒時(shí)間。為了對程序的性能更好地進(jìn)行描述，進(jìn)行細(xì)粒度的時(shí)間分析。圖1為實(shí)驗(yàn)采用的模擬器的整體結(jié)構(gòu)。本文采用基于事件的模擬器設(shè)計(jì)方法，采用3個(gè)輸入文件。第一個(gè)輸入文件包含系統(tǒng)的配置參數(shù)，如兩個(gè)處理器的在每種狀態(tài)下的能耗參數(shù)、CPU的運(yùn)行頻率、任務(wù)的調(diào)度策略以及狀態(tài)轉(zhuǎn)換能耗；第二個(gè)輸入文件為應(yīng)用程序配置文件，該文件描述應(yīng)用程序的任務(wù)片段劃分和連接結(jié)構(gòu)；最后一個(gè)輸入文件為多個(gè)應(yīng)用程序的跟蹤數(shù)據(jù)。模擬器計(jì)算出應(yīng)用程序的整個(gè)執(zhí)行路徑，并將相關(guān)的統(tǒng)計(jì)信息輸出，如處理器的能耗統(tǒng)計(jì)、執(zhí)行時(shí)間和狀態(tài)轉(zhuǎn)換次數(shù)等。模擬器的應(yīng)用處理器采用QSD8250精簡指令集處理器，低功耗處理器采用MSP430。

圖1 模擬器結(jié)構(gòu)圖

3.2 性能評估

為了評價(jià)模擬器上任務(wù)劃分的性能優(yōu)化程度，實(shí)驗(yàn)采用了活動識別和參考文獻(xiàn)[9]所提出的兩個(gè)具有代表性的方法進(jìn)行試驗(yàn)對比?；顒幼R別包括兩個(gè)階段，第一階段為讀取加速計(jì)的采樣數(shù)據(jù)并將其存儲在緩沖中，第二階段采用樸素貝葉斯方法對內(nèi)存中累積的數(shù)據(jù)進(jìn)行分類。SoundSense也是一種分類方法，其包括采樣、FFT、MFCC和貝葉斯分類4個(gè)階段。表2和3分別給出活動識別和SoundSense這兩種應(yīng)用的運(yùn)行時(shí)間。

表2 活動識別運(yùn)行時(shí)間

表3 SoundSense運(yùn)行時(shí)間

運(yùn)行時(shí)間分析：為了評價(jià)優(yōu)化算法的性能，實(shí)驗(yàn)分別在3種情況下實(shí)現(xiàn)了活動識別算法。第1種情況是兩個(gè)任務(wù)分別運(yùn)行在應(yīng)用處理器上，記為AP；第2種情況是兩個(gè)任務(wù)分別運(yùn)行在低功耗處理器上，記為LP；第3種情況采用優(yōu)化算法將任務(wù)劃分在不同的處理器上，記為LP-AP。圖2為活動識別算法在3種情況下的能量比例因子對比。在活動識別應(yīng)用中，隨著處理器頻率的增加，能量比例因子逐漸降低，在4種處理器頻率下LPAP的能量比例因子都是最小的并且與LP相接近。此外，實(shí)驗(yàn)測試了SoundSense算法下的能量比例因子效率，結(jié)果如圖3所示。在圖3中，橫軸表示SoundSense算法的不同階段運(yùn)行在不同的處理器上，縱軸為能量比例因子，分別將前 k(k=0，1，2，3，4)個(gè)節(jié)點(diǎn)遷移到 LP 上運(yùn)行。從圖中可以看出，當(dāng)k=2時(shí)，能量比例因子達(dá)到最小值，此后能量比例因子的變化很小。

圖2 活動識別能量比例因子對比

圖3 SoundSense能量比例因子對比

4 結(jié)論

本文引入了低功耗處理器，并提出了應(yīng)用程序在這兩個(gè)處理器上的任務(wù)劃分優(yōu)化方法。應(yīng)用處理器用于處理計(jì)算密集型任務(wù)，低功耗處理器用于周期性地感知外部環(huán)境的數(shù)據(jù)。模擬實(shí)驗(yàn)表明，由于將感知任務(wù)遷移到低功耗處理器上運(yùn)行，本文提出的優(yōu)化方法能大大提高移動設(shè)備的能量利用效率。

[1]王玉祥，喬秀全，李曉峰，等.上下文感知的移動社交網(wǎng)絡(luò)服務(wù)選擇機(jī)制研究[J].計(jì)算機(jī)學(xué)報(bào)，2010，33(11)：2126-2135.

[2]LU H，YANG J，LIU Z，et al.The Jigsaw continuous sensing engine for mobile phone applications[C].Proceedings of the 8th ACM Conference on Embedded Networked Sensor Systems，ACM，2010：71-84.

[3]BALAN R K，GERGLE D，SATYANARAYANAN M，et al.Simplifying cyber foraging for mobile devices[C].Proceedings of the 5th International Conference on Mobile systems，Applications and Services，ACM，2007：272-285.

[4]安健，桂小林，張文東，等.物聯(lián)網(wǎng)移動感知中的社會關(guān)系認(rèn)知模型[J].計(jì)算機(jī)學(xué)報(bào)，2012，35(6)：1164-1174.

[5]RA M R，SHETH A，MUMMERT L，et al.Odessa：enabling interactive perception applications on mobile devices[C].Proceedings of the 9th International Conference on Mobile Systems，Applications and Services，ACM，2011：43-56.

[6]PRIYANTHA B，LYMBEROPOULOS D，LIU J.Littlerock:Enabling energy-efficient continuous sensing on mobile phones[J].Pervasive Computing，IEEE，2011，10(2)：12-15.

[7]CUERVO E，BALASUBRAMANIAN A，CHO D，et al.MAUI：making smartphones last longer with code offload[C].Proceedings of the 8th International Conference on Mobile Systems，Applications and Services，ACM，2010：49-62.

[8]GORACZKO M，LIU J，LYMBEROPOULOS D，et al.Energyoptimal software partitioning in heterogeneous multiprocessor embedded systems[C].Proceedings of the 45th Annual Design Automation Conference，ACM，2008：191-196.

[9]NEWTON R，TOLEDO S，GIROD L，et al.Wishbone：Profile-based partitioning for sensornet applications[C].NSDI.2009，9：395-408.