. .. Graphs, 104 6.2.3 Scheduling Algorithms for Co-simulation under Real-time Constraints

. .. Industrial-use-case,

C. Faure, Real-time simulation of physical models toward hardware-in-the-loop validation, 2011.

A. Ben-khaled, Distributed real-time simulation of numerical models: application to powertrain, 2014.
URL : https://hal.archives-ouvertes.fr/tel-01144469

E. A. Lee and S. A. Seshia, Introduction to embedded systems: a cyber-physical systems approach, 2017.

, Functional mock-up interface for model exchange and co-Simulation, 2014.

A. Ben-khaled, Fast multi-core co-simulation of cyber-physical systems: application to internal combustion engines, Simulation Modelling Practice and Theory, vol.47, pp.79-91, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01018348

J. Reinders, Intel threading building blocks: outfitting C++ for multi-core processor parallelism, 2007.

B. P. Zeigler, H. Praehofer, and T. G. Kim, Theory of modeling and simulation: integrating discrete event and continuous complex dynamic systems, 2000.

D. Harel, Statecharts: a visual formalism for complex systems, Science of Computer Programming, vol.8, issue.3, pp.231-274, 1987.

C. A. Petri, Kommunikation mit automaten, 1962.

E. Kofman and S. Junco, Quantized-state systems: a DEVS Approach for continuous system simulation, Transactions of The Society for Modeling and Simulation International, vol.18, pp.123-132, 2001.

A. Ben-khaled, Context-based polynomial extrapolation and slackened synchronization for fast multi-core simulation using FMI, Proceedings of the 10th International Modelica Conference, pp.225-234, 2014.
URL : https://hal.archives-ouvertes.fr/hal-00968895

A. Ben-khaled-el-feki, CHOPtrey: contextual online polynomial extrapolation for enhanced multi-core co-simulation of complex systems, Simulation 93, vol.3, pp.185-200, 2017.
URL : https://hal.archives-ouvertes.fr/lirmm-01326188

. Ieee-standards-association, 1516-2010-IEEE Standard for modeling and simulation (M&S) High Level Architecture (HLA), 2012.

K. Lamberg and P. Wältermann, Using HIL simulation to test mechatronic components in automotive engineering, dSPACE GmbH, vol.15, p.16, 2000.

, Modelica Association. The Modelica Language Specification Version 3, 2017.

M. O. Faruque, Real-time simulation technologies for power systems design, testing, and analysis, IEEE Power and Energy Technology Systems Journal, vol.2, issue.2, pp.63-73, 2015.

G. E. Moore, Cramming more components onto integrated circuits, Electronics 38, vol.8, pp.114-117, 1965.

G. M. , Validity of the single processor approach to achieving large scale computing capabilities, AFIPS '67 (Spring) Proceedings of the, 1967.

M. Flynn, Some computer organizations and their effectiveness, IEEE transactions on computers, vol.100, pp.948-960, 1972.

. Openmp, OpenMP application programming interface, Available at www.openmp.org, 2015.

. Mpi and . Mpi, Available at www.mpi-forum.org, version 3.1, 2015.

J. Diaz, C. Munoz-caro, and A. Nino, A survey of parallel programming models and tools in the multi and many-core era, IEEE Transactions on Parallel and Distributed Systems, vol.23, pp.1369-1386, 2012.

R. I. Davis and A. Burns, A survey of hard real-time scheduling for multiprocessor systems, ACM Computing Surveys, vol.43, 2011.

J. Y. and -. Leung, Handbook of scheduling: algorithms, models, and performance analysis, 2004.

M. R. Garey and D. S. Johnson, Computers and intractability, vol.29, 2002.

T. C. Hu, Parallel sequencing and assembly line Problems, Operations Research, vol.9, pp.841-848, 1961.

E. G. Coffman and R. L. Graham, Optimal scheduling for two-processor systems, In: Acta Informatica, vol.1, pp.200-213, 1972.

C. H. Papadimitriou and M. Yannakakis, Scheduling interval-ordered tasks, SIAM Journal on Computing, vol.8, issue.3, pp.405-409, 1979.

P. C. Fishburn, Interval orders and interval graphs: a study of partially ordered sets, 1985.

