Introduction
In modern Multi-Processor Systems-on-Chip (MPSoCs), the Network-on-Chip (NoC) serves as the critical communication backbone. As the number of processing cores increases, the challenge of efficiently mapping tasks to cores and scheduling their execution becomes increasingly complex. A primary hurdle is network contention: when multiple data transfers compete for the same communication paths simultaneously, latency spikes and power consumption rises.
The Challenge of Network Contention
Traditional optimization methods often treat task mapping (spatial placement) and scheduling (temporal ordering) as separate problems. However, in NoC-based systems, these two aspects are deeply intertwined. Placing communicating tasks close together reduces energy but can lead to localized "traffic jams" if their communication windows overlap. Effective optimization must therefore account for both the physical routing paths and the timing of data transfers to minimize contention probability.
Methodology: The MOHA Framework
The researchers address this multi-objective optimization problem through a two-fold strategy involving formal logic and a hybrid evolutionary algorithm.
1. Logical Constraint Formulation
The problem is first modeled using a flexible set of logical formulas. This approach allows the hardware constraints to be translated into various formats compatible with different exact solvers, such as Mixed Integer Linear Programming (MILP), Constraint Programming (CP), and Satisfiability Modulo Theories (SMT). This versatility enables the use of the most efficient solver for a given problem size.
2. Multi-Objective Hybrid Algorithm (MOHA)
To handle larger task sets where exact solvers become computationally prohibitive, the authors developed MOHA. This algorithm incorporates several key heuristics:
- Task Clustering: Grouping tasks with high communication requirements to minimize long-distance traffic.
- Spiral Mapping: A specialized heuristic for the physical placement of task clusters on the 2D mesh of the NoC.
- Pareto Local Search: An evolutionary mechanism designed to explore the trade-offs between makespan (total execution time), energy consumption, and average contention probability.
As illustrated in the comparison of local search and initialization techniques, these specific heuristics are critical for finding high-quality solutions that standard evolutionary algorithms might miss.
Experimental Evaluation
The proposed methods were evaluated using benchmarks from the Task Graphs For Free (TGFF) tool, simulating various real-world application workloads. The study compared MOHA against the popular NSGAII evolutionary algorithm and several exact solvers.
Key Results
The experimental results demonstrate that MOHA consistently outperforms or matches the performance of NSGAII. In many test cases, MOHA identified "dominating" solutions that were superior across all three optimization objectives simultaneously.
As shown in the performance table, for small-scale problems (5-10 tasks), the SMT solver (Z3) proved exceptionally fast. However, as complexity increased, the heuristic-driven MOHA maintained its ability to find high-quality solutions where exact methods struggled.
Conclusion and Future Directions
This research highlights the importance of considering temporal contention in NoC design. By combining formal logical modeling with specialized evolutionary heuristics, the MOHA framework provides a robust solution for the complex mapping and scheduling challenges in MPSoCs.
While the current work focuses on static scheduling for fixed workloads, future research will explore dynamic scheduling to account for runtime variability. Additionally, validating these models on physical FPGA hardware or high-fidelity simulators remains a key goal for moving these theoretical advancements toward practical industrial application.
Summary updated