Temporal Graph Placement on Mesh-Based Coarse Grain Reconfigurable Systems Using the Spectral Method

Florian Dittmann, Christophe BobdaIess 2005 · DOI

Introduction

Mapping complex computational tasks onto Coarse-Grain Reconfigurable Architectures (CGRAs) requires balancing spatial and temporal constraints. This paper proposes a novel approach that combines spectral methods—a mathematical technique for wire-length minimization—with "As Soon As Possible" (ASAP) scheduling. This integrated strategy efficiently places data flow graphs (DFGs) onto a grid of processing elements (PEs) over time, significantly reducing communication overhead and latency.

The Routing Challenge in CGRAs

As the demand for high-performance, energy-efficient hardware grows, CGRAs have emerged as a middle ground between the rigidity of Application-Specific Integrated Circuits (ASICs) and the flexibility of general-purpose processors. CGRAs consist of a mesh of PEs that can be reconfigured for specific tasks. However, their primary limitation is restricted routing. Unlike FPGAs, CGRAs have limited connection paths between PEs. Inefficient task placement leads to data traveling across multiple "hops," increasing delays and power consumption. The objective is to place communicating nodes physically close to each other within the reconfigurable fabric.

Proposed Methodology

The authors introduce a two-stage optimization process to address the placement problem.

Spatial Optimization: The Spectral Method

The first stage treats the DFG as a mathematical object. By representing the graph as a Laplacian matrix and calculating its eigenvectors, the spectral method assigns each node a coordinate in 2D space. This approach naturally clusters nodes that communicate frequently, minimizing the total squared distance of all connections (wire length).

2D spatial mapping of the data flow graph nodes generated using the spectral method.

Temporal Optimization: ASAP Scheduling

Because large tasks often exceed the hardware's capacity at any single moment, execution must be staged. The researchers employ "As Soon As Possible" (ASAP) scheduling to determine the earliest execution level for each node based on its data dependencies.

Integrated Temporal Placement

The core innovation lies in combining spatial coordinates with temporal levels. The 2D spectral coordinates are "sliced" according to ASAP levels:

  1. Initial Placement: Nodes in the first level are assigned to PEs based on their spectral coordinates.
  2. Persistence and Locking: Nodes that must persist across multiple cycles are "locked" to their current PEs. This avoids the costly overhead of moving intermediate data to external memory.
  3. Dynamic Mapping: New nodes are placed in remaining gaps, using their spectral coordinates to maintain proximity to their dependencies.

Evaluation Methodology

The algorithm was evaluated using an exemplary data flow graph consisting of 19 nodes with various interdependencies. This serves as a proof-of-concept for the proposed mapping strategy.

The exemplary 19-node data flow graph used for proof-of-concept evaluation.

Key Results and Insights

The proposed method demonstrates several advantages:

  • Localized Communication: Final mappings show that most communications occur between direct neighbors or within the same PE across different time steps, avoiding long-wire overhead.
  • Reduced Latency: By minimizing "hops," the method enhances execution speed and reduces power consumption.
  • Dimensionality Reduction: Solving for 2D space before layering the temporal dimension keeps the optimization computationally efficient while respecting timing constraints.
  • Flexibility in Density: The authors suggest aggregation (combining levels) or splitting (breaking levels into sub-levels) to maintain peak efficiency across different graph sizes and hardware capacities.

Conclusion and Future Work

While the spectral method effectively minimizes communication overhead, memory bottlenecks remain a challenge. Complicated access patterns can still lead to idle cycles. Future research will focus on extending the placement algorithm to account for memory-related waiting cycles and refining cluster growth methods for larger graphs that significantly exceed hardware capacity.

Summary updated

BibTeX
@inproceedings{dittmann2005temporal,
  author = {Florian Dittmann and Christophe Bobda},
  title = {{Temporal Graph Placement on Mesh-Based Coarse Grain Reconfigurable Systems Using the Spectral Method}},
  booktitle = {Iess},
  year = {2005},
  doi = {10.1007/11523277\_29},
}
Figure