面向伪码的算法能耗复杂度的研究

作     者：徐澍 

作者单位：东北大学 

学位级别：硕士

导师姓名：宋杰

授予年度：2015年

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：能耗评价 算法能耗 能耗图灵机 能耗推导 能耗特征参数 

摘      要：日益普及的大规模计算系统能耗过大已经成为一个IT界亟待解决的难题,因此近些年能耗也逐渐成为一个衡量软硬件系统的新指标。如同计算机系统性能研究经历了从早期关注硬件性能,到后来扩展到包括软件在内的整个系统的发展过程一样,近些年来,通过软件层面降低系统能耗的问题得到广泛重视,而算法作为细粒度的软件,其能耗评价技术更是成为研究重点之一。现存面向算法层面的能耗研究并且提出通用的算法能耗分析方法的文献比较有限,大多数研究文献或是针对某一个或多个算法进行研究或是针对特定的环境下的算法能耗进行分析,同时该层面的研究一般或和高级语言相关或和计算机的硬件信息有关,并不具有通用性以及可扩展性。比照算法的时间复杂度和空间复杂度的概念,本文认为能耗复杂度对于评价算法同等重要,是认知算法能耗的有效手段。本文旨在研究算法的能耗复杂度,并建立算法能耗复杂度模型、研究能耗复杂度推导方法。首先,本文以经典计算模型——图灵机为起点,建立更适于分析算法能耗的能耗图灵机,并定义算法能耗复杂度模型,为评价算法的能耗以及分析、评价其能耗情况提供理论依据;然后,分析算法时间复杂度、空间复杂度以及算法其他特征参数与算法能耗之间存在的关系,并建立基于算法时间复杂度和交叉复杂度的算法能耗复杂度推导方法;其次,从算法伪代码语句和结构层面对算法执行能耗代价进行分析,并由繁到简给出一个算法能耗复杂度表达式,建立面向伪代码的算法能耗复杂度推导方法;最后,本文进行一系列的实验,依次对一个算法能耗复杂度模型、两个能耗复杂度推导方法进行了验证,证明评价方法的合理性和有效性。本研究可提供算法能耗的评价方法,在实际的应用开发过程中使用此评价方法有助于对多个算法的能耗进行比较,方便选择能耗更低的算法,或优化程序设计方法,从而提升软件产品的竞争力;同时潜在的经济与生态影响也极为明显,能耗的降低即有助于节约成本,又可以减少碳的排放,实现环境保护。