TW519599B - Component-activity data flow equation on compiler for low power instruction sets - Google Patents

Description

519599 五、發明說明（1) 發明領域 本發明係關於元件為主資料流方程式分析 (component based data f 1 ⑽ eqUati〇n ana 1 ysis )。特 別是’關於一種結合彳氏紅此八隹〆, 口吸乾此指令集（1 〇 w ρ 〇 w e r instruction set)在編譯器（c〇mpi ler)的元件為主資料流 方程式分析方法。 發明背景 普式改重篇 益帶的演多 日攜上扮有 的決體上， 統解硬題理 系 了了問處 式為除耗的 入。，消化 嵌要題源佳 和重問能最 品常耗在做。 產非消也中文 子得源否程論 電變能與過表 式題的壞生發 帶問統好產和 攜的系的在獻 為耗式寫體文 因消入撰軟利 ，源嵌體對專 來能和軟針國 年得品，。美 近使產外色的 ，子之角Ea阳 及電良要相 如美國專利號5，7 9 0，8 7 4，在於分析程式指令間的相 依丨生（dependence)，並調整指令順序（instruction sequence ) ’以節省指令匯流排（bus )所消耗的電源。 應用頂域為h a m m i n g距離的縮小化（m i n i m i z i n g h a m in i n g distance) 〇 美國專利號5，8 8 Ο，9 8 1的文獻裡，揭露了一種在可程

519599

五、發明說明（2) 能Ϊ的方法。其中j吏 e r )次數的技術達到 用 低 式化的數位訊號處理器裡降低耗損 降低傳送資料到乘法器（mu 1 t 1 p U 耗能的效果。 美國專利说5，9 2 0，7 1 6的文獻裡，揭露了一種編譯p 段使用資料流分析方法分析程式中的述詞碼（predicate = code)，並且掌握區域性（i〇cai)述詞與全域性（gl〇bai) 述祠間關係的育訊。另一篇與述詞碼分析相關的美國專利 號5, 9 2 0, 7 1 6的文獻裡，使用資料流分析的方法分析程式 中的整個程序（procedure )，並且針對流程圖中每一區 塊（block)的述詞碼產生一組基礎集合（basis set)，然 後再針對基礎集合中的每一個述詞產生一組活集合 (1 i v e s e t) ’此糸統&供了配置暫存器（a 1 1〇c a t e register )時，暫存器之間的資訊。

另外’在已發表之論文裡’較為相關的為D a v i d I. August # A ^"Proceedings of the 30th International Symposium on Microarchitecture, December 1997， pages · 92-103 n 中提出之 nA Framework for Balancing Control Flow and Predication"，此文獻提出一個軟體架構（framework)， 利用此架構有效地收集資料流和控制流（c ο n t r ο 1 f 1 o w ) 的資料，並利用這些資訊協助編譯器對軟體進行最佳化動 作。另一篇由Erik Ruf 在Micros oft Research，March

第5頁 519599 五、發明說明（3) 出之，，〇PtimiZlng SpaI*Se Representatlons matrix)的八= = J此文獻^十對稀疏矩陣（sparse 式對於此絲、不/ 仃九，透過貢料流方程式來收集程 、此稀疏I料的使用 示HI51接士 、 用方法，亚利用這些資訊來重新表 少的轉換^料’使之Μ取此稀疏資料時’可以達到最 針對軟體在產生過程中 繹過程中改進原有的程式碼 間’促使軟體可以利用較少 做最佳化的處理，可在程式編 ’減少處理器中元件的活動期 的能源達到應有的表現。

" 般而言’電子系統的處理器中每-元件在每一個執

二週』（executlon cycle)中都有兩種狀態：一為活動狀 悲 UctlVe State)，另-為休眠狀態（resting state 在活動狀悲日守，兀件為充電狀態，隨時可以因應指令 品求，以執行所給予的任務，或正忙碌於執行指令。在休 眠狀態時’元件完全不做動作’係處於閒置（idU)狀態， 正寺待執行指令，不消耗任何電源或消耗微量電源。然 而，從休眠狀態返回活動狀態需要一額外電源，稱之為尖 峰電壓（peak voltage)。通常，在執行某一軟體前，元件 大多處於休眠狀態，一旦元件因執行需求進入活動狀態 後，則會一直處於該狀態，直到元件經過一段長時間沒有 動作後，才會被迫進入休眠狀態，此種情形稱之為時間耗 盡（timeout)。不同的元件時間耗盡期間的長度則不同。

