Search

Interference between tasks running on separate cores in multi-core processors is a major challenge to predictability for real-time systems, and a source of over-estimation of worst-case execution duration bounds. This paper investigates how the multi-phase task model can be used together with static scheduling algorithms to improve the precision of the interference analysis. The paper focuses on single-period task systems (or multi-periodic systems that can be expanded over an hyperperiod). In particular, we propose an Integer Linear Programming (ILP) formulation of a generic scheduling problem as well as 3 heuristics that we evaluate on synthetic benchmarks and on 2 realistic applications. We observe that, compared to the classical 1-phase model, the multi-phase model allows to reduce the effect of interference on the worst-case makespan of the system by around 9% on average using the ILP on small systems, and up to 24% on our larger case studies. These results pave the way for future heuristics and for the adoption of the multi-phase model in multi-core context. [ABSTRACT FROM AUTHOR]

In the scheduling of hard real-time systems on multicore platforms, significant unpredictability arises from interference caused by shared hardware resources. The objective of this paper is to offer a schedulability analysis for such systems by assuming a general model that introduces interference as a time parameter for each task. The analysis assumes constrained deadlines and is provided for fixed priorities. It is based on worst-case response time analysis, which exists in the literature for monocore systems. We demonstrate that the worst-case response time is an upper bound, and we evaluate our proposal with synthetic loads and execution on a real platform. [ABSTRACT FROM AUTHOR]

Summary: Scheduling the tasks of parallel scientific applications is very important for efficient utilization of resources and reducing the overall execution time (makespan). Parallel applications typically include both data parallelism and task parallelism. It is known that the scheduling problem on multiprocessor systems problem is NP‐Hard even for applications involving pure task parallelism. The problem becomes more difficult when data parallelism is also taken into consideration. These problems usually considered in two steps, processor allocation and task scheduling, and various algorithms have been proposed. In this study, we introduce a genetic algorithm based hyper‐heuristic approach for the processor allocation problem. Experimental results indicate that the algorithm provides better performance compared to various greedy algorithms. [ABSTRACT FROM AUTHOR]

In the scheduling of hard real-time systems on multicore platforms, significant unpredictability arises from interference caused by shared hardware resources. The objective of this paper is to offer a schedulability analysis for such systems by assuming a general model that introduces interference as a time parameter for each task. The analysis assumes constrained deadlines and is provided for fixed priorities. It is based on worst-case response time analysis, which exists in the literature for monocore systems. We demonstrate that the worst-case response time is an upper bound, and we evaluate our proposal with synthetic loads and execution on a real platform.

Flexible job shop scheduling problem is a NP-hard combinatorial optimization problem, which has significant applications in the field of workshop scheduling and intelligent manufacturing. Due to its complexity and significance, lots of attention have been paid to tackle this problem. This paper reviews some of the researches on this problem, by presenting and classifying the different criteria, constraints, and solution approaches. The existing solution methods for the flexible job shop scheduling problem in this literature are classified into exact algorithms, heuristics, and meta-heuristics, which are thoroughly reviewed. Particularly, the paper highlights the flexible job shop scheduling problem in the context of dynamic events and preventive maintenance. These dynamic events, such as machine breakdowns and unexpected changes in job requirements, present additional challenges to the scheduling problem. Furthermore, this paper analyzes the development trends in the manufacturing industry and summarizes detailed future research opportunities for the flexible job shop scheduling problem. [ABSTRACT FROM AUTHOR]

Multicore systems were developed to provide a substantial performance increase over monocore systems. But shared hardware resources are a problem as they add unpredictable delays that affect the schedulability of multicore hard real-time systems. In recent years much effort has been put into modelling interference and proposing scheduling techniques to mitigate its negative effect. Using one of these models, we propose a scheduling technique, based on Integer Linear Programming (ILP) that, in combination with a task to core allocator, not only achieves a feasible schedule but also reduces the interference produced by shared hardware resources in the context of hard real-time multicore systems. The evaluation shows how interference is reduced ( $\approx 83.47$ %) and schedulability is increased ( $\approx 12.25$ %) compared to traditional heuristics.

