Dynamic Voltage Scaling for Low-Power Hard Real-Time Systems:Inter Task Voltage Scaling for Hard Real-Time Systems

By -
Inter Task Voltage Scaling for Hard Real-Time Systems

Where intratask dynamic voltage scheduling targets energy reduction by scheduling speeds inside a task, without employing knowledge about other tasks that might run in the system, intertask scheduling addresses speed selection at task group level. The advantage of using a group level speed scheduling comes from the possibility of distributing the workload more evenly over tasks and execution time. As a result, more time is spent at lower speeds, leading to lower energy consumption.

As detailed in the previous chapter, intratask DVS means, in principle, selecting the right processor speed for specific task sections. At that level, timing is strictly determined by the speed to section assignment, and therefore intratask DVS scheduling and speed selection at task level refer basically to the same notion. However, moving up to groups of tasks, intertask DVS refers not only to assigning speeds to tasks, but also to deciding a start time for each task. Alternatively, one can view this as assigning certain time intervals for each task, within which these have to start and complete their execution in an optimal manner from the energy point of view. Thus, in general the intertask DVS problem is at least as hard as the classic scheduling problem. Occasionally, research in this area addresses intertask DVS in two steps, first deciding on the order of task execution (scheduling) followed by assigning speeds to individual tasks (speed selection). However, we will use dynamic voltage scheduling or speed scheduling to refer to this process as a whole.

Typically, at task group level one is not interested in how exactly each individual task makes use of its assigned time interval. In general, it is assumed that tasks can optimally select their execution speed inside the assigned interval. In this sense, intratask and intertask DVS are orthogonal and can and should be used to complement each other. Nevertheless, it may not always pay off to use the best, and usually most complex, techniques at both individual task and task group level. For once, intertask strategies may compensate for poor choices of intratask decisions, making complex task-level approaches obsolete. Secondly, the energy optimization version of the law of diminishing returns§ says that less and less energy is gained for the same added effort. Consequently, the scheduling overhead might end up consuming more energy than it is actually gained.

Given the extensive research and results in the area of hard real-time scheduling, it is understandable that the majority of the intertask DVS strategies build on top of classic hard real-time scheduling approaches. In fact, because of the strong dependency between energy, processor speed, and timing, using DVS to reduce energy consumption while keeping hard deadlines is more of a challenge in these kind of real-time systems rather than in any other. Although DVS techniques designed for soft real-time, Quality of Service, and user perceived latency oriented systems do exist, this chapter focuses on hard real-time approaches, as these are still applicable for less constrained systems.

From the architectural point of view, multiprocessor systems appear to be at least as efficient in terms of energy as uniprocessor systems. DVS strategies especially designed for multiprocessor systems do exist [29–43]. However, given the restricted space, only techniques designed for uniprocessor systems are presented in the following. Nevertheless, these can be extended for multiprocessor architectures in the same way classic real-time algorithms can be derived for multiprocessor systems.

A Taxonomy of InterDVS

A classification of the existing intertask DVS hard real-time approaches is by no means trivial. Other than that, there are a large number of InterDVS algorithms proposed in recent years (perhaps, more than necessary in practice!), most InterDVS algorithms are a blend of various techniques and methods, which make it difficult to classify them. Very few of these belong exclusively to one class, and therefore we will

Dynamic Voltage Scaling for Low-Power Hard Real-Time Systems-0058_thumb

rather classify scheduling decisions than complete approaches. One can group intertask DVS scheduling methods according to:

• Their occurrence, or the moment they are employed. Approaches range from fully static, when all the decisions regarding scheduling and speed selection are taken off-line, before the system becomes functional to mostly dynamic, where run-time speed management and scheduling are employed.

• Their complexity, or the overhead required by the scheduling strategy. Since, generally inter-task DVS, just as classic scheduling, is a hard problem, optimal algorithms are expensive. Heuristics with lower overhead may be employed at the expense of efficiency.

• Their foundation, or classic scheduling algorithm they build upon. To guarantee hard real-time requirements, most approaches employ a classic scheduling algorithm, such as rate-monotonic (RM) [44] or earliest deadline first (EDF) [45], which is then extended with various off-line and run-time speed selection strategies.

• Their flexibility, or the ability to accommodate and employ run-time task execution variations. Some approaches use only the WCET of tasks to take scheduling decisions while others may employ profiling, statistic information, and even execution history, to adapt to run-time variations.

Notice that the criteria identified above are not necessarily independent, as for example, high overhead, but accurate methods are more likely to be employed off-line than at run time. Furthermore, depending on the foundation, intertask DVS methods may be more or less flexible, employing predominantly run time or off-line decisions. In this paper, we classify existing techniques mainly according to occurrence and foundation, as shown in Table 18.1.

Comments

Post a Comment

Popular posts from this blog

SRAM:Decoder and Word-Line Decoding Circuit [10–13].

By -
Image
Decoder and Word-Line Decoding Circuit [10–13] Two kinds of decoders are used in SRAM: the row decoder and the column decoder. Row decoders are needed to select one row of word-lines out of a set of rows in the array. A fast decoder can be implemented by using AND/NAND and OR/NOR gates. Figure 52.7 shows the schematic diagrams of static and dynamic AND gate decoders. The static NAND-type structure is chosen due to its low power consumption, that is, only the decoded row transitions. The dynamic structure is chosen due to its speed and power improvement over conventional static NAND gates. From a low-voltage operation standpoint, a dynamic NOR-base decoding would provide lower delay times through the decoder due to the limited amount of stacking of devices. Figure 52.8 shows circuit diagrams of dynamic NOR gates. The dynamic CMOS gate as shown in Figure 52.8(a) consists of input- NMOSs whose drain nodes are precharged to a high level by a PMOS when a clock signal Φ is at a low lev...
Read more

ASIC and Custom IC Cell Information Representation:GDS2

By -
Image
GDS2 The Graphical Design System (GDS) format is a binary format developed by Calma Company in 1971 to convey IC layout information between IC designers and fabricators. Calma presented GDS2 format, the improved version of GDS, in 1978. Finally in 1991, when Cadence acquired Calma, GDS2 rights were transferred to it. In the design process, after the completion of routing and placement, design rule check (DRC) and layout versus schematic (LVS) are performed to verify the final layout. Then the verified layout, dumped in a GDS2 file, is transferred to IC foundries for fabrication. GDS2 File Format GDS2 is a standard mask layout intermediate format containing a single cell or a library of cells each of which includes a number of geometrical objects such as boundaries, paths, boxes, etc. These objects correspond to different layers of a cell where each layer is specified by a layer number and data type [3]. The file format of GDS2 is in binary. A GDS2 file contains a number of variable...
Read more

Timing Description Languages:SDF

By -
Image
SDF Standard Delay Format (SDF) is an ASCII format used to convey timing information between EDA tools. SDF was first developed by Cadence in 1990. Open Verilog International (OVI) approved SDF version 2 in 1993 and SDF version 2.1 and 3 in the following years. Improving SDF version 3 features, resulted in IEEE Standard 1497 [1]. Role of SDF in Design Process SDF can be used in different levels of a design process to annotate timing specifications, including timing data and constraints. Timing constraints are used during the forward-annotation process while timing data are applied during the back-annotation process. Forward-annotation process deals with porting timing constraints to synthesis, floorplanner, layout, and routing tools to meet the required constraints. During the design process, timing data can be back-annotated to analysis tools (including simulators, static timing analysis tools, etc.) to provide more accurate timing representations. SDF Structure An SDF f...
Read more