Home

From .cpp to DFG

Finite Impulse Response kernel.cpp

LLVM Intermediate Representation

Data Flow Graph (DFG)

Mapping DFG to CGRA

Mapper.heuristicMap() is responsible for mapping DFG to CGRA, and its pseudocode is as follows:

II = Max(RecMII,ResMII)
While(1){
    constructMRRG(DFG, CGRA, II) // construct Modulo Routing Resource Graph (MRRG) according to DFG, CGRA, and current II 

    for each node in DFGNodes do
        for each row in CGRA.rows do
            for each column in CGRA.cols do
                Tile = CGRA[row][col] // locate the Tile
                pathWithTimeCost = caculateCost(node, Tile) // find the shortest path (time cost minimum) that mapping current DFGNode to current Tile
                pathList.append(timeCost)
            end for
        end for
        optimalPath = getPathWithMinCostAndConstraints(pathList) // find the path with minimum time cost and other constraints
        flag = schedule(optimalPath) // occupy the CGRALink among the optimalPath, allocate the register for the last CGRANode of the optimalPath
    end for

    if flag 
        break // mapping success
    else
        II += 1 // update II, repeat steps above
}

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:

More details about the functions called internally:

constructMRRG()

caculateCost()

getPathWithMinCostAndConstraints()

schedule()

CGRA Architecture & Timing

The details of the CGRA architecture is firstly introduced, followed by the timing analysis of a concrete operation 'multiplication'

CGRA Architecture

CGRA Timing