Communication and control are two intensively coupled aspects in a networked control system (NCS), the design of one may affect the quality or performance of the other. The co-design problem of control and communication scheduling for NCSs has attracted tremendous attention. This paper provides an overview of recent advances in control and scheduling co-design for networked control systems. First, a basic framework of control and scheduling co-design problem setup is established. Second, representative results and methodologies reported in the literature are reviewed and some in-depth analysis and discussions are given, along the lines of the scheduling schemes including static scheduling, dynamic scheduling, and random scheduling. Finally, some unsettled issues and trending topics in this direction are outlined for future research. [ABSTRACT FROM AUTHOR]

Intelligent manufacturing is an inevitable trend in the development of our country' s manufacturing industry, and intelligent shop scheduling is a key technology for the integration of manufacturing upgrades and deepening. This paper mainly studied the application of reinforcement learning algorithms in shop scheduling problems, which layed the foundation for sub sequent research. Shop scheduling mainly included static scheduling and dynamic scheduling, reinforcement learning algorithms mainly included value-based functions and Actor-Critic (AC) networks. First of all, this article described the research status of reinforcement learning methods on the two major issues of Job-Shop scheduling and Flow-Shop scheduling in general. Secondly, it classified the establishment rules of mathematical model of the shop scheduling problem and the most critical Mark ov model in reinforcement learning algorithms. Finally, according to the research status and the current needs of industrial digital trans- formation, it prospected the future research direction of intelligent workshop scheduling technology . [ABSTRACT FROM AUTHOR]

• Frequency constraints lower scheduling difficulty significantly. • Problem formulation is key when aiming for optimal solutions. • Core partitioning is more effective than partitioning along the time axis. • Fully heuristic scheduling approach is viable for larger task sets. Static scheduling of independent, moldable tasks on parallel machines with frequency scaling comprises decisions on core allocation, assignment, frequency scaling and ordering, to meet a deadline and minimize energy consumption. Constraining some of these decisions reduces the solution space, i.e. may increase energy consumption, but may also open the path to new, near-optimal approaches. We investigate how constraints of different steps influence energy consumption, starting with an unrestricted scheduler for moldable tasks. The constraints are partly derived from existing schedulers, but also generalized in a systematic way. We present integer linear programs for all scheduling variants. We compare energy consumption of schedules for a benchmark suite of synthetic task sets of different sizes and for task sets derived from real applications. In addition, we check how close the results are to the optimum results when the ILP solver meets a timeout. Our results indicate that constraints on task execution order, which avoid explicit representation of task order in ILPs, are mostly responsible for near-optimal energy consumption among large task sets. Furthermore, we find that for all steps except allocation, non-optimal fast heuristics can be used without sacrificing too much energy for the resulting schedule. Finally, we can show that an ILP for a new scheduler, for which also a heuristic version exists, is comparable in quality to more complicated schedulers. [ABSTRACT FROM AUTHOR]

Models for energy-efficient static scheduling of parallelizable tasks with deadlines on frequency-scalable parallel machines comprise moldable vs. malleable tasks and continuous vs. discrete frequency levels, plus preemptive vs. non-preemptive task execution with or without task migration. We investigate the tradeoff between scheduling time and energy efficiency when going from continuous to discrete core allocation and frequency levels on a multicore processor, and from preemptive to non-preemptive task execution. To this end, we present a tool to convert a schedule computed for malleable tasks on machines with continuous frequency scaling [Sanders and Speck, Euro-Par (2012)] into one for moldable tasks on a machine with discrete frequency levels. We compare the energy efficiency of the converted schedule to the energy consumed by a schedule produced by the integrated crown scheduler [Melot et al., ACM TACO (2015)] for moldable tasks and a machine with discrete frequency levels. Our experiments with synthetic and application-based task sets indicate that the converted Sanders Speck schedules, while computed faster, consume more energy on average than crown schedules. Surprisingly, it is not the step from malleable to moldable tasks that is responsible but the step from continuous to discrete frequency levels. One-time frequency scaling during a task's execution can compensate for most of the energy overhead caused by frequency discretization. [ABSTRACT FROM AUTHOR]

