自動化時間複雜度分析的設計與實作–從軟體層面評估嵌入式系統的功率消耗

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：14

、訪客IP：3.16.81.94

姓名

潘俊霖(Chun-Lin Pan) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

自動化時間複雜度分析的設計與實作–從軟體層面評估嵌入式系統的功率消耗
(The Design and Implementation of Automated Time Complexity Analysis: To Evaluate the Power Consumption of Embedded System at Software Level)

相關論文

★ 條件判斷式事件驅動程式設計之C語言擴充	★ 基于小波变换的指纹活度检测,具有聚集 LPQ 和 LBP 特征
★ 應用自動化測試於異質環境機器學習管道之 MLOps 系統	★ 設計具有可視化思維工具和程式作為單一步的輔助學習程式之棋盤式遊戲
★ TOCTOU 漏洞的靜態分析與實作	★ 用於繪製風力發電控制邏輯之特定領域語言
★ 在Java程式語言中以雙向結構表達數學公式間關聯之設計與實作	★ 支援模組化規則製作之程式碼轉換工具
★ 基於替代語意的 pandas DataFrame 靜態型別檢查器	★ 以震波層析成像為應用之特定領域語言實作與分析
★ 用特徵選擇減少疲勞偵測腦電圖通道數	★ 一個應用紙本運算與數位化於程式設計學習使程序性思維可視化的機制
★ 基於抽象語法樹的陣列形狀錯誤偵測	★ 從合作學習角色分工獲得函式程式設計思維學習遞迴程式的機制
★ 基於抽象語法樹的深度複製及彈性別名之所有權系統解決 Java 表示暴露問題	★ 基於 Python 型別提示檢查不可變性

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 (2025-8-1以後開放)

摘要(中)

嵌入式系統的功率消耗可以藉由硬體與軟體來減少，而功率消耗可從硬體方面藉由電流、電壓計算得出。但是，對於軟體而言，無法直接計算出一個程式的功率消耗，因為同一個程式，可能會因為執行環境的不同而產生不同的功率消耗。不過，我們可以將功率消耗的問題轉換到與功率消耗正相關的時間複雜度上，藉由程式的時間複雜度來評估是否有較大的功率消耗。本研究提出了自動化時間複雜度分析工具 DYSTA，幫助軟體工程師在大型專案中能夠快速的分析各個函式的時間複雜度，更快的了解到哪一個函式較為耗電。

DYSTA 為一個從抽象語法樹上進行靜態分析的時間複雜度計算工具，其特色在於能夠分析含有 While、If Else 的程式。這些語法常常出現在嵌入式系統中，但是既有的以抽象語法樹分析為基礎的時間複雜度分析工具，卻無法支援同時含有 While、If Else 的程式，原因在於這些工具沒有使用符號表來記錄變數或是維護符號表的演算法無法處理遇到if-else選擇結構的情況。本研究提出了一個動態規劃的符號表演算法並實作於DYSTA當中，在走訪抽象語法樹的同時，以符號表預先記錄條件分歧與巢狀結構裡各種可能用來計算迴圈執行次數的變數。本研究使用動態規劃，使得在最差的情況下從符號表中搜尋變數的時間複雜度大幅地降低。從較直覺演算法的O(n*2^h)降低為線性時間O(n)，其中n為符號表內的符號個數、h為作用域堆疊的深度。

摘要(英)

Power consumption of embedded system can be reduced by hardware and software, and it can be calculated from hardware level by current and voltage.However, for software, it is impossible to directly calculate the power consumption of a program because a program may have different power consumption due to different execution environments.To address this issue, we consider the problem of power consumption from time complexity since it has positive correlation with power consumption. In other words, using time complexity to evaluate whether consuming more power or not.In this work, we propose an automated time complexity analyzer called DYSTA to help software designers rapidly analyze time complexities of functions in a large project in order to understand which functions will consume more power.

