Abstract
Full-mission simulators (FMSs) are considered the most critical simulation tool belonging to the flight simulator family. FMSs include a faithful reproduction of fighter aircraft. They are used by armed forces for design, training, and investigation purposes. Due to the criticality of their timing constraints and the high computation cost of the whole simulation, FMSs need to run in a high-performance computing system. Heterogeneous distributed systems are among the leading computing platforms and can guarantee a significant increase in performance by providing a large number of parallel powerful execution resources. One of the most persistent challenges raised by these platforms is the difficulty of finding an optimal mapping of n tasks on m processing elements. The mapping problem is considered a variant of the quadratic assignment problem, in which an exhaustive search cannot be performed. The mapping problem is an NP-hard problem and solving it requires the use of meta-heuristics, and it becomes more challenging when one has to optimize more than one objective with respect to the timing constraints. Multi-objective evolutionary algorithms have proven their efficiency when tackling this problem. Most of the existent works deal with the task mapping by considering either a single objective or homogeneous architectures. Therefore, the main contribution of this paper is a framework based on the model-driven design paradigm allowing us to map a set of intercommunicating real-time tasks making up the FMS model onto the heterogeneous distributed multi-processor system model. We propose a multi-objective approach based on the well-known optimization algorithm “Non-dominated Sorting Genetic Algorithm-II” satisfying the tight timing constraints of the simulation and minimizing makespan, communication cost, and memory consumption simultaneously.
Keywords
1. Introduction
A heterogeneous distributed multi-processor system (hereafter named “HDMS”) is a complex yet powerful architecture that refers to a collection of autonomous interconnected multiprocessor machines with various capabilities. 1 This type of architecture was developed to meet the high computation and timing requirements of real-time systems and have been widely used in industry, covering different domains such as aerospace, automotive, and avionics. One of the most critical systems that needs to be executed on large distributed computing systems is full-mission simulators (FMSs). An FMS is a complex simulator allowing the crew to practice regular flight operations, fire weapons, and familiarize themselves with the cockpit in normal and extreme situations by faithfully reproducing the aircraft and the mission environment in which it will operate. Moreover, many FMSs are able to communicate between each other in the distributed mission operation. The simulation provides an environment allowing military forces to train as they fight. For further details regarding FMSs, please refer to Section 2.
Exploiting the full potential of HDMS for improving FMS performance is a current challenge in aerospace and defense fields. The FMS software is contributed to by different teams with different specific backgrounds (e.g., mechanic, hydraulic, electronic). Therefore, efficient FMS execution on a HDMS requires a global view of the FMS and deep knowledge of the execution platform. In this context, we propose a new approach for efficiently improving the FMS performance using the HDMS. This approach is based mainly on a model-based paradigm. Starting from FMS and HDMS models, we apply our optimization algorithm for mapping the different real-time tasks making up the FMS on the components of the HDMS. The FMS and the HDMS models represent the basis for collaboration between the different teams involved in the FMS design while the optimization algorithm using as inputs the FMS and HDMS models facilitates integration.
The problem of finding an optimal mapping of n tasks on m heterogeneous processing elements is NP-hard.
2
In other words, if we assume that our aim is to map an application composed of 16 tasks on a quad-core architecture, the solution space that will be explored to find the optimal mapping schema contains
In this work, by analyzing existing FMSs, we extract a series of key performance metrics. The solutions are rated according to three metrics: makespan, communication cost, and memory consumption. As these metrics might be conflicting, suitable trade-offs are considered. To the best of our knowledge, there is no other work in the literature that addresses all the following research axes simultaneously: heterogeneity of the target architecture, dependency among the tasks modeling the system, the respect of tight timing constraints, and multi-objective optimization. Accordingly, the main contribution of this paper is that we are providing an efficient framework for mapping real-time tasks implementing the FMS among the available components of the HDMS with respect to the hard real-time constraints and minimizing at the same time makespan, communication cost, and memory consumption.
The remainder of this paper is organized as follows. In Section 2 we briefly review some basic concepts. Section 3 discusses related work. In Section 4, we formally model the FMS in the context of our problem. In Section 5 we detail our implementation and we illustrate it by a set of experiments described in Section 6. Finally, Section 7 presents concluding remarks and lists our future work.
2. Background information
This section provides a broad overview of the basic concepts applied in this work. Thus, the reader who is familiar with such concepts may skip to the next section.
2.1. Full-mission simulators
In the fast growing aviation industry, military aircraft contribute substantially. Military training relies heavily on hands-on experience with the training engines whether it be aircraft, tanks, ships, or submarines. One could easily imagine the high cost of training new recruits on these different devices. The National Training Systems Association (NTSA) reports that for the fiscal year of 2000, flying an F-16 fighter cost an estimated $5, 000 per hour. That aside, the dangerous environment and difficulty of training might lead to human casualties as well as infrastructure damage that will cost billions of dollars. To mitigate these issues, simulators have long been employed in civil industry and especially the military to reduce cost and casualties. Simulators are nowadays used for all various types of military training, such as Air Force pilots to fly fighter aircraft and Apaches, Navy officers to navigate ships and submarines, etc. Even better, the trainees have easily adapted to the use of simulators as a training tool due to the fact that they come from a generation acquainted with simulations such as video games and virtual reality. These simulators will reproduce the sounds, motion, visual scenes, and represent all the other instruments and systems to create a realistic training environment. This eased the integration of simulators which are extremely cost effective and provide a safe environment. In the NTSA report, for training on an Apache helicopter, the cost is estimated at $3, 101 per hour; whereas on a simulator, the cost plummets to $70 per hour. 4 FMSs are devices that artificially re-create aircraft flight and the external environment. These simulators are extremely complex, as they must replicate the equations that govern aerodynamics, flight controls, weapon load-out, and how the aircraft reacts to environmental factors such as air density, turbulence, wind shear, precipitation, etc.
2.2. Real-time systems
Systems are referred to as real-time when their correct behavior depends not only on the proper functioning of the operations they perform, but also on the time at which they are performed by respecting the system’s deadline. 5 Therefore, in real-time applications, the timing requirements are the main constraints and controlling them is the predominant factor for assessing the quality of service. 6
We distinguish two classes of real-time timing constraints: hard and soft, depending on the criticality of timing constraints. We consider a real-time system as hard when timing faults may cause some human or economic disaster. A real-time system is considered as soft when timing faults cause only some performance degradation. In terms of modeling, we use the term “tasks” to refer to the basic executable entities. These tasks could be periodic or aperiodic.
Regardless of the tasks’ behavior, it is important to state that some of them, once elected for execution, may be interrupted to allocate the processor to another one. Due to such behavior, they are called preemptive. On the other hand, when an elected task should not be interrupted before the end of their execution, it is called non-preemptive.
2.3. Multi-objective optimization
Problems with more than one objective have the distinction of being much more difficult to treat than their mono-objective equivalent. The difficulty lies in the absence of a ranking criteria to compare solutions. A solution may be better than another for some objectives and worse for others. 7 The solutions found by a multi-objective optimization approach have to be optimal with respect to distinct objectives, which are typically conflicting. It is not possible to find an optimal solution that satisfies all objectives but rather a pool of efficient solutions characterized by the fact that their cost cannot be improved in one dimension without being worsened in another as depicted in Figure 1. That is why the concept of an optimal solution becomes less relevant in multi-objective optimization. These solutions form the Pareto optimal front referring to the economist Vilfredo Pareto. 8

