With the growing complexity of real-time applications, Multi-Processor Systems-on-Chip (MPSoCs) have become a vital solution for meeting stringent performance, power, and scalability requirements. Eficient task mapping plays a crucial role in optimizing the performance of such systems, particularly for real-time applications that demand strict timing constraints. Traditional mapping techniques, including static and dynamic strategies, struggle with balancing execution time, energy eficiency, and communication overhead in heterogeneous MPSoC architectures. In this paper, we propose a novel approach for optimizing task mapping in MPSoCs, based on the Grey Wolf Optimizer (GWO), a bio-inspired metaheuristic renowned for its efectiveness in solving complex optimization problems. This methodology aims to minimize task execution times and communication delays by intelligently mapping real-time tasks onto heterogeneous processing elements (PEs), while also adhering to real-time constraints and reducing energy consumption. The results confirm that the improved GWO algorithm is a powerful tool for addressing the challenges of real-time task mapping in MPSoCs, providing a robust and scalable solution for future embedded systems.
Embedded systems [
Embedded applications are frequently complex and often hierarchical, as seen in applications like
MPEG [
Given the specific demands of hierarchical applications, a single mapping strategy is often insuficient
to address both processing types optimally. Instead, an efective approach requires separate handling of
regular and irregular processing components [
Our approach uses the Binary Multi-objective Grey Wolf Optimizer (BMOGWO) to optimize the mapping on the MPSoC architecture, these techniques enable eficient task mapping that addresses both real-time constraints and energy optimization in complex embedded applications.
The rest of the paper is organized as follows: Section 2 discusses the definitions and the necessary mathematical formulations for problem mapping onto the MPSoCs architecture. In Section 3, the proposed mapping strategies are presented. Experimental results are provided in Section 4, and the paper concludes with Section 5.
Communications between the tasks of our application and the components of our target architecture is represented by two directed graphs.
The application graph, also known as the Task Graph (TG), is a directed graph (, ), where each vertex ∈ represents a module or task within the application. Each directed edge (, ), denoted as ∈ , signifies a communication link between tasks and . The weight of the edge , represented by , indicates the volume of data transferred between and , reflecting communication demand and aiding in optimizing resource allocation (see Fig. 1).
The architecture graph, denoted as (Architecture Graph), is a directed graph (, ) where each vertex ∈ represents a node within the topology. The directed edge (, ), denoted as ∈ , signifies a physical link that directly connects two elements, and , within the architecture. The weight of the edge , represented by , encapsulates critical characteristics of the physical link, including bandwidth, latency, and energy consumption. This comprehensive representation allows for efective analysis and optimization of communication pathways in Multi-Procesur-on-Chip (MPSoC) architectures (see Fig. 2).
The mapping of the application graph (, ) onto the architecture graph (, ) is defined by the mapping function: map : → such that map() = ∀ ∈ , ∃ ∈ . (1)
This mapping is valid under the condition that the number of tasks | | is greater than or equal to the
number of processing elements || (see Fig. 3) [
The mapping process is crucial in optimizing resource allocation within MPSoCs, as it determines
how application tasks are distributed across the available processing elements. An efective mapping
strategy not only facilitates parallel execution of tasks but also minimizes communication overhead,
ensuring that system performance and energy eficiency are maximized [
Our application is defined as a set of tasks = {1, 2, . . . , }, while the target architecture is represented as a set of processors = {1, 2, . . . , }. It is important to note that each processor can operate in multiple modes, denoted as 1, 2, 3. This capability of processors to function in various modes introduces greater diversity in optimization strategies for task placement.
By enabling processors to adapt their operational modes based on the specific requirements of
tasks, we can achieve more eficient resource utilization and improved performance. This multi-mode
functionality allows for fine-tuning of processing capabilities, enabling better handling of both regular
and irregular task types. As a result, it facilitates enhanced flexibility in mapping strategies, leading to
optimized execution times and reduced energy consumption within the multiprocessor system-on-chip
(MPSoC) framework [
=
Taille()
where: - is the execution time of task on processor . - Taille() denotes the size of task for processor . - is the frequency of processor operating in mode .
The overall execution time for the application is given by:
= max() for = 1, . . . , number of tasks where is the maximum execution time among all tasks , taking into account their dependencies.
The duration of communication between tasks and is calculated as: =
Min |,| ×
∑︁ latency(, ) where: - is the communication duration between tasks and . - represents the data volume that needs to be communicated between tasks and . - Min |,| denotes the minimum bandwidth of the path connecting processors and . - The summation ∑︀ latency(, ) accounts for the cumulative latency across the communication path.
This approach ensures that both execution and communication times are adequately considered for optimizing task mapping in MPSoCs, thereby improving overall system performance and eficiency. 2.2. Energy Consumption The energy consumption in a multiprocessor system-on-chip (MPSoC) can be categorized into execution energy and communication energy. 2.2.1. Execution Energy The energy consumed during the execution of a task on processor in mode is defined as: exec = Size × where: - exec is the execution energy of task . - Size represents the number of cycles required for task to execute on processor in mode . - denotes the energy consumption per cycle for processor in mode . (2) (3) (4) (5) 2.2.2. Communication Energy The energy consumed due to communication between tasks and assigned to processors and is given by:
com = ∑︁ × ,
=1 where: - com is the communication energy between tasks and . - represents the volume of data exchanged between tasks and . - , is the energy cost associated with the communication link between processors and . 2.2.3. Total Energy Consumption The total energy consumption for executing all tasks and their communications within the system can be expressed as:
task total = ∑︁ (exec + com)
=1 where: - total is the overall energy consumption for all tasks in the application. - The summation encompasses both the execution energy and communication energy across all tasks. 2.3. Task Placement Indicator An auxiliary variable is used to indicate the placement of tasks on processors, defined as follows: = {︃1 if task is placed on processor and operates in mode
0 otherwise
This formulation allows for a comprehensive analysis of energy consumption during task execution and inter-task communication, facilitating the optimization of task mapping strategies in MPSoCs. By minimizing both execution and communication energy, the overall eficiency and sustainability of the system can be significantly enhanced. (6) (7) (8)
The comprehensive problem we aim to address is the Assignment, and Scheduling (AS) problem. This encompasses the assignment and scheduling of application tasks and their associated communications onto the resources of a target architecture, with the objective of achieving specified performance metrics.
In our approach, we consider multiple objectives, including minimizing energy consumption and
maximizing performance eficiency. These goals are crucial for the operation of mobile embedded
systems, as they directly influence battery life [
To navigate these conflicting objectives, we adopt a multi-objective optimization strategy that seeks to find an efective compromise among the various goals. Specifically, we propose an approach utilizing the Multi-Objective Grey Wolf Optimizer (MOGWO) technique. This method is improved to eficiently tackle the AS problem by balancing energy eficiency with performance requirements, ultimately enhancing the overall efectiveness of task mapping in MPSoCs.
By integrating these advanced optimization techniques, our approach aims to provide a robust
solution that aligns with the dynamic demands of mobile embedded systems while addressing the
critical constraints of energy consumption and execution time.
3.1. Grey Wolf Optimizer (GWO)
The Grey Wolf Optimizer (GWO), introduced by [
In the hunting process, the alpha, beta, and delta wolves primarily guide the search, while the omega wolves follow, refining their positions based on these leaders. 3.1.1. Stages of GWO Grey wolves use three organized hunting stages in GWO: encircling, hunting, and attacking. The encircling behavior is mathematically represented by the following equations:
⃗ = ⃒⃒⃒ ⃗ · ⃗() − ⃗()⃒⃒⃒ ⃗( + 1) = ⃗() − ⃗ · ⃗ ⃗ = 2 · ⃗ · ⃗1 − ⃗
⃗ = 2 · ⃗2
Here, is the iteration counter, ⃗ represents the position of a wolf, ⃗ denotes the position of the prey, and ⃗ and ⃗ are coeficient vectors. The vectors ⃗ and ⃗ are defined as:
where ⃗1 and ⃗2 are random vectors within [
The next position of a wolf is derived by averaging the three leaders’ positions:
3 = ⃗ − 3 ·
⃗ ⃗
⃗( + 1) =
1 + ⃗2 + ⃗3
⃗
3
(18)
(19)
3.1.3. Attacking Mechanism
The vector ⃗ controls the balance between exploration and exploitation, with its elements set within
the range [− , ] and gradually reducing from 2 to 0. This is formulated as:
2
⃗ = 2 − · maxIter (20)
where maxIter is the maximum number of iterations, and is the current iteration. As the algorithm
progresses, GWO transitions from exploration to exploitation, allowing wolves to converge towards the
prey, representing the optimal solution.
3.2. GWO for Mullti-Objective Problems (MOGWO)
Despite the initial design of the Grey Wolf Optimizer (GWO) for single-objective problems, The authors
in [
The archive includes a control mechanism that determines whether new solutions should be added,
which ensures it only holds relevant non-dominated solutions. At each iteration, newly obtained
non-dominated solutions are compared with those already stored, updating the archive to reflect the
best trade-ofs achieved so far, as illustrated in Figure 4. In the multi-objective domain, comparing
solutions is complex due to the Pareto front concept, where solutions are not directly comparable by a
single measure [
Where is the number of non-dominated solutions in the -th segment, and is a constant greater than 1. This approach ensures a bias toward selecting solutions from less crowded regions, fostering diversity and enhancing the search efectiveness across the Pareto front. 3.3. Binary Grey Wolf Optimizer for Multi-Objective Problems (BMOGWO) The MOGWO was initially developed for continuous optimization tasks and thus cannot directly address the mapping challenges on MPSoCs architectures. To adapt MOGWO for such discrete multi-objective mapping tasks, a binary version was developed by introducing a sigmoid-based activation function to transform continuous position vectors into binary values.
In the original MOGWO, candidate solutions move continuously within the real-valued search space.
However, to facilitate binary movement, the continuous position update equation must be adapted.
This modified position update equation for binary space is defined as:
across the Pareto front and guiding convergence toward global optimality [
MOGWO employs a roulette-wheel selection approach based on probabilities assigned to each segment or hypercube of the objective space: +1 = {︃1 if sigmoid (︀ 1+2+3 )︀ ≥ rand
3
0 otherwise
sigmoid() =
Here, +1 represents the binary position in dimension at iteration , while rand is a uniformly
distributed random value between [
The intermediate variables 1, 2, and 3, originally defined in equations (16), (17), and (18), are
transformed to binary space as follows:
(21)
(22)
(23)
Here, rand is a random number drawn from a uniform distribution [
1 1 + − 10(1 ,, − 0.5) 3.4. Description of Our Approach In our design flow, the placement and scheduling phase is crucial as it directly influences the application’s implementation on a specialized architecture. This phase takes the following inputs: • Application model: A detailed representation of the application, outlining its structure and dependencies. • Target architecture model: A model of the hardware architecture, defining the available resources and their interconnections. • Performance and energy constraints: Specific requirements that the implementation must meet, including limits on execution time and energy consumption.
• Objective functions: Metrics to be optimized, such as minimizing latency, energy usage.
The output of this phase is a mapped assignment of tasks and communications to physical resources, with an optimized scheduling of tasks across these resources to meet the specified performance and energy constraints. The figure 7 present the global description of our approach.
Our approach was implemented using the JAVA programming language, and all experiments were conducted on a system with an Intel(R) Core(TM) i5-7300HQ CPU running Windows 10. Following the execution of our binary MOGWO-based mapping solution, configured with the properties and parameters detailed in Table 1, we obtained the following results: 4.1. Comparison of BMOWGO, MOPSO, and NSGA-II In validating our proposed solution for mapping applications on MPSoCs, we implemented the Binary Multi-Objective Grey Wolf Optimizer (BMOGWO) and compared it with two other widely used multiobjective optimization techniques: Multi-Objective Particle Swarm Optimization (MOPSO) and Nondominated Sorting Genetic Algorithm II (NSGA-II). We conducted the comparison on a set of examples of average size, evaluating execution time and energy consumption across varying numbers of processors and task quantities.
The table 2 summarizes the performance of the three methods, highlighting BMOGWO’s efectiveness in optimizing both execution time and energy consumption. The study ofers insight into each algorithm’s performance under diferent MPSoC configurations, demonstrating the adaptability and eficiency of BMOGWO for discrete mapping challenges in MPSoC environments.
The results illustrate that BMOGWO consistently delivers lower execution times and energy consumption compared to MOPSO and NSGA-II, particularly in configurations with higher task loads and processor counts. This demonstrates BMOGWO’s potential as a highly efective solution for application mapping in MPSoC environments, particularly where discrete and energy-eficient mapping is critical.
In this paper, we introduced a novel approach leveraging the multi-objective variant of the Grey Wolf Optimizer (GWO) to tackle the challenging problem of mapping hierarchical real-time applications onto a hierarchical MPSoC architecture. Our approach was further refined by adapting GWO with a binary encoding scheme, enabling efective optimization of both execution time and energy consumption—critical factors in real-time embedded systems.
The results obtained from our experimental analysis were benchmarked against two well-established metaheuristic algorithms, demonstrating that our proposed solution consistently surpassed these alternatives in both execution time and energy eficiency. These promising findings underscore the eficacy of our approach for optimizing task mapping in MPSoC environments.
With additional experiments and simulations, we are confident that our method will continue to prove efective in addressing similar multi-objective optimization challenges within real-time and embedded systems, contributing valuable insights to this field.