TWI251171B - Task scheduling method with low power consumption and a SOC using the method - Google Patents

Description

1251171 九、發明說明： 【發明所屬之技術領域】 本發明是有關於-種排程方法，特別是指—種可對一 系統晶另具有的各元件進行循環多次的低耗能排程方法及 其裝置。 【先前技術】 目珂由於如手機、個人數位助理等可攜式電子產品的 風行，需在單一系統晶片（System on a Chip; SOC)上放入更 多的電晶體（Transistors)以達成輕、薄、短、小的目的，但 是當電晶體或邏輯問越來越多時，其功率消耗（p〇wer Dissipation)就會相對增加，若不能有效控制功率消耗，將 導致可攜式電子產品使用時因過熱導致系統不穩定。 主要為互補金氧半 cmTent)損失導致的 電子元件中一般功率消耗的來源， 導體（CMOS)電路中因為漏電流（Leakage 靜態功率消耗（Static pGwei. dlssipat_)，或因為切換暫態電 流（Sw]tChing transient current)和負載電容之充放電所產生 的動態功率消耗（Dynamic P〇wer dlssipati〇n)。 ^ 靜態功率消耗P心〜的功率消耗公式為·· 公式1 、N表示電晶體數目 則表示積體電路由反 流。

Psianc = XNX X J 其中’厂心表示電晶體之輸入電壓 、々如如表示系統設計常數，及W 向偏壓（reverse bias 】eakage)造成的漏電 至於動態功率消耗的功率消耗公式為· 公式2

Pdynannc = ^ X Q X f X Vj^ 1251171 公式 3 其中，f是工作時脈頻率、c是負載電容值、α是轉換 活性（switching activity)、々表示系統設計常數，及％表示 臨界電壓值。 由於系統晶月中的電晶體具有上述靜態及動態的功率 損耗因素，降低系統晶片耗電量的重要性與日俱增，而透 過低功率電路的設計與動態耗能管理（DynamiC p⑽U Management)，可使系統晶片在正常運算下，不會時常處於 高溫甚至過熱的狀態，減少了散熱的問題，且廠商也不用 為了替過燙晶月散熱付出更多的成本在晶片封裝上，使線 路的可靠性提高，並同時增加晶月的使用壽命。 為降低系統晶片的功率消耗，許多以調節電壓排程 (Variable Voltage Scheduling)方法的研究報告及發明被相繼 提出，例如 2001 年在 ASPDAC (Asia and Somh Pacific Design Automation Conference)會議中所發表名稱為，，Task scheduling for low-energy systems using variable supply voltage processor”，或 2000 年在 ICASSP(Internati〇nal Confeience on Acoustics Speech，Signal Processing)會議中所 % 表名稱為 Variable voltage task scheduling for minimizing energy or minimizing power”等論文中，提供了以動態調整 電壓（Dynamic voltage scaling)的方式對給定的工作（Tasks)進 行低功耗的排程來降低系統晶片整體的能量消耗。 至於如何排定各工作給不同的處理元件（processing Elements; PEs)的最低耗能之資料路徑及排程原理，可分別 1251171 參考在美國專利案公告號第5,83 1，864號i，，Designtoolsf〇r high-level synthesis of a low-power data path”及在美國專利 案公開號第 2003/0217090 號之”Energy-aware scheduling 〇f

