Jump to content

Meta-scheduling

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Qwerfjkl (talk | contribs) at 18:27, 18 December 2021 (Debolded section header(s) (CW Error #44) (via Bandersnatch)). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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) for MPSoCs and NoCs

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

Scenario-based meta-scheduling (SBMeS) general model

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[disambiguation needed].

This topic 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.

Figure 27. Meta-visualization of an event
Schedule Gantt map
Figure 24 shows the results of each event in each 〖SM〗_x.

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%.

Figure 14.The effect of TSDF on tasks et(t) and core fault

Introduction

Many algorithms, methods, and techniques are proposed for scheduling distributed embedded real-time systems. Schedulability analysis is a primary component of real-time systems scheduling. In particular, the real-time system depends on static schedules that define the use of computational and communication resources based on a global time base. In [1], Kopetz explains how the correctness of a real-time system also depends on the timing of the computational results.

A group of tasks and messages is said to be schedulable with a certain scheduling method if enough resources (e.g., cores, routers) are available to execute all these tasks and transmit all messages before their deadlines. Each real-time task and message is assigned a deadline, which is defined in an application model (AM). In the time-triggered paradigm [1] of real-time scheduling, processes are controlled and scheduled by the progression of time only, and a schedule is designed for the total duration of a system’s execution. One of the typical techniques used for time-triggered systems (TTS) is the schedule table. These are easy to verify and thus favorable in safety-critical systems that must be certified [2].

Scenario-based scheduling can support adaptive TTS by decreasing dependence on expensive and complex hardware, dynamic computational costs, and equipment vendor solutions and by replacing or reducing componential hardware functions with scheduling implementations on low-cost multi-purpose devices.  

Energy-efficiency, energy-management, energy-saving, and energy reduction methods and algorithms are used in many applications (e.g., mobile phones, smart TVs), while their applicability in safety-critical systems is restricted.

Network-on-chip (NoC) technology contributes significantly to the overall energy consumption of an MPSoC, and we introduce a meta-scheduler (MeS) for SBMeS that supports dynamic voltage and frequency scaling (DVFS) in time-triggered NoCs and MPSoCs.

Some of the results and methods (e.g., meta-scheduling) described in this thesis are also used in the SAFEPOWER project platform and documents [3].

Motivation

Embedded systems are pervasive in modern safety-relevant systems. They range from automotive electronics to aerospace flight control and multi-purpose complex aerospace vehicle systems; and many premium carmakers plan to invest heavily in e-cars, which significantly depend on embedded systems [4].

However, in the era of the IoT, the minimizing of power consumption is a primary concern for system designers. Scheduling optimization helps engineers and system designers to increase energy-efficiency and improve the behavior of a system [5].

Many embedded systems are based on time-triggered networks (TTN) and used in safety-critical applications (e.g., healthcare, e-cars, space, military, nuclear stations, and aircraft). Efficient scheduling algorithms and methods are required for such systems (e.g., mathematical programming, artificial intelligence, scheduling heuristics, neighborhood search [6]), where failure has severe consequences [7]. “Scheduling limited resources among requesting entities is one of the most challenging problems in computer science [8]”.

In SBMeS systems, the MeS generates specific schedules for each situation triggered by relevant events (e.g., fault and slack). To evaluate schedules, system designers must design, model, compare, understand, debug, and simulate the schedules. These are the important challenges for SBMeS. Adapting to significant events within the computer system or in the environment is another challenge in TTS.

NoCs have emerged in recent years to improve performance and solve the challenges of existing interconnect solutions for many cores. NoCs provide a scalable and high-performance communication architecture for complex integrated systems.

Moreover, this solution tackles the challenge of power consumption, which is one of the essential concerns of complex embedded systems. Research findings indicate that the communication interconnect can consume up to of the power required in an MPSoC [9]. This significant power consumption calls for low-power techniques for NoCs.

The output of most schedulers is in text format, making it difficult to identify problems, especially when a large number of schedules are generated and must be debugged or compared [10].

This challenge is intangible when using text logs with large amounts of data or abstract graphics that absorb the engineer’s mental resources. The majority of the schedule visualizers are designed to illustrate a single schedule and cannot cover multiple schedules in one scope. However, the generation of schedules via scenario-based scheduling solutions and algorithms for real-time multi-processor systems is gaining importance [10]. The MeS approach is to add dynamic actions by computing several valid schedules, dynamically chosen based on the system status [11].

SBMeS is a scheduling technique [12, 13], which predicts, controls, and models the circumstance events in safety-critical systems. MPSoC systems typically represent one of the most power consuming components of embedded systems, and most research focuses on reducing power and energy consumption of computational cores. MPSoCs typically support the scaling of frequency and voltage (e.g., DVFS), as well as multiple sleep states for cores. However, frequency tuning for both cores and routers in multi-core architectures (e.g., NoC) has so far been an open research challenge.

In addition, energy efficiency and energy management are becoming important issues in real-time systems design [14]. One NoC design goal has emerged in the embedded and real-time systems market as a means of reducing and managing power consumption [15].

To deploy TT NoCs, static scheduling of application workloads is a prerequisite. In addition to ensuring application requirements, such as precedence constraints and deadlines, energy consumption is influenced significantly by task allocations and communication/execution plans [14].

Finding the optimum schedules for maximum energy reduction is the goal of the scheduling techniques presented in this work. This will result in better task allocations and communication plans. The scheduling algorithm extends previous work (e.g., [12], [14], [16]), introducing an energy reduction scheduling method for TTS [17]. Energy reduction is achieved via DVFS by SBMeS, a widely used technique that provides the support to reduce energy consumption of embedded systems and multi-core architectures.

Energy-efficiency in DVFS is achieved by dynamically adjusting the voltage, frequency, and performance settings of the application. To achieve the full advantage of the slack that results from variations in task execution time, it is important to recalculate the frequency and voltage settings during these periods (i.e., online).

Energy-efficiency optimization uses dynamic frequency scaling, in which we can individually scale the frequency of each core and router. This algorithm is suitable for mixed-criticality [18] and safety-criticality [19] by supporting fault-tolerant [20] applications and adaptive systems. Compared to static slack (SS) scheduling techniques, our approach provides more energy efficiency and enhanced flexibility.

The frequency is tuned for each component (core or router) and is optimized depending on the task or message, regarding events and the system global time.

However, optimal voltage and frequency scaling algorithms are computationally expensive and complex, if used at runtime. Therefore, to overcome and reduce online complexity, we propose quasi-static scheduling [21] for frequency scaling, supporting TT  multi-core architectures. This method allows exploitation of dynamic slack (DS) and avoids energy dissipation due to online adaptation of the frequency settings.

Our method can support fault-tolerance and energy-efficiency, which are significant objectives in many safety-critical systems. Our algorithm considers the task execution times, message injection and transmission times, and possibilities of frequency changes and can schedule and map the tasks and messages to be executed before the corresponding deadlines [22].

Our SBMeS model optimizes the trade-off between reliability, fault-tolerance, and energy-efficiency to handle multiple tasks and message sets regarding events (i.e., based on frequency tuning and scaling inside cores and routers). We consider the impact of each event on other events (e.g., increasing or decreasing frequency) for better resource and energy management in the TTS.

We present scheduling techniques for attaining the optimal schedules for different events with maximum energy reduction, while meeting other functional and nonfunctional constraints. A corresponding optimization problem is formulated in IBM Ilog CPLEX, and the results indicate significant improvements in energy efficiency.

In the e-car area, safety is one of the most critical parameters; hence, the fault-tolerant scheduling method used in SBMeS can be applied in automotive systems to achieve greater safety.

In this work, slack occurrence is defined as an event. The required algorithm, methods, and scenarios are designed to support this event in improving energy-efficiency.

In many works, schedule results are explained by presenting the abstract text of the essential information (e.g., tasks, messages, makespan, deadlines, times).

A visualization of a schedule enables the engineers and system designers to easily perform sanity checks – checking and tracing the tasks, messages, makespan, nodes, and in SBMeS, the behavior and reactions for each scenario after an event. Although scheduling is an essential issue in TTS, embedded systems, and computer science, few visualization tools [8] are available to help engineers and scientists extend and develop more reliable scheduling algorithms, methods, and models [23]. Some visualization tools show only abstract schedules as graphical output and contain neither complete information nor detailed explanations of the events and the schedules (e.g., differences or changes) [7].

Comparing, understanding, and debugging thousands of schedules generated by SBMeS poses severe challenges for system designers, as discussed later in this work.

This work introduces a scenario-based tool, MeSViz – designed to support developers and engineers in evaluating scheduling algorithms, models, and methods for adaptive TTS. This tool can show event details and schedule changes and dependencies due to events. It visualizes schedules on four different layers: the first presenting individual schedules for each scenario, the second displaying multiple schedules for multi-scenario events, the third generating graphs, and the fourth showing energy and timing.

The novelty of SBMes

The novelty contributions of SBMes can be summarized as follows:

1.      Scheduling of TT communication and computational activities: The scheduling algorithm considers the task-execution times, message-transmission times and the possibilities of frequency changes. Our scheduler supports the mapping and scheduling of both tasks and messages to multi-core architectures, for minimizing the total energy consumption regarding the timing and frequencies of cores, routers and slack distribution.

2.      DVFS in time-triggered architecture: This work enables the use of DVFS for both communication and computation resources for MPSoCs, in order to attain energy efficiency of TT multi-core architectures. Hence, it can extend energy efficiency optimisation of SBMeS for MPSoCs with time-triggered communication (TTC) not only providing frequency scaling of not only cores but also the NoC’s routers.

3.      The scheduling method for improved reliability and fault-tolerance: SBMeS can be used for automotive and safety-critical systems to achieve greater safety. In the e-car area, safety is one of the most critical parameters.

4.      Trade-off between fault-tolerance, reliability, and energy-efficiency: Our proposed model optimizes the trade-off between fault-tolerance, reliability, and energy-efficiency in SBMeS to handle multiple tasks and message sets regarding reliability [20] and energy-efficiency for adaptive TTS (i.e., base frequency tuning and scaling inside cores and routers).

5.     An optimal scheduling algorithm for energy efficiency: Our proposed optimization method establishes the minimum energy consumption for each slack event by mixed-integer quadratic programming (MIQP) equations. The MIQP model considers different parameters (e.g., cores, routers) and decision variables (e.g., slow-down factors of cores and routers) in the constraints and the objective function.

6.     Visualization of meta-schedules: Our MeSViz is proposed for specific visualization and evaluation of single and multi-schedules on MPSoCs.

7.     Memory optimization regarding schedules size: Delta scheduling is used to reduce and optimize memory usage of schedules and can store a significant number of schedules based on delta graph generator models [25], [16].

In contrast, our approach is an off-line static-scheduling algorithm for determining the optimal meta-schedules and dynamic frequency scaling in TT MPSoCs and NoCs for energy-efficiency[disambiguation needed] in safety-critical embedded systems. This work thus develops a DS -reclamation technique to reduce static and dynamic energy consumption.

Implementations

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

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.

References of SBMeS

[1]   H. Kopetz, Real-time systems: design principles for distributed embedded applications: Springer Science & Business Media, 2011.

[2]   J. Theis, G. Fohler, and S. Baruah, “Schedule table generation for time-triggered mixed criticality systems,” Proc. WMC, RTSS, pp. 79–84, 2013.

[3]   Safepower, D3.8 User guide of the heterogeneous MPSoC design. [Online] Available: http://safepower-project.eu/wp-content/uploads/2019/01/D3.8-User_guide_of_the_heterogeneous_MPSoC_design_v1-0_final.pdf.

[4]   DW BUSINESS, BMW increases R&D spending on e-cars, autonomous vehicles.

[5]   S. R. Sakhare and M. S. Ali, “Genetic algorithm based adaptive scheduling algorithm for real time operating systems,” International Journal of Embedded Systems and Applications (IJESA), vol. 2, no. 3, pp. 91–97, 2012.

[6]   R. Obermaisser, Ed., Time-triggered communication. Boca Raton, FL: CRC Press, 2012.

[7]   P. Munk, “Visualization of scheduling in real-time embedded systems,” University of Stuttgart, Institute of Software Technology, Department of Programming Languages and Compilers, 20103.

[8]   S. Hunold, R. Hoffmann, and F. Suter, “Jedule: A Tool for Visualizing Schedules of Parallel Applications,” in 2010 International Conference on Parallel Processing Workshops (ICPPW), San Diego, CA, USA, pp. 169–178.

[9]   H. Wang, L.-S. Peh, and S. Malik, “Power-driven design of router microarchitectures in on-chip networks,” in 36th International symposium on microarchitecture, San Diego, CA, USA, 2003, pp. 105–116.

[10] 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.

[11] A. C. Persya and T. R. G. Nair, “Model based design of super schedulers managing catastrophic scenario in hard real time systems,” in 2013 International Conference on Information Communication and Embedded Systems (ICICES), Chennai, 2013, pp. 1149–1155.

[12] B. Sorkhpour, O. Roman, and Y. Bebawy, Eds., Optimization of Frequency-Scaling in Time-Triggered Multi-Core Architectures using Scenario-Based Meta-Scheduling: VDE, 2019.

[13] B. Sorkhpour, A. Murshed, and R. Obermaisser, “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, 2017, pp. 143–150.

[14] J. Huang, C. Buckl, A. Raabe, and A. Knoll, “Energy-Aware Task Allocation for Network-on-Chip Based Heterogeneous Multiprocessor Systems,” in 2011 19th International Euromicro Conference on Parallel, Distributed and Network-Based Processing, Ayia Napa, Cyprus, 2011, pp. 447–454.

[15] S. Prabhu, B. Grot, P. Gratz, and J. Hu, “Ocin tsim-DVFS aware simulator for NoCs,” Proc. SAW, vol. 1, 2010.

[16] Roman Obermaisser et al., “Adaptive Time-Triggered Multi-Core Architecture,” Designs, vol. 3, no. 1, p. 7, 2019.

[17] H. Kopetz, Ed., Real-Time Systems: Design Principles for Distributed Embedded Applications (Real-Time Systems Series) // Real-time systems: Design principles for distributed embedded applications, 2nd ed. New York: Springer, 2011.

[18] F. Guan, L. Peng, L. Perneel, H. Fayyad-Kazan, and M. Timmerman, “A Design That Incorporates Adaptive Reservation into Mixed-Criticality Systems,” Scientific Programming, vol. 2017, 2017.

[19] Y. Lin, Y.-l. Zhou, S.-t. Fan, and Y.-m. Jia, “Analysis on Time Triggered Flexible Scheduling with Safety-Critical System,” in Chinese Intelligent Systems Conference, 2017, pp. 495–504.

[20] IEEE, “TTP - A Time-Triggered Protocol For Fault-tolerant Real-time System - Fault-Tolerant Computing, 1993. FTCS-23. Digest of Papers., The Twenty-Third International Symposi,”

[21] J. Cortadella, A. Kondratyev, L. Lavagno, C. Passerone, and Y. Watanabe, “Quasi-static scheduling of independent tasks for reactive systems,” IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 24, no. 10, pp. 1492–1514, 2005.

[22] R. Rajaei, S. Hessabi, and B. V. Vahdat, “An energy-aware methodology for mapping and scheduling of concurrent applications in MPSOC architectures,” in Electrical Engineering (ICEE), 2011 19th Iranian Conference on, 2011, pp. 1–6.

[23] A. Menna, “Allocation, Assignment and Scheduling for Multi-processor System on Chip,” PhD, Universit ´e des Sciences et Technologies de Lille, 2006.

[24] A. Murshed, “Scheduling Event-Triggered and Time-Triggered Applications with Optimal Reliability and Predictability on Networked Multi-Core Chips,”

[25] A. Maleki, H. Ahmadian, and R. Obermaisser, “Fault-Tolerant and Energy-Efficient Communication in Mixed-Criticality Networks-on-Chips,” in 2018 IEEE Nordic Circuits and Systems Conference (NORCAS): NORCHIP and International Symposium of System-on-Chip (SoC), 2018, pp. 1–7.

[26] P. Eitschberger, S. Holmbacka, and J. Keller, “Trade-Off Between Performance, Fault Tolerance and Energy Consumption in Duplication-Based Taskgraph Scheduling,” in Architecture of Computing Systems – ARCS 2018.

[27] R. Lent, “Grid Scheduling with Makespan and Energy-Based Goals,” Journal of Grid Computing, vol. 13, no. 4, pp. 527–546, 2015.

[28] P. Eitschberger, “Energy-efficient and Fault-tolerant Scheduling for Manycores and Grids,” Fakultät für Mathematik und Informatik, FernUniversität in Hagen, Hagen, 2017.

[29] A. Murshed, “Scheduling event-triggered and time-triggered applications with optimal reliability and predictability on networked multi-core chips,” Dissertation, Embedded Systems, Universität Siegen, Siegen, 2018.

[30] E. Dubrova, Fault-Tolerant Design. New York, NY: Springer; Imprint, 2013.

[31] A. Avizienis, J.-C. Laprie, B. Randell, and others, Fundamental concepts of dependability: University of Newcastle upon Tyne, Computing Science, 2001.

[32] I. Bate, A. Burns, and R. I. Davis, “A Bailout Protocol for Mixed Criticality Systems,” in 2015 27th Euromicro Conference on Real-Time Systems: ECRTS 2015 : proceedings, Lund, Sweden, 2015, pp. 259–268.

[33] A. Burns and R. Davis, “Mixed criticality systems-a review,” Department of Computer Science, University of York, Tech. Rep, pp. 1–69, 2013.

[34] B. Hu et al., “FFOB: efficient online mode-switch procrastination in mixed-criticality systems,” Real-Time Syst, vol. 79, no. 1, p. 39, 2018.

[35] H. Isakovic and R. Grosu, “A Mixed-Criticality Integration in Cyber-Physical Systems: A Heterogeneous Time-Triggered Architecture on a Hybrid SoC Platform,” in Computer Systems and Software Engineering: Concepts, Methodologies, Tools, and Applications: IGI Global, 2018, pp. 1153–1178.

[36] 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.

[37] B. Hu, “Schedulability Analysis of General Task Model and Demand Aware Scheduling in Mixed-Criticality Systems,” Technische Universität München.

[38] H. Ahmadian, F. Nekouei, and R. Obermaisser, “Fault recovery and adaptation in time-triggered Networks-on-Chips for mixed-criticality systems,” in 12th International Symposium on Reconfigurable Communication-centric Systems-on-Chip, (ReCoSoC 2017): July 12-14, 2017, Madrid, Spain : proceedings, Madrid, Spain, 2017, pp. 1–8.

[39] R. Trüb, G. Giannopoulou, A. Tretter, and L. Thiele, “Implementation of partitioned mixed-criticality scheduling on a multi-core platform,” ACM Transactions on Embedded Computing Systems (TECS), vol. 16, no. 5s, p. 122, 2017.

[40] C. Schöler, “Novel scheduling strategies for future NoC and MPSoC architectures,” 2017.

[41] M. I. Huse, “FlexRay Analysis, Configuration Parameter Estimation, and Adversaries,” NTNU.

[42] W. Steiner, “Synthesis of Static Communication Schedules for Mixed-Criticality Systems,” in 2011 14th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing workshops (ISORCW): 28-31 March 2011, Newport Beach, California, USA ; proceedings, Newport Beach, CA, USA, 2011, pp. 11–18.

[43] G. Marchetto, S. Tahir, and M. Grosso, “A blocking probability study for the aethereal network-on-chip,” in Proceedings of 2016 11th International Design & Test Symposium (IDT): December 18-20-2016, Hammamet, Tunisia, Hammamet, Tunisia, 2016, pp. 104–109.

[44] M. Ruff, “Evolution of local interconnect network (LIN) solutions,” in VTC2003-Fall Orlando: 2003 IEEE 58th Vehicular Technology Conference : proceedings : 6-9 October, 2003, Orlando, Florida, USA, Orlando, FL, USA, 2004, 3382-3389 Vol.5.

[45] R. B. Atitallah, S. Niar, A. Greiner, S. Meftali, and J. L. Dekeyser, “Estimating Energy Consumption for an MPSoC Architectural Exploration,” in Lecture Notes in Computer Science, Architecture of Computing Systems - ARCS 2006, W. Grass, B. Sick, and K. Waldschmidt, Eds., Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 298–310.

[46] U. U. Tariq, H. Wu, and S. Abd Ishak, “Energy-Aware Scheduling of Conditional Task Graphs on NoC-Based MPSoCs,” in Proceedings of the 51st Hawaii International Conference on System Sciences, 2018.

[47] Compiler-Directed Frequency and Voltage Scaling for a Multiple Clock Domain: ACM Press.

[48] A. B. Mehta, “Clock Domain Crossing (CDC) Verification,” in ASIC/SoC Functional Design Verification.

[49] Mecanismo de controle de QoS através de DFS em MPSOCS: Pontifícia Universidade Católica do Rio Grande do Sul; Porto Alegre, 2014.

[50] Marc Boyer, Benoît Dupont de Dinechin, Amaury Graillat, and Lionel Havet, “Computing Routes and Delay Bounds for the Network-on-Chip of the Kalray MPPA2 Processor,”

[51] B. D. de Dinechin and A. Graillat, “Feed-Forward Routing for the Wormhole Switching Network-on-Chip of the Kalray MPPA2 Processor,” in Proceedings of the 10th International Workshop on Network on Chip Architectures - NoCArc'17, Cambridge, MA, USA, 2017, pp. 1–6.

[52] KALRAY Corporation, Kalray’s MPPA network-on-chip. [Online] Available: http://www.kalrayinc.com/portfolio/processors/.

[53] I. Lee, J. Y. T. Leung, and S. H. Son, Handbook of real-time and embedded systems: CRC Press, 2007.

[54] Wikipedia, XtratuM - Wikipedia. [Online] Available: https://en.wikipedia.org/w/index.php?oldid=877711274. Accessed on: Feb. 11 2019.

[55] I. Ripoll et al., “Configuration and Scheduling tools for TSP systems based on XtratuM,” Data Systems In Aerospace (DASIA 2010), 2010.

[56] V. Brocal et al., “Xoncrete: a scheduling tool for partitioned real-time systems,” Embedded Real-Time Software and Systems, 2010.

[57] R. Jejurikar and R. Gupta, “Dynamic slack reclamation with procrastination scheduling in real-time embedded systems,” in Proceedings of the 42nd annual Design Automation Conference, 2005, pp. 111–116.

[58] H. Li, S. Bhunia, Y. Chen, T. N. Vijaykumar, and K. Roy, “Deterministic clock gating for microprocessor power reduction,” in The 9th international symposium on high-performance computer architecture, Anaheim, CA, USA, 2003, pp. 113–122.

[59] H. Matsutani, M. Koibuchi, H. Nakamura, and H. Amano, “Run-Time Power-Gating Techniques for Low-Power On-Chip Networks,” in Low Power Networks-on-Chip.

[60] P. W. Cook et al., “Power-aware microarchitecture: design and modeling challenges for next-generation microprocessors,” IEEE Micro, vol. 20, no. 6, pp. 26–44, 2000.

[61] W. Kim, J. Kim, and S. L. Min, “Dynamic voltage scaling algorithm for dynamic-priority hard real-time systems using slack time analysis,” in Design, Automation and Test in Europe Conference and Exhibition, 2002. Proceedings, 2002, pp. 788–794.

[62] D. M. Brooks et al., “Power-aware microarchitecture: Design and modeling challenges for next-generation microprocessors,” IEEE Micro, vol. 20, no. 6, pp. 26–44, 2000.

[63] S. Prabhu, Ocin_tsim - A DVFS Aware Simulator for NoC Design Space Exploration and Optimization. [College Station, Tex.]: [Texas A & M University], 2010.

[64] A. Bianco, P. Giaccone, and N. Li, “Exploiting Dynamic Voltage and Frequency Scaling in networks on chip,” in IEEE 13th International Conference on High Performance Switching and Routing (HPSR), 2012, Belgrade, Serbia, 2012, pp. 229–234.

[65] M. Caria, F. Carpio, A. Jukan, and M. Hoffmann, “Migration to energy efficient routers: Where to start?,” in IEEE International Conference on Communications (ICC), 2014: 10-14 June 2014, Sydney, Australia, Sydney, NSW, 2014, pp. 4300–4306.

[66] D. M. Brooks et al., “Power-aware microarchitecture: Design and modeling challenges for next-generation microprocessors,” IEEE Micro, vol. 20, no. 6, pp. 26–44, 2000.

[67] S. Chai, Y. Li, J. Wang, and C. Wu, “An energy-efficient scheduling algorithm for computation-intensive tasks on NoC-based MPSoCs,” Journal of Computational Information Systems, vol. 9, no. 5, pp. 1817–1826, 2013.

[68] P. K. Sharma, S. Biswas, and P. Mitra, “Energy efficient heuristic application mapping for 2-D mesh-based network-on-chip,” Microprocessors and Microsystems, vol. 64, pp. 88–100, 2019.

[69] H. M. Kamali, K. Z. Azar, and S. Hessabi, “DuCNoC: A High-Throughput FPGA-Based NoC Simulator Using Dual-Clock Lightweight Router Micro-Architecture,” IEEE Trans. Comput., vol. 67, no. 2, pp. 208–221, 2018.

[70] H. Farrokhbakht, H. M. Kamali, and S. Hessabi, “SMART,” in Proceedings of the Eleventh IEEE/ACM International Symposium on Networks-on-Chip - NOCS '17, Seoul, Republic of Korea, 2017, pp. 1–8.

[71] W. Hu, X. Tang, B. Xie, T. Chen, and D. Wang, “An Efficient Power-Aware Optimization for Task Scheduling on NoC-based Many-core System,” in 2010 10th IEEE International Conference on Computer and Information Technology, Bradford, United Kingdom, 2010, pp. 171–178.

[72] H. F. Sheikh and I. Ahmad, “Simultaneous optimization of performance, energy and temperature for DAG scheduling in multi-core processors,” in Green Computing Conference (IGCC), 2012 International, 2012, pp. 1–6.

[73] J. Hu and R. Marculescu, “Energy-aware communication and task scheduling for network-on-chip architectures under real-time constraints,” in Design, Automation and Test in Europe Conference and Exhibition, 2004. Proceedings, 2004, pp. 234–239.

[74] H. Bokhari, H. Javaid, M. Shafique, J. Henkel, and S. Parameswaran, “darkNoC,” in Proceedings of the 51st Annual Design Automation Conference, San Francisco, CA, USA, 2014, pp. 1–6.

[75] H. Aydin, R. Melhem, D. Mosse, and P. Mejia-Alvarez, “Dynamic and aggressive scheduling techniques for power-aware real-time systems,” in 22nd IEEE real-time systems symposium: (RTSS 2001), London, UK, 2001, pp. 95–105.

[76] R. Jejurikar and R. Gupta, “Dynamic slack reclamation with procrastination scheduling in real-time embedded systems,” in DAC 42, San Diego, California, USA, 2005, p. 111.

[77] G. Ma, L. Gu, and N. Li, “Scenario-Based Proactive Robust Optimization for Critical-Chain Project Scheduling,” J. Constr. Eng. Manage., vol. 141, no. 10, p. 4015030, 2015.

[78] H. K. Mondal and S. Deb, “Power-and performance-aware on-chip interconnection architectures for many-core systems,” IIIT-Delhi.

[79] J. Wang et al., “Designing Voltage-Frequency Island Aware Power-Efficient NoC through Slack Optimization,” in International Conference on Information Science and Applications (ICISA), 2014: 6-9 May 2014, Seoul, South Korea, Seoul, South Korea, 2014, pp. 1–4.

[80] K. Han, J.-J. Lee, J. Lee, W. Lee, and M. Pedram, “TEI-NoC: Optimizing Ultralow Power NoCs Exploiting the Temperature Effect Inversion,” IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 37, no. 2, pp. 458–471, 2018.

[81] D. Li and J. Wu, “Energy-efficient contention-aware application mapping and scheduling on NoC-based MPSoCs,” Journal of Parallel and Distributed Computing, vol. 96, pp. 1–11, 2016.

[82] W. Y. Lee, Y. W. Ko, H. Lee, and H. Kim, “Energy-efficient scheduling of a real-time task on dvfs-enabled multi-cores,” in Proceedings of the 2009 International Conference on Hybrid Information Technology, 2009, pp. 273–277.

[83] B. Sprunt, L. Sha, and J. Lehoczky, “Aperiodic task scheduling for Hard-Real-Time systems,” Real-Time Syst, vol. 1, no. 1, pp. 27–60, 1989.

[84] J. K. Strosnider, J. P. Lehoczky, and L. Sha, “The deferrable server algorithm for enhanced aperiodic responsiveness in hard real-time environments,” IEEE Trans. Comput., vol. 44, no. 1, pp. 73–91, 1995.

[85] N. Chatterjee, S. Paul, and S. Chattopadhyay, “Task mapping and scheduling for network-on-chip based multi-core platform with transient faults,” Journal of Systems Architecture, vol. 83, pp. 34–56, 2018.

[86] R. N. Mahapatra and W. Zhao, “An energy-efficient slack distribution technique for multimode distributed real-time embedded systems,” IEEE Trans. Parallel Distrib. Syst., vol. 16, no. 7, pp. 650–662, 2005.

[87] G. Avni, S. Guha, and G. Rodriguez-Navas, “Synthesizing time-triggered schedules for switched networks with faulty links,” in Proceedings of the 13th International Conference on Embedded Software, Pittsburgh, Pennsylvania, 2016, pp. 1–10.

[88] F. Benhamou, Principle and Practice of Constraint Programming - CP 2006: 12th International Conference, CP 2006, Nantes, France, September 25-29, 2006, Proceedings. Berlin Heidelberg: Springer-Verlag, 2006.

[89] Satisfiability Modulo Graph Theory for Task Mapping and Scheduling on Multiprocessor Systems, 2011.

[90] A. Murshed, R. Obermaisser, H. Ahmadian, and A. Khalifeh, “Scheduling and allocation of time-triggered and event-triggered services for multi-core processors with networks-on-a-chip,” pp. 1424–1431.

[91] F. Wang, C. Nicopoulos, X. Wu, Y. Xie, and N. Vijaykrishnan, “Variation-aware task allocation and scheduling for MPSoC,” in IEEE/ACM International Conference on Computer-Aided Design, 2007, San Jose, CA, USA, 2007, pp. 598–603.

[92] D. Mirzoyan, B. Akesson, and K. Goossens, “Process-variation-aware mapping of best-effort and real-time streaming applications to MPSoCs,” ACM Trans. Embed. Comput. Syst., vol. 13, no. 2s, pp. 1–24, 2014.

[93] C. MacLean and G. COWIE, Data flow graph: Google Patents.

[94] S. K. Baruah, A. Burns, and R. I. Davis, “Response-Time Analysis for Mixed Criticality Systems,” in IEEE 32nd Real-Time Systems Symposium (RTSS), 2011, Vienna, Austria, 2011, pp. 34–43.

[95] A. Burns and S. Baruah, “Timing Faults and Mixed Criticality Systems,” in Lecture notes in computer science, 0302-9743, 6875. Festschrift, Dependable and historic computing: Essays dedicated to Brian Randell on the occasion of his 75th birthday /  Cliff B. Jones, John L. Lloyd (eds.), B. Randell, C. B. Jones, and J. L. Lloyd, Eds., Heidelberg: Springer, 2011, pp. 147–166.

[96] P. Ekberg and W. Yi, “Outstanding Paper Award: Bounding and Shaping the Demand of Mixed-Criticality Sporadic Tasks,” in Proceedings of The 24th Euromicro Conference on Real-Time Systems: 10-13 July 2012, Pisa, Italy, Pisa, Italy, 2012, pp. 135–144.

[97] M. R. Garey, D. S. Johnson, and L. Stockmeyer, “Some simplified NP-complete problems,” in Proceedings of the sixth annual ACM symposium on Theory of computing - STOC '74, Seattle, Washington, United States, 1974, pp. 47–63.

[98] L. Su et al., “Synthesizing Fault-Tolerant Schedule for Time-Triggered Network Without Hot Backup,” IEEE Trans. Ind. Electron., vol. 66, no. 2, pp. 1345–1355, 2019.

[99] A. Carvalho Junior, M. Bruschi, C. Santana, and J. Santana, “Green Cloud Meta-Scheduling : A Flexible and Automatic Approach,” (eng), Journal of Grid Computing : From Grids to Cloud Federations, vol. 14, no. 1, pp. 109–126, http://dx.doi.org/10.1007/s10723-015-9333-z, 2016.

[100]   T. Tiendrebeogo, “Prospect of Reduction of the GreenHouse Gas Emission by ICT in Africa,” in e-Infrastructure and e-Services.

[101]   Deutsche Welle (www.dw.com), Carmaker BMW to invest heavily in battery cell center | DW | 24.11.2017. [Online] Available: https://p.dw.com/p/2oD3x. Accessed on: Dec. 03 2018.

[102]   G. Fohler, “Changing operational modes in the context of pre run-time scheduling,” IEICE transactions on information and systems, vol. 76, no. 11, pp. 1333–1340, 1993.

[103]   H. Jung, H. Oh, and S. Ha, “Multiprocessor scheduling of a multi-mode dataflow graph considering mode transition delay,” ACM Transactions on Design Automation of Electronic Systems (TODAES), vol. 22, no. 2, p. 37, 2017.

[104]   A. Das, A. Kumar, and B. Veeravalli, “Energy-Aware Communication and Remapping of Tasks for Reliable Multimedia Multiprocessor Systems,” in IEEE 18th International Conference on Parallel and Distributed Systems (ICPADS), 2012, Singapore, Singapore, 2012, pp. 564–571.

[105]   S. A. Ishak, H. Wu, and U. U. Tariq, “Energy-Aware Task Scheduling on Heterogeneous NoC-Based MPSoCs,” in IEEE 35th IEEE International Conference on Computer Design: ICCD 2017 : 5-8 November 2017 Boston, MA, USA : proceedings, Boston, MA, 2017, pp. 165–168.

[106]   C. A. Floudas and V. Visweswaran, “Quadratic Optimization,” in Nonconvex Optimization and Its Applications, vol. 2, Handbook of Global Optimization, R. Horst and P. M. Pardalos, Eds., Boston, MA, s.l.: Springer US, 1995, pp. 217–269.

[107]   R. Lazimy, “Mixed-integer quadratic programming,” Mathematical Programming, vol. 22, no. 1, pp. 332–349, 1982.

[108]   A. Majd, G. Sahebi, M. Daneshtalab, and E. Troubitsyna, “Optimizing scheduling for heterogeneous computing systems using combinatorial meta-heuristic solution,” in 2017 IEEE SmartWorld: Ubiquitous Intelligence & Computing, Advanced & Trusted Computed, Scalable Computing & Communications, Cloud & Big Data Computing, Internet of People and Smart City Innovation (SmartWorld/SCALCOM/UIC/ATC/CBDCom/IOP/SCI) : 2017 conference proceedings : San Francisco Bay Area, California, USA, August 4-8, 2017, San Francisco, CA, 2017, pp. 1–8.

[109]   B. Xing and W.-J. Gao, “Imperialist Competitive Algorithm,” in Intelligent Systems Reference Library, Innovative computational intelligence: A rough guide to 134 clever algorithms, B. Xing and W.-J. Gao, Eds., New York NY: Springer Berlin Heidelberg, 2013, pp. 203–209.

[110]   J. D. Foster, A. M. Berry, N. Boland, and H. Waterer, “Comparison of Mixed-Integer Programming and Genetic Algorithm Methods for Distributed Generation Planning,” IEEE Trans. Power Syst., vol. 29, no. 2, pp. 833–843, 2014.

[111]   J. Yin, P. Zhou, A. Holey, S. S. Sapatnekar, and A. Zhai, “Energy-efficient non-minimal path on-chip interconnection network for heterogeneous systems,” in ISPLED'12: Proceedings of the international symposium on low power electronics and design, Redondo Beach, California, USA, 2012, p. 57.

[112]   J. Falk et al., “Quasi-static scheduling of data flow graphs in the presence of limited channel capacities,” in The 13th IEEE Symposium on Embedded Systems for Real-time Multimedia: October 8-9, 2015, Amsterdam, Netherlands, Amsterdam, Netherlands, 2015, pp. 1–10.

[113]   T. Wei, P. Mishra, K. Wu, and J. Zhou, “Quasi-static fault-tolerant scheduling schemes for energy-efficient hard real-time systems,” Journal of Systems and Software, vol. 85, no. 6, pp. 1386–1399, 2012.

[114]   M. J. Ryan, “A Case Study on the Impact of Convergence on Physical Architectures—The Tactical Communications System,”

[115]   Y. Huang and D. P. Palomar, “Randomized Algorithms for Optimal Solutions of Double-Sided QCQP With Applications in Signal Processing,” IEEE Trans. Signal Process., vol. 62, no. 5, pp. 1093–1108, 2014.

[116]   X. Cai, W. Hu, T. Ma, and R. Ma, “A hybrid scheduling algorithm for reconfigurable processor architecture,” in Proceedings of the 13th IEEE Conference on Industrial Electronics and Applications (ICIEA 2018): 31 May-2 June 2018 Wuhan, China, Wuhan, 2018, pp. 745–749.

[117]   P.-A. Hsiung and J.-S. Shen, Dynamic reconfigurable network-on-chip design: Innovations for computational processing and communication. Hershey, Pa.: IGI Global, 2010.

[118]   R. Misener and C. A. Floudas, “Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations,” Mathematical Programming, vol. 136, no. 1, pp. 155–182, 2012.

[119]   D. Axehill, “Applications of integer quadratic programming in control and communication,” Institutionen för systemteknik, 2005.

[120]   A. Nemirovskii, “Several NP-hard problems arising in robust stability analysis,” Math. Control Signal Systems, vol. 6, no. 2, pp. 99–105, 1993.

[121]   A. Sarwar, “Cmos power consumption and cpd calculation,” Proceeding: Design Considerations for Logic Products, 1997.

[122]   S. Kaxiras and M. Martonosi, “Computer Architecture Techniques for Power-Efficiency,” Synthesis Lectures on Computer Architecture, vol. 3, no. 1, pp. 1–207, 2008.

[123]   D. Kouzoupis, G. Frison, A. Zanelli, and M. Diehl, “Recent Advances in Quadratic Programming Algorithms for Nonlinear Model Predictive Control,” Vietnam Journal of Mathematics, vol. 46, no. 4, pp. 863–882, 2018.

[124]   R. Fourer, “Strategies for “Not Linear” Optimization,” Houston, TX, Mar. 6 2014.

[125]   L. A. Cortes, P. Eles, and Z. Peng, “Quasi-Static Scheduling for Multiprocessor Real-Time Systems with Hard and Soft Tasks,” in 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications: 17-19 August 2005, Hong Kong, China : proceedings, Hong Kong, China, 2005, pp. 422–428.

[126]   L. Benini, “Platform and MPSoC Design,”

[127]   R. Obermaisser and P. Peti, “A Fault Hypothesis for Integrated Architectures,” in Proceedings of the Fourth Workshop on Intelligent Solutions in Embedded Systems: Vienna University of Technology, Vienna, Austria, 2006 June 30, Vienna, Austria, 2005, pp. 1–18.

[128]   R. Obermaisser et al., “Adaptive Time-Triggered Multi-Core Architecture,” Designs, vol. 3, no. 1, p. 7, https://www.mdpi.com/2411-9660/3/1/7/pdf, 2019.

[129]   IBM, IBM ILOG CPLEX Optimization Studio CPLEX User’s Manual: IBM, 1987-2016.

[130]   Chart Component and Control Library for .NET (C#/VB), Java, C++, ASP, COM, PHP, Perl, Python, Ruby, ColdFusion. [Online] Available: https://www.advsofteng.com/product.html. Accessed on: Jan. 10 2019.

[131]   J. Ellson, E. Gansner, L. Koutsofios, S. C. North, and G. Woodhull, “Graphviz—open source graph drawing tools,” in International Symposium on Graph Drawing, 2001, pp. 483–484.

[132]   T. Lei and S. Kumar, “Algorithms and tools for network on chip based system design,” in Chip in sampa, Sao Paulo, Brazil, 2003, pp. 163–168.

[133]   G. D. Micheli and L. Benini, “Powering networks on chips: energy-efficient and reliable interconnect design for SoCs,” in isss, 2001, pp. 33–38.

Stub icon

This computing article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Meta-scheduling&oldid=1060953732"