Search

Power consumption is becoming complicated to tackle each day in the embedded systems industry. As the demand for speed and accuracy increases, so does the power consumption of these systems. While introduction of multiprocessors have been shown to reduce the power problem compared to a uni-processor, researchers have tried to attain results using methods such as voltage and frequency scaling and scheduling methods. As an extension of these methods, task migration can be used to further reduce the power consumption of multiprocessor architectures. This article introduces a three-part framework to energy reduction of applications on a multiprocessor through an effective task allocation technique followed by task migration and finally a proper task scheduling scheme based on the earliest deadline first (EDF) method. Our experimental results showed great improvement over multiple state of the art energy reduction methods in the literature especially in the case of higher system workload over a range of underlying system architectures. [ABSTRACT FROM AUTHOR]

Heterogeneous distributed embedded systems are widely used because they can significantly improve the computing performance of parallel applications in embedded systems. Since such systems are limited by both system energy consumption and schedule length, further scheduling optimization design is required. To achieve a balance between computing performance and energy consumption, the task scheduling problem under energy constraints has attracted great attention from researchers in recent years. However, state-of-the-art algorithms ignore the impact of the task structure of the application on scheduling performance. In this study, a structure-aware task scheduling strategy is proposed for the parallel application scheduling problem in heterogeneous distributed embedded systems. Specifically, the structure of the application is considered a factor affecting the algorithm. Meanwhile, to reduce the schedule length of the application and avoid pessimistic energy allocation, this study proposes an improved weighted energy pre-allocation algorithm. Experimental results demonstrate that the task structure-aware algorithm can decrease the scheduling length for energy consumption-constrained parallel applications. Compared with the MSLECC algorithm, the task scheduling length of the task structure-aware algorithm in the Gaussian Elimination transform can be shortened by 42.39%. [ABSTRACT FROM AUTHOR]

The development of real-time systems has stimulated studies of real-time scheduling algorithms and schedulability analysis methods for parallel tasks, whose number has increased from year to year. For parallel tasks that cannot be converted to sequential tasks, the existing scheduling strategies mostly use one scheduling strategy. From the experiment results when we use different scheduling strategies to schedule the same tasks, we can observe these strategies have advantages for tasks with specific parameter characteristics. We combine the strengths of three algorithms: the partitioned algorithm, the federated scheduling algorithm and the GFP algorithm. A BH-Mixed scheduling algorithm for directed acyclic graph tasks with constrained deadlines is proposed in this paper. We design a classification method according to the feature of these three algorithms. The tasks are divided into three groups and scheduled by the partitioned algorithm, the federated scheduling algorithm and the GFP algorithm respectively. Experimental results show that the BH-Mixed scheduling algorithm outperforms other algorithms tested in this paper. [ABSTRACT FROM AUTHOR]

Heterogeneous multiprocessor platform has been widely adopted as an effective approach to providing strong calculation capability while keeping complexity and energy consumption under control in large-scale systems. Although this platform is able to achieve efficient cost reduction and flexibility enhancement in the design and development process of real-time applications, it brings a serious and complex multi-task scheduling problem, especially for dependent tasks with energy consumption constraints. All tasks should be scheduled according to appropriate strategies such that their dependence requirements and energy consumption limitations would be satisfied even in the worst-case situations. In this work, we focus on the energy-aware scheduling problem of dependent tasks in heterogeneous multiprocessor systems. First, we model the dependent tasks and heterogeneous processors, and formulate the energy-aware scheduling problem as a constrained optimization one with an objective of minimizing the schedule length of tasks. Then, by adopting an efficient task prioritization strategy and a weight-based energy distribution strategy, we propose a list-based energy-aware scheduling algorithm to seek an approximate optimal start time and processor allocation for each task, guaranteeing that all tasks would be executed efficiently while meeting the dependence and energy requirements. Experiments with randomly generated tasks are conducted to evaluate the performances of the proposed approach in terms of schedule length, optimal solution ratio, and execution time. [ABSTRACT FROM AUTHOR]

Response time analysis of adaptive variable-rate tasks (AVR tasks) is a challenging problem in automotive real-time systems. While in periodic event-triggered systems, the worst-case response time is easy to determine, the analysis of AVR tasks has to deal with an exponentially growing number of combinations of execution paths. Each execution path has a specific dynamic behavior. In this paper, we present a new approach for reducing the number of potential worst-case combinations by introducing an intuitive view on the relation of start and end speeds given by speed-phase diagram. Here we propose a minimal inter-arrival time algorithm (MIAT) which is built on time constant lines (isochrones) in a speed-phase diagram first introduced in this work. Compared with previous work, the MIAT algorithm is more accurate and shows a significant improvement in runtime. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we focus on the semi-partitioned scheduling of sporadic tasks with constrained deadlines and identical processors. We study two cases of semi-partitioning: (i) the case where the worst case execution time (WCET) of a job can be portioned, each portion being executed on a dedicated processor, according to a static pattern of migration; (ii) the case where the jobs of a task are released on a processor, 1 time out of p, where p is an integer at most equal to the number of processors, according to a round-robin migration pattern. The first approach has been investigated in the state-of-the-art by migrating a job at its local deadline, computed from the deadline of the task it belongs to. We study several local deadline assignment heuristics (fair, based on processor utilization and based on the minimum acceptable local deadline for a job on a processor). In both cases, we propose feasibility conditions for the schedulability of sporadic tasks scheduled using earliest deadline first (EDF) semi-partitioned scheduling. We show that the load function used for global scheduling to establish the feasibility of sporadic task sets exhibits interesting properties in the semi-partitioning context. We carry out simulations to study the performance of the two approaches in terms of success rate and number of migrations, for platforms composed of four and eight processors. We compare the performance of these semi-partitioned heuristics with the performance of classical partitioned scheduling algorithms and with a global scheduling heuristic which is currently considered to have good performances. [Copyright &y& Elsevier]

