We use Fibonacci as an educative example; what we show here is not meant to be an ideal or elegant implementation of Fibonacci. We only use Fibonacci as a simple enough problem to demonstrate CnC and highlight some of its features.
The Fibonacci number of a given value n is recursively defined as fib(n) = fib(n-1) + fib(n-2). As the values can grow very large, let's define our own data type that we can adjust if needed:
Fibonacci is a very simple algorithm. There only one computation which simply adds the values of the two previous Fibonacci numbers. Let's call it "fib_step". In CnC all execution instances of such a function are held in one collection, a CnC::step_collection. Declaring such a step-collection instance (with name m_steps) for steps of type "fib_step" is as simple as this:
The only data we seem to care about are the Fibonacci numbers that we compute. The only way in CnC to read values from a computation is through item-collections. So we clearly need to store the final result in such an item-collection. Additionally we need to get the result of another computation to compute a new value. Luckily, Fibonacci is recursive and the kind of the input data is the same as the output data (and with kind we mean that it not only has the same data-type but it also has the same meaning). So we can use one item-collection for the intermediate results and for the final result. More complex programs will of course use more than just a single item-collection.
Defining an item-collection is straight forward:CnC::item_collection). The second type-argument is the type of the data to be stored. For our Fibonacci numbers we declared our own type "fib_type", so "fib_type" is the second argument. But what about the first? The first type argument is the tag-type for identifying each data-instance. Just like a traditional key/value pair, the value of our item is accessible (only) through its identifier, the tag. What would make a good identifier for a Fibonacci number? Of course we can simply use an integer; so semantically, the above item-collection maps an integer key to its Fibonacci value. Our "fib_step" will fill this data structure during execution.
In general you can use any C++ type or class for tags and items as long as they provide a copy-constructor (which is true for most types). The tag types must also separately be supported by a hash-function (by default cnc_tag_hash_compare).
Apparently we need the step which actually computes the Fibonacci number from a given value. Computation units in CnC are defined as steps. Such a step is a class with an execute method which accepts two arguments: a control tag and a second argument, which usually is the context (see below) but could also be anything else.
From the step's perspective, the control tag distinguishes between execution instances of the same step. For example the control tag tells the above fib_step for which Fibonacci number it is currently executed; this should not be confused with input data, which is handled by item-collections.
It is recommended to pass the tag by const-reference, in particular if you are not using standard data types.
In CnC steps are never called explicitly. If a step needs to be executed with a given tag, this tag is put into a so called tag-collection. The tag-collection will make sure that the step gets executed eventually. So putting a tag tells the CnC runtime that a step-instance needs to be executed, but does not (and can not) say when it is going to run. So let's define the tag-collection which we will use to control our step-collections above:CnC C++ API once achieves generality through templates; tags can be of any type, as long as it provides a copy-constructor.
Before we can actually write the step-code, we need the before mentioned context. The context is what in the CnC literature is often referred to as "graph". It brings together the different collections (tags, items and steps) by defining them as members. Internally it takes care for the runtime mechanics and is used to control the graph evaluation (e.g. waiting for completion). Hence it is recommended to define tag- and item-collections as members of the context.
Each context must be derived from a base class, which again is a template. The accepted template argument is the newly defined derived class. Don't bother about the recursive nature if you are not used to it, it's legal C++. In our case it could look like this
So far we have all the definitions of all collections and the context. Now we need the mechanics, e.g. the relations between the different collections. Producer and consumer relations are declared by calling the respective produces/consumes methods. Then we want that for each tag which is put into the tag-collection m_tags a step from m_steps is executed. We do this by simply calling prescribe on m_tags. We declare all these relations in the context-constructor:
Now we have set up the graph and are ready to define the step functionality. The second argument to our step is the context, through which we have access to the tag- and item-collections. To compute the result for a given value, we need the results for the previous two values, which is expressed through getting them from the item-collection. Publishing/producing the result is the reverse operation: a put to the item-collection. The step-code could look as follows:
Let's now complete the program by providing the "main", in which we instantiate our context
Now we wait for the evaluation to complete
Here is the full example code: fibTutorial.cpp
The code can also be found in the "Samples" directory, including project files for VS on MS Windows* and Makefiles for Linux.
Next: Debugging features