Example of a Pareto frontier. The pentagons represent feasible solutions. Triangles are not on the Pareto Frontier because they are dominated by pentagons. Points A and B are not strictly dominated by any other, and hence do lie on the frontier.
Mathematically, the multi-objective optimization problem is defined as follows:
In the literature, many approaches have been developed to address this problem and could be classified into two main categories as follows.
2.3.1. Scalar or weight-based approach
The weight-based approach consists of formulating a single-objective optimization problem such that its optimal solutions are optimal solutions to the multi-objective optimization problem. This technique is one of the oldest techniques in multi-objective optimization using heuristics such as genetic algorithms (GAs)9–11 and simulated annealing. 12 Since setting a weight vector leads to a single point, to find different solutions with various trade-offs, the optimization process is performed with different weight vectors which produce an extensive computational cost and the decision maker has to set the most suitable weight combinations to reproduce a representative part of these Pareto solutions. Furthermore, a main technical shortcoming of this approach is that the non-convex points of the Pareto front are unreachable.
2.3.2. Pareto approach
The Pareto approach directly uses the concepts of dominance in solution generation. Therefore, the Pareto optimum gives more than a single solution, but rather a set of solutions called non-dominant solutions. The main advantage of these approaches is the simultaneous optimization of conflicting objectives. Non-dominated Sorting Genetic Algorithm (NSGA) 13 , NSGA-II 14 , SPEA 15 and SPEA-II 16 are among the most known multi-objective algorithms based on this technique.
3. Related Work
It is now more than a quarter of a century since researchers started publishing papers on distributing computation across the execution resource of parallel architectures. This section is a sampling of related literature and is not meant to be exhaustive. It covers the different levels of parallelism, the system heterogeneity, the optimization objectives, and whether the methodology considers real-time constraints.
Braun et al. 17 presented a comparison among static heuristics for mapping applications onto heterogeneous distributed computing systems aiming to minimize the makespan. Through this comparison, which included GAs, tabu search, and simulated annealing among others, the experimental results showed that GAs consistently gave the best results for the parameters and implementation used in this exhaustive study. Nevertheless, this work is limited to independent tasks and a single objective. Owing to the relevance of biologically inspired methodologies for scheduling, Tumeo et al. 18 provided an ant colony optimization for mapping and scheduling in heterogeneous multiprocessor systems. Their solution showed 64% and 55% better results compared to simulated annealing and tabu search respectively. Lu and He 19 proposed a PSO-based GA hybrid algorithm to schedule a set of tasks on a heterogeneous multi-processor system to minimize the makespan taking into account the precedence constraints. The schedule obtained outperforms the GA and is within 9% of the optimal schedule. Kang and Zhang 20 presented a hybrid GA for static task mapping and scheduling on heterogeneous systems with satisfaction of the precedence requirements of the application.
A study of the efficiency of multi-objective evolutionary algorithms (MOEAs) in the task mapping and scheduling on heterogeneous systems is performed with two different objectives in Chitra et al., 21 minimizing the makespan and the average flow-time. Devi and Anju 22 proposed a multi-objective scheduling algorithm using an MOEA for scheduling a collection of dependent tasks on available resources in a multi-processor environment. NSGA-II is used to get the Pareto optimal solutions to minimize at the same time the makespan and the reliability cost. Rajeswari et al. 23 presented an efficient allocation and scheduling method using multi-objective GAs for independent tasks. Such a procedure minimizes the makespan and flow-time simultaneously in a distributed computing system.
Samur and Bulkan 24 presented a GA approach to solve a bi-criteria problem (makespan and tardiness) in homogeneous parallel machines and tried to make their method fairly general to be applied to some other bi-criteria objective functions. Saranya et al. 25 presented a parallel multi-objective GA for the task dispatching problem in a heterogeneous distributed computing environment. It exploits the inherent parallelism of GAs on a multi-core processor to optimize the result. Navaz and Ansari 26 considered two objectives: execution time and total cost. They used the R-NSGA-II approach which is based on an evolutionary computing paradigm and uses an epsilon dominance based MOEA. In Serafini and Dehuri, 27 a combinatorial multi-objective particle swarm optimization based algorithm is proposed to map a set of dependent tasks on heterogeneous systems with consideration of failure on processors and links. The obtained results outperform the NSGA-II. However, the authors don’t consider the tuning of the NSGA-II parameters.
Dorronsoro et al. 28 investigated the problem of multi-objective mapping on Grids, optimizing simultaneously the makespan and its robustness. For this purpose, four different MOEAs were studied. These algorithms are NSGA-II, MOEA/D, IBEA and MOCell. From their experiments, the latter leads to the best results compared to the others. Miryani and Naghibzadeh 29 scheduled hard real-time systems on heterogeneous multi-processor systems taking into account the precedence relationship between tasks. Likewise, the authors studied the mapping problem from a multi-objective perspective aiming to minimize the completion time and the number of processors.
After this brief description, Table 1 depicts a detailed comparison of these works. In terms of the comparison’s characteristics, we identify the hardware architecture, real-time aspects, communication between tasks, and optimization strategy.
Comparison of related work.
PSO: ; MOGA: ; MOEA: multi-objective evolutionary algorithm; NSGA-II: Non-dominated Sorting Genetic Algorithm II; IBEA: ; MOCell: .
GA parameters configuration.
GA: genetic algorithm.
4. FMS model
An FMS is a very complex piece of software and exhibits a high-level of system integration. Several system models need to communicate data to other systems to replicate functions of the aircraft. When developing military flight simulator software, the development team has to rely on the competence of experts in different areas and with expertise from a multitude of domains, such as mechanics, power electronics, avionics, and more. The use of different models and their combination for the production of software is referred to as model-based design. This multi-domain modular approach to designing FMSs allows specialists to build, configure and test their modules concurrently, regardless of other modules. After initial testing, the modules are connected and characterized accordingly to form the complete simulation software for test and validation purposes. This latter process is called system integration. Such complex activity results in a network of sub-systems that need to be interconnected in order to deliver the platform’s intended functionality.
We aim to automate and optimize the integration process by efficiently mapping these real-time sub-systems (hereafter named tasks) implementing the FMS to the available resources of the HDMS. We formally define the graph modeling the FMS as
We start by defining the tasks’ expected execution time on the HDMS. This information is defined by specifying a
Liu and Layland
30
proved that a feasible schedule, that will always meet deadlines, exists if the processor utilization U is below a specific bound. For each task set
5. Proposed solution
To achieve a valid mapping solution respecting all the timing constraints and minimizing the defined fitness functions, our solution uses an approach involving two phases. Firstly, we assign the tasks implementing the FMS onto the available resources of the target architecture depending on the objective functions. Then, we perform the schedulability test of the assigned tasks to each processor of the execution platform to ensure the correctness of the solution from a scheduling point of view. The system model and the mapping approach are depicted in Figure 2.