Application executi〇n”等發明案。其中的美國專利案公開號 第2003/02Π090號中，即揭示一種以行動電話中具有的一 排程器（scheduler)對於欲排定之多項工作如何在多個處理元 件（mialt〗ple processors)進行排序，其排序原理是先就各工作 之消耗能量作排序，再根據各別工作的截止時間We』·) 先後依序分配至不同的處理元件上作處理，因而可得到最 佳的低耗能排程結果。 然而，先前的技術僅揭示了如何將各工作分配至系统 晶片令多個主要處理元件（PEs)的低減排程方法，對於系 統晶片中所具有的其它協同處理元件（NGn_PEs)(例如：輪出 =面及㈣電路等）’並未提出—套合併考慮的排程分析 人所知’在工作執行時，其它協助處理元件與 處理凡件之間的處理工作的效能是相互影響的，若是單： ，處理元件的低耗能排程而忽略其它協助處理= 因本，則乐統晶片整體功耗的估算 、 【發明内容】 〜果將疋不確實的。 , 一 I V风I六一禋以车絲曰ΰ 处理兀件與其它協助處理元 ’曰 低耗能排財法。 丨之_ ^進行综合評估

本發明之叉_ p, ,, B

目的，即在提供一種可即時m B 之處理元件盥复—π丄士 了 u β統日日 〜、匕協助處理元件之間的效能進行综合評 125117] 亚將各工作加以排程後發配至夂 方法。 σ件執行的低耗能排程 本务明之另—目的，即在一 它協助處理元# ’、種可對處理元件與其 、里兀件之間的效能進行 程的系統晶片。 口汗估以進行低耗能排 本赉明低耗能排程方法 / 執行之複數工作進行排ρ ^ 系對灰一系統晶片上欲 及複數協同處理元件，該等工 二數處理元件 協同處理元件上執行，該方法包含下二寺處理元件及該等 協同處理元件為最大耗能狀態二〔：㈧設定該等 該等處理元件上進行初步之排程Γ(Β)建立工作在 該等協同處理元件之間的_分）/亥寺處理元件及 算該等工作在該等戍 …::亚以该分析模式估 數；（cu 、广7°及6亥等協同處理元件之時間參 旧低耗刀析模式估計各工作在該等協同處理元件上之 取低耗能及時序關係仵上之 址果.及…4 (附-出在该寺處理元件上之排程 …互循環的方式重複步驟(c)及步驟 = 到穩定狀態。 辨狂〜果這 —本發明低耗能排程方法係對於一系統晶片上欲執行之 複數工作進行排裎，$ — “糸、、、克曰曰片具有複數處理元件及複數 協同處理元件，兮望τ ^〆丄 μ、乍係在該等處理元件及該等協處 理元件上執行，該系統晶片具有-排程器、-資诉分配模 組厂電源管理模組、複數處理元件及複數協同處理元件 ’該方法包含下述步驟：⑷該排程器以該等處理元件及該 1251171 專協同處理元件之味鬥姿垂 干之哙間麥數，將複數給定 理元件及該等協同處3 ^ 4 〇工作在该等處 刀IJ %理兀件加以分析，並 能之排序；I侍到所需最低耗 J茨排桎為將排序之結果交由 ，並進行各工作於爷# _ 、源为配杈組 戸万…亥寺處理凡件及該等協同 程；及（C)由导恭、IS Μ 义理兀件之排 … 管理模組進行各工作在該等；^ 1 该專協同處理元件上处兀件及 1干上的動悲電壓管理配置。 本發明糸統黑Η目士、— 丁兄日日片具有歿數處 件，及-主要控制置兀件*數協同處理元 之主要運管·兮# * k里兀件用以執行複數工作 運-，螻寺協同處理元件具有 將該等工作之t、f次> 你 匯k排，用以 述貢訊傳遞予該等處理元件；該算幸至4 制單元具有一排程器、一八 + 、要控 ，该排程器用以分妍今笠滲 里板組 時間參數對該等1作進扞⑽。…、⑺處以件之 &，该資源分配模4a用！^ $ 各工作於該等處理元件及#_❹ U用以调配 王…田 亥寺協同處理元件，及該電” 一 處兀件及該等協同處理元件上進t # /¾電壓管理配置。 仃動 【貫施方式】 有關本發明之前述及其他技術内容、特點與功 以下配合參考圖式之一者 在 楚的呈現。 列的詳細說明中，將可清 p如圖1所示’說明應用本發明低耗能排程方法的— 曰 …、先日日片1為一可加密/解密的晶片，在 曰日片1中可勃< ’丁、、、先 甲了執仃不同的工作（丁asks)，工作的定義 密/解密程式、中斷服菸笙 -如加 断服各寺，且各工作可獨立或與其他工作 1251171 同時被執行，至於欲處理的内容 步驟。然而孰"二同"的加密/解密 本發明之低耗能排程方法於I有广曰片設計者或可應用 片’並不以上述用以力 月牛么的日日片為限制。 必須說明的是，該方法是假設系統晶 件ΡΕ广ΡΕη具有動態電 . 牙'了處理元 -^^^(Dynamic voltage Scaling- :及電力卿。赠Ga㈣PG)特性，其它協同處』 mr)亦同樣具有相同的特性。而本發明之低桃能排 式供曰二：：疋在—電子計算機上執行的-程式軟體形 ❸進仃模擬’或者亦可以直接在系統晶片i 作成電路或燒製程式於其中，如此便可以即時地對資料進 行排程分析及處理。 本實施例中，該系統晶片1包括有-主要控制單元 lUMainControI]er)、一處理模組12、一輸出入介面模組 (DMA M〇dule)13、二外部匯流排14]、142及—内部匯流排 143等元件。 其中，主要控制單元U是用以對各工作進行資料運算 、分析及電力供給與資料流向的管理配置，在主要控制單 元Π内部整合有一排程器（Schedu】er)m、一電源管理模組 (Power Management) U2 及一資源分配模組（Res〇urce