519599 五、發明說明（4) 然而，以低功率的角度來看，在時間耗盡的這段期間便浪 費了許多不必要能源，因為元件消耗電源使其處於活動狀 態，但事實上並沒有任何動作發生。 為解決上述處理器中元件能源浪費的問題，本發明提 出一個有效的解決方法，利用元件為主資料流方程式分析 程式，在程式編繹過程中改進原有的程式碼，減少處理器 中元件的活動期間，降低電源的消耗量。 發明概要 本發明之元件流程分析系統的主要運作原理係利用 元件為主貧料流方程式分析程式’結合低耗能指令集在編 譯器，將來在處理器執行時的各個元件的活動狀態時，找 出程式碼中某元件長時間沒有動作的區段，以及利用此資 訊，編譯器可在此區段前插入元件休眠功能，促使元件提 早進入休眠狀態，以解決能源浪費的問題。 其主要目的之一是，提供一種結合低耗能指令集在編 譯器之元件流程分析系統。此元件流程分析系統主要包含 三個子系統，亦即，建構控制流程圖（c〇n s t r u c t f 1〇w g r a p h)、元件為主資料流方程式分析，以及指令碼 (instruction code)最佳 4匕。 519599 五、發明說明（5) 日月 <另一目的是，提供設計此元件流程分析系統 的方法。 ^ ^ 〇 x ^ ? 建構控制流程圖」模組將原始的指令 馬依二*秋顺序將分支（branch)、迴圈（1 oop)等控制流程 用圖升y α %地表現出來，並將程式指令切割成數個基本區 塊=不同基本區塊間的流程順序以箭頭表示。其輸入為 原也私式碼’而輪出為該原始程式碼的控制流程圖。 元件為主資料流方程式分析」模組更包含兩個子模 組。一子模組用以計算元件產生集合（c〇mp〇nent gen set)，另一子模組用以計算元件進入集合（c〇mp〇nent ιη set)、元件消滅集合（C〇mponent km set)和元件離開集 ^(component out set)。 八广1令碼最佳：匕；帛組則從「元件為主資料流方程式 刀析」模組所得到母個元件的活動灿、u α ， 幾個指令週期下，狀態都為休眠：’…件在連續 省電的條件下，在此指令區間=令區’並且在滿足

讓該元件休眠以節省能源。故其料個兀件休眠功能， 立控制流程圖」所輸出的原始程^為由上述子糸統「建 述模紐「計算元件進入集合、元件二制流程圖、以及由上 合」的元件離開集合，而輪出為改^滅集合與兀件離開集 螞。 良過後最佳化的裎式

519599 五、發明說明（6) 依此’本發明同時可適於硬體的元件環境，如果一硬 體元件一陣子不使用，則自動會關閉電源的情況，針對不 同的編6睪的不同指令安排（instruction scheduling)方 式’本發明可蒐集元件的電源開啟及關閉在程式中執行的 狀況’而評斷不同的指令安排方式，何者在元件活動方面 較為省電。 兹配合下列圖式、實施例之詳細說明及專利申請範 圍’將上述及本發明之其他目的與優點詳述於后。 發明之洋細說明 圖1為本發明之元件流程分析架構的方塊示意圖。如 圖1所示’此元件流程分析架構分成「建構控制流程圖」 模組1 0 1、 「元件為主資料流方程式分析」模組丨〇 2，以及 「指令碼最佳化模組」1 〇 3。 「建構控制流程圖」模組1 〇 1建構了一個有向圖（ directed graph)，此有向圖將控制流程資訊（n ow — 〇ίο 〇 n t r 〇 1 i n f〇r m a t i〇η )力口人原女台指令石馬白勺區塊白勺集合裡〇 「元件為主資料流方程式分析」模組1 〇 2包含兩個子模組 1 0 2 a和1 0 2 b。子模組1 0 2 a用以計算在控制流程圖裡每一個 區塊的元件產生集合，子模組1 0 2 b用以計算在控制流程圖

liillis 111

第9頁 ---- 、發明說明（7) 元件消滅集合和元件離開 個區塊的元件進 集合。 市口 根據本發明，「备 將原始的指八码^六” ^構控制流程圖」模組建構的有向圖 訊用圖报、、主1 ’、、、心、流程順序將分支、迴圈等控制流程資 區塊：二t表現出*，並將程式指令切割成數個基本 l0 ^ _ 土本區塊間的流程順序以建立鏈結（1 i n k )， 如以河頭表示’來表示流程。 而 「元俾炎+ — 指令使用處王里哭'/貧2流方程式分析」模組102分析每個 式，準確地算：：：：的狀態，#用反覆的資料流分析方 元件。 ：個日寸序（clock cycle)中狀態為活動的 程式二 ^^^^2^；；s：；；c^；+〇^ ^^^ > a ^ ^ < ^-^vinstruction cvni^\ ,, ^ 為休眠的指令區卩彳# )下，狀悲都 區間前加入-個：眠在:…電的條件下，在此指令 休眠功此，讓該元件休眠以節省能源。 、下羊、、、田。兒明各模組的細部流程。 圖2 a說明本 之 建構控制流程圖」 程圖」模組1 0 1的輪 部流程。「建構: /；IL 模組1 0 1的細 八為原始程式