Hardware Trojans can compromise System-on-Chip (SoC) performance. Protection schemes implemented to combat these threats cannot guarantee 100% detection rate and may also introduce performance overhead. This paper defines the risk of running a job on an SoC as a function of the misdetection rate of the hardware Trojan detection methods implemented on the cores in the SoC. Given the user-defined deadlines of each job, our goal is to minimize the job-level risk as well as the deadline violation rate for both static and dynamic scheduling scenarios. We assume that there is no relationship between the execution time and risk of a task executed on a core. Our risk-aware scheduling algorithm first calculates the probability of possible task allocations and then uses it to derive the task-level deadlines. Each task is then allocated to the core with minimum risk that satisfies the task-level deadline. In addition, in dynamic scheduling, where multiple jobs are injected randomly, we propose to explicitly operate with a reduced virtual deadline to avoid possible future deadline violations. Simulations on randomly generated graphs show that our static scheduler has no deadline violations and achieves 5.1%–17.2% lower job-level risk than the popular Earliest Time First (ETF) algorithm when the deadline constraint is 1.2×–3.0× the makespan of ETF. In the dynamic case, the proposed algorithm achieves a violation rate comparable to that of Earliest Deadline First (EDF), an algorithm optimized for dynamic scenarios. Even when the injection rate is high, it outperforms EDF with 8.4%–10% lower risk when the deadline is 1.5×–3.0× the makespan of ETF. [ABSTRACT FROM AUTHOR]

Production scheduling is one of the key technologies in steel manufacturing process. It plays a significant role in reducing the production cost and improving the production efficiency of iron and steel enterprises. In recent years, with the rapid development of intelligent steel-manufacturing technology, production scheduling has attracted increasing attention and become a research hotspot in the field of iron and steel metallurgy. The process of production scheduling in the process of steelmaking‒continuous casting was summarized and discussed through reviews of previous researches, and the characteristics and application scopes of various methods were compared and classified. Typical cases of the computer-aided scheduling system in domestic and overseas steelmaking plants were discussed, and the characteristics of each system were studied and analyzed comparatively. On the basis of the previous studies, forward-looking strategies and a methodology of production scheduling were proposed for the future study of steelmaking‒continuous casting process. For static scheduling, a new concept “rules + algorithm” was proposed, and a scheduling model construction method based on the production mode optimization of a steel mill was developed for a domestic special-steelmaking plant as a case study. For dynamic scheduling, multi-process collaboration was suggested, and a collaborative control method based on multi-agent was proposed. This method was developed for multi-process control, quality control, and scheduling control of the steelmaking-continuous casting process. An optimized and effective method for modeling and solving is one of the important means to solve the production-scheduling problem, aiming at improving the levels of setting up production plan and the feasibility of production planning. Meanwhile proposed method for modeling and solving can strengthen the on-site real-time control in steel mills and is of great significance to realize stable, orderly, and continuous operation in steelmaking-continuous casting process.

Hard real-time systems focus on obtaining a feasible schedule while satisfying different temporal requirements. In safety-critical applications, this schedule is generated offline. This article explores different integer linear programming techniques (ILP) to schedule uniprocessor hard real-time systems. The goal is to efficiently obtain a static schedule for periodic tasks and partitioned systems where temporal and spatial isolation is crucial. The advantage of the proposed ILP techniques is the possibility of choosing the optimization criteria so that deadlines are met and better performance quality is achieved. The drawback is the time spent finding an optimal solution. We propose an ILP method that reduces by 70% the time needed to obtain an optimal solution compared to basic approaches. This method is called the rolling task MILP approach and the optimization problem is addressed task by task. Experimental results show that our approach also achieves better results than heuristics when trying to reduce temporal parameters such as response times, context switches, and jitter. This makes our solution suitable for control systems and other applications.

Summary: We investigate static scheduling of taskgraphs onto parallel machines where the frequency of processors can be scaled at runtime. Given a deadline until which execution of the resulting schedule must be completed, we aim at minimizing the energy consumed by the parallel processors during execution. We present optimal and heuristic solutions to this problem and partial problems. We quantify the increase in energy consumption when switching from a globally optimal solution via a combination of optimal partial solutions to heuristic solutions. We find that, on our set of benchmark taskgraphs, the increase is 32.56% on average for a combination of heuristic solutions and thus tolerable. [ABSTRACT FROM AUTHOR]