Allocation Modu】e)113。 必須5兒明的是’熟知該領域的人士可知，排程器1 1 1除 可製成硬體元件或以程式的方式建構在主要控制單元}1中 ，亦可由外部的中央處理元件（CPU)之處理系統（〇s)或一外 10 1251171 部程式提供所需的排程功能，或是經由任一靜態處理方法 (Static me偏），亦、即離線之執行方式所獲取的預先排程， 均為可應用本發明之低耗能排程方法的範鳴。 處理模，组12具有複數處理元# PE广pEn，以往的排程 技術即是運用各種最佳化耗能分析將各工作在處理元件 PMn作運算，由於各處理元件PE]〜PEn的處理時間不一 ，當任—操作完成時處理元件PEI〜PEn將通知主要控 11 〇 、—輸出入介面模、组13具有複數通道（ch咖els)CH广CHm 及複數傳輸m31(Transfei. Engines);至於外部匯流排 1二' 142及内部匯流排（Internal Bus)l43等元件則是用以接 收貝枓，傳輸引擎131是根據通道CH]〜CHm中的資料格式 ㈣外部匯流排142要求記憶體(圖未示)中資料的轉換，接 :傳輸…31發配資料經内部匯流排143到各個處理元 件PE广PEn^内部匯流排143更可支援高速的資料轉換。 操作理單元112可以程式設U方式調控各元件分配 '巧低’而所有兀件的操作電壓共分為四個狀態： (^^壓、低Μ·、極低（咖L叫電壓及休眠 處理：：’配合排程器111的使用，各工作在各元件上的 將可依上述的操作電壓狀態切換。 參考先前技術所述的公式2及公式3可知， 操作電壓（vdd2)俞古 ^ 田兀件之 樣地，1 牛的處理速率（ρ—_)則愈快；同 、兀牛的工作頻率（f)愈高，則處 因此，夂-从丄， 丁々巧止相關。 ° 操作電壓為高電壓時，其處理逮率將最快 1251171 ，低電壓、極低電壓之處理速率則依少梦 則為無處理工作，因此 ：：’而休眠狀態 態。當欲产㈣ 〜耗力羊為極低或為不消耗的狀 便調二=工作負擔(L。-刺，電物 更。月匕知作電壓為高電壓 能增快，如此，晶…可依== 木作’壓而可達到降低功耗的功效。 配口圖1、2所示，說明在系統晶片1之中各元件 子於各工作進行排程分析及處理。 ° 可 進：各，描述資訊自外邹一 (步驟202)由主要控制單 由排程* m^ 將各工作的描述資訊交 -叫對欲排定之：…11使用一分析模式(An，ical 後再述)。 。工作進行預先的交互排程分析(方法容 、厂”、(步驟2〇3)排程器ln分析完成後，將分析結果交由資 組—爾工作排好的時程，將各工作排定： G驟204)啟動出出入介面模組& :::程進入各—理，-一包含各:： 兀PE】〜PE„以及其他的協同處理元件（例如：輸出入入 面模幻3、外部匯流排⑷、142及内部匯流排143等）。" _ G-K)5)在各工作的實際執行過程中’由電源管理單 兀112進行各工作在各元件所需之最低電能配置及供應。 以下將對於本發明之低耗能排程方法之分析模^作較 12 1251171 两砰細的說明： 如公式4所示，說明在單位時間内，假定等待在久處 理元件PE「PEn耗費的處理時間為Σ、'等待在協同二 兀件的處理時間為^^乂，，以及耗費 一 貝隹非處理兀件及協同 u的其它耗費時間為φ，例如記憶體讀取時間'外部匯流 排141、142傳輸時間、主要控制單 °又疋日守間或傳輪引 莩131啟動延遲時間等，故公 一 表不了在早位時間中各 元件佔用的時間比例（fracti〇n f 1 tlme)關係，假設其總和為 1 口此’只要知道了豈中任-却y八+ ”甲任—分的時間關係，即可推屮 剩下的另一部份的時間比例。 公式4 藉由以上公式4推得的運算結果，可 處理元件ΡΕι〜ΡΕη的處理 費在寺待各 理元件的處理時間為Σ、. /，·'、耗費在等㈣^ 才门马Ω"，進而估算出平均由 件所造成的時序（Laten i 之規劃。 船了'而依據其結果作出排程 定系統排程的穩定條件，該穩定條件有二， 二:：到穩定狀態時，進入處理元件的速率應等 同方；處理兀件實際處理-θ 子 ，立進出岸报-4 . 一疋在乐統達到穩定狀態時 總傳輸速率。 +、'心和應导同於内部匯流排的 θ所7F ’ #明本發明低耗能排程方 以下的例子是舉輪出入介面模組13之通道CH[^驟 部匯流排143等元件术你执 ,CHm 、内 寺几件虽作協同處理元件來作說明，該低耗 13 1251171 此饼桎万沄入级 第一階段 ，丨，丨„ ,八、首先輸入欲排定之工作（步驟3〇1)，假設其 它的協同處理元件是以最佳效能（Maximum perf〇rmance)狀 態來決定每一工作在主要處理元件PE,〜PEn上之操作電壓情 況，並由排程器先就各工作以先進先出（first_c〇me fim_ seived)的排程規則，對各工作的截止時間…㈡⑴比幻進行檢 查，。並將各工作調配至各處理元件PE]〜％來得到一初步的 排程結果（Initial scheduling 〇n pEs)(步驟 3的）。 必須說明的是’由於如何在處理元件％〜％以先進先 出的排程原理配置各工作之相關原理，並非本發明的重點 ，亚且可參考現有的排程技術，故在此不再詳述。 第二階段、接著’建立該等處理元 驟要：r;r#t靖理元件之時間參數(步 元件對要處理元# 〜％受其它協同處理 件對其處理效率的

功柘,★ (】1Cy)，其影響主要可分A 功耗及時間參數二部份。 女J刀為 因此，使用上述分析模式中 處理元件(例如：通道CH CH 式’即可決定協同 估計各工作在兮茸内部匯流排143)之影響以 在。亥寻協同處理元#卜夕曰 步驟304)，進而取低耗能及時序關係( r ,干 决疋對於通道CH广CHm及内部m义妞 細作電壓之π — 久門。Is匯流排ι43 又疋，以及推算每筆工作平抝# 士 件上的時間，接 二化在協同處理元 η . _ ’再與步驟302所得之排* 同處理元件在（步驟3 H，與協 )斤侍之耗能設定作比較(步驟3〇5)。 14 1251171 第三階段、分析諸程結果μ達到穩定狀^ 306) ’若得出的時序結果變異度極大，則以步驟州1 結果設定重新將各工作在料處理元件進行排程（步驟2 ’亦即，重複進行第…第二階段的排序及推算交） (InteraCtively)以上述估算值將各工作加以排序，持續以六 互循環的方式重複步驟（3G3)至步驟（3()5)直到排程結果又 穩定狀態。直到最後確定得出的時序結果趨於二j (1謂riable) ’若為歡值則輸出時序分析結果，並依,昭=

序分析結果作資源配置的動作（步驟3〇7)。 、 以下說明實際使用本發明低耗能排程方法排程 及電壓配置的實施例：假設系統晶片具有3個處理： (PE,〜叫、2個内部匯流排_s】〜ibuS2)及3 (cHl〜CH3)，另有8個工作項目π，)欲執行， 1組到達時間（Al.rival time)、截止時間（DeadHne t】^古 =壓之執行時間（Exeem_ time)，各卫作之到達時間问 時間及操作電壓為高電壓之執行時間，如表一所示· 止 表一