五、發明說明（8) 碼，而輸出為該原始程 馬的控制流程圖。 參考圖2a，控制流裎 步驟2 0卜2 0 4 : <建構流程依序分成下列四個 步驟201 :決定原始程式碼 本區塊（basic h 二敘述（statement )為基 l〇ck)的首引（ieader)。 步驟2 0 2 ·對每—個首弓丨， 引為基本區塊的自組成一個基本區塊，以首 但不包含下—:頌’包含所有以下的敘述， *首弓1之後的敘述。 步驟2 0 3 :依照原始程式， 來表示流程。 立鍵結以連接不同基本區塊 步驟2 0 4 :將基本區塊中的$ 即每個區塊中只=個敘述晝分為一個區塊， 、匕含~個敘述。 根據本發明，步驟2 〇]之 ^

一個敘述即為一首引，（b ) ’、疋的法則為：（a )程式的第 (conditional goto)或無條二==條件跳躍 a ^ kk ^ ^ p\ (unconditional goto) 目標的敘述即為一 i引，（c )钰 g〇1：0； 跳躍（conditional goto)後的敘述卽氧 ☆土’、件 i延即為一百引。而步驟 20 3中建立鏈結的方式可以箭頭來表示流程。

$ 11頁 519599 五、發明說明（9) 圖2b為一個aAlpha機器碼（machine c〇d 古 的原始程式碼’作為「建立控制流程圖」模組“= 押岳丨！2c為圖2b原始程式碼經圖2a之流程步驟後，產生的 B制&5圖。圖2c中，根據步驟2〇1之決定的法則，區塊 步㈣2 BBH6和严塊&内所含的敛述為首引。根據 SB X L 基本區塊，分別含區塊&至區塊Β ]〇 。鬼11至&塊^、區塊B16至區塊I、和區塊3 B3。。根據步驟20 3，整個圖2c即為控制流程圖。： ▲ 驟m ’四個基本區塊共分為 Ύ广 個區塊中只包含一個敘述。 叫至£ _3Q，且母 、b2 假設原始程式可分為μ固區塊，分別為]

Bk，欲分析的元件有η個’分別為Cl、c 、c 、. c . 據本發明，則計算元件逄4 2 3 、cn。根 程式碼、沪八1 & 生木3的模組1 02a的輸入為原始 Ϊ匕二 的對照表、…「建立控制流 的元件產生集合以及每—區 輛出為所有&塊 數。圖3a說明模組102“"土：】：：：件所須要的時序 考圖3a，此細部流程依生集合的細部流程。參 外刀成下列三個步驟3〇1〜3 0 3 : 步驟301 :對每一個區塊針對欲分析的每-元件，新增一

第12頁 519599

五、發明說明（10) 個二維陣列的參數 C y c 1 e C 〇 u n t，ϋ且將 CycleCount所有的元素的初始值皆設為0，亦即 CycleCount[Bi][Cj] = 0，其中 1 — i ^ k、 j ^ n。CycleCount[Bi][Cj]用來表示區 塊B使用元件C所須要的時序數。 步驟302:在每一區塊中，建構屬於該區塊的元件產生集 合comp_gen set。並且將此集合的初始值設為 空集合。 步驟3 0 3 :依指令的執行順序，對每一區塊b i中的指令做 下列動作： 從指令與元件使用的對照表中查得該指令與元 件使用的關係，假設該指令使用C元件& j固時 序、C武件CC 2個時序.....c死件cc ^固時1序 則將時序數不為〇的元件加入該區塊的產生隹 中，並且將CycleCounttBiHC!^值加上cc市、合

CycleCount [Bi] [(：2]的值加上 CC2、···、 Γ CycleCountCBJCCJ的值加上 CCn。 現舉例說明如下：假設一原始程式碼，在十個

至B 1Q中含六種指令I至I ^如圖3b所示。在~系統中品^鬼乂B 析的有四種元件CrCr分別為算術邏輯單位（ALU)奴^ 法器（multi pi ier)、除法器（divider)，知次士丨三乘 ^貝料匯流

第13頁 519599

