【作者】 刘惠；

【导师】 陈平；

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

【摘要】 对于电池供电的嵌入式设备来说,低能耗是一个关键设计指标,嵌入式低能耗研究有着广阔的应用前景和重要的应用价值,逐渐引起工业界和学术界的高度关注。本文研究了嵌入式系统的节能调度问题。针对嵌入式系统中具有严格执行时限要求的周期性任务,提出了四种节能调度算法。还针对无线传感器网络,提出了三维空间K虚拟栅栏覆盖节能调度算法。对于电压可变的处理器,已有研究考虑了理想的具有连续可变电压的处理器模型,而真实的可变电压处理器仅具有离散的电压等级。动态电压缩放(Dynamic Voltage Scaling,DVS)是一个有效的节能技术,它通过降低处理器运行时的电压来节能。但是,降低电压的同时会导致任务执行时间增加,因此需要优化延迟和能耗这对互为矛盾的指标。对于具有离散电压等级的单处理器,本文首先提出了一种最优电压选择算法,使得在不违背给定应用执行时限的前提下系统能耗最少。与已有启发式算法不同,最优电压选择算法将该节能调度问题转化为多选择背包问题的变种,然后采用动态规划方法求得最优解。更进一步,由于在处理器上调度任务时,电压切换会引起额外的跃迁代价,影响系统的延迟和能耗,因此又提出了一种改进的单处理器节能调度算法,该算法考虑了离散电压模型、动态能耗,以及电压跃迁代价。对于多处理器MPSoC架构上的任务,传统任务调度算法关注并行化的挖掘以提高系统吞吐率,降低延迟。现在,MPSoC架构已被广泛的应用到嵌入式系统中,像多媒体和网络处理等计算密集型的嵌入式应用,对能耗和延迟都很关注,因而对任务调度算法提出了新的挑战。针对运行在MPSoC架构上的实时嵌入式应用,提出了两种两阶段的基于重定时的节能调度算法,它们将充分发掘MPSoC架构的并行潜力,并且和减少能耗关联起来考虑,既满足了应用执行时限的要求,又达到了降低应用能耗的目标。在设计算法时,两个算法第一阶段都采用重定时技术进行任务并行化,将一个迭代周期内的迭代内依赖关系转化成迭代间的依赖关系,从而减少了由于迭代内依赖关系和处理器间通信所导致的空闲时隙。这些赢得的空闲时隙在第二个阶段所利用以进行能量优化。在第二个能量优化阶段,第一个算法是模拟弹簧行为的启发式节能调度算法,它考虑了动态能耗和静态能耗。更进一步,由于影响系统能耗的因素很多,这些因素对能耗的影响又是错综复杂的,所以本文又提出了第二个基于遗传算法的节能调度算法,该算法考虑了多种能耗相关的因素,如动态能耗、静态能耗、电压跃迁代价、处理器间通信代价等因素,设计了染色体的基因编码方式、适度函数、交叉算子等。该算法可以充分发掘多处理器MPSoC架构的潜力以及现代芯片的节能特性,实现对能耗和性能的多目标优化。无线传感器网络是典型的分布式嵌入式系统,以上所提出的系统级的节能调度算法在每一个传感器硬件节点上同样适用。但是对于传感器网络,不仅应该关注每一个节点的能耗,还应该从整个网络协同工作角度出发考虑节能。因此,本文还研究了无线传感器网络三维空间栅栏覆盖中的节能问题。研究表明,单个虚拟栅栏覆盖的节点睡眠调度算法是NP-Hard问题,本文提出了单个虚拟栅栏覆盖调度算法求得近似解。在此基础上,又提出了K-虚拟栅栏覆盖调度算法来最优化K-虚拟栅栏调度,使得在同一时刻,在满足传感检测范围的前提下,让最少数量的传感器节点交替工作,既满足网络覆盖要求,又减少能耗,延长了传感器网络的生命周期。更多还原

【Abstract】 For battery-based embedded systems, low power is an important performance metric, thus, how to save energy and extend the systems’life time is a key challenge. Low power in embedded systems has promising and valuable applications and more and more researchers from industry and academic have conducted research in this area. The problem of energy-efficient scheduling in embedded systems is studied in this thesis. For hard real-time periodic tasks on embedded systems, four energy-efficient scheduling algorithms are presented in this paper. Furthermore, we present two energy-efficient algorithms for the 3D coverage problem in wireless sensor networks. For modern variable voltage processors, existing research work considers the ideal processor model with continuous variable voltage. However, actual processor model only have discrete voltage levels. Dynamic voltage scaling (DVS) is an efficient energy-saving technique by reducing processor running voltage. However, the lower voltage will lead to the more execution time, therefore, how to balance latency and power is a key challenge.For actual variable voltage processor with discrete voltage levels, first, this paper presents an optimal voltage selection algorithm, which can obtain the minimum energy consumption. Different from the existing heuristics, we first formulize the voltage selection problem as a variation of the multiple choice knapsack problem, and then present a dynamic programming algorithm to achieve the optimal solution. Furthermore, recent research work shows that the adjacent voltage transition on a processor can produce extra transition overhead that will affect the system’s latency and energy. Therefore, we present another improved energy-efficient scheduling algorithm for single processor. This algorithm considers discrete voltage model, DVS, and the overhead of voltage transition.For multiple processors, traditional task scheduling algorithms focused on exploring parallel potential so as to promote throughput and reduce latency. Nowadays, MPSoC architecture has been widely used in embedded systems. Multimedia and network processing applications are typical computing-intensive embedded applications. These applications require low power and low latency simultaneously, which is a key challenge for nowadays task scheduling techniques. We present two energy-efficient scheduling algorithms based on the retiming technique. The idea is to explore more parallel potential for the gain of energy, thus to obtain the multi-objective optimization of latency and energy. First, we present a task parallel algorithm based on retiming technique. The algorithm transforms the intra-task dependency in one iteration into intra-task dependency in different iterations, in other words, this algorithm makes the tasks in the same iteration to be independent each other, thus it can reduce the idle time slot caused by inter-task data dependency or processor communications. Based on this step, we present two energy-efficient scheduling algorithms. The first is a heuristic one that simulates the behavior of spring to generate the schedule. This algorithm considers dynamic power and static power. Furthermore, due to the system energy is affected by multiple factors and the relationships between these factors are complicated, we present another genetic energy-efficient scheduling algorithm. In this algorithm, according to dynamic power, static power, voltage transition overhead, inter-processor communication overhead, and so on, we design the gene coding of chromosome, the fitness function, the crossover operator etc. This algorithm can fully explore the potential of MPSoC architecture and the low power optimization techniques to obtain the multi-objective optimization on latency and energy.Wireless sensor networks (WSNs) is also typical distributed embedded system, all the algorithms presented above is adapted to one sensor node. However, in WSNs, besides the energy consumption of one node, we must consider energy saving from the whole network angle by design scheduling algorithm to obtain a good network node collaborative results. Thus, we study the energy-saving on barriers coverage problem in 3D space. Existed research shows that single virtual barriers coverage problem in 3D space is NP-hard problem. We present a single virtual barrier coverage sleep-wakeup scheduling algorithm, namely maximum virtual grid covers algorithm, to solve this problem. Based on this, we present a K-virtual barriers coverage sleep-wakeup scheduling algorithm to achieve optimal barrier partition to solve the K-virtual barriers coverage problem in 3D space. This algorithm divides the sensor nodes into different partitions, and each node set satisfies monitor scope at one moment. This algorithm scheduling these nodes set alternatively, thus can reduce the network whole energy consumption and extend the life time of the WSNs.更多还原