15 1251171 將欲排定之工作項目（τ】〜Ts)之描述資訊輪 先出的排程規則之排程器，先設定各協同處理 内部匯流排（IBUS】〜IBUS2)及通道（CH〗〜CH3)， 壓狀態來操作，來得到各工作項目在處理元件 壓情況，其初步排程結果如表二所示：

入給以先進 凡件，亦即 皆以最高電 上的操作電 接著，建立處理元件（PE】〜PEs)及内部匯流 (IBUS】〜mus2)、通道（CH广ch3)之間的分 1 丨妖八亚以該 通道 分析模式估算時間參數後決定各工作項目（τ丨〜丁8)在内部$ 流排（IBUS广IBUS2)、通道（CH,〜CH3)上的最低耗能及時: 關係，進而得到内部匯流排（I]BUS1〜IBUS2)、 (CH】〜CH3)之電壓狀態，如表三所示： 表三 _協同處理元件 電壓狀態 _ IBUS] 低 — ibus2 低 — CH】 低 — ch2 低 ch3 低 16 1251171 依照所得内部匯流排（BUS丨〜IBUS2)、通道（ch】〜ch 之電壓狀態，可推算每筆工作項目(τ]，費在内:嶋 扉uSl〜IBUS2)、通道（叫〜叫上的時間，將此資訊回 饋至排程器’ 1以最低耗能狀態重新決定各工作項目(T〜 丁8)在處理元件（PE】哪）之實際操作電I，如表四所示：1〜

