2D Convolution

A 2D convolution is simply the application of a mask to a 2D image, conceptually the same as a "blur" operation in computer graphics. The prototype of a Sequoia task which implements a 2D convolution is as follows.

void task Conv2D(in float A[M+U-1][N+V-1], in float H[U][V], out float C[M][N]);

The output image, C, is computed from the input image, A, and the convolution mask, H, according to the following expression.

A 2D convolution problem, producing an output image of size M*N, can be decomposed into a set of parallel 2D convolution subproblems, each computing a non-overlapping region of the output image of size S*T. This is the decomposition that is used to implement this algorithm in Sequoia.

Note that in this formulation of 2D convolution, a size (M+U-1)*(N+V-1) input image is used to compute the size M*N output image, and similarly, a size (S+U-1)*(T+V-1) input subimage is used to compute each size S*T output subimage. In this formulation, the input subimages overlap with each other, even though the output subimages don't.

Sequoia Source Code

The abstract Sequoia implementation of a 2D convolution is as follows.

void task Conv2D(in float A[M+U-1][N+V-1], in float H[U][V], out float C[M][N]);
    
void task<inner> Conv2D::Inner(in float A[M+U-1][N+V-1], in float H[U][V], out float C[M][N])
{
    tunable S, T;
    mappar (unsigned int i = 0 : (M+S-1)/S) {
        mappar (unsigned int j = 0 : (N+T-1)/T) {
            Conv2D(A[i*S;S+U-1][j*T;T+V-1], H, C[i*S;S][j*T;T]);
        }
    }
}
    
void task<leaf> Conv2D::Leaf(in float A[M+U-1][N+V-1], in float H[U][V], out float C[M][N])
{
    for (unsigned int m = 0; m < M; m++) {
        for (unsigned int n = 0; n < N; n++) {
            C[m][n] = 0;
            for (unsigned int u = 0; u < U; u++) {
                for (unsigned int v = 0; v < V; v++) {
                    C[m][n] += H[u][v] * A[m+u][n+v];
                }
            }
        }
    }
}

In the above implementation, the tunable values that describe the subarray sizes, S and T, don't need to evenly divide the output image size parameters, M and N respectively, as both the array block expressions and the mappar iteration bounds properly handle this case.

XML Mapping File for the Cell Target

Note: The XML mapping file interface will soon be replaced with a new interface which is much less verbose and which is more convenient. The XML mapping example provided here will be replaced with an example that uses the new mapping interface when it is ready.

The XML mapping directives for targeting this program to Cell are as follows.

<?xml version="1.0"?>
<mapping>
<machine filename="cell.xml"/>

<entrypoints>Conv2DMainInst</entrypoints>

<taskmapping name="Conv2D">

    <instance name="Conv2DMainInst">
        <variant>Inner</variant>
        <level>2</level>
        <tunable name="S">32</tunable>
        <tunable name="T">256</tunable>
        <data>
            <array name="H">
                <arraysizeprecond type="exact" name="h">5, 5</arraysizeprecond>
            </array>
        </data>
        <ctrl>
            <level>0</level>
            <loop name="i">
                <spmd>
                    <fullrange> 0, 8 </fullrange>
                    <ways> 8 </ways>
                    <iterblk>1</iterblk>
                </spmd>
            </loop>
            <loop name="j">
                <swp> 2 </swp>
            </loop>
            <callsite name="Conv2D">
                <target name="Conv2DLeafInst">
                </target>
            </callsite>
        </ctrl>
    </instance>

   <instance name="Conv2DLeafInst">
        <variant>Leaf</variant>
        <level>0</level>
    </instance>

</taskmapping>

</mapping>

printer-friendly version

Sequoia

Docs

Navigation

User login

2D Convolution