This paper presents a multi-stage multi-objective evolutionary approach (MS-MOEA) for allocating parallel computations on multi-core processors by joint optimizing performance (P), energy (E), and temperature (T). Evolutionary techniques have been shown to be effective for solving optimization problems, including our own previous work on solving the PET -optimized scheduling (PETOS) problem. There have long been a great many debates and rivalries between various evolutionary approaches, such as the SPEA or NSGA, with regard to their relative matters. The novelty of the proposed MS-MOEA approach is its amalgamation of the basic evolutionary algorithms that are already shown to be highly effective, thereby creating a niche of these techniques. The niche takes advantages of the strengths of each baseline technique for achieving additional enhancement in the precision of the optimization. We propose six multi-stage hybrids, each designed with either niched fitness assignment strategy, or combining populations from multiple MOEAs , or incorporating the problem knowledge into the conventional technique. The experimental results measure the quality of resulting Pareto fronts and demonstrate that the proposed MS-MOEAs yield better optimization for the PETOS problem in achieving three-objective in parallel task-to-core mapping. [ABSTRACT FROM AUTHOR]

Efficient scheduling is critical for achieving improved performance of distributed applications where an application is to be considered as a group of interrelated tasks and represented by a task graph. In this work, we present a clustering-based scheduling algorithm called effective critical path (ECP) to schedule precedence constrained tasks on multiprocessor computing systems. The main aim of the algorithm is to minimize the schedule length of the given application. It uses the concept of edge zeroing on the critical path of the task graph for clustering the tasks of an application. An experimental analysis is performed using random task graphs and the task graphs derived from the real-world applications such as Gaussian Elimination, fast Fourier transform and systolic array. The results illustrate that the ECP algorithm gives better performance than the previous algorithms, considered herein, in terms of the average normalized schedule length and average speedup. [ABSTRACT FROM AUTHOR]

Cloud computing is a popular and widely adopted computing platform for the execution of scientific workflows as it provides flexible infrastructure and offers access to collection of autonomous heterogeneous resources. Effective scheduling of computationally complex workflows which contain many interconnected tasks is a complex problem and becomes more challenging in cloud environment. Optimal solutions can be obtained by considering not only the heterogeneity of computation costs involved, but also by taking into account the communication costs among the tasks in a way that schedule length of the application is reduced. In this paper, we propose a list scheduling heuristic, namely minimal optimistic processing time (MOPT), with optimized duplication approach. The additional feature is introduced for the entry task and is applied only in scenarios in which duplication is more practical and effective. The prioritization phase of the proposed work is based on an optimistic processing time matrix that is used for ranking of the tasks. The algorithm has same time complexity as state-of-the-art existing algorithms, but notable improvements are acquired in terms of makespan and other performance evaluation parameters. Extensive experimental analysis of the proposed algorithm is carried out using synthesized graphs and graphs from the real-world applications. The results prove that MOPT achieves quality schedules with reduced makespans. As communication cost among the tasks grows higher, performance of the proposed algorithm becomes more effective, thus providing the evidence that the MOPT algorithm is well-suited for communication-intensive applications. [ABSTRACT FROM AUTHOR]

