Search

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]

Abstract Parallel real-time scheduling on multi-core platforms is widely studied and focused in academic and industrial fields. DAG (directed acyclic graph) is a widely-used parallel model. But existing scheduling algorithms for DAG suffer schedulability analysis of significant inaccuracy and resource waste. In this paper, we propose a hierarchical scheduling framework for DAG tasks with constrained deadlines that it provides a much more efficient resource sharing solution without distinguishing the types of tasks. We have evaluated and implemented our proposed hierarchical scheduling and the results show that our proposed method has promising performance. [ABSTRACT FROM AUTHOR]

Abstract Non-preemptive tasks with strict periods are usually adopted in practical multi-core real-time systems when continual sampling and processing of data are required. Systems designers need to provide a proper scheduling strategy such that the tasks' deadlines will be met even under the worst-case conditions. In this paper, we study the scheduling problem of non-preemptive tasks with strict periods in multi-core real-time systems. We first derive a necessary and sufficient condition to determine whether a new task is schedulable upon a multi-core platform without changing the allocations of the existing tasks. Then, with a game theory analogy, we design a recursive method to calculate the maximum permissible execution time for a given task, and propose a new schedulability condition used when the start time and processor assignments of the existing tasks can be modified. Finally, based on the conditions derived previously, we present a task assignment algorithm, which not only provides valid allocations for all tasks, but also obtains the minimum number of processors required by the system. Simulation experiments with randomly generated task sets have been conducted to show the high efficiency and reliability of the proposed approach. [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]

Abstract: As the power density of modern electronic circuits increases dramatically, systems are prone to overheating. Thermal management has become a prominent issue in system design. This paper explores thermal-aware scheduling for sporadic real-time tasks to minimize the peak temperature in a homogeneous multicore system, in which heat might transfer among some cores. By deriving an ideally preferred speed for each core, we propose global scheduling algorithms which can exploit the flexibility of multicore platforms at low temperature. We perform simulations to evaluate the performance of the proposed approach. [Copyright &y& Elsevier]

Abstract: Thread-level redundancy is an efficient approach for transient fault detection and recovery in Chip Multiprocessors (CMPs), in which two adjacent cores are statically coupled to form a functional Dual Modular Redundancy (DMR). Manufacturing process variations cause core-to-core (C2C) performance asymmetry across the chip, which can be further divided into the asymmetry among core-pairs and the asymmetry within a core-pair. We call them inter- and intra-pair asymmetries, respectively, both of which should be taken into considerations in application scheduling for CMPs with static core coupling. In this paper, we first formulate the above scheduling problem as a 0–1 programming problem to maximize the system Weighted Throughput. An efficient IVF&AppSen algorithm is then proposed, which we prove to be optimal when the number of applications equals to that of core-pairs. We also adapt the Simulated Annealing technique to tackle this problem when applications are less than core-pairs on chip. Simulations on a 64-core CMP shows that the proposed algorithms achieve 2.5–9.3% improvement in Weighted Throughput when compared to prior VarF&AppIPC algorithm. [ABSTRACT FROM AUTHOR]

Abstract: This paper addresses the most crucial optimization problem of high-level synthesis: scheduling. A formal framework is described that was tailored specifically for the definition and investigation of the time-constrained scheduling problem of pipelined datapaths. Theoretical results are presented on the complexity of the problem. Moreover, two new heuristic algorithms are introduced. The first one is a genetic algorithm, which, unlike previous approaches, searches the space of schedulings directly. The second algorithm realizes a heuristic search using constraint logic programming methods. The performance of the proposed algorithms has been evaluated on a set of benchmarks and compared to previous approaches. [Copyright &y& Elsevier]

In this paper, we consider simultaneously energy consumption and resource synchronization in mixed-criticality (MC) single processor systems. First, we give a feasibility analysis of single processor systems that execute real-time MC tasks. Second, an energy efficient speed based on sufficient feasibility condition is computed. In addition, we propose a single speed energy efficient algorithm for MC tasks with shared resources (ASS). The ASS algorithm scheduling tasks with S L O is too conservative with much room to save more energy. For energy efficiency, dual speeds scheduling algorithm (DSS) based on ASS algorithm is proposed. It schedules tasks at S L O with blocking and S L O ′ without blocking. Blocking means that the higher priority tasks cannot preempt the execution of current low-priority tasks because low-priority tasks occupy the shared resources required for the higher priority tasks. Moreover, we prove that the DSS algorithm is feasible. Finally, the real-life synthetic application and extensive simulation are applied to validate the proposed algorithm. The experimental results show that the DSS algorithm can reduce energy consumption up to 11.82% compared with the existing approaches. [ABSTRACT FROM AUTHOR]

In hard real-time embedded systems, switching to multicores is a step that most application domains delay as much as possible. This is mainly due to the number of sources of indeterminism, which mainly involve shared hardware resources, such as buses, caches, and memories. In this paper, a new task model that considers the interference that task execution causes in other tasks running on other cores due to memory contention is proposed. We propose a scheduling algorithm that calculates the exact interference. We also analyse and compare existing partitioning algorithms and propose three strategies to allocate tasks to cores to schedule as many tasks as possible and minimise total interference. • Definition of a task model that considers interference delays due to contention of shared hardware resources. • Proposal of a new scheduling algorithm that copes with the new task model. This scheduling algorithm is formulated to be included in any priority-based scheduling algorithm for monocores. • Proposal of three allocation algorithms and comparison with existing ones in terms of schedulability and total utilisation of the system. [ABSTRACT FROM AUTHOR]

Edge computing enables users to offload certain computation loads in complex applications to a nearby network consisting of multiple mobile devices such that the mobile devices' resources can be integrated to afford these complex applications. Due to the social relationships among the owners of mobile devices, networks in edge computing are always complex and consist of multiple sub-networks intersecting at several joint devices. In such complex networks, a joint device can communicate with all devices belonging to all sub-networks that intersect at this joint device while a general device can only communicate with the devices belonging to the same sub-network. This paper studies the makespan-minimization workflow scheduling problem for the aforementioned complex networks in edge computing environments, and formulates the problem as an integer program. Due to the limited energy capacity of each device, the dependence among workflow tasks, as well as network complexity, it is challenging to achieve feasible scheduling solutions for the concerned problem. Therefore, we propose a family of task allocation strategies to cope with different types of tasks in the workflow. These strategies are further integrated with a greedy strategy to construct an improved greedy search (IGS) algorithm which is capable of generating feasible solutions satisfying all constraints. In addition, we propose an improved composite heuristic (ICH) algorithm that employs IGS to initialize a feasible solution and uses a two-layer improvement scheme to further enhance the quality of the initial solution. Simulation results show that our proposed IGS achieves an 100% probability of generating feasible solutions, as compared to a 2.3% probability achieved by using the general round-robin scheduling algorithm. Furthermore, IGS and ICH outperform the counterpart scheduling algorithms in terms of makespan reduction. [ABSTRACT FROM AUTHOR]