انتقال آگاهانه ی الگوریتم DVS برای سیستم های زمان واقعی با استفاده از تجزیه و تحلیل ساختار درختی

Dynamic voltage scaling (DVS) is a key technique for embedded real-time systems to reduce energy consumption by lowering the supply voltage and operating frequency. Many existing DVS algorithms have to generate the canonical schedules or estimate the lengths of slack time in advance for generating the voltage scaling decisions. Therefore, these methods have to compute the schedules with exponential time complexities in general. In this paper, we consider a set of jitter-controlled, independent, periodic, hard real-time tasks scheduled according to preemptive pinwheel model. Our approach constructs a tree structure corresponding to a schedule and maintains the data structure at each early-completion point. Our approach consists of off-line and on-line algorithms which consider the effects of transition time and energy. The off-line and on-line algorithm takes O(k + n log n) and O(k + (pmax/pmin)) time complexity, respectively, where n, k, pmax and pmin denotes the number of tasks, jobs, longest and shortest task period, respectively. Experimental results show that the proposed approach is effective in reducing computational complexity, transition time and energy overhead.

Power-aware computing has widely spread not only for mobile devices powered by batteries, but also for large systems in which the cost of energy consumption and cooling is substantial. With dynamic voltage scaling (DVS) technique [2], [17], [20], [21], [23], [25], [26], [28], [32], [33], [39] and [48], processors perform at a range of voltage and frequencies. Since the energy consumption E of CMOS circuits has a quadratic dependency on the supply voltage, lowering the supply voltage is one of the most effective ways to reduce the energy consumption while satisfying the time constraint of each real-time task. Most DVS scheduling algorithm are known to be quite effective in reducing the energy consumption of a target system. However, a significant limitation of DVS processor is that they are unable to change the operation voltage and frequency immediately. The limitation, known as transition time overhead, includes translation time required for power delivery system and the time for relocking a clock generator requires approximately 130 μs in Intel® M processors [13] and [49]. The architecture, in addition, needs 10–15 μs to ensure system memory access unavailability to match isochronous device needs. Therefore, ignoring time overhead in real-time systems may incur deadline misses, which results in low system performance or even system failure [32]. Another problem is the transition energy overhead, which increases the systems’ energy consumption if DVS algorithm adjusts voltage/speed level frequently. Therefore, much literature ignoring transition energy overhead may not reduce actual total energy consumption in the systems. In the network systems, jitter or packet delay variation (PDV) is defined as the variation in the time between successive packet arrivals caused by network congestion, time drift or route changes [28] and [47]. PDV is an important quality-of-service factor to evaluate the network performance. One of the most widespread techniques to improve PDV is pinwheel scheduling [16], [24], [27], [29], [31] and [35]. A pinwheel task i is characterized by two positive integer parameters an execution requirement and a window length with explanation that the task i need to be allocated the shared resource for at least a out of every b consecutive time units. Pinwheel task systems are the first motivated by the performance requirements of satellite-based communications. In the recent applications, broadband 3G (B3G) wireless communication systems provide a packet-switched core network to support broadband wireless multimedia services. The resource management policies in the cell of B3G system are to guarantee the quality-of-service (QoS) of real-time (RT) traffics. To guarantee the QoS of RT traffics in a cell, many researchers [4], [24], [30] and [31] proposed the pinwheel scheduling algorithms to reduce the jitter of variable bit rate (VBR) traffic in a cell. In addition, pinwheel scheduling is also applied in the channel assignment policies with buffer and preemptive priority for RT traffics. In other applications, such as the medium access control (MAC) layer of CDMA and TDMA-based wireless networks [8], [10] and [28], many pinwheel scheduling schemes are proposed for solving the frame-based packet scheduling problems. These pinwheel methods provide low delay and low jitter for RT traffic and short-queue length for non-RT traffic. In the periodic real-time systems, the jitter is defined as the difference in the end-to-end delay between successive jobs in a sequence with respect to a processor. It is usually caused by the changes of task periods or the interference of other tasks [33]. The former applications using jitter-controlled or pinwheel algorithm are all designed for a single node. Pinwheel scheduling is also used in the end-to-end scheduling model [15] to solve the timing and reliability constraints. For example, in the wireless sensor network applications, a multi-sensor situation assessment task is invoked either periodically or triggered by certain events. This assessment process may have one or more input tasks to collect data from different sensors. The end-to-end deadline between a trigger event and the corresponding response processing to response may have somewhere limitations. Similar requirements exist in the phased-array radar systems; the dwell tasks collect device data and must recognize properties of the aircrafts within a certain end-to-end deadlines [15]. Other examples include the use of broadcast disks [4] in the on-board automotive navigational systems [4], [18] and [19] that allow for automated route guidance and automatic routing around traffic incidents. Many applications have applied the concept of jitter control in their computer and communication hardware/software systems. For example, the delay and jitter control in ATM (Asynchronous Transfer Mode), a multimedia stream requires QoS including end-to-end delay 100 ms in the network systems. Novel real-time applications like Voice over IP (VoIP) and Video on Demand (VoD) have jitter control requirements. In many RT applications, tasks must be executed in a distance- constrained manner, rather than just periodically. In the distance-constrained task systems (DCTS), the temporal distance between any two consecutive executions of a job should always be less than a certain value. In DCTS, pinwheel tasks transform the distance-constraints into 2n multiples of other shorter periods [7] and [14], which are shorter or equal to their original distance-constraints. The advantage of the period transformation is that the produced schedules have regular start, preemption and finish times, and therefore provide good predictability.

In this paper, we have proposed a novel tree structured method for scheduling DVS real-time tasks. It includes the consideration of transition overhead as well as the discrete voltage levels. Because of the predictability of jitter-controlled schedules and the innovative search-tree technique, our off-line preprocessing and on-line scheduling algorithms have time complexity O(k + n log n) and O(View the MathML sourcek+pmaxpmin), respectively. In the future works, our method will be improved so that it can be implemented in the systems without jitter-controlled tasks. In addition, more generated benchmark examples as well as real-life voice codec example will be applied to showing the performance of the investigated approaches.