In an earlier post I argued that, contrary to much of the literature in the area, parallelism is all about efficiency, and has little or nothing to do with concurrency. Concurrency is concerned with controlling non-determinism, which can arise in all sorts of situations having nothing to do with parallelism. Process calculi, for example, are best viewed as expressing substructural composition of programs, and have very little to do with parallel computing. (See my PFPL and Rob Simmons’ forthcoming Ph.D. dissertation for more on this perspective.) Parallelism, on the other hand, is captured by analyzing the cost of a computation whose meaning is independent of its parallel execution. A cost semantics specifies the abstract cost of a program that is validated by a provable implementation that transfers the abstract cost to a precise concrete cost on a particular platform. The cost of parallel execution is neatly captured by the concept of a cost graph that captures the dynamic data dependencies among subcomputations. Details such as the number of processors or the nature of the interconnect are factored into the provable implementation, which predicts the asymptotic behavior of a program on a hardware platform based on its cost graph. One advantage of cost semantics for parallelism is that it is easy to teach freshmen how to write parallel programs; we’ve been doing this successfully for two years now, with little fuss or bother.
This summer Guy Blelloch and I began thinking about other characterizations of the complexity of programs besides the familiar abstractions of execution time and space requirements of a computation. One important measure, introduced by Jeff Vitter, is called I/O Complexity. It measures the efficiency of algorithms with respect to memory traffic, a very significant determiner of performance of programs. The model is sufficiently abstract as to encompass several different interpretations of I/O complexity. Basically, the model assumes an unbounded main memory in which all data is ultimately stored, and considers a cache of blocked into chunks of size that provides quick access to main memory. The complexity of algorithms is analyzed in terms of these parameters, under the assumption that in-cache accesses are cost-free, so that the only significant costs are those incurred by loading and flushing the cache. You may interpret the abstract concepts of main memory and cache in the standard way as a two-level hierarchy representing, say, on- and off-chip memory access, or instead as representing a disk (or other storage medium) loaded into memory for processing. The point is that the relative costs of processing cached versus uncached data is huge, and worth considering as a measure of the efficiency of an algorithm.
As usual in the algorithms world Vitter makes use of a low-level machine model in which to express and evaluate algorithms. Using this model Vitter obtains a lower-bound for sorting in the I/O model, and a matching upper bound using a -way merge sort, where is chosen as a function of and (that is, it is not cache oblivious in the sense of Leiserson, et al.) Although such models provide a concrete, and well-understood, basis for analyzing algorithms, we all know full well that programming at such a low-level is at best a tedious exercise. Worse, machine models provide no foundation for composition of programs, the single most important characteristic of higher-level language models. (Indeed, the purpose of types is to mediate composition of components; without types, you’re toast.)
The point of Guy’s and my work this summer is to adapt the I/O model to functional programs, avoiding the mess, bother, and futility of trying to work at the machine level. You might think that it would be impossible to reason about the cache complexity of a functional program (especially if you’re under the impression that functional programming necessarily has something to do with Haskell, which it does not, though you may perhaps say that Haskell has something to do with functional programming). Traditional algorithms work, particularly as concerns cache complexity, is extremely finicky about memory management in order to ensure that reasonable bounds are met, and you might reasonably suspect that it will ever be thus. The point of our paper, however, is to show that the same asymptotic bounds obtained by Vitter in the I/O model may be met using purely functional programming, provided that the functional language is (a) non-lazy (of course), and (b) implemented properly (as we describe).
Specifically, we give a cost semantics for functional programs (in the paper, a fragment of ML) that takes account of the memory traffic engendered by evaluation, and a provable implementation that validates the cost semantics by describing how to implement it on a machine-like model. The crux of the matter is to account for the cache effects that arise from maintaining a control stack during evaluation, even though the abstract semantics has no concept of a stack (it’s part of the implementation, and cannot be avoided). The cost semantics makes explicit the reading and allocation of values in the store (using Felleisen, Morrisett, and H’s “Abstract Models of Memory Management”), and imposes enough structure on the store to capture the critical concept of locality that is required to ensure good cache (or I/O) behavior. The abstract model is parameterized by and described above, but interpreted as representing the number of objects in the cache and the neighborhood of an object in memory (the objects that are allocated near it, and that are therefore fetched along with the object whenever the cache is loaded).
The provable implementation is given in two steps. First, we show how to transfer the abstract cost assigned to a computation into the amount of memory traffic incurred on an abstract machine with an explicit control stack. The key idea here is an amortization argument that allows us to obtain tight bounds on the overhead required to maintain the stack. Second, we show how to implement the crucial read and allocate operations that underpin the abstract semantics and the abstract machine. Here we rely on a competitive analysis, given by Sleator, et al., of the ideal cache model, and on an amortization of the cost of garbage collection in the style of Appel. We also make use of an original (as far as I know) technique for implementing the control stack so as to avoid unnecessary interference with the data objects in cache. The net result is that the cost semantics provides an accurate asymptotic analysis of the I/O complexity of a functional algorithm, provided that it is implemented in the manner we describe in the paper (which, in fact, is not far from standard implementation techniques, the only trick being how to manage the control stack properly). We then use the model to derive bounds for several algorithms that are comparable to those obtained by Vitter using a low-level machine model.
The upshot of all of this is that we can reason about the I/O or cache complexity of functional algorithms, much as we can reason about the parallel complexity of functional algorithms, namely by using a cost semantics. There is no need to drop down to a low-level machine model to get a handle on this important performance metric for your programs, provided, of course, that you’re not stuck with a lazy language (for those poor souls, there is no hope).