Rethink grid mapping semantics with pattern matching

This is a proposal for a fairly broad change to the way that various "mappings" happen in the language: namely, configuration tile groups map onto physical target tiles; data maps onto memories; and code maps onto tile groups.

First, let's sum up the status quo: a weird thing about the way all of these mappings currently work is the mysterious way that coordinate variables like x and y tend to crop up. Here's a config tile group in our current syntax, for example:

group tg[4][4] {
    tile target.t[x][y];
};

It's weird that x and y appear "out of nowhere," without having been "bound" anywhere. The same effect appears in data declarations, like this one:

g_src0: int[dim] = block[target.g.x_max] {
    target.g[x];
}

Again, x sort of appears out of nowhere.

A related strange thing about our current syntax is that mappings can sometimes seem to conflict. For example, this is a currently-valid code section:

config.tg[0][0]{
    bsg_finish();
}

config.tg[x][y]{
    for(int i = x+(y*x_max); i<csize; i=i+1){
        g_dest[i] = g_src0[i] + g_src1[i];
    }
    g_done_flag = 1;
}

What's supposed to happen at tile (0, 0) in tg? There are two definitions that seem to cover this tile. Clearly, we want the first one to trigger for (0, 0) and the second to trigger for all other tiles in the group, but the syntax here doesn't exactly make it clear that's what's going on.

So here's the proposal: it has two main parts.

All the interesting mapping happens in config. The data and code section must have simple, declarative mappings: every tile in a tile group has to run the same code, and data arrays just say "block/stripe this data across this set of memories." There is no possibility for complex index math in the data section, and if you want tiles to run different code, you have to set up separate tile groups in the config section to permit that. In the above example, you might declare a single-tile group master that only contains (0, 0) and a separate tile group workers that covers all the remaining tiles. The idea is to centralize the interesting mapping logic into one place where we can make it actually good.
Mapping in config works like pattern matching. The tile group configurations bind their coordinate variables, and they're matched top to bottom for each tile.

A new syntax for tile group configuration might look like this:

group master = t[0][0] { ... }
group workers = t[x][y] where x > 0 && y > 0 { ... }

As in standard FP pattern matching, if you want to know which group a t tile belongs to, you scan down the list and find the first one where the coordinates satisfy the pattern. And the names x and y are not special—those could have just as easily have been called foo and bar; the pattern binds those variables and makes them available in the body.

Then, in the code section, you'd write:

master { /* the coordinate binders are optional if you don't need them */ }
workers[row][col] { /* in here, `row` and `col` refer to the coordinates within the group */ }

Here are some alternatives for the mapping syntax that might be more sensible. First, it might be nice to group together all the "patterns" that match a given underlying resource. This would probably facilitate nested mappings more naturally. It would look something like this:

groups t {
    (0, 0) => master;
    (x, y) where x > 0 && y > 0 => workers;
}

Another option is to avoid where conditions like this and instead use numeric intervals right in the pattern:

groups t {
    (0, 0) => master;
    (x in [1..], y in [1..]) => workers;
}

I can imagine the interesting mapping being specified in either direction: as a mapping from physical to logical indices, or vice versa.

For instance: Given a 2D physical resource, t[x][y], we can define a 2D logical resource, grid, that is 2 tiles wide (row-wise) and 1 tile long (column-wise).

One design performs maps indices from physical to logical:

t[x][y] -> grid[x][y] {
    case [x][y] =>
        group row[floor(x/2)] of col[y];
}

It's worth explaining that there are two kinds of indexing in this hypothetical config code, corresponding to nested and primitive "groups": 1) indexing into an array of primitive logical resources (ex., grid[x][y] and col[y']) 2) indexing into a logical group of uniformly structured logical resources (ex., row[floor(x'/2)])

With this in mind, the code above reads as follows: the mapping of physical resource index t[x][y] to logical resource grid[x][y] is given by the y'-th element of the 1D col resource from the floor(x'/2)-th resource from the 1D resource group row. In other words, the given mapping maps any physical resource to a logical resource (from a resource array) in a group (from a group array).

An alternative design maps indices from logical to physical:

grid[x][y] -> t[x1:x2][y] {
    case [x][y] as row[x].col[y] =>
        t[2*x : 2*x+1][y]
}

This design reads as follows: the mapping of logical index grid[x][y] to physical index set t[x1:x2][y] via nested resource group row[x] containing resource array col[y] is given by t[2*x : 2*x+1][y]. In other words, the given mapping maps any logical resource (from a resource array) in a group (from a group array) to a physical resource.

Another example assigns one tile as master and the rest as worker, using pattern matching:

Physical to logical:

t[x][y] -> master_worker[x][y] {
    case [0][0] => master
    case [x][y] => worker[x][y]
}

Logical to physical:

master_worker[x][y] -> t[x][y] {
    case [0][0] as master => t[0][0]
    case [x][y] as worker[x][y] => t[x][y]
}

Whichever of these designs make sense, if any, ultimately depends on how they need to be used. What are all the different ways we need to leverage resource groups (e.g., automatic memory layout, communication in code section)? Is there a mapping direction that's more important to accomplish these (from physical to logical or vice versa)? What's the advantage of nested groups, versus multidimensional primitive arrays of resources?

cucapra / hbir

Rethink grid mapping semantics with pattern matching #15