面向偽碼的算法能耗復(fù)雜度的研究.pdf

1、日益普及的大規(guī)模計算系統(tǒng)能耗過大已經(jīng)成為一個IT界亟待解決的難題，因此近些年能耗也逐漸成為一個衡量軟硬件系統(tǒng)的新指標。如同計算機系統(tǒng)性能研究經(jīng)歷了從早期關(guān)注硬件性能，到后來擴展到包括軟件在內(nèi)的整個系統(tǒng)的發(fā)展過程一樣，近些年來，通過軟件層面降低系統(tǒng)能耗的問題得到廣泛重視，而算法作為細粒度的軟件，其能耗評價技術(shù)更是成為研究重點之一。
　　現(xiàn)存面向算法層面的能耗研究并且提出通用的算法能耗分析方法的文獻比較有限，大多數(shù)研究文獻或是針對某一

2、個或多個算法進行研究或是針對特定的環(huán)境下的算法能耗進行分析，同時該層面的研究一般或和高級語言相關(guān)或和計算機的硬件信息有關(guān)，并不具有通用性以及可擴展性。
　　比照算法的時間復(fù)雜度和空間復(fù)雜度的概念，本文認為能耗復(fù)雜度對于評價算法同等重要，是認知算法能耗的有效手段。本文旨在研究算法的能耗復(fù)雜度，并建立算法能耗復(fù)雜度模型、研究能耗復(fù)雜度推導(dǎo)方法。首先，本文以經(jīng)典計算模型——圖靈機為起點，建立更適于分析算法能耗的能耗圖靈機，并定義算法能耗

3、復(fù)雜度模型，為評價算法的能耗以及分析、評價其能耗情況提供理論依據(jù);然后，分析算法時間復(fù)雜度、空間復(fù)雜度以及算法其他特征參數(shù)與算法能耗之間存在的關(guān)系，并建立基于算法時間復(fù)雜度和交叉復(fù)雜度的算法能耗復(fù)雜度推導(dǎo)方法;其次，從算法偽代碼語句和結(jié)構(gòu)層面對算法執(zhí)行能耗代價進行分析，并由繁到簡給出一個算法能耗復(fù)雜度表達式，建立面向偽代碼的算法能耗復(fù)雜度推導(dǎo)方法;最后，本文進行一系列的實驗，依次對一個算法能耗復(fù)雜度模型、兩個能耗復(fù)雜度推導(dǎo)方法進行了驗證