T. L. Adam, K. M. Chandy, and J. R. Dickson, A comparison of list scheduling for parallel processing systems, Communications of the ACM, vol.17, pp.685-690, 1974.

H. Kasahara and S. Narita, Practical multiprocessor scheduling algorithms for efficient parallel processing, IEEE Transactions on Computers C, vol.33, pp.1023-1029, 1984.

B. Shirazi, M. Wang, and G. Pathak, Analysis and evaluation of heuristic methods for static task scheduling, In: Journal of Parallel and Distributed Computing, vol.10, issue.3, pp.222-232, 1990.

B. Kruatrachue and T. G. Lewis, Duplication scheduling heuristics (DSH): a new precedence task scheduler for parallel processor systems, 1987.

M. Wu and D. D. Gajski, Hypertool: A programming aid for message-passing systems, IEEE Transactions on Parallel and Distributed Systems, vol.1, issue.3, pp.330-343, 1990.
DOI : 10.1109/71.80160

J. Hwang, Scheduling precedence graphs in systems with interprocessor communication times, SIAM Journal on Computing, vol.18, issue.2, pp.244-257, 1989.
DOI : 10.1137/0218016

G. C. Sih and E. A. Lee, A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures, IEEE Transactions on Parallel and Distributed Systems, vol.4, pp.75-87, 1993.
DOI : 10.1109/71.207593

T. Yang and A. Gerasoulis, DSC: scheduling parallel tasks on an unbounded number of processors, IEEE Transactions on Parallel and Distributed Systems, vol.5, issue.9, pp.951-967, 1994.

E. S. Hou, N. Ansari, and H. Ren, A genetic algorithm for multiprocessor scheduling, IEEE Transactions on Parallel and Distributed Systems, vol.5, issue.2, pp.113-120, 1994.

A. S. Wu, An incremental genetic algorithm approach to multiprocessor scheduling, IEEE Transactions on Parallel and Distributed Systems, vol.15, pp.824-834, 2004.
DOI : 10.1109/tpds.2004.38
URL : http://www.cs.ucf.edu/~ecl/papers/0403.ieee.pds.pdf

F. A. Omara and M. M. Arafa, Genetic algorithms for task scheduling problem, Journal of Parallel and Distributed Computing, vol.70, issue.1, pp.13-22, 2010.
DOI : 10.1016/j.jpdc.2009.09.009

J. A. Stankovic, Misconceptions about real-time computing: a serious problem for next-generation systems, Computer 21, vol.10, pp.10-19, 1988.
DOI : 10.1109/2.7053

C. L. Liu and J. W. Layland, Scheduling algorithms for multiprogramming in a hard-real-time environment, Journal of the ACM (JACM), vol.20, pp.46-61, 1973.

J. Y. , -. Leung, and J. Whitehead, On the complexity of fixed-priority scheduling of periodic, real-time tasks, Performance evaluation, vol.2, pp.237-250, 1982.

A. Mok, Fundamental design problems of distributed systems for the hard real-time environment, 1983.

B. Andersson and J. Jonsson, Fixed-priority preemptive multiprocessor scheduling: to partition or not to partition, Proceedings of the 7th International Conference on Real-Time Computing Systems and Applications, pp.337-346, 2000.
DOI : 10.1109/rtcsa.2000.896409
URL : http://www.artes.uu.se/events/gsconf00/papers/ba.pdf

Y. Sorel, Real-time embedded image processing applications using the algorithm architecture adequation methodology, Proceedings of IEEE International Conference on Image Processing, ICIP'96, 1996.

A. Iserles and S. P. Nørsett, On the theory of parallel runge-kutta methods, IMA Journal of Numerical Analysis, vol.10, pp.463-488, 1990.

G. D. Byrne and A. C. Hindmarsh, PVODE, an ODE solver for parallel computers, International Journal of High Performance Computing Applications, vol.13, pp.254-365, 1999.
DOI : 10.1177/109434209901300405

H. Elmqvist, Automatic GPU code generation of modelica functions, Proceedings of the 11th International modelica conference, 2015.

M. Gebremedhin, A data-parallel algorithmic modelica extension for efficient execution on multi-core platforms, Proceedings of the 9th International Modelica Conference, 2012.

