Meta-scheduling

Meta-scheduling or Super scheduling is a computer software technique of optimizing computational workloads by combining an organization's multiple Distributed Resource Managers into a single aggregated view, allowing batch jobs to be directed to the best location for execution.

Meta-Scheduling for MPSoCs

Meta-scheduling technique is a solution for scheduling a set of depended or independent faults with different scenarios that are mapping and modeling in an event-tree. It can be used as a dynamic or static scheduling method. In this work, we use it for static scheduling on adaptive TT MPSoC systems.

Meta-scheduling can be described as a technique to optimize the computational workload by combining and organizing multiple distributed resources in an integrated view. In other words, it is an extended data-flow model and quasi-static scheduling for dynamic behaviour changes.

Scenario-Based Meta-Scheduling (SBMeS)

Scenario-based and multi-mode approaches are essential techniques in embedded-systems, e.g., design space exploration for MPSoCs and reconfigurable systems .

Optimization techniques for the generation of schedule graphs supporting such a SBMeS approach have been developed and implemented.

SBMeS  can promise better performance by reducing dynamic scheduling overhead and recovering from faults.

Abstract of SBMeS

Complex electronic systems are used in many safety-critical applications (e.g. aerospace, automotive, nuclear power plants), for which certification standards prescribe the use of safe construction methods and tools. Scenario-based meta-planning (SBMeS) is a way to control the complexity of adaptive systems using predictable behavior patterns that are determined by static planning algorithms. SBMeS is very important for the Internet of Things (IoT) and real-time systems. Real-time systems are often based on time-controlled operating systems and networks and can benefit from SBMeS for more energy efficiency, flexibility and reliability.

This paper introduces an SBMeS algorithm that calculates an individual schedule for each relevant combination of events, such as dynamic slip events. The dynamic frequency scaling of processor cores and routers serves to improve energy efficiency while maintaining the correctness of time-controlled calculation and communication activities (e.g. collision avoidance, real-time capability). With the help of models of applications, platforms and contexts, planning tools are used to prepare reactions to events and to generate meta-plans.

In the course of this work, techniques and tools are developed to plan a series of calculations and messages on network-on-chip (NoC) architectures, with the aim of minimizing the total energy consumption taking into account time requirements and adjustable frequencies. The algorithm supports safety-critical adaptive time-controlled systems and can cover the requirements regarding fault tolerance. It can also help respond to malfunctions by restoring the system. We also present a meta planning tool (MeSViz) for the visualization of time-controlled plans.

We experimentally analyze and evaluate the energy efficiency of the plans for processor cores and routers. In addition, the time behavior is assessed analytically on the basis of static and dynamic slip events. Simulation results show that our dynamic slip algorithm results in an average energy saving of 64.4% in a single schedule and 41.61% energy saving for NoCs. Compressing the schedules can reduce memory usage by more than 61%.

Implementations

The following is a partial list of noteworthy open source and commercial meta-schedulers currently available.

• GridWay by the Globus Alliance
• Community Scheduler Framework by Platform Computing & Jilin University
• MP Synergy by United Devices
• Moab Cluster Suite and Maui Cluster scheduler from Adaptive Computing
• DIOGENES (DIstributed Optimal GENEtic algorithm for grid applications Scheduling, started project)
• SynfiniWay's meta-scheduler.
• MeS is designed to generate schedules for anticipated changes of scenarios by Dr.-Ing. Babak Sorkhpour & Prof. Dr.-Ing.Roman Obermaisser in Chair for Embedded Systems in university of Siegen for Energy-Efficient, Robust and Adaptive Time-Triggered Systems (multi-core architectures with Networks-on-chip (NoC)) .

References

• Schopf, Jennifer (2002). "A General Architecture for Scheduling on the Grid" (PDF). Argonne National Laboratory. Archived from the original (PDF) on 2008-09-24.
• B. Sorkhpour and R. Obermaisser. "MeSViz: Visualizing Scenario-based Meta-Schedules for Adaptive Time-Triggered Systems.". in AmE 2018-Automotive meets Electronics; 9th GMM-Symposium, 2018, pp. 1–6
• B. Sorkhpour, R. Obermaisser and A. Murshed, "Meta-Scheduling Techniques for Energy-Efficient, Robust and Adaptive Time-Triggered Systems," in Knowledge-Based Engineering and Innovation (KBEI), 2017 IEEE 4th International Conference on, Tehran, 2017.
• B. Sorkhpour, O. Roman, and Y. Bebawy, Eds., Optimization of Frequency-Scaling in Time-Triggered Multi-Core Architectures using Scenario-Based Meta-Scheduling: “in AmE 2019-Automotive meets Electronics; 10th GMM-Symposium VDE, 2019
• B. Sorkhpour. "Scenario-based meta-scheduling for energy-efficient, robust and adaptive time-triggered multi-core architectures", University of Siegen, Doctoral thesis, July 2019.

External links

• Super Scheduler project by the Asia-Pacific Science Technology Center.
• Meta-Scheduling Techniques for Energy-Efficient by Dr.-Ing. Babak sorkhpour.