Non-uniform memory access (NUMA) systems are characterized by varying memory latencies so that execution times may become unpredictable in a multicore real-time system. This results in overly conservative scheduling with low utilization due to loose bounds on a task's worst-case execution time (WCET). This work contributes a controller/node-aware memory coloring (CAMC) allocator inside the Linux kernel for the entire address space to reduce access conflicts and latencies by isolating tasks from one another. CAMC improves timing predictability and performance over Linux' buddy allocator and prior coloring methods. It provides core isolation with respect to banks and memory controllers for real-time systems. This work is the first to consider multiple memory controllers in real-time systems, combine them with bank coloring, and assess its performance on a NUMA architecture, to the best of our knowledge. [ABSTRACT FROM AUTHOR]

In recent years, Network-on-Chip (NoC) based multicore systems have become popular for executing real-time applications. Mapping and scheduling of these applications are critical for system performance. The complexity of the problem increases for dynamic scenarios with real-time applications where new applications unknown at design-time, are submitted by users at runtime. Most of the existing works in this domain either ignore the allocation of communication workload or use estimated network contention while neglecting the impact on timing performance of tasks. In this work, we present an improved algorithm for dynamic task assignment and scheduling with link contention-awareness, which jointly allocates the tasks on the processors of NoC based multicore platform and schedules the communications on on-chip links. It minimizes communication latency and helps to satisfy the deadline of the tasks present in the allocated real-time applications. Experimental results show that the proposed approach achieves 25.3% and 45.6% improvement in task deadline satisfaction and communication latency compared to recent dynamic task allocation approaches while exhibiting 31.2% reduced runtime overhead. • Proposes a dynamic resource allocation approach for jointly allocating and scheduling the computation and communication workload present in real-time applications on NoC based multicore systems. • Presents an online scheme considering the future communication traffic depending on the link utilization and dynamically selects a route for communication packets of applications. • Presents an improved heuristic method for deadline and link-contention aware runtime mapping and scheduling of tasks and their communication transactions for mitigating network contention during application execution. [ABSTRACT FROM AUTHOR]

Efficient task scheduling improves offloading performance in mobile edge computing (MEC) environment. The jobs offloaded by different users would have different dependent tasks with diverse resource demands at different times. Meanwhile, due to the heterogeneity of edge servers configurations in MEC, offloaded jobs may frequently have placement constraints , restricting them to run on a particular class of edge servers meeting specific software running settings. This spatio-temporal information gives the opportunity to improve the resource utilization of the computing system. In this paper, we study the scheduling method for the jobs consisting of dependent tasks offloaded by different users in MEC. A new task offloading scheduler, Horae, is proposed to not only improve the resource utilization of MEC environment but also guarantees to select the edge server which could satisfy placement constraints for each offloaded task. Concretely, considering the fact that each job would experience slack time as a result of competing for limited resource with other jobs in MEC, Horae minimizes the sum of all slack time values of all the jobs while guaranteeing placement constraints, and therefore improve the resource utilization of the system. Horae was validated for its feasibility and efficiency by means of extensive experiments, which are presented in this paper. [ABSTRACT FROM AUTHOR]

Efficient energy management and fault tolerance are two key issues that demand judicious handling while scheduling real-time task-sets. Standby-sparing technique is available in literature for fault tolerance, while dynamic power management (DPM) and dynamic voltage scaling (DVS) schemes are exploited for energy management. However, usage of auxiliary processor for running backup jobs leads to increased energy consumption making fault tolerant scheduling energy inefficient. In the current work, overloading of backup jobs in overlapping time intervals is proposed, implemented and investigated for reducing energy consumption on auxiliary processor for scheduling real-time periodic tasks. Two energy efficient fault tolerant scheduling algorithms FEED-O and FEED-OD are proposed and extensive performance analysis through simulations is carried out indicating their usefulness especially at higher task-set utilization in comparison to other state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

An AUTOSAR-based embedded software consists of a set of inter-connected Software Components (SWCs). Each SWC contains a set of runnables which are small code-fragments that should be mapped to Operating System (OS) tasks. This process of mapping runnables to tasks may affect both the system real-time schedulability and performance. This paper proposes fast and efficient algorithms for mapping runnables to tasks. For a given embedded software containing a defined set of runnables, proposed algorithms define the number of required tasks to schedule the set of runnables, tasks priority assignment, and execution order of runnables inside each task. Experimental studies have been carried out to assess the proposed solutions. They outline both the computational efficiency, and the performance of proposed algorithms in comparison with other existing methods. [ABSTRACT FROM AUTHOR]

Energy management is one of the crucial design issues when executing real-time applications with stringent timing requirements. Dynamic slowdown of processor voltage if accompanied with processor shutdown method, helps in better saving energy. Traditionally, energy management has been applied to real-time scheduling algorithms that prioritize tasks based on timing parameters only, however, recently applications having tasks with different execution-preferences on the same computing unit found significant importance in various areas. In this paper, dynamic voltage scaling (DVS) and dynamic power management (DPM) techniques are used for energy management while scheduling preference-oriented fixed-priority periodic real-time tasks. Preference-oriented energy-aware rate-monotonic scheduling (PER) and preference-oriented extended energy-aware rate-monotonic scheduling (PEER) algorithms are proposed that maximize energy savings while fulfilling preference-value of tasks. Extensive simulations show that PER and PEER outperforms in terms of energy savings when compared to several related studies. [ABSTRACT FROM AUTHOR]