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 then
        II += 1
        break
    end if
}

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