A3MAP: Architecture-aware analytic mapping for networks-on-chip

Wooyoung Jang, David Z. PanACM Trans. Design Autom. Electr. Syst 2012 · DOI

TL;DR

This paper introduces A3MAP, a novel approach for mapping applications onto Networks-on-Chip (NoCs). It formulates the mapping problem as a Mixed Integer Quadratic Program (MIQP) and proposes efficient heuristic algorithms (A3MAP-SR and A3MAP-GA) to solve it, achieving better performance and energy efficiency across various NoC architectures, including irregular and custom designs.

What Problem Does This Paper Address?

Modern System-on-Chips (SoCs) are integrating an increasing number of processing elements (PEs), leading to complex on-chip communication demands. Networks-on-Chip (NoCs) have emerged as a solution, but efficiently mapping applications to these NoCs is crucial for performance and energy efficiency. Traditional mapping algorithms often assume regular mesh NoC architectures and struggle with the heterogeneity and irregularity found in modern SoCs (e.g., different-sized PEs, custom interconnects, or faulty links). This leads to suboptimal performance and increased communication energy consumption. The paper addresses the need for a flexible and efficient application mapping solution that can adapt to diverse NoC architectures.

Methods

The core of A3MAP lies in its novel formulation of the application mapping problem.

  • Metric Space Formulation: The authors represent both the application's communication graph and the NoC's interconnection topology as metric spaces. This allows for a unified representation of various network architectures, including regular meshes, irregular meshes, and custom designs.
  • Mixed Integer Quadratic Programming (MIQP): The application mapping problem is then precisely formulated as an MIQP. The objective is to minimize the "distortion" of embedding the application graph into the network's metric space, which translates to minimizing communication volume and hop count.
  • Heuristic Algorithms: Since MIQP is NP-hard, two efficient heuristics are proposed:
  • A3MAP-SR (Successive Relaxation): This algorithm uses a successive relaxation approach to convert the MIQP into a sequence of Quadratic Programming (QP) problems, which are solved much faster. It aims for a good balance between mapping quality and runtime.
  • A3MAP-GA (Genetic Algorithm): This algorithm employs a genetic algorithm with cycle crossover and pairwise swapping mutation to achieve high mapping quality, even if it takes longer than A3MAP-SR.
  • Partition-Based Approach for Large-Scale NoCs: For very large NoCs, a partition-based approach is introduced. The NoC and the application are divided into smaller groups, and A3MAP is applied to each group, significantly reducing runtime while maintaining good mapping quality.

Datasets

Not discussed in the paper. The authors use synthetic benchmarks generated by TGFF and industrial benchmarks like MPEG-4 Video Object Plane Decoder (VOPD) and E3S benchmark suites.

Key Insights and Ideas

  • Unified Representation for Diverse Architectures: The metric space approach is a powerful insight, enabling a single mapping framework to handle a wide array of NoC topologies (regular, irregular, custom, faulty) without needing architecture-specific algorithms.
  • MIQP for Global Optimization: Formulating the problem as MIQP allows for a global optimization perspective, aiming to find the best overall mapping rather than relying on greedy or local optimization strategies.
  • Heuristics for Practicality: The development of A3MAP-SR and A3MAP-GA demonstrates a practical approach to tackling the NP-hard nature of the problem, offering a trade-off between runtime and mapping quality.
  • Partitioning for Scalability: The partition-based approach is a crucial innovation for handling the ever-increasing scale of modern SoCs, making the proposed mapping solution practical for large-scale systems.
  • Architecture-Awareness Pays Off: The weighted interconnection matrix, which accounts for factors like wirelength and bandwidth differences, proves effective in minimizing communication energy, especially in custom and irregular networks.

Key Results

  • Improved Hop Count: A3MAP algorithms consistently reduce the total hop count compared to existing methods like NMAP and CMAP, especially in irregular and custom networks. For instance, in irregular mesh networks, A3MAP-SR and A3MAP-GA reduced hop count by 19.2% and 25.6% respectively, compared to NMAP.
  • Energy Efficiency: By minimizing hop count and considering communication volume and link characteristics, A3MAP leads to significant reductions in communication energy consumption. The paper notes that the improvement in total distance traveled by packets (related to energy) was greater than the improvement in hop count, highlighting the effectiveness of the weighted interconnection matrix.
  • Runtime Efficiency: A3MAP-SR provides a fast solution, while A3MAP-GA offers high mapping quality. The partition-based approach significantly reduces runtime for large-scale NoCs.
  • Adaptability: The algorithms demonstrate superior performance on irregular and custom NoC architectures compared to methods optimized for regular meshes.

Limitations and Future Work

  • Runtime for Large-Scale: While the partition-based approach addresses scalability, the full MIQP formulation can still be computationally intensive for very large numbers of cores/tiles.
  • Heuristic Nature: A3MAP-SR and A3MAP-GA are heuristics, meaning they do not guarantee an absolutely optimal solution, though they achieve near-optimal results in practice.
  • Future Work: The paper suggests that the proposed A3MAP algorithms are suitable for large-scale NoCs and can be further extended to handle more complex scenarios, such as dynamic application behavior or more sophisticated power management techniques. The architecture-aware analytical manner of A3MAP makes it adaptable to future NoC designs.

Summary updated

BibTeX
@article{jang2012map,
  author = {Wooyoung Jang and David Z. Pan},
  title = {{A3MAP: Architecture-aware analytic mapping for networks-on-chip}},
  journal = {ACM Trans. Design Autom. Electr. Syst.},
  year = {2012},
  doi = {10.1145/2209291.2209299},
}
Figure