五、發明說明（π) 排（data bus)。圖3c表示圖3b中指令與元件使用的對昭 表。例如由圖3 Μ寻知，區塊B執行指令I 1，且由圖3 '得… 知，指令I用到元件C算術邏輯單位，且執行指令！須f c 個時序。因此，Cy c 1 e Coun t [ B 2] [ C !]的值加3且區塊b μ產^ 生集合包含元件C!。經此元件產生集合之計算步驟3〇 3處 理後，得到每一區塊的元件產生集合以及母一區塊B使用 元件C所須要的時序數CycleCount[Bi][Ci]，如圖示 接下來，圖4a説明模組1 0 2b計算元件進入集合、元件 消滅集合與元件離開集合的細部流程。模組1 0 2b的輪入為 由上述「建立控制流释圖」模組1 0 1所輸出的原始程式控 制流程圖、「計算元件產生集合」模組1 〇 2a所輪出的每個 區塊的元件產生集合，以及每一區塊使用每一元件所須要 的時序數，而輸出為所有區塊之元件的進入集合、消滅集 合及離開集合。 假設原始程式使用k個區塊’且使用姻元件’而輸入 為每一區塊Bi的元件產生集合comp-gen[Bi]以及每一區塊 B使用元件C所須要的時序數Cyc 1 eCount [ B i] [ C ]·]，输出為 每1一區塊B的元件進入集合comp-i n [ B」、元件消滅集合 comp一ki 1 1 [BJ與元件離開集合comP-〇ut ，其中K匕 k且 1$ η。

第14頁 519599 五、發明說明（12) 參考圖4 a，此細部流程依序分成下列三個步驟 401〜403 : 步驟4 0 1 ·在母一區塊I中，建構屬於該區塊h的元件進 入集合comp — intBi]、元件〉肖滅集合 comp —ki 1 1 [^ ]及元件離開集合comp —out [B,]; 元件進入集合comp+infBi]與元件消滅集合 c〇mp —ki 1 1 [ Bi ]的初始值設為空集合，元件離開 集合comp__ou t [ Bi ]的初始值設為該區塊的元件 產生集合comp —gen [ Bj ]。 步驟4 0 2 ··對每一區塊&做下列動作： 4 0 2 a :對每一個欲分析元件Cj，比較匕的所有前 區塊（predecessor)的 CycleCountfBjfQ] 值，取其最大值，假設此最大值為CCmax ，若CCmax不為〇，則將CCmax的值減1， 若減1後的值為0，則將元件Cj加入該 區塊的元件消滅集合comp_ki 1 1 α ]中。 若（CCmax-1)的值大於 的值，則將C y c丨e C 〇 u n t [ Bi ] [ Cj ]的值設為 (CCmax-1) 〇 4 0 2 b ··將該區塊的元件進入集合c 0 m p _ i n [ Bi ]設 為該區塊所有前區塊的元件離開集合 comp — outiBd 的聯集（union)，亦即

第15頁 519599 五、發明說明（13) comp—intBi]: Ucomp一〇ut[P]，其中P 為1 的前區塊。 4 0 2 c ··將言玄區塊的元件离隹開集合c〇m p —〇u t [ B】]言史 為該區塊元件進入集合comp_in[Bi]與元 件消滅集合comp_k i 1 1 [ Bi ]的差集 (difference)後，再與元件產生集合 comp —gen [BJ作聯集，亦即 comp —outA ]=comp —gentB! ] U (comp_i n [ B1 ] - comp_k i 1 1 [ B}])。 步驟40 3 :重複步驟40 2，直到所有區塊的元件離開集合不 再產生變化。 用上述圖3C 至Bi4中含六 元件心~(：4， 料匯流排。 立控制流程 為「計算元 產生集合。 合、元件消 位元（blt ) 合不包含此

說明如下：圖4 b例示一輸入的原始程式碼。使 所示之指令與元件使用對照表。在丨4個區塊b 種指令L至Ιβ，且在一系統中欲分析的有四種 分別為异術邏輯單位、乘法器、除法器，和次 圖4c所不為圖4b之原始程式碼經過子系統「建 圖」1 〇 1所輪出的原始程式控制流程圖。圖& d 件產生集合」模組丨〇 2 a輸出的每個區塊的元件 圖4e為由步驟40 1所得到的初始元件進入集 滅集合及元件離開集合，其中每一集合由^ 一分別代表C]、（：2、Q、Q四個元件，〇表示此集 元件，1表示此集合包含此元件。例如 木

第16頁 519599 、發明說明（14) " ---— c omp—out[B2]:l〇0〇 表示comp 一〇u t [ B2 ]這j固隹 元件離開集合」模組1 0 2b的輸出元件進入7^隹件^消滅集合 [Bi ]、元件消滅集合c〇mp —k i 1 1 [ β·]與 木 0 c〇mP_ i n comp —out [Bi ]示於圖4f中。 離開集合 元件且不包含元件C2、元件C3、和元件c 。，合包含這個 ί 0 2的運算之後，「計算元件進入集合4、元、、二過2次步驟 .102b的輸出元件淮 肖减集合與 *丁遣入集人一 如 休眠兩 以因應 指令； 狀態， 。然而 常，在 件因執 到元件 態。判 value) 元件在每一個執 ’元件 予的任 完全不 耗任何 狀態需 大多處 ，貝1J會 作後， 狀態的 行週期 為充電 務’或 做動作 電源或 要一額 於休眠 一直處 才會被 b界值 前所述，每 種狀態。在 指令需求， 而在休眠狀 正專待執行 ’從休眠狀 執行某一軟 行需求進入 經過一段長 定是否將元 記為L_st。 活動狀態時 以執行所給 態時，元件 指令，不消 態返回活動 體前，元件 活動狀態後 時間沒有動 件轉為休眠 中有活動或 狀態，隨時 正忙碌於執 係處於閒 ’肖耗微量電 外電源。通 狀態，一旦 於該狀態， 迫進入休眠 (critical 休眠=明針對不同的元件硬體設計’提供下列相對應的 )右1元件提供開/關（〇n/〇 f f)硬體設計，即此元件可 才曰々或‘令集的下達，切斷其電源之提供，使該元 519599 五、發明說明（15) 件從耗電狀態轉為不耗電狀態。在此情況之下， Lc〇nst值可依下列的成本模式（c 〇 s ^ ^ 〇d e 1 )決定

