CEAL Manual and User Guide (DRAFT)

Abstract

CEAL is a C-based language for self-adjusting computation. CEAL extends C with a small set of primitives that allow programmers to write self-adjusting computations in a manner similar to conventional C programming and embed these computations into larger C programs.

The current implementation of CEAL consists of a compiler, cealc, as well as a suite of CEAL benchmarks that we use for performance evaluation. This manual briefly describes how to download and build the cealc compiler. We also briefly describe how to use the CEAL language itself using examples from our benchmark suite.

Your questions and comments are appreciated and should be directed to hammer@mpi-sws.org.

Building from Source

Our build system is still a work in progress, but you should be able to compile and use the system in a local directory on your machine (there is no mechanism yet to install the tools permanently). The build process has the following requirements:

Once you've got the prerequisites installed, download the source distribution:

http://mpi-sws.org/~hammer/pldi09/ceal-0.1.1.tar.gz

Extract the source distribution to a local directory and change to this directory.

To start building the system, begin by building CIL as follows:

  cd cil
  ./configure
  make
  cd ..

Next, build the CEAL runtime library and the benchmark suite as follows:

  make

Now the bin directory should contain:

Optionally, you can also re-generate this manual (if you have doxygen installed on your machine), as follows:

  cd doc
  doxygen
  cd ..

Then doc/html/ will contain this manual in HTML format.

The CEAL compiler

cealc is a perl-script wrapper for cilly, and cilly is itself a perl-script wrapper for CIL and gcc. Check out http://cil.sourceforge.net/ for information about both CIL and cilly. The purpose of this script is to invoke cilly with the right options to translate CEAL source code into C target code (and by default) compile it to a native binary via gcc. Its use is analogous to cilly, whose use is itself analogous to gcc: supply one or more source files as arguments and it will compile a binary a.out.

Many gcc options work here too. The -o option can be used to redirect the output. The -c option can be used to create an object file only. As a general rule, any flag accepted by either gcc or cilly can be passed to this process and it will pass it along down the line as necessary. This fact is largely the result of the fact that cilly accepts options recognized by gcc and "does the right thing with them".

Special Options:

Preliminaries and Terminology

In this section we review the key notions involved in self-adjusting computation. Conceptually, a self-adjusting computation is made up of two stratified levels called meta and core, respectively. The core-level portion of the program (hereafter, the core-program) consists of the code that we expect to respond automatically to changes in its data (e.g., its input). The meta-level portion of the program (hereafter, the meta-program) is able to run one (or more) core programs, change their inputs, and automatically update the core outputs via a general purpose change-propagation mechanism. Although using the terms "core-program" and "meta-program" gives the impression that these levels run as separate executables, in fact both portions of the code are compiled and run together as a single executable; we use the term "program" loosely here to refer to a portion of code with a well-defined entry-point (e.g., a function and all the functions it calls)---not a separate binary executable.

At a high-level, a typical meta-program is structured as follows. First it performs an initial-run of a core program:

  1. construct initial core input
  2. run core program
  3. inspect core output

In the initial run (also referred to as the from-scratch run), the self-adjusting framework transparently creates an execution trace. The trace describes the dynamic data and control dependencies of the core program's run, and records how the core program produced its output (and intermediate results, etc.) from its input.

After the initial run, the meta program makes one or more changes to the core input. To get the output associated with the changed input in a conventional programming paradigm, the meta program would re-invoke the core program from-scratch to recompute the new output. However, in the self-adjusting setting the meta program uses change-propagation to automatically update the core output with respect to the input changes. Behind the scenes, change propagation uses the core program's execution trace to selectively re-execute the executions steps that are affected by the changes.

  4. repeat:
      4.A change core input
      4.B propagate changes
      4.C inspect updated core output

The meta-program benefits from a self-adjusting core program when it is faster to use change propagation to update the output than to to recompute it from-scratch. There is a sizeable class of programs for which this performance benefit is asymptotic (e.g., for small changes, change propagation can sometimes be faster by a linear factor over recomputing from scratch). Although it may also be slower in some cases, it is only ever slower by a constant factor (again, when compared to running from scratch).

We often say that a core program is stable for a certain class of input changes if we can show that for any such change, change propagation will always update the core output in a desirable amount of time. The property of a core program being stable is usually relative to which kinds of input changes we want to consider, and possibly the size of the input itself. As an example, consider a core program that produces a sequence of sorted elements given an unsorted input sequence. We might consider an input change to be an insertion or deletion of an input element. Then we might say the core program is stable if change propagation can respond to such a change in time O(log n), where n is the total number of input elements. In this case, the time for handling a small change via change propagation is consistent with the optimum time for maintaining a sorted list of elements under insertions and deletions.

The stability of a core program is determined in part by how it's written, and core programs that do not exhibit good stability can sometimes be rewritten as stable ones.

Language Primitives

A central concept of self-adjusting computation is that of a modifiable reference. A modifiable reference (modref for short) is a mutable storage location that holds one word of mutable data (e.g., a pointer, an integer, etc.). Modrefs have type modref_t, and the interface for working with modrefs uses modref pointers (of type modref_t*).

From a core-program's perspective, a modref is like any mutable (pointer-sized) location in memory: it can be read-from (using read) and written-to (using write). In both cases, the read or written value is of type void*. The modref function creates fresh modrefs that are initially empty.

Modrefs are typically used to hold inputs and outputs of core programs, as well as their intermediate results. Typically, after the meta-program runs the core program initially, it (1) mutates the core input by writing one or more modrefs with new values (via write), and (2) forces the changes to propagate to core output (via slime_propagate).

Note:
Before choosing the name CEAL, this project was internally referred to as SLIME. In future revisions, we will rename primitives like slime_propagate as ceal_propagate.
Warning:
Correct usage of CEAL requires that a modref be written before it is used with read or modref_deref. It is important to note that this requirement is not enforced statically or during run-time.

Examples

Limitations

TODO
Generated on Thu Mar 5 14:27:55 2009 for CEAL by  doxygen 1.5.6