H. Elmqvist, S. E. Mattsson, and H. Olsson, Parallel model execution on many cores, Proceedings of the 10th International Modelica Conference, 2014.
DOI : 10.3384/ecp14096363
URL : http://www.ep.liu.se/ecp/096/038/ecp14096038.pdf

J. Clauberg and H. Ulbrich, An adaptive internal parallelization method for multibody simulations, 12th Pan-American Congress of Applied Mechanics, 2012.

J. Lions, Y. Maday, and G. Turinici, Résolution d'EDP par un schéma en temps «pararéel», Comptes Rendus de l'Académie des Sciences-Series I-Mathematics, vol.332, pp.661-668, 2001.

C. Farhat and M. Chandesris, Time-decomposed parallel time-integrators: theory and feasibility studies for fluid, structure, and fluid-structure applications, International Journal for Numerical Methods in Engineering, vol.58, pp.1397-1434, 2003.

M. Emmett and M. Minion, Toward an efficient parallel in time method for partial differential equations, Communications in Applied Mathematics and Computational Science, vol.7, issue.1, pp.105-132, 2012.

E. Lelarasmee, A. E. Ruehli, and A. L. Sangiovanni-vincentelli, The waveform relaxation method for time-domain analysis of large scale integrated circuits, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol.1, issue.3, pp.131-145, 1982.