* ACT(v)； P(V) + SLEEP(v) 一又據此λ式。十异Lc〇nst的最小值，其中，p (v )為該 件的大峰包I，SLEEP( v)為使該元件進入休眠狀態 的電壓，ACT(V)為使該元件維持在活動狀態的電壓。 (b)若該元件僅提供低耗電硬 或指令集的下達，降低其 電狀態轉為低耗電狀態. 下列的成本模式決定： 體設計，即此元件可依指令 黾源之提供，使該元件從耗 在此情況之下，Le〇nst值可依

P(v) + SLEEP(v) const 木 [ACT(v) -LPOff(v) 執：⑽⑺為該元件維持在低耗 執仃週期（execution cycle)么 σσ a ^ ^ 休眠狀態的時間大於L元件連續肩 入休眠功㊣ -值，則在此連續時區之前' 接下來 圖5 a說明本發明之 m的細部流程。「指令碼最佳、佳化」模組 丹k利机％圖」杈組丨〇 i所輸出 门 J原I桎式控制流程圖

第18頁

519599 五、發明說明（16) 和模組「計算元件進入集合、元件消滅集合與元件離開集 合」1 0 2 b所輸出的元件離開集合，而「指令碼最佳化」模 組1 0 3的輸出為改良過後的最佳化程式碼。 假設欲分析的元件有η個，分別為C!、C2、C3、…、 C n，並且全集合（a 1 1 s e t)包含所有的元件。假設程式 可分為k個區塊B i，每一區塊的元件離開集合為 comp—out[BJ，其中 1 $ i ^ k。 參考圖5 a，此細部流程依序分成下列四個步驟5 0 1〜 5 0 4 ： 步驟5 0 1 :在每一區塊B !中，建構屬於該區塊B妁活動集 合與休眠集合，活動集合指該區塊中活動元件 的集合，休眠集合則指該區塊中休眠元件的集 合，因此活動集合即為該區塊的離開集合，休 眠集合為全集合與活動集合做差集的結果。可 以陣列方式表示為 action[Bi]與 rest[Bi]， 其中 1 $ i ^ k。 步驟5 0 2 :對每一個基本區塊，將其中所有區塊的休眠集 合依序兩兩交集’並將結果存放於另一陣列 中，再對此陣列中的集合依序兩兩交集，再存 放至另一陣列中，重覆此動作直到陣列中所有

第19頁 519599 五、發明說明（17)