Mapping strategy of the FMS on the target platform.
Our optimization approach is implemented on top of the NSGA-II taking into account schedulability. The studied fitness functions of our implementation are set out in more detail below. We are using a closed-form expression for the three objectives to avoid the timing cost raised by evaluation using simulation.
In Figure 3 an example of scheduling eight tasks on two processors is provided. The makespan is equal to 7.

Example of scheduling eight tasks on two processors.
In the bio-inspired GA, a given population represents a set of solutions to the problem and new generations are created through genetic operators. According to the evolution theory, only the strongest individuals of the population are likely to survive and generate offspring, transmitting their biological inheritance to the next generation. NSGA-II varies from GAs not only in the fact that it addresses multi-objective optimization problems but also in the selection operation. It also gives the non-dominated solutions belonging to or near the Pareto front in one single run. Before selecting a number of individuals to apply the genetic operators on, the population is ranked on the basis of the non-dominance and crowding distance concepts. Below, we give more details about how we are implementing and adapting the NSGA-II to our problem to minimize the fitness functions and deliver valid solutions from a scheduling perspective.
The pseudo-code of the proposed solution is given in Algorithm 1.

Example of chromosome (i.e., solution) encoding.

Non-dominated sorting.
The individual with lesser rank is selected if
If the two individuals belong to the same front

