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

NCUIR > College of Electrical Engineering & Computer Science > Graduate Institute of Computer Science and Information Engineering > Electronic Thesis & Dissertation > Item 987654321/84007

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/84007

Title:	自動化時間複雜度分析的設計與實作–從軟體層面評估嵌入式系統的功率消耗;The Design and Implementation of Automated Time Complexity Analysis: To Evaluate the Power Consumption of Embedded System at Software Level
Authors:	潘俊霖;Pan, Chun-Lin
Contributors:	資訊工程學系
Keywords:	程式語言;時間複雜度;嵌入式系統;抽象語法樹分析;programming language;time complexity;embedded system;AST analysis
Date:	2020-07-28
Issue Date:	2020-09-02 17:54:21 (UTC+8)
Publisher:	國立中央大學
Abstract:	嵌入式系統的功率消耗可以藉由硬體與軟體來減少，而功率消耗可從硬體方面藉由電流、電壓計算得出。但是，對於軟體而言，無法直接計算出一個程式的功率消耗，因為同一個程式，可能會因為執行環境的不同而產生不同的功率消耗。不過，我們可以將功率消耗的問題轉換到與功率消耗正相關的時間複雜度上，藉由程式的時間複雜度來評估是否有較大的功率消耗。本研究提出了自動化時間複雜度分析工具 DYSTA，幫助軟體工程師在大型專案中能夠快速的分析各個函式的時間複雜度，更快的了解到哪一個函式較為耗電。 DYSTA 為一個從抽象語法樹上進行靜態分析的時間複雜度計算工具，其特色在於能夠分析含有 While、If Else 的程式。這些語法常常出現在嵌入式系統中，但是既有的以抽象語法樹分析為基礎的時間複雜度分析工具，卻無法支援同時含有 While、If Else 的程式，原因在於這些工具沒有使用符號表來記錄變數或是維護符號表的演算法無法處理遇到if-else選擇結構的情況。本研究提出了一個動態規劃的符號表演算法並實作於DYSTA當中，在走訪抽象語法樹的同時，以符號表預先記錄條件分歧與巢狀結構裡各種可能用來計算迴圈執行次數的變數。本研究使用動態規劃，使得在最差的情況下從符號表中搜尋變數的時間複雜度大幅地降低。從較直覺演算法的O(n2^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(n2^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.
Appears in Collections:	[Graduate Institute of Computer Science and Information Engineering] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	154	View/Open

社群 sharing

Loading...