Study On Energy-efficient Scheduling Algorithms In Embedded Systems

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.