算法能耗复杂度的定义与推导

发布时间：2018-06-03 21:36

本文选题：绿色计算 + 能耗度量　；参考：《计算机学报》2018年03期

【摘要】：计算机系统的性能优化研究早期关注硬件性能,后来更关注软件性能.能耗优化研究与之类似,近年来,面向软件或代码的系统能耗优化方法研究受到重视,而算法作为代码的抽象,其能耗评价技术更是一个研究重点.现有算法能耗研究大多针对特定算法以及特定运行环境,且和编程语言或硬件特性相关,并不具有普适性.比照算法的时间复杂度和空间复杂度,提出能耗复杂度是认知算法能耗特性的有效模型.首先,以图灵机为起点,建立更适于算法能耗分析的能耗图灵机,并定义算法能耗复杂度,为评价和优化算法能耗提供理论依据;然后,分析算法能耗与算法空间复杂度、时间复杂度、存储和运算语句的交叉度之间的关系,并设计利用后两者推导能耗复杂度的方法;最后,实验验证算法能耗复杂度的正确性.能耗复杂度的定义将为设计更低能耗的算法、算法选择以及算法能耗优化提供理论依据.
[Abstract]:Performance optimization of computer systems focused on hardware performance early and software performance later. The research on energy consumption optimization is similar to that in recent years, software or code-oriented system energy consumption optimization methods have been paid attention to, and algorithm as the abstraction of code, its energy consumption evaluation technology is a research focus. Most of the existing algorithms are focused on specific algorithms and specific running environments, and they are not universal because they are related to programming language or hardware characteristics. Compared with the time and space complexity of the algorithm, the energy consumption complexity is an effective model for the cognitive algorithm. First of all, taking Turing machine as the starting point, the energy consumption Turing machine which is more suitable for algorithm energy consumption analysis is established, and the algorithm energy consumption complexity is defined to provide the theoretical basis for evaluating and optimizing the algorithm energy consumption. Then, the algorithm energy consumption and algorithm space complexity are analyzed. The relationship between the time complexity, the crossover between storage and operation sentences, and the method to deduce the energy consumption complexity by using the latter two are designed. Finally, the correctness of the energy consumption complexity of the algorithm is verified by experiments. The definition of energy complexity will provide a theoretical basis for the design of lower energy consumption algorithms, algorithm selection and optimization of algorithm energy consumption.
【作者单位】：东北大学软件学院;东北大学计算机科学与工程学院;
【基金】：国家自然科学基金(61433008,61672143,61662057,61502090,61402090)资助
【分类号】：TP301.6

【参考文献】