集合皆為空集合為止。第一次兩兩交集的結果 存放於R2，第二次兩兩交集的結果存放於 以此類推。假設一共做了 1次交集，即R1 + 1 有的集合皆為空集合。 步驟5 0 3 :針對&中所有不為空集合的集合，假設該集合 為& 中第j個集合，對該集合中的所有元件 做下列動作：若1 大於該元件的Lec)nst，則記 錄此元件可在第j個區塊前插入休眠功能的資 訊’並連同區間（j， j + i ) 的資訊也記錄 下來，做為往後檢視用。其中在記錄資訊前先 檢視該元件與該區間是否包含於已記錄區間， 若上述情形成立，則跳過記錄的動作。 步驟_5 0 4 :依據記錄，在程式碼中插入該元件的休眠功能 指令。 舉例說明如下·假設圖5b表不元件的Lec)nst值’經由 模組「計算元件進入集合、元件消滅集合與元件離開集 合」1 0 2 b，欲分析的元件在每一個指令的狀態，如圖5 c所^ 示。經過「指令碼最佳化」模組1 0 3處理後，得到每一個 區塊的心值，如圖5 d所示。由圖5 d得知元件(算術邏 輯單位）在B5之後的連續5個執行週期都處於休眠狀態，並 且這段時間大於算術邏輯單位的LeQnst (二4 )，根據本發 ‘

第20頁 519599 五、發明說明（18) 明，可以在&之前插入一個讓算術邏輯單位進入休眠 的休眠功能’如SLEEP指令。同王里，也可以在前可以心 插入一個讓C3 (除法器）進入休眠狀態的休眠功能’如 SLEEP指令，在及心之前可以插入一個讓Q (乘法 入休眠狀態的休眠功能，如SLEEp指令。 叩J退 綜 式，結 系統與 態時， 此資訊 件提早 及的可 理、筆 明可延 本發明 子不使 令安排 中執行 活動方 上所述 合低耗 方法。 找出程 ，編譯 進入休 攜式電 記型電 長電池 同時可 用，則 方式， 的狀況 面較為 ，本發明 能指令集 此系統在 式碼中某 器可在此 眠狀態， 子產品、 腦、或是 的使用時 適於硬體 自動會關 本發明可 ，而評斷 省電。 利用元件 在編譯器 處理器執 元件長時 區段前插 達到節省 嵌入式系 可攜式通 間，並且 的元件環 閉電源， 蒐集元件 不同的指 為主貢 ’提供 行時的 間沒有 入元件 能源的 統等， 不會影 境’如 針對不 的電源 令安排 料流方 一種元 各個元 動作的 休眠功 效果D 不 u命在 晶片中 響其執 果一硬 同的蝙 開啟及 方式， 程式分析程 件流程分析 件的活動狀 區段，利用 能，促使元 對於現今普 個人數位助 使用本發 仃的效能。 體元件一陣 譯的不同指 關閉在程式 何者在元件 唯，以上所述者，僅為本發明之較每A 不能以此限定本發明實施之範圍。即大二^例而已，| 利範圍所作之均等變化與修飾，皆V :本發明申請肩 發明專利涵1

第21頁 519599 五、發明說明（19) 之範圍内。 ❿

第22頁 519599 圖式簡單說明 圖1為本發明之元件流程分析架構的方塊示意圖。 圖2 a說明本發明之「控制流程圖」模組的細部流程。 圖2b為一個以A 1 pha機器碼語言撰寫的原始程式碼，作為 「建立控制流程圖」模組1 0 1的輸入。 圖2c為圖2b之原始程式碼經圖2a之流程步驟後，產生的控 制流程圖。 ❶ 圖3 a說明模組1 0 2 a計算元件產生集合的細部流程。 圖3b例示一原始程式碼，作為本發明之「計算元件產生集 合」的模組1 0 2 a的輸入。 圖3c表示圖3b中指令與元件使用的對照表，作為本發明之 「計算元件產生集合」的模組102a的輸入。 圖3 d為圖3 b與圖3 c經圖3 a之流程步驟後，產生的元件產生 集合。 ❿ 圖4a說明模組10 2b計算元件進入集合、消滅集合與離開集 合的細部流程。

第23頁 519599 圖式簡單說明 圖4 b例示一原始程式碼’作為本發明之計异元件進入集 合、消滅集合與離開集合的模組1 0 2b的輸入。 圖4c為圖4b之原始程式碼經過「建立控制流程圖」模組所 輸出的原始程式控制流程圖。 圖4 d為圖4b經模組1 0 2 a計算元件產生集合所輸出的每個區 塊的元件產生集合。 圖4e為由模組102b計算元件進入集合、元件消滅集合與元 4 件離開集合」之步驟4 01所得到的初始元件進入集合、元 件消滅集合及元件離開集合。 圖4ί為經過2次本發明之模組102b計算元件進入集合、元 件消滅集合與元件離開集合之步驟4 0 2後，所得到的元件 進入集合、元件消滅集合與元件離開集合。 圖5 a說明本發明之「指令碼最佳化」模組的細部流程。 圖5b例示一元件的L⑽st值，作為本發明之「指令碼最佳 @ 化」模組的輸入。 圖5 c為圖4 b之原始程式碼經過本發明之模組「計算元件進 入集合、元件消滅集合與元件離開集合」1 0 2b所輸出的每

第24頁 519599 圖式簡單說明 一個元件在每一個指令的狀態。 圖5 d為由本發明之「指令碼最佳化」模組所得到的的輸 出。 圖號說明 1 0 1 建構控制流程圖模組 1 0 2 元件為主資料流方程式分析模組 10 2a計算元件產生集合的模組 1 0 2b計算元件進入集合、消滅集合與離開集合的模組 10 3指令碼最佳化模組 2 0 1〜2 0 4 本發明之控制流程圖之建構流程步驟 3 0 1〜3 0 3 本發明之計算元件產生集合模組之流程步驟 4 0 1〜4 0 3 本發明之計算元件進入集合、消滅集合與離開集 合模組之流程步驟 5 0 1〜5 0 4 本發明之最佳化程式碼之流程步驟

111 «11 第25頁

Claims (1)

1. 519599 六、申請專利範圍 1. 一種結合低耗能指令集在編譯器之元件流程分析結構， ： 包含有： 一建構控制流程圖模組，建構一個有向圖，該有向圖將 輸入的原始指令碼切割成複數個基本區塊，並依照流程 順序將控制流程資訊加入該輸入之原始指令碼的區塊的 集合裡，而不同基本區塊間的流程順序係以建立鏈結來 表示流程； 一元件為主貧料流方程式分析板組’根據該有向圖來分 析每個指令使用處理器中元件的狀態，並利用一資料流 分析方式，算出每個時序中狀態為活動的元件；以及 一指令碼最佳化模組，從該元件為主資料流方程式分析 模組得到每個元件的活動狀況，找出元件在連續幾個指 令週期下，狀態都為休眠的指令區間，在該指令區間前 加入一個休眠功能，讓該元件休眠以節省能源。 2. 如申請專利範圍第1項所述之元件流程分析結構，其中 該元件為主資料流方程式分析模組更包含下列子模組： 一第一模組，用以計算在該有向圖裡每一個區塊的元件 產生集合，和每一區塊使用元件所須要的時序數； 以及 瞻 一第二模組，用以計算在該有向圖裡每一個區塊的元件 進入集合、元件消滅集合和元件離開集合。 3. 如申請專利範圍第1項所述之元件流程分析結構，其中

   第26頁 519599 六、申請專利範圍 對不同的元件硬體設計，提供相對應的休眠功能。 4.如申請專利範圍第3項所述之元件流程分析結構，其中 若該元件提供開/關硬體設計，則該元件依指令或指令 集的下達5切斷其電源之提供，使該元件從耗電狀悲轉 為不耗電狀態。 5.如申請專利範圍第3項所述之元件流程分析結構，其中 若該元件僅提供低耗電硬體設計’則該元件依指令或指 令集的下達，降低其電源之提供，使該元件從耗電狀態 丨_ 轉為低耗電狀態。 6. —種結合低耗能指令集在編譯器之元件流程分析方法， 包含下列步驟： (a) 建構一控制流程圖，該控制流程圖將輸入的原始指 令碼切割成複數個基本區塊，並依照流程順序將控 制流程資訊加入該輸入之原始指令碼的區塊的集合 裡，且在不同基本區塊間以建立鏈結來表示流程順 序； (b) 根據該控制流程圖來分析每個指令使用處理器中元 件的狀態，並利用一資料流分析方式，算出每個時 序中狀態為活動的元件；以及 (c) 從該元件為主資料流方程式分析模組得到每個元件 的活動狀況，找出元件在連續幾個指令週期下，狀

   第27頁 519599 六、申請專利範圍 態都為休眠的指令區間，並將該原始指令碼最佳 ’ 化，以使該元件休眠而節省能源。 7. 如申請專利範圍第6項所述之元件流程分析方法，其中 該步驟（a )之控制流程圖之建構依序更包含下列四個步 驟： (a 1 )決定原始程式碼中那些敘述為基本區塊的首引； (a2)對每一個首引，組成一個基本區塊，以首引為基本 區塊的開頭，包含所有以下的敘述，但不包含下一 個首引之後的敘述； (a 3)依照該原始程式，建立鏈結以連接不同基本區塊來 表示流程；以及 (a 4)將該基本區塊中的每一個欽述晝分為一個區塊。 8. 如申請專利範圍第6項所述之元件流程分析方法，其中 該步驟（b )依序更包含下列兩個步驟： (b 1 )計算在該控制流程圖裡每一個區塊的元件產生集 合，和每一區塊使用元件所須要的時序數；以及 (b 2)計算在該控制流程圖裡每一個區塊的元件進入集 合、元件消滅集合和元件離開集合。 ® 9.如申請專利範圍第6項所述之元件流程分析方法，其中 該步驟（c)之控制流程圖之建構依序更包含下列四個步 驟：

   第28頁 519599 六、申請專利範圍 (cl )在每一區塊&中，建構屬於該區塊B,的活動集合 與休眠集合，活動集合指該區塊中活動元件的集 合，休眠集合則指該區塊中休眠元件的集合，活動 集合即為該區塊的離開集合，休眠集合為全集合與 活動集合做差集的結果；

   (c 2)對每一個基本區塊，將其中所有區塊的休眠集合依 序兩兩交集，並將結果存放於另一陣列中，再對此 陣列中的集合依序兩兩交集，再存放至另一陣列 中，重覆此動作直到陣列中所有集合皆為空集合為 止。第一次兩兩交集的結果存放於R2，第二次兩兩 交集的結果存放於R3，以此類推，假設一共做了 1 次交集，即RH1内所有的集合皆為空集合； (c 3 )針對&中所有不為空集合的集合，假設該集合為 R,中第j個集合，對該集合中的所有元件做下 列動作：若1 大於該元件的L_st，則記錄此 元件可在第j 個區塊前插入休眠功能的資訊，並 連同區間（j， j + 1 ) 的資訊也記錄下來，做為

   往後檢視用。其中在記錄資訊前先檢視該元件與 該區間是否包含於已記錄區間，若上述情形成立， 則跳過記錄的動作；以及 (c4)依據該記錄，在該程式碼中插入該元件的休眠功能 指令。 1 0.如專利申請範圍第第6項所述之元件流程分析方法，其

   第29頁 519599 六、申請專利範圍 中該步驟（b 1 )依序更包含下列三個步驟： (b 1 1 )對每一個區塊針對欲分析的每一元件，新增一 個二維陣列的參數C y c 1 e C 〇 u n t，並且將 C y c 1 e C o u n t所有的元素的初始值皆設為Ο，亦即 CycleCountfBinCj] = 0 ，其中1 S i $ k，1 S j S n，CycleC〇unt[Bi][Cj]用來表示區塊 B,使用元件q所須要的時序數； (b 1 2 )在每一區塊中，建構屬於該區塊的元件產生集 合Comp_gen set,並且將此集合的初始值設為 空集合；以及 (b 1 3 )依指令的執行順序，對每一區塊&中的指令做下 列動作： 從指令與元件使用的對照表中查得該使令與元 件使用的關係，假設該指令使用q元件cq個時 序、C2元件CC2個時序、…、Cn元件CCn個時序， 則將時序數不為0的元件加入該區塊的產生集合 中，並且將Cy c 1 eCoun t [ Bi ] [ C!]的值加上CC!、 C y c 1 e C o u n t [ Bi ] [ C2 ]白勺值力u 上 C C2 、…、 C y c 1 e C 〇 u n t [ ] [ Cn ]白勺值力口上 C Cn o Π .如專利申請範圍第第6項所述之元件流程分析方法，其 中該步驟（b 2 )依序更包含下列三個步驟： (b 2 1 )在每一區塊中，建構屬於該區塊的元件進入 集合comp—infB」、元件消滅集合comp — kill[Bj]

   第30頁 519599 六、申請專利範圍 及元件離開集合comp一out [ B!]，元件進入集合 comp—]與元件消滅集合comp — ki Π [Bi ]的 初始值設為空集合’元件離開集合c 0 m p __ 0 u t [ b j 的初始值设為該區塊的兀件產生集合 comp^gen [ ]； (b22)對每一區塊&做下列動作： (b2 2a)對每一個欲分析元件q，比較&的所有前 區塊（predecessor)白勺 CycleCountanCj]值，取其最大值，假 設此最大值為CCmax，若cCmax不為0，則 將CCmax的值減1，若減1後的值為〇，則將 元件C加入該區塊的元件消滅集合 comp —killfB!]中’若（CCmax-1)的值大於 C y c 1 e C 〇 u η ΐ [ ] [ C」·]的值，則將 CycleCountl^nCj]的值設為（CCmax~~l)， (b22b)將該區塊的元件進入集合c〇mp—in[Bi ]設 為該區塊所有前區塊的元件離開集合 c〇m p — 〇 u t [ Bi ]的聯集，亦即 comp—i η [ ]二 u comp_〇ut [ P ]，其中 P 為 B1的前區塊， (b2 2c)將該區塊的元件離開集合c〇mp_〇ut [I ]設 為该區塊元件進入集與元 件消滅集合c〇mp_kl u [h ]的差集後，再 與元件產生集合c 〇 m p — g e η [ ]作聯集，亦

   — 第31頁 519599 六、申請專利範圍 即comp —〇ut[Bi ]=comp一gen[Bi ] U (comp—infBi] - comp —killfBi]);以及 (b2 3 )重複步驟（b2 2 )，直到所有區塊的元件離開集合 不再產生變化。 ^ 12·如申請專利範圍第7項所述之元件流程分析方法，其中 或步驟（a 1)之首引決定的法則有三： (a 11 )程式的第一個敘述即為一首引； U12)任何為條件跳躍（conditional g〇t〇)或無條件跳 躍（unconditional goto)目標的敘述即為一首 引；以及 ” (al3)任何跟在跳躍（goto)或條件跳躍（c〇ndi ti⑽al goto)後的敘述即為一首引。 1 3 ·如申请專利範圍第1項所述之元件流程分析方法，其中 對不同的元件硬體設計，提供相對應的休眠功能，並以 一臨界值LCQnst來判定是否將元件轉為休眠狀態。 1 4 ·如申請專利範圍第1 3項所述之元件流程分析方法，其 中若該元件提供開/關硬體設計，則該元件依指令或指 令集的下達，切斷其電源之提供，使該元件從耗電狀態 轉為不耗電狀態，且該L⑶nst值依下列的成本模式決定： P(v) + SLEEP(v) ^ Lconst * ACT(v)；