表四 如圖4所;————— 筆穩定… 父互排程分析後，即可得到-

心的排程結果，而排程後的處理 壓分配結果說明如下： -件PE,〜PE 壓狀能為^兀件PE] •處理的工作項目T]〜T3，其操作1 狀心為處理卫作項目τ]後， > 休眠狀態。 -电壓、南電壓及 2·處理元件ΡΕ2 :處理的工作頂 壓狀態自處理工作項目τ / 4〜Τ6,其操作寫 盆餘時HP" 分別為極低電壓、高電壓， /、餘日寸間則呈休眠狀態。 土 3·處理元件PE3 :同時處理工 電壓狀態自處理工作項目τ 4 負目L〜丁其操Μ 作員目L後，分別為低電壓至處理完居 17 歸納上述，以本發明而言， 〆 一筌工你^ > rb忐 、设雜的系統晶片中， - 處理元件(PES)作出處理時，必定在… 凡件（non-PEs)上具有—定的 非處毛 排程好的工作，盆勒二費時間，而在此類系統晶> 征灯日j丄忭，具執打時間鹿 時間，而非以往僅考岸進；：我‘屯外^進入系統6 得知工作可供處理元件的時間，也因此⑸

首山 的真正時間限制，方才能I π出正確的工作開始執行間來加 ^ 各處理元件的低耗能排 "由方；以彺只考肩 ，使得夺統B K M w Λ 一匕協助處理兀件的因·! 整體功耗的估算 的低耗能排程方法，以李“猎由本發明 理兀件之間的效能進行綷 匕協助處 更為精確。 丁…估，將可使得到的排程結果 之較佳實施例而已，當不 即大凡依本發明申請專利 的等效變化與修飾，皆仍 二惟以上所述者，僅為本發明 ，以此限定本發明實施之範圍， 範圍及發明說明内容所作之簡單 屬本發明專利涵蓋之範圍内。 【圖式簡單說明】 々呢圑，說明應用本發明低耗 法的系統晶片具有的各元件； 热々圖2是一流程圖，說明在系統晶片之中各元件如 、D工作進行排程分析及處理； 圖 3 曰 、古 驟· 疋一奴程圖，說明本發明低耗能排程方法的/ ’及 18 1251171 圖4是一示意圖，說明經過本發明之低耗能排程方法 排程後的處理元件的電壓分配結果。

19 1251171 【主要元件符號說明】 1 …糸統晶片 11 •主要控制單元 111 …排程器 112; …電源管理模組 113 - …資源分配模組 1 2…… …處理模組 1 3 "… …輸出入介面 13 1 - …傳輸引擎 141、142外部匯流排 143 内部匯流排 201〜205步驟 301〜308步驟 - CH广CHm通道 ‘ PE广PEn，處理元件

20

Claims (1)

