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

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

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

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