• We present a compiler capable of transforming code to be suitable for predictable execution and real-time scheduling. The compiler generates programs that adhere to the Predictable Execution Model (PREM). • We shed light on compiler optimizations for prefetching based systems, and their impact on the ARM Cortex-A57. • We extend the state-of-the-art in scheduling heuristics to support multiple so called take-give resources, and are able to solve complex scheduling problems, infeasible for optimal solvers, in a few seconds. The heuristics create schedules that are close (about 10%) to the optimal schedule. • We provide insights on the effects of memory contention in MPSoC systems, and how active memory scheduling can greatly reduce the pessimism in worst-case execution time and scheduling jitter in real-time systems. Many applications require both high performance and predictable timing. High-performance can be provided by COTS Multi-Core System on Chips (MPSoC), however, as cores in these systems share main memory, they are susceptible to interference from each other, which is a problem for timing predictability. We achieve predictability on multi-cores by employing the predictable execution model (PREM), which splits execution into a sequence of memory and compute phases, and schedules these such that only a single core is executing a memory phase at a time. We present a toolchain consisting of a compiler and a scheduling tool. Our compiler uses region and loop based analysis and performs tiling to transform application code into PREM-compliant binaries. In addition to enabling predictable execution, the compiler transformation optimizes accesses to the shared main memory. The scheduling tool uses a state-of-the-art heuristic algorithm and is able to schedule industrial-size instances. For smaller instances, we compare the results of the algorithm with optimal solutions found by solving an integer linear programming model. Furthermore, we solve the problem of scheduling execution on multiple cores while preventing interference of memory phases. We evaluate our toolchain on Advanced Driver Assistance System (ADAS) application workloads running on an NVIDIA Tegra X1 embedded system-on-chip (SoC). The results show that our approach maintains similar average performance to the original (unmodified) program code and execution, while reducing variance of completion times by a factor of 9 with the identified optimal solutions and by a factor of 5 with schedules generated by our heuristic scheduler. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Guangxi Normal University - Natural Science Edition is the property of Gai Kan Bian Wei Hui and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Copyright of SDU Journal of Engineering Sciences & Design / Mühendislik Bilimleri ve Tasarım Dergisi is the property of Journal of Engineering Sciences & Design and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Scheduling of parallel modules of an application may produce a significant impact on the performance. The problem of finding optimal schedule is, however, NP-complete. The diversity of the processing elements adds to the complexity that is addressed by presenting heuristic algorithms. This paper presents a novel heuristic Relative Latency-based Scheduling (RLS) for producing schedules for heterogeneous systems. The suggested approach makes use of processing capabilities of the existing processors for diverse number of successors in a task graph while making scheduling decisions. The experiments have been performed on a large number of graphs using different topologies including fork-join, Laplace equation solver, Cholesky decomposition and random graphs. The RLS variants produce better results with a significant difference in schedule length as compared to the well-known HEFT and LMT strategies used for scheduling heterogeneous systems. [ABSTRACT FROM AUTHOR]

A novel task scheduling algorithm called Merge Tasks and Predict Earliest Finish Time (MTPEFT) has been proposed for static task scheduling in a heterogeneous computing environment. The algorithm merges tasks satisfying constraints and assigns the best processor for the node that has at least one immediate successor as the critical node, thereby effectively reducing the schedule length without increasing the algorithm time complexity. Experiments regarding aspects of randomly generated graphs and real-world application graphs are performed, and comparisons are made based on the scheduling length ratio, robustness and frequency of the best result. The results show that the MTPEFT algorithm outperforms the PEFT, CPOP and HEFT algorithms in terms of the schedule length ratio, frequency of the best result and robustness while maintaining the same time complexity. [ABSTRACT FROM AUTHOR]

This paper presents a novel list-based scheduling algorithm called Improved Predict Earliest Finish Time for static task scheduling in a heterogeneous computing environment. The algorithm calculates the task priority with a pessimistic cost table, implements the feature prediction with a critical node cost table, and assigns the best processor for the node that has at least 1 immediate successor as the critical node, thereby effectively reducing the schedule makespan without increasing the algorithm time complexity. Experiments regarding aspects of randomly generated graphs and real-world application graphs are performed, and comparisons are made based on the scheduling length ratio, robustness, and frequency of the best result. The results demonstrate that the Improved Predict Earliest Finish Time algorithm outperforms the Predict Earliest Finish Time and Heterogeneous Earliest Finish Time algorithms in terms of the schedule length ratio, frequency of the best result, and robustness while maintaining the same time complexity. [ABSTRACT FROM AUTHOR]

The Controller Area Network (CAN) has become a de-facto communication protocol in automation systems over the last three decades. Some CAN networks now employ TDMA-based communication in order to help meet real-time constraints. Whilst this form of media access control brings several timeliness benefits, studies have also illustrated negative effects on transmission reliability; duplicated message instances can help to increase this reliability. In this paper a transmission window technique for CAN is proposed. A bounded amount of re-transmission is allowed for each message within this window, which can in many cases provides increased reliability in the presence of errors or bursts of errors. A probabilistic analysis of transmission windows is presented and used to develop a simple algorithm for calculating the optimal window size to achieve a specified statistical guarantee of message delivery. Stochastic simulations along with computational and empirical results are presented which validate the analysis, and indicate that in many circumstances the technique can potentially reduce the amount of bandwidth needed for specified reliability levels when compared to the use of message duplicates. Suggestions are also made to help increase the reliability of message duplications in error burst environments. [ABSTRACT FROM AUTHOR]