S. Y. Hui and C. Christopoulos, Numerical simulation of power circuits using transmission-line modelling, IEE Proceedings A (Physical Science, Measurement and Instrumentation, vol.137, pp.379-384, 1990.

M. Sjölund, Towards efficient distributed simulation in Modelica using transmission line modeling, 3rd International Workshop on Equation-Based Object-Oriented Languages and Tools EOOLT, pp.71-80, 2010.

R. Braun and P. Krus, Multi-threaded real-time simulations of fluid power systems using transmission line elements, 8th International Fluid Power Conference, 2012.

P. Aronsson, Automatic parallelization of equation-based simulation programs, 2006.

A. Ben-khaled, Multicore simulation of powertrains using weakly synchronized model partitioning, Proceedings of IFAC Workshop on Engine and Powertrain Control Simulation and Modeling ECOSM, pp.448-455, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00746968

V. Galtier, FMI-based distributed multi-simulation with DACCOSIM, Proceedings of the Symposium on Theory of Modeling & Simulation: DEVS Integrative M&S Symposium. Society for Computer Simulation International, pp.39-46, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01155707

V. Galtier, Experimenting with matryoshka co-Simulation: building parallel and hierarchical FMUs, Proceedings of the 12th International Modelica Conference, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01521767

H. Lundvall and P. Fritzson, Automatic parallelization of object oriented models executed with inline solvers, Proceedings of the European Parallel Virtual Machine/Message Passing Interface Users' Group Meeting, pp.365-372, 2007.

W. H. Kohler, A preliminary evaluation of the critical path method for scheduling tasks on multiprocessor systems, IEEE Transactions on Computers, vol.100, pp.1235-1238, 1975.

O. Kermia and Y. Sorel, A rapid heuristic for scheduling non-preemptive dependent periodic tasks onto multiprocessor, Proceedings of ISCA 20th international conference on Parallel and Distributed Computing Systems, PDCS'07, 2007.
URL : https://hal.archives-ouvertes.fr/inria-00413486

K. Ramamritham, Allocation and scheduling of precedence-related periodic tasks, IEEE Transactions on Parallel and Distributed Systems, vol.6, pp.412-420, 1995.

E. Balas, Machine sequencing via disjunctive graphs: an implicit enumeration algorithm, Operations research, vol.17, issue.6, pp.941-957, 1969.

V. C. Barbosa and J. L. Szwarcfiter, Generating all the acyclic orientations of an undirected graph, Information Processing Letters, vol.72, pp.71-74, 1999.

T. R. Jensen and B. Toft, Graph coloring problems, vol.39, 2011.

T. Gallai, On directed paths and circuits, Theory of Graphs, pp.115-118, 1968.

B. Roy, Nombre chromatique et plus longs chemins d'un graphe, Revue française d'informatique et de recherche opérationnelle, vol.1, pp.129-132, 1967.

M. Hasse and H. Reichel, Zur algebraischen Begründung der Graphentheorie. III, Mathematische Nachrichten, vol.31, pp.335-345, 1966.

L. M. Vitaver, Determination of minimal coloring of vertices of a graph by means of boolean powers of the incidence matrix, Doklady Akademii Nauk SSSR, vol.147, pp.758-759, 1962.

R. M. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations, pp.85-103, 1972.

B. Ries, Coloring some classes of mixed graphs, Discrete Applied Mathematics, vol.155, pp.1-6, 2007.

G. V. Andreev, Y. , N. Sotskov, and F. Werner, Branch and bound method for mixed graph coloring and scheduling, Proceedings of the 16th International Conference on CAD/CAM, Robotics and Factories of the Future, pp.1-8, 2000.

Y. N. Sotskov, V. S. Tanaev, and F. Werner, Scheduling problems and mixed graph colorings, Optimization 51, vol.3, pp.597-624, 2002.

F. S. Al-anzi, Using mixed graph coloring to minimize total completion time in job shop scheduling, Applied Mathematics and Computation, vol.182, issue.2, pp.1137-1148, 2006.

J. Bélanger, P. Venne, and J. N. Paquin, The what, where and why of real-time simulation, p.1, 2010.

T. Grandpierre, C. Lavarenne, and Y. Sorel, Optimized rapid prototyping for real-time embedded heterogeneous multiprocessors, Proceedings of the 7th International Workshop on Hardware/Software Co-Design, CODES'99, 1999.
URL : https://hal.archives-ouvertes.fr/hal-01800625

A. Benveniste and G. Berry, The synchronous approach to reactive and real-time systems, Proceedings of the IEEE, vol.79, pp.1270-1282, 1991.
URL : https://hal.archives-ouvertes.fr/inria-00075115

A. Benveniste, The synchronous languages 12 years later, Proceedings of the IEEE 91, vol.1, pp.64-83, 2003.

H. Chetto, M. Silly, and T. Bouchentouf, Dynamic scheduling of real-time tasks under precedence constraints, Real-Time Systems, vol.2, pp.181-194, 1990.

L. Cucu and J. Goossens, Feasibility intervals for fixed-priority real-time scheduling on uniform multiprocessors, Proceedings of Emerging Technologies and Factory Automation, ETFA'06, pp.397-404, 2006.

B. P. Dave, G. Lakshminarayana, and N. K. Jha, COSYN: hardware-software co-synthesis of heterogeneous distributed embedded systems, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol.7, pp.92-104, 1999.

L. Cucu and J. Goossens, Feasibility intervals for multiprocessor fixed-priority scheduling of arbitrary deadline periodic systems, Proceedings of Design, Automation & Test in Europe Conference & Exhibition, DATE'07, pp.1-6, 2007.
URL : https://hal.archives-ouvertes.fr/inria-00192210

E. Grolleau, J. Goossens, and L. Cucu-grosjean, On the periodic behavior of real-time schedulers on identical multiprocessor platforms, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00920529

H. Kalla, Génération automatique de distributions/ordonnancements temps réel fiables et tolérant les fautes, 2004.

M. Berkelaar, K. Eikland, and P. Notebaert, lpsolve: open source (mixed-integer) linear programming system, 2004.

. Inc and . Gurobi, Optimization. Gurobi Optimizer Reference Manual, 2016.

. Ibm and . Cplex, V12. 7: user's manual for CPLEX, International Business Machines Corporation, 2017.

Z. Benjelloun-touimi, From physical modeling to real-time simulation: feedback on the use of modelica in the engine control development toolchain, Proceedings of the 8th International Modelica Conference, 2011.

B. Kruatrachue and T. Lewis, Grain size determination for parallel processing, IEEE software, vol.5, pp.23-32, 1988.
DOI : 10.1109/52.1991

G. Migoni, E. Kofman, and F. Cellier, Quantization-based new integration methods for stiff ordinary differential equations, Simulation, vol.88, pp.387-407, 2012.
DOI : 10.1177/0037549711403645

O. Kermia, Ordonnancement temps réel multiprocesseur de tâches non préemptives avec contraintes de précédence, de périodicité stricte et de latence, 2009.