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

NCU Institutional Repository > 資訊電機學院 > 資訊工程研究所 > 博碩士論文 > Item 987654321/84007

請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/84007

題名:	自動化時間複雜度分析的設計與實作–從軟體層面評估嵌入式系統的功率消耗;The Design and Implementation of Automated Time Complexity Analysis: To Evaluate the Power Consumption of Embedded System at Software Level
作者:	潘俊霖;Pan, Chun-Lin
貢獻者:	資訊工程學系
關鍵詞:	程式語言;時間複雜度;嵌入式系統;抽象語法樹分析;programming language;time complexity;embedded system;AST analysis
日期:	2020-07-28
上傳時間:	2020-09-02 17:54:21 (UTC+8)
出版者:	國立中央大學
摘要:	嵌入式系統的功率消耗可以藉由硬體與軟體來減少，而功率消耗可從硬體方面藉由電流、電壓計算得出。但是，對於軟體而言，無法直接計算出一個程式的功率消耗，因為同一個程式，可能會因為執行環境的不同而產生不同的功率消耗。不過，我們可以將功率消耗的問題轉換到與功率消耗正相關的時間複雜度上，藉由程式的時間複雜度來評估是否有較大的功率消耗。本研究提出了自動化時間複雜度分析工具 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.
顯示於類別:	[資訊工程研究所] 博碩士論文

文件中的檔案:

檔案	描述	大小	格式	瀏覽次數
index.html		0Kb	HTML	154	檢視/開啟

在NCUIR中所有的資料項目都受到原著作權保護.

社群 sharing

資料載入中.....