DYSTA is a time complexity analyzer using static AST analysis.It features in analyzing a program having ′while′, ′if-else′ statements.So far as we know, existing time complexity analyzers based on AST analysis cannot deal with a program contains those statements, though those statements are usually used in a embedded system program.The reason might include the lack of using symbol table and the handling for ′if-else′ statement.In this work, we propose a symbol table algorithm and give a preliminary implementation, DYSTA. We use symbol table to maintain variables in selection/nested structure and calculate the execution times of loop during AST traversal. Our work uses dynamic programming to reduce the time complexity of searching a variable in symbol table in the worst case. Instead of O(n*2^h) in a naive implementation, the time complexity in DYSTA is reduced to linear time O(n), which n is the number of variables in symbol table and $h$ is the depth of scope stack.

關鍵字(中)

★ 程式語言
★ 時間複雜度
★ 嵌入式系統
★ 抽象語法樹分析

關鍵字(英)

★ programming language
★ time complexity
★ embedded system
★ AST analysis

論文目次

一、緒論 1
1.1 低功率嵌入式系統 ................................. 1
1.2 減少功耗的幾種方式-硬體方面、軟體方面.............. 2
1.3 時間複雜度 ...................................... 4
1.4 程式碼分析 ...................................... 5
1.5 程式碼分析方式應用於時間複雜度分析................. 5
1.5.1 動態分析 ...................................... 5
1.5.2 中間碼、機器碼 ................................ 6
1.5.3 流程圖控制 .................................... 7
1.5.4 抽象語法樹 .................................... 7
1.6 本研究採用的分析方式與論文架構 .................... 8
二、動機 9
2.1 以 Binary Search 為例 ........................... 9
2.2 相關研究應用於時間複雜度分析 ..................... 12
2.2.1 Big-O Calc ................................... 12
2.2.2 Complexity.................................... 13
2.2.3 ABOAA ........................................ 13
2.3 本研究開發一靜態分析工具 ......................... 15
三、 DYSTA 16
3.1 整體架構 ........................................ 16
3.1.1 剖析器 ........................................ 19
3.1.2 Big-O AST 轉換器............................... 20
3.1.3 符號表管理器 .................................. 21
3.1.4 時間複雜度計算器 .............................. 21
3.1.5 化簡時間複雜度 ................................ 22
3.2 時間複雜度計算 .................................. 23
3.2.1 循序結構 ...................................... 24
3.2.2 選擇結構 ...................................... 24
3.2.3 重複結構 ...................................... 24
3.3 迴圈執行次數 .................................... 24
3.3.1 遞增迴圈 ...................................... 25
3.3.2 倍增迴圈 ...................................... 26
3.3.3 初始值等差改變，邊界值等差改變 ................. 26
3.3.4 初始值等比改變，邊界值等比改變 ................. 27
3.3.5 初始值等差改變，邊界值等比改變 ................. 28
3.3.6 初始值等比改變，邊界值等差改變 ................. 30
3.4 變數更新率 ...................................... 32
3.5 符號表 .......................................... 33
3.5.1 作用域 ........................................ 34
3.5.2 符號表在編譯器中扮演的角色 ..................... 35
3.5.3 符號表演算法 .................................. 35
四、實作 40
4.1 符號表模組的資料結構 ............................. 41
4.1.1 多個符號表實作的時間複雜度分析 ................. 43
4.2 單一符號表 ...................................... 44
4.2.1 單一符號表實作的時間複雜度分析 .................. 44
4.3 直覺的符號表演算法 ............................... 45
4.3.1 直覺的符號表演算法實作的時間複雜度分析 .......... 46
五、評估 48
5.1 分析與解釋 ...................................... 49
5.2 分析總結 ........................................ 50
六、相關研究 51
6.1 動態分析 ........................................ 51
6.2 中間碼、機器碼分析 .............................. 52
6.3 控制流程圖分析 .................................. 52
七、結論 54
參考文獻 56

參考文獻