1251171 L—' … £ K ...-.·〜一 — ..、 、申請專利範圍·· 1. —種低耗能排程方法，係對於 數工作進行排程 广片上欲執行之複 處理元件上執行二處理元件及該等協同 匕3下逑步驟： ()σ又疋σ亥等協同處理元件 下，先將各該工作在之條件 ⑻· 寻處理兀件上進行初步之排程. € -分析模式，並以該分㈣4 :協同處理元件之間的 元件及該等協同广^ 作在該等處理 幼1 j處理凡件之時間參數； (C) 以該分析模式估計各工 上之最低耗能及時序關係； …同處理元件 (D) t异出在該等處理元件上之排程結果；及 續以其排程結果是否達到穩定狀態，若否則持 Λ又j %的方式重複步驟(c)及：、 果達到穩定狀態。 ）罝至排程結 2 ·依據申請專利節圖楚 判乾圍# 1項所述之低耗能排 ，在步驟（B)中，兮八1 在其中 )中，该分析模式估算之時間參數 分別在各處理元件及各協同處理元件的處理時;寻工作 3 ·依據申請專利節圖楚 J乾圍乐1項所述之低耗能排程方 ’在步驟（A)中，々/、中 σ ό亥工作在該等處理元件上 〃一、 之排程係以先進先出方式分配至各該處理元件作處=初步 4.種可以執仃低耗能排μ $ ^ w m _ 含複數可供一電腦載入以執行如申請專利範圍第7項二 21 1251171 述之方 / 第⑽31 28573申請案修^ 万法的電腦程式碼。 （修正日期·· 94年11月 5· —種低耗能排 數工作進行排程，，，於系統曰曰片上欲執行之複 協同處理元件，二統晶片具有複數處理元件及複數 處理元件上郝"°亥寺工作係在該等處理元件及該等協同 配模組、一 ':二該系統晶片具有-排程器、-資源分 理元件，心：：理模組、複數處理元件及複數協同處 4方法包含下述步驟·· )x排矛王為'以該等處理元件及兮笼门由 之時間參數m 亥寺協同處理元件 ,Λ π . :複數給定的工作在該等處理元件沒兮耸 協同處理元件力σ w八』 于处主兀件及该寻 ”彳’亚得到所需最低耗能之排序； (B) ,亥排程器 並進行各工作於^序之、‘、。果父由遠貧源分配模組， 程；及 、以W元件及該等協同處理元件之排 (C) 由該電源管理模組進行各工 及該等協同處理亓杜μ A 乍在n玄寺處理元件 6.依據申請專二ΤΓ態電•管理配置。 ’該排程器係以多次交二述耗嶋 該等協同處理元件所衣刀析求得該等處理元件及( 7 — 兀仵所而取低耗能之排序。 含複數=行低耗能排程之電腦可讀取之記錄婢體，5 s钹數可供—電 卞嫘肢，包 述之方法的電腦程式碼仃如中請專利範圍第5項所 8.—财以執行低耗能排程之系統晶片，具有·· 複數處理元件，用/ …叙力 用執行複數工作之主要運曾· 復數協同處理元件，罝 斤， ^ 父一匯流排，用以將該 22 斤 L4—一― ” ·斤；第093128 5 73申·請案.修正 等工作之資料流傳遞予該‘等〜产·……（修正日期：94年]1月 μ、义理元 一主要控制單元，具有一排程， 一電壓管理模组，兮从 °。、一資源分配模組及 俣、、且，该排程器用 等協同處理元件之時間參數對兮：析該等處理元件及該 源分配模組用以調配各工作於：：工作進行排程，該資 處理元件，及該#茂~ 、μ寺處理元件及該等協同 久々兒壓官理模組用 等協同處理元件上 在戎等處理元件及該 十上進仃動悲電壓管 9·'依據申請專利 呂理配置。 礼固弟8項所述之可、 系統晶片，：i： Φ 以執行低耗能排程之 一，該排程器係以多攻六 該等處理元件及 父互循環分析求得 干及该寺協同處理元件所仔（ 〇 而取低耗能之排序 10·依據申請專利蘇 τ已圍昂8項所述之可以郝y 系統晶片，其φ 戮仃低耗能排程 5亥寺協同處理元件# 排或至少一通道。 千係包括至少一匯流 23