Example of single point crossover operator.

Example of uniform mutation operator.
6. Experimental study
This section is dedicated to the computational experiments in which the performance of our framework is evaluated. For this purpose, a protocol test is developed in which the data are randomly generated. During this phase, we opted for a procedure to generate values close to that of a real FMS. First, the execution time of tasks implementing the FMS are randomly generated in the range
Since it is a variant of GAs, one of the main issues of NSGA-II is the parameter tuning process to improve the quality of the obtained solutions and minimize the convergence time. To calibrate these genetic discrete parameters, we used a star plan in which we start from an initial configuration of these values. Then, each parameter covers a sample of its possible values while the others are held fixed at their latest values. When the performance metrics reach their best rates, the GA parameter under tuning is fixed to its current value and we pass to the next parameter, and so on. This operation has been processed based on a FMS modeled by 100 tasks and 10 heterogeneous machines with four processors each. Thence, a summary of the genetic parameters values yielded the best results on average which will be used to guide all our experiments.
In the whole experimental process, the focus is on measuring the impact of our mapping methodology on improving the FMS performance metrics. To quantify the algorithm sensitivity to the problem parameters (number of machines, number of tasks, connectivity degree, etc), 30 independent runs are performed for each of the test sets in order to guarantee a Gaussian approximation for the distribution of the reported averages. Then, we compute the average accuracy values. Since, the studied fitness functions have different scales, we apply feature scaling to create shifted and scaled versions of these values to facilitate the comparison and analysis tasks.
In Figure 8, we present the sensitivity of the different fitness functions to the number of machines and the number of tasks implementing the FMS. The study shows that increasing the number of machines of the HDMS helps in reducing the makespan, and the memory consumption, which is expected. For the communication cost, the algorithm will try to place tasks that communicate frequently on the same processor or machine to increase the data locality. By doing so, it creates a conflict with the previously mentioned fitness functions. Nonetheless, increasing the number of tasks implementing the FMS has an opposite impact on the mapping metrics by increasing them.

