Search

This book has presented a task scheduling methodology which can effectively explore the performance vs energy trade-off space when mapping dynamical and concurrent tasks onto multiple heterogeneous processors. The principle of this methodology is a two-phase scheduling framework, i.e., the design-time scheduling phase and the run-time scheduling phase. Both a basic (Chapter 4), and a scalable (Chapter 5) design-time scheduling techniques are described in order to perform intra-task (thread node) level design space exploration. These design-time scheduling techniques are different from the existing scheduling algorithms in their systematically explorations of the design trade-off space instead of obtaining a single optimal solution. The fast and effective exploration of large design space based on these design-time scheduling techniques provide system architects the crucial information to perform the system level trade-offs. [ABSTRACT FROM AUTHOR]

The ever-increasing transistor density on silicon chips has enabled the production of complex MPSoC. A typical MPSoC may consist of many heterogeneous processors which provide not only a better performance due to the parallelism offered by the underlying platform, but also an extremely high-energy efficiency compared with the conventional single processors. Such energy efficiency is a prerequisite for most ubiquitous high-performance embedded systems. This chapter uses the example of mapping a real-life application on a MPSoC to demonstrate the TCM prototype tools. [ABSTRACT FROM AUTHOR]

The memory system is an important contributor to the performance and power consumption of embedded software. This is particularly true for multimedia applications [37, 165, 243]. Because the memory subsystem is that important to embedded systems, several architectural extensions and dedicated compilation techniques have been proposed to optimize it (see [20, 37, 165, 243] for good overviews). Unfortunately, the current techniques are mostly limited to applications with a single thread of control that are statically analyzable. They cannot cope with the multithreaded nor with the dynamic behavior of our application domain. [ABSTRACT FROM AUTHOR]

The mapping methodology presented in this book requires a fast technique to estimate the execution time and the energy consumed per each thread node, when run on each processing element in the system, per each scenario. [ABSTRACT FROM AUTHOR]

Embedded systems running under dynamic conditions often encounter the arrivals of new TF at run-time. Conventional run-time scheduling approaches are mostly focused on the topic of how to schedule both existing TF and new TF together such that all (hard and/or soft) real-time constraints are met. However, today's portable embedded systems do not only require a schedule that can fulfill the timing constraints, they also need a run-time scheduler that produces energy-efficient schedules and causes very little overheads in order to meet the constraints of energy dissipation. Chapter 6 has considered the needs of energy-efficient run-time scheduling and presented the basic run-time scheduling technique. [ABSTRACT FROM AUTHOR]

Since the application complexity is growing and applications can be dynamically activated, the major challenge for multiprocessor platforms is to select at run time an energy-efficient mapping of these applications. As motivated earlier, in Chapter 3, to alleviate the run-time decision-making, and to avoid conservative worst-case assumptions, a two-phase customized runtime management concept can be used (Fig. 7.1). [ABSTRACT FROM AUTHOR]

As explained in previous chapters, a run-time scheduler is indispensable to efficiently explore the design space and make system level trade-off according to the dynamic context. For that sake, a fast and effective heuristic is needed. In this chapter, we first review again why we need a two-phase approach for task scheduling and how it is applied. The problem is then defined in a more formalized way and a greedy heuristic is described. After that, experimental results on both randomly generated and real-life applications are explained. In this chapter, we will illustrate our method on 2-dimensional Pareto trade-offs with execution time vs energy as axes. But the underlying techniques can also be applied to other axes and more dimensional trade-offs, which will be demonstrated in the next chapter. [ABSTRACT FROM AUTHOR]

Task scheduling on multiple heterogeneous processors is notorious for its computation intractability. Although previous design-time task schedulers have tackled this intractability with fast heuristics, it remains time-consuming to explore the design space for large input TF. This chapter presents a novel method that combines the graph partition and the TF interleaving technique to tackle the trade-off exploration problem in a scalable way. Based on this method, we have developed a hierarchical scheduler that can employ the existing design-time schedulers and can significantly accelerate the design space explorations for large TF. [ABSTRACT FROM AUTHOR]

In this chapter, we present the development of a novel task scheduling algorithm for the design-time scheduling phase of our two-phase TCM framework. Scheduling has different meanings in different contexts. In this chapter, scheduling has two meanings. First, assigning every thread node of a given TF to one of the processors of a given platform. Second, deciding the start time to execute every node on its assigned processor. We have two assumptions for this scheduling problem. First, whether a node can be executed on a certain processor should be known. Second, if a node can be executed on a certain processor, the execution time should be known, calculable or predictable. Based on the second assumption, having decided the start time of executing a node on a certain processor, the scheduler can derive the finish time of such an execution immediately. Therefore, the execution order of all the nodes assigned to each processor is known. In summary, scheduling in our context means node-to-processor assignment and ordering. [ABSTRACT FROM AUTHOR]

The Task Concurrency Management (TCM) methodology developed at IMEC and its university research partners since 1997 [36, 234] addresses the mapping of dynamic and concurrent tasks on multiple processors for real-time embedded systems, where energy consumption is often a major concern. The cornerstone of this methodology is a well-balanced two-phase scheduling method, which provides the required flexibility at a low run-time overhead. The rationale behind the two-phase scheduling is that the only way to handle very dynamic applications in a resource-efficient way is to postpone some design decisions till the run-time stage. Fixing everything at designtime according to the worst case estimation of the system would result in either a too energy-hungry platform or a poorly performing application most of the time. In the meantime, only the minimal amount of effort should be done at the run-time to minimize the overhead, and to still meet all hard realtime constraints. [ABSTRACT FROM AUTHOR]

Task scheduling has been investigated overwhelmingly in different communities in the past decades. Traditionally, it was used to guarantee objectives such as timeliness or resource constraints, or to optimize objectives such as system response time. Recently, as power consumption is receiving more and more attention in embedded systems, many new task scheduling approaches have been proposed to tackle the issues of low-power designs. [ABSTRACT FROM AUTHOR]

Electronic systems that use CPUs or processing platforms to perform a specific function that is known up-front, are generally known as embedded systems. This is especially so when they are neither used nor perceived as computers [240]. Embedded systems are widely deployed in consumer products that we use everyday, such as TV sets, automobiles, mobile phones. In fact, International Data Corporation (IDC) reports that of the nearly 2 billion microprocessor chips manufactured each year, over 95% go into non-PC "embedded" devices. [ABSTRACT FROM AUTHOR]