User-defined Operators in Ct
Ct supports a complete scalar set of types for a couple of reasons. First, operations involving both TVECs and scalars are useful. Second, programmers should be able to define their own operations or function to apply across TVECs or to use as combining operators in reductions and scans. (For functional programming folks, think map, fold, and foldlist.) This flavor of data parallel programming can be referred to as “kernel” style, as opposed to the “vector” flavor also supported in Ct. Both are useful in differing circumstances. For linear algebra, we find the “vector” style easier to express algorithms, whereas for some signal and image processing algorithms, we find the “kernel” style easier. The underlying machinery is the same, but having both styles is an expressive convenience to the programmer.
Instead of expressing the following color conversion as:
Y = YRCoeff*R + YGCoeff*G + YBCoeff*B;
U = URCoeff*R + UGCoeff*G + UBCoeff*B;
V = VRCoeff*R + VGCoeff*G + VBCoeff*B;
The programmer can write:
Y = map(RGBtoY, R, G, B);
U = map(RGBtoU, R, G, B);
V = map(RGBtoV, R, G, B);
Where the programmer has defined:
TElt<U16> RGBtoY(TElt<U16> R, TElt<U16> G, TElt<U16> B) {
return (YRCoeff*R + YGCoeff*G + YBCoeff*B);
}
This is a basic example. Things get interesting when the programmer introduces some control flow (If-Then-Else's, For loops, While loops) or wants to touch neighboring pixels, say, for a 3x3 filter.
TElt<F32> threebythreefun(TElt<F32> arg, F32 w0, F32 w1, F32 w2, F32 w3, F32 w4) {
return w0*arg + w1*arg[-1][0] + w2*arg[0][-1] + w3*arg[1][0] + w4*arg[0][1];
}
…
map(threebythreefun, some2DGrid, smooth1, smooth2, smooth3, ... [ etc.]);
The alternative would have been to shift this image around, logically creating 4 additional copies. Though the compiler would have optimized these copies away, it’s a little misleading and not transparent enough in terms of the programmer’s intent. One can even express partial orders on the applications of these kernels (think deblocking filters for H.264):
TElt<I32> errordiffuse(TElt<I32> pixel) {
return someexpression(pixel,RESULT[-1][0],RESULT[-1][-1],RESULT[0][-1]);
};
ditheredcolors = map(errordiffuse, filteredcolors);
With reduction and scans, things get more interesting. For circuit folks, carry look-ahead adders are just specialized scans.
Tasks in Ct
The Ct API is a declarative way of specifying parallel tasks that are dependent on each other. So, collections of Ct operations on TVECs become collections of task dependence graphs. This still might be too constraining for those who would like to get at tasking abstractions directly. To this end, Ct introduces two abstractions for task parallelism.
The basic tasking unit in the Ct runtime is a future, an idea that goes back to MultiLisp. A future is basically a parallel-ready thunk (a function and arguments) that may or may not be executed immediately (and asynchronously), but whose execution must precede the reading of any value it generates (the runtime guarantees this). So, futures are exposed at the API level. Simply take any Ct functions and invoke it using the “spawn” function in the Ct namespace. The runtime makes sure any dependencies are satisfied so that the corrected order of execution is respected while parallelizing the call. The value a Ct future returns, in essence, is the only “effect” that is visible. Ct also incorporates a structured task parallel abstraction called hierarchical, synchronous tasks (HSTs). The basic idea is that tasks can execute in parallel, but their “effects” to be isolated from each other. Some of these effects are useful, but we want them combined in some predictable (deterministic) way. This can be viewed as a generalization of bulk synchronous processes. With HSTs, Ct easily support various other forms of structured parallelism, including pipeline and fork-join patterns (all with deterministic behaviors).
Execution Semantics of Ct
Ct is a dynamically compiled via a language runtime through library initialization. This is done so that one can expose these higher-level abstractions to heavy compiler optimizations, especially as one migrates code between platforms. This means that the Ct API calls used in a program may execute out of order and asynchronously with respect to the rest of one's C/C++ code. The only Ct API calls that are guaranteed to be “synchronous” with the C/C++ code are those that move data back and forth between TVECs and native C/C++ memory. The semantics of Ct allow this aggressive reordering by the compiler and runtime, though there will be some effort required if one is heavily intermixing C/C++ code and Ct API calls to optimize one's code. For functional programmers, the evaluation of Ct API calls can be viewed as “lenient” (Ct is strict and purely functional). For web programmers, the execution model will look similar to Python in that one “executes” all the code at least once, including the object declarations (which are bits of code that create and initialize the objects), then one uses the objects and their methods. In Ct, the analogy would be that the C/C++ sequencing of Ct API calls is the first pass through, then the runtime’s code cache is