Impact of varying the number of machines and the number of FMS tasks.
Another crucial parameter that differs from one FMS to another is the connectivity degree of the tasks implementing a given simulator. In the graph modeling the FMS, two tasks are connected if there is an edge between them. We define the connectivity of a task as the average number of tasks directly connected to it.
For this parameter, we studied different connectivity ratios to cover a wide range of simulator categories going from five to 50 for an FMS modeled by 100 tasks. From Figure 9, we note that the connectivity degree has a perfect linear correlation relationship with the communication cost fitness function with a correlation coefficient

Impact of varying the connectivity degree.
In Figure 10 we show the progression of the three fitness functions during the evolution process. We notice that as the number of generations increases, the fitness functions improve gradually while keeping a trade-off between the different metrics. Since we are using the optimal number of generations found by the tuning process, the figure does not show the steady state of the fitness functions after

Impact of varying the connectivity degree.
Finally, Figure 11 shows the non-dominated solutions obtained in a single run by NSGA-II. Each point in the three-dimensional space is a valid mapping configuration near or belonging to the Pareto front and respecting all the predefined timing constraints of the FMS. It is up to the decision makers to choose the most suitable one for their needs.

Non-dominated solutions.
7. Conclusion and future work
In this paper, we propose a new framework enabling a multi-objective mapping of real-time tasks implementing the FMS on HDMSs. The aim of our approach is to simultaneously minimize the makespan, the communication cost, and the memory consumption ensuring that the hard timing constraints are met. We showcased that exact algorithms cannot solve our problem, and thus we studied the use of MOEAs, and we opted for NSGA-II in our study. This paper also paves the way for future research building upon its contributions. Our attempt in future work will be, from one side, to migrate to NSGA-III for more flexibility and scalability when integrating new objectives. From the other side, to implement a tool to select the most representative sample of non-dominated solutions to facilitate the task of the decision maker. A deep study of the quality indicators is needed for this purpose.
Footnotes
Funding
This work was partially supported by CAE Inc.