This paper proposes a multi-objective evolutionary algorithm (MOEA)-based task scheduling approach for determining Pareto optimal solutions with simultaneous optimization of performance (P), energy (E ), and temperature (T). Our algorithm includes problem-specific solution encoding, determining the initial population of the solution space, and the genetic operators that collectively work on generating efficient solutions in fast turnaround time. Multiple schedules offer a diverse range of values for makespan, energy consumed, and peak temperature and thus present an efficient way of identifying trade-offs among the desired objectives, for a given application and machine pair. We also present a methodology for selecting one solution from the Pareto front given the user's preference. The proposed algorithm for scheduling tasks to cores achieves three-way optimization with fast turnaround time. The proposed algorithm is advantageous because it reduces both energy and temperature together rather than in isolation. We evaluate the proposed algorithm using implementation and simulation, and compare it with integer linear programming as well as with other scheduling algorithms that are energy- or thermal-aware. The time complexity of the proposed scheme is considerably better than the compared algorithms. [ABSTRACT FROM PUBLISHER]

Efficient application scheduling algorithms are important for obtaining high performance in heterogeneous computing systems. In this paper, we present a novel list-based scheduling algorithm called Predict Earliest Finish Time (PEFT) for heterogeneous computing systems. The algorithm has the same time complexity as the state-of-the-art algorithm for the same purpose, that is, $(O(v^2.p))$ for $(v)$ tasks and $(p)$ processors, but offers significant makespan improvements by introducing a look-ahead feature without increasing the time complexity associated with computation of an optimistic cost table (OCT). The calculated value is an optimistic cost because processor availability is not considered in the computation. Our algorithm is only based on an OCT that is used to rank tasks and for processor selection. The analysis and experiments based on randomly generated graphs with various characteristics and graphs of real-world applications show that the PEFT algorithm outperforms the state-of-the-art list-based algorithms for heterogeneous systems in terms of schedule length ratio, efficiency, and frequency of best results. [ABSTRACT FROM AUTHOR]

Multi‐processor system on chip (MPSoC) consists of multiple cores communicating via an on‐chip communication backplane. An application to be executed on an MPSoC is represented using a task graph where a node represents an operation to be scheduled on a core and the edges represent the communication between these operations. Typically task graph scheduling on MPSoC is done statically during hardware–software co‐design, based on estimated execution times. Static scheduling makes a program non‐portable, hence dynamic scheduling is preferred. In this study, the authors present hardware‐based dynamic feedback‐driven task rescheduling heuristic that executes in real time. This task scheduling heuristic is based on the observation that during the course of execution, an application goes through a phase where a sub‐graph (phase graph) of the application task graph repeatedly executes for a very large number of times. The proposed approach is iterative, where the schedule length of a phase graph converges to a smaller value in subsequent iterations. Experimental results show (i) real‐time scheduling can be performed using proposed game theoretic approach which converges to a minimum in fewer than 100 iterations (ii) reducing the schedule length ranging 3–16% as compared with greedy heuristic. [ABSTRACT FROM AUTHOR]

Abstract: This paper has two complementary focuses. The first is the system design and algorithmic development for air traffic control (ATC) using an associative SIMD processor (AP). The second is the comparison of this implementation with a multiprocessor implementation and the implications of these comparisons. This paper demonstrates how one application, ATC, can more easily, more simply, and more efficiently be implemented on an AP than is generally possible on other types of traditional hardware. The AP implementation of ATC will take advantage of its deterministic hardware to use static scheduling. The software will be dramatically smaller and cheaper to create and maintain. Likewise, a large AP system will be considerably simpler and cheaper than the MIMD hardware currently used. While APs were used for ATC-type applications earlier, these are no longer available. We use a ClearSpeed CSX600 accelerator to emulate the AP solutions of ATC on an ATC prototype consisting of eight data-intensive ATC real-time tasks. Its performance is compared with an 8-core multiprocessor (MP) using OpenMP. Our extensive experiments show that the AP implementation meets all deadlines while the MP will regularly miss a large number of deadlines. The AP code will be similar in size to sequential code for the same tasks and will avoid all of the additional support software needed with an MP to handle dynamic scheduling, load balancing, shared resource management, race conditions, false sharing, etc. At this point, essentially only MIMD systems are built. Many of the advantages of using an AP to solve an ATC problem would carry over to other applications. AP solutions for a wide variety of applications will be cited in this paper. Applications that involve a high degree of data parallelism such as database management, text processing, image processing, graph processing, bioinformatics, weather modeling, managing UAS (Unmanned Aircraft Systems or drones) etc., are good candidates for AP solutions. This raises the issue of whether we should routinely consider using non-multiprocessor hardware like the AP for applications where substantially simpler software solutions will normally exist. It also raises the question of whether the use of both AP and MIMD hardware in a single hetergeneous system could provide more versatility and efficiency. Either the AP or MIMD could serve as the primary system, but could hand off jobs it could not handle efficiently to the other system. [Copyright &y& Elsevier]

