A two-phase design space exploration strategy for system-level real-time application mapping onto MPSoC

Zai Jian Jia, Antonio Núñez, Tomás Bautista, Andy D. PimentelMicroprocess. Microsystems 2014 · DOI

TL;DR

This paper introduces a novel two-phase design space exploration (DSE) strategy for mapping real-time applications onto Multi-Processor Systems-on-Chip (MPSoCs). By combining fast analytical estimation for initial pruning with accurate system simulation for final evaluation, their approach significantly accelerates the DSE process while maintaining solution quality, outperforming traditional simulation-heavy methods.

What Problem Does This Paper Address?

Designing modern embedded systems, especially those based on Multi-Processor Systems-on-Chip (MPSoCs), is incredibly complex. These systems involve numerous processing elements, memory, and interconnects, leading to a vast "design space" of possible configurations and mappings. Finding the optimal configuration that meets stringent real-time constraints, performance targets, and resource limitations is a significant challenge. Traditional methods either rely on slow but accurate simulations, which are infeasible for exploring large design spaces, or use fast but less accurate analytical models, which might miss optimal solutions or fail to capture complex system behaviors like communication contention. This paper tackles the problem of efficiently exploring this design space to find optimal mappings for real-time applications onto MPSoCs, balancing speed and accuracy.

Methods

The core of this paper is a two-phase design space exploration (DSE) strategy:

  1. Pruning Phase (Analytical Estimation): This phase uses a combination of heuristic algorithms and an analytical estimation model to rapidly explore the design space.
  2. Heuristics: These algorithms address sub-problems like HW/SW partitioning (deciding if a task runs on a processor or a dedicated hardware block), task clustering (grouping tasks into virtual processors), and cluster assignment (mapping virtual processors to physical processing elements).
  3. Analytical Model: This model estimates the performance of potential mappings, considering both static computation times and dynamic communication delays, including contention effects. The goal is to quickly identify and discard design points that are unlikely to meet the real-time constraints or are suboptimal.
  4. Simulation Phase (System Simulation): The reduced set of promising design points identified in the pruning phase are then evaluated more accurately using a system-level simulator (CASSE in their experiments). This phase provides a precise performance assessment and helps in finding the final (sub-)optimal solutions.

This separation allows for the integration of different analytical models and simulation tools, offering flexibility.

Datasets

The paper uses a visual tracking algorithm as a case study for evaluating their approach. The application's task graph, computation times (profiled on an ARM-9 processor), and data channel sizes are provided. The MPSoC template is also described, including the number and types of processing elements (PEs), storage elements (SEs), and network elements (NEs). No specific public datasets were used; rather, a representative real-time application and a target MPSoC architecture were defined for experimental purposes.

Key Insights and Ideas

  • Bridging the Speed-Accuracy Gap: The most significant insight is the effectiveness of a two-phase approach. By using fast analytical methods to prune the vast design space before resorting to slow, accurate simulations, the overall DSE time can be drastically reduced without sacrificing the quality of the final solution.
  • Handling Communication Complexity: The analytical model's inclusion of communication delays, particularly contention effects, is crucial for realistic performance estimation in MPSoCs, where shared resources can significantly impact performance.
  • Modularity and Flexibility: The clear separation of the pruning and simulation phases, facilitated by well-defined interfaces, makes the framework highly modular. This allows for easy integration of alternative analytical models or simulation tools, making the approach adaptable to different MPSoC architectures and applications.
  • Heuristics for Pruning: The use of heuristic algorithms for partitioning, clustering, and assignment provides a structured way to generate candidate mappings, which are then fed into the analytical estimation.

Key Results

  • Efficiency: The proposed two-phase approach achieved a significant speedup, outperforming genetic algorithm (GA)-based DSE by two orders of magnitude in terms of total run-time to reach the first valid solution. For example, achieving a solution in 30 seconds (Estimation + Simulation) compared to 1800-6000 seconds for GA-based methods.
  • Accuracy: The analytical estimation model demonstrated reasonable accuracy, with an error margin of 1.1% to 8.2% compared to simulation results. This margin is attributed to inherent simplifications in analytical models, especially concerning complex contention scenarios.
  • Solution Quality: The approach found mapping solutions that used fewer processing and storage elements compared to GA-based methods, leading to better resource usage efficiency and lower communication traffic. For instance, one solution used 3 PEs (and 0 SEs) compared to 4 PEs (and 3 SEs) for a similar real-time constraint.

Limitations and Future Work

  • Analytical Model Accuracy: The authors acknowledge that the analytical model's accuracy can be affected by complex contention scenarios and the lack of certain variables (like specific network arbiter types). This leads to potential "invalid" mappings being passed to the simulation phase, which are then discarded.
  • Optimization Objectives: Currently, the analytical models do not directly optimize for power/energy or cost/area, which are critical design objectives.
  • Future Work:
    • Conducting more experiments with diverse applications and architectures to validate scalability.
  • Demonstrating the framework's flexibility by integrating other pruning/exploration algorithms and evaluation methods (e.g., using the Sesame simulator).
  • Extending the analytical models to incorporate power/energy and cost/area optimization objectives.

Summary updated

BibTeX
@article{jia2014two,
  author = {Zai Jian Jia and Antonio Núñez and Tomás Bautista and Andy D. Pimentel},
  title = {{A two-phase design space exploration strategy for system-level real-time application mapping onto MPSoC}},
  journal = {Microprocess. Microsystems},
  year = {2014},
  doi = {10.1016/j.micpro.2013.10.005},
}
Figure