RPN in Cilk


Cilk is a multithreaded parallel programming language based on C.

From Cilk's Reference Manual: ‘Cilk is designed for general-purpose parallel programming, but it is especially effective for exploiting dynamic, highly asynchronous parallelism, which can be difficult to write in data-parallel or message-passing style. [...] a programmer should concentrate on structuring the program to expose parallelism and exploit locality, leaving the runtime system with the responsibility of scheduling the computation to run efficiently on a given platform. [...] the runtime system guarantees efficient and predictable performance.

Syntactically, Cilk only differs from C by using several specific keywords.

The word cilk denotes a Cilk procedure, as opposed to a plain-C function. A procedure can spawn threads and be called as a spawn itself. In any program, the main must be a Cilk procedure.

spawn marks a specific procedure call as spawning a thread. The call must be a statement (not an expression) unless it is an argument to an inlet (see below). All the threads spawned from a Cilk procedure can be terminated by an abort command.

The word inlet denotes a C function, internal to a Cilk procedure, whose arguments can be spawned procedure calls. Certain kinds of expressions are treated as implicit inlets and so parts of them can be subject to spawning.

sync is a command that synchronizes – including waiting for completion of – all spawned threads with the procedure from which they are called.

The threads of a procedure instance, including its inlets, operate mutually exclusively with respect to their commonly accessible data. Writes to shared memory performed by the threads are seen by the code after the corresponding sync. Explicit mutual exclusion may be needed for threads spawned from different procedure instances. It can be programmed my means of locks (called semaphores in other languages).

The language definition guarantees that if a Cilk program only uses cilk, spawn, and sync, that program will execute on a sequential machine semantically indistinguishable from the C program, obtained from it by removing those keywords. Such a ‘decilked’ version of the program is called serial elision or C elision.

Links of Relevance

‘The Cilk Project’: the home page of Cilk

Cilk++: a C++ extended in the Cilk direction – commercial, but also available for free