【作者】 王颖锋；

【导师】 刘志镜；

【作者基本信息】 西安电子科技大学 ， 计算机应用技术， 2010， 博士

【摘要】 随着半导体芯片技术的快速发展,能量消耗已经成为嵌入式系统的一个重要设计课题和性能指标。一些节能技术如动态电压调节,动态电源管理,和自适应衬底偏置以及它们的混合为降低嵌入式系统的能量消耗提供了很好的机会。任务调度和电压选择在能量最小化方面起着积极作用。因此将节能技术并入调度算法对嵌入式系统节能变得重要起来。事实上,数据或者控制依赖对节能有着负面影响。因此,在节能调度算法的设计中这一因素的负面影响需要被有效地解决。考虑到重定时有向无环图能够有效地克服迭代内数据依赖的影响,从而为降低调度长度或能量消耗提供更多的机会,本文以重定时有向无环图为调度对象设计了几个节能策略。本文的主要研究工作概括如下:1.如果一个调度是基于重定时有向无环图产生的,并且所有的任务都执行两个性能模式,恰当地重排序任务顺序和每个任务的性能模式顺序能够产生更多的松弛用于降低能量消耗。为了提供更多的机会降低能量消耗,利用重定时有向无环图只有迭代间数据依赖这一特点以及一个任务重排序性能模式顺序对任务执行没有影响这一优点,提出了一个技术重排序任务和性能模式。首先,当一个组件上的一个任务被设置为第一个执行的任务时,对于该组件上给定的任务集,计算最小的电压转换时间。然后从这些最小电压转换时间里选择一个最小的作为该组件上任务集的最小电压转换时间。相应任务顺序和性能模式顺序是最终要执行的任务和性能模式顺序。2.许多处理器如PXA255, AMD Mobile Athlon4, Transmeta’s Crusoe具有动态电压调节能力。此外,多核体系结构已经占领了嵌入式系统市场。在电压转换时间是固定的或者可以忽略不计的情况下,为了降低具有动态电压调节能力的多核系统的能量消耗,提出了一个用于最小化多核系统能量消耗的算法。提出的算法考虑了性能模式转换开销和处理核之间的通信开销,该算法用于降低含有依赖任务并具有公共时间限制的应用程序的电压转换能量消耗和动态能量消耗。首先,提出的算法在给定时间限制下通过选择合理的任务映射和频率安排获取最小的初始调度长度。然后,它迭代地选择任务进行频率调节以便当将被选择的任务降低一个频率并把被选择的任务所在的处理核上的任务按降电压顺序执行时,产生最小的能量消耗。3.日益缩小的特征尺寸导致在未来泄露能量会超过动态能量。动态电压调节和自适应衬底偏置是同时降低动态能量和泄露能量的有效手段。为了响应这一趋势,提出了一个算法应用上述两种技术降低具有硬时间限制的应用程序在多核系统上的能量消耗。首先,提出的方法确定初始的任务顺序和频率安排以在给定的时间限制下获得最小的初始调度长度。然后它迭代地选择候选任务,调节候选任务的频率以获得最大的压缩能量和增长时间的比值。为了能够获得更多的松弛以降低能量消耗,它在每次频率调节后重排序侯选任务所在处理核的任务。4.近年来,新的多核系统被提出作为降低能量消耗的颇有前景的办法。在这样的系统里不仅处理核而且总线具有动态电压调节和自适应衬底偏置能力。对于这样的系统,一个算法被提出用来降低处理核和通信链路的能量消耗。首先,提出的算法利用映射选择以降低处理核之间的通讯量。然后,它通过同时调节计算任务和总线的频率以获得最大的压缩能量和增长时间比。这样的操作一直进行到进一步调节会导致背离给定时间限制为止。更多还原

【Abstract】 With the rapid growth of semi-conductor chip’s technology, energy consumption has become an important design issue and performance metric in embedded systems. Some energy saving techniques such as dynamic voltage scaling, dynamic power management, adaptive body biasing and their combinations offer good opportunities to decrease energy consumption in embedded systems. Task scheduling and voltage selection play active roles in energy minimization. Therefore, the integration of energy saving techniques into the design of scheduling algorithms becomes very important for embedded systems to decrease energy consumption. In fact, data or control dependencies are pervasive in many applications while data dependencies or control dependencies have negative effects on energy conservation, which, therefore, are also required to be solved in the design of energy-efficient scheduling algorithms effectively. Considering retimed directed acyclic graphs can effectively overcome the effect of intra-iteration data dependencies so that more opportunities can be provided to decrease scheduling length and energy consumption, this thesis designed several energy efficient policies which take retimed directed acyclic graphs as scheduled objects to realize energy conservation.The main research work in this thesis can be summarized as follows:1. If a task scheduling is generated based on a retimed directed acyclic graph and all the tasks are executed with two performance modes, appropriately reordering both task order and performance mode order of each task can generate more slacks to decrease energy consumption. To provide more opportunities to lower energy consumption, a technique is proposed to reorder both task and performance mode that employ the character of only inter-iteration data dependencies of retimed directed acyclic graphs and the merit of performance mode reordering that has no effect on task execution. Firstly, the minimum voltage transition time is calculated for the given task set on a component when one task of the task set is set the first task to be executed.Then, selecting the smallest one from these minimum voltage transition time as the minimum voltage transition time for the given task set on the corresponding component.The corresponding task order and performance mode order are the final task order and performance mode order to be executed.2. Many processors, such as PXA255, AMD Mobile Athlon4, Transmeta’s Crusoe are equipped with dyanic voltage scaling ability. In addition, multi-core architecture has dominated the market of embedded systems. In order to decrease energy consumption in multi-core systems with dynamic voltage scaling ability, an algorithm is proposed to minimize energy consumption of multi-core systems when voltage transition time is fixed or negligible. The proposed algorithm reduces both transition and dynamic energy consumption for applications including dependent tasks with common timing constraints considering transition overhead between performance modes and communication overhead between processor cores. First, the proposed algorithm achieves the minimum initial scheduling length by choosing reasonable task mapping and frequency assignment under given timing constraint. Then, it iteratively selects tasks to conduct frequency scaling so that the minimum energy consumption can be generated when decreasing the frequency of the chosen tasks to adjacent frequency and executing tasks in decreasing voltage levels on the processor core where the scaled tasks locate.3. The trend of increasingly shrunken feacture size will lead to leakage energy larger than dynamic energy consumption in the future. The combination of dynamic voltage scaling and adaptive body bias is an efficient method for joint dynamic and leakage enrgy reduction. In response to this trend, an algorithm is proposed to apply above two techniques to decrease energy consumption for applications with hard timing constraints on multi-core systems. First, the proposed method determines initial task order and frequency assignment to get the minimum initial scheduling length under given timing constraint. Then it iteratively selects candidate task and scales the frequency of the candidate task to achieve the maximum ratio of reduced energy to increased time. In order to achieve more slacks to decrease energy consumption, it reorders tasks on the processor core where candidate tasks locate after each frequency scaling.4. In recent years, new multi-core systems in which not only processor cores but also buses feature dynamic voltage scaling and adaptive body bias capabilities have been proposed as a promising solution to decrease energy consumption. An algorithm is proposed for such systems to decrease energy consumption of both processor cores and communication links by the combination of dynamic voltage scaling, adaptive body bias and dynamic power management. First, the proposed algorithm utilizes the choice of mapping algorithm to decrease volume of communication among processor cores. Then it achieves the maximum ratio of reduced energy to increased time by scaling frequencies of both candidate computation tasks and the bus. This operation is continued until further scaling will lead to violate given timing constraint.更多还原