Mapping DFG to CGRA

constructMRRG()

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:

calculateCost()

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.

Generally we have 4 placement options for DFGNode cmp:

(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

(a) MRRG Tile2 at Cycle2: the result of DFGNode add is transfered from MRRG Tile1 at Cycle0, through MRRG Tile2 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)

dijkstra_search()

getPathWithMinCostAndConstraints()

schedule()

tryToRoute()

Modulo Scheduling