[1] M. Satyanarayanan, “Fundamental challenges in mobile computing,” in Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, ser. PODC ’96, Philadelphia, Pennsylvania, USA: Association for Computing Machinery, 1996, pp. 1–7, isbn: 0897918002. doi: 10.1145/248052.248053. [Online]. Available: https://doi.org/10.1145/248052.248053.
[2] X. Ge, J. Yang, H. Gharavi, and Y. Sun, “Energy efficiency challenges of 5g small cell networks,” IEEE Communications Magazine, vol. 55, no. 5, pp. 184–191, 2017.
[3] M. Gruber, O. Blume, D. Ferling, D. Zeller, M. A. Imran, and E. C. Strinati, “Earth—energy aware radio and network technologies,” in 2009 IEEE 20th International Symposium on Personal, Indoor and Mobile Radio Communications, 2009, pp. 1–5.
[4] A. S. Sedra and K. C. Smith, Microelectronic Circuits, fifth. Oxford University Press, 2004.
[5] A. Chatzigeorgiou and G. Stephanides, “Energy issues in software design of embedded systems,” in 2nd WSEAS International Conference on Applied Informatics, Rethymnon, 2002.
[6] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, Third Edition, 3rd. The MIT Press, 2009, isbn: 0262033844.
[7] A. V. Aho and J. D. Ullman, Principles of Compiler Design (Addison-Wesley Series in Computer Science and Information Processing). USA: Addison-Wesley Longman Publishing Co., Inc., 1977, isbn: 0201000229.
[8] T. Dobravec, “Estimating the time complexity of the algorithms by counting the java bytecode instructions,” in 2017 IEEE 14th International Scientific Conference on Informatics, 2017, pp. 74–79.
[9] F. Demontiê, J. Cezar, M. Bigonha, F. Campos, and F. Magno Quintão Pereira, “Automatic inference of loop complexity through polynomial interpolation,” in Programming Languages, A. Pardo and S. D. Swierstra, Eds., Cham: Springer International Publishing, 2015, pp. 1–15, isbn: 978-3-319-24012-. 56
[10] H. Dong-Ying, “Static Analysis of Time Complexity with Big-O AST: A Case Study of Algorithmic Competitive Programming Problems,” M.S. thesis, CSIE. Dept., NCU, Taoyan, Taiwan, 2019. [Online]. Available: https://github.com/ncu-psl/BigO-Calc (visited on 05/01/2020).
[11] M. Rav. (). “Complexity,” GitHub, [Online]. Available: https://github.com/Mortal/complexity (visited on 05/01/2020).
[12] R. Vaz, V. Shah, A. Sawhney, and R. V. Deolekar, “Automated big-o analysis of algorithms,” 2017 International Conference on Nascent Technologies in Engineering (ICNTE), pp. 1–6, 2017.
[13] 何東穎 and 莊永裕, “使用 ast 進行靜態程式碼分析函式時間複雜度,” 繁體中文, 2018 年, Nov. 2018, pp. 2220–2225. doi:10.6861/TANET.201810.0411.
[14] E. W. Dijkstra, “Chapter i: Notes on structured programming,” in Structured Programming. GBR: Academic Press Ltd., 1972, pp. 1–82, isbn: 0122005503.
[15] (). “Leetcode,” [Online]. Available: https://leetcode.com/(visited on 05/01/2020).
[16] A. Srikanth, B. Sahin, and W. R. Harris, “Complexity verification using guided theorem enumeration,” in Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, ser. POPL 2017, Paris, France: Association for Computing Machinery, 2017, pp. 639–652, isbn: 9781450346603. doi: 10.1145/3009837.3009864. [Online]. Available: https://doi.org/10.1145/3009837. 3009864.
[17] ——, “Complexity verification using guided theorem enumeration,” SIGPLAN Not., vol. 52, no. 1, pp. 639–652, Jan. 2017, issn: 0362-1340. doi: 10.1145/3093333. 3009864. [Online]. Available: https://doi.org/10.1145/3093333.3009864.
[18] K. S. Kumar and D. Malathi, “A novel method to find time complexity of an algorithm by using control flow graph,” in 2017 International Conference on Technical Advancements in Computers and Communications (ICTACC), 2017, pp. 66–68.

指導教授

莊永裕(Yung-Yu Zhuang)

審核日期

2020-7-28

推文