Mapping DFG to CGRA
Assume that a 2x2 CGRA with II=2, MRRG can be interpreted as the duplicated representation of Tile and Link resources in the CGRA along the time axis, so that the occupy status of each Tile and Link at each time cycle can be clearly reflected.
Explain MRRG:
Assume that the DFGNode add has been mapped to MRRG Tile1 at Cycle0, now the mapper is trying to determine the placement of its successor DFGNode cmp.
As CGRA2x2 only has 4 Tile, so there are generally 4 placement options for DFGNode cmp, including Tile0, Tile1, Tile2, Tile3, whose exact cycle in MRRG is confirmed by dijkstra_search() function:
(a) MRRG Tile1 at Cycle0: use the same Tile as its predecessor, the result of DFGNode 'add' is directly registered in Tile 1, no routing fabric is required, with timeCost = 0
(b) MRRG Tile0 at Cycle1: the result of DFGNode add is transfered from MRRG Tile1 at Cycle0 to MRRG Tile0 at Cycle1, with timeCost = 1
(c) MRRG Tile3 at Cycle1: the result of DFGNode add is transfered from MRRG Tile1 at Cycle0 to MRRG Tile3 at Cycle1, with timeCost = 1
(d) MRRG Tile2 at Cycle2: the result of DFGNode add is transfered from MRRG Tile1 at Cycle0, through MRRG Tile0/Tile3 at Cycle1, to MRRG Tile2 at Cycle2, with timeCost = 2 (there is no routing fabric between Tile1 and Tile2, so an addition Tile0/Tile3 must be adopted to bridge the result of DFGNode add)
This function is used for calculating the shortest path between the source Tile to destination Tile. Take placement option (a) as an example, the source node is MRRG Tile1 at Cycle0, the destination Tile is MRRG Tile1 at any Cycle, so the path might be:
-
MRRG Tile1 at Cycle0->MRRG Tile1 at Cycle1 -
MRRG Tile1 at Cycle0->MRRG Tile0 at Cycle1->MRRG Tile1 at Cycle2 -
MRRG Tile1 at Cycle0->MRRG Tile3 at Cycle1->MRRG Tile3 at Cycle2->MRRG Tile1 at Cycle3 -
MRRG Tile1 at Cycle0->MRRG Tile0 at Cycle1->MRRG Tile2 at Cycle2->MRRG Tile3 at Cycle3->MRRG Tile1 at Cycle4 - ......
Although there are actually infinite possible options fo the path, it is obvious that MRRG Tile1 at Cycle0->MRRG Tile1 at Cycle1 is the optimal path with the minimum timeCost=0.
However in some complex cases, identifying the optimal path is not as easy as the example above, so the dijkstra algorithm is adopted to iteratively search the optimal path.