Abstract: A complex computing problem may be efficiently solved on a system with multiple processing elements by dividing its implementation code into several tasks or modules that execute in parallel. The modules may then be assigned to and scheduled on the processing elements so that the total execution time is minimum. Finding an optimal schedule for parallel programs is a non-trivial task and is considered to be NP-complete. For heterogeneous systems having processors with different characteristics, most of the scheduling algorithms use greedy approach to assign processors to the modules. This paper suggests a novel approach called constrained earliest finish time (CEFT) to provide better schedules for heterogeneous systems using the concept of the constrained critical paths (CCPs). In contrast to other approaches used for heterogeneous systems, the CEFT strategy takes into account a broader view of the input task graph. Furthermore, the statically generated CCPs may be efficiently scheduled in comparison with other approaches. The experimentation results show that the CEFT scheduling strategy outperforms the well-known HEFT, DLS and LMT strategies by producing shorter schedules for a diverse collection of task graphs. [Copyright &y& Elsevier]

In this paper, we focus on the problem of scheduling a collection of similar task graphs on a heterogeneous platform, when the task graph is an intree. We rely on steady-state scheduling techniques, and aim at optimizing the throughput of the system. Contrarily to previous studies, we concentrate on practical aspects of steady-state scheduling, when dealing with a collection (or batch) of limited size. We focus here on two optimizations. The first one consists in reducing the processing time of each task graph, thus making steady-state scheduling applicable to smaller batches. The second one consists in degrading a little the optimal-throughput solution to get a simpler solution, more efficient on small batches. We present our optimizations in details, and show that they both help to overcome the limitation of steady-state scheduling: our simulations show that we are able to reach a better efficiency on small batches, to reduce the size of the buffers, and to significantly decrease the processing time of a single task graph (latency). [ABSTRACT FROM AUTHOR]

Abstract: This paper proposes the Makespan and Reliability Cost Driven (MRCD) heuristic, a static scheduling strategy for heterogeneous distributed systems that not only minimizes the makespan, but also maximizes the reliability of the application. The MRCD scheduling decisions are guided by a weighted function that considers both objectives simultaneously, instead of prioritizing one of them. This work also introduces a classification of the solutions produced by weighted bi-objective schedulers to aid users to tune the weighting function such that an appropriate solution can be selected in accordance with their needs. In comparison with the related work, MRCD produced schedules with makespans that were significantly better then those produced by the other strategies at expense of an insignificant deterioration in reliability. [Copyright &y& Elsevier]

Large and dynamic computational Grids, generally known as wide-area Grids, are characterized by a large availability, heterogene- ity on computational resources, and high vari- ability on their status during the time. Such Grid infrastructures require appropriate schedule mechanisms in order to satisfy the application performance requirements (QoS). In this paper we propose a launch-time heuristics to schedule component-based parallel applications on such kind of Grid. The goal of the proposed heuristics is threefold: to meet the minimal task computation- al requirement, to maximize the throughput between communicating tasks, and to evaluate on-the-fly the resource availability to minimize the aging effect on the resources state. We evaluate the proposed heuristics by simulations applying it to a suite of task graphs and Grid platforms randomly generated. Moreover, a further test was conducted to schedule a real application on a real Grid. Experimental results shown that the proposed solution can be a viable one. [ABSTRACT FROM AUTHOR]