Getting Started with Fibonacci

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.

Let's start.

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:

typedef unsigned long long fib_type;

The CnC Specification

Identifying Computation Units

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:

    CnC::step_collection< fib_step >       m_steps;

As we do not need any other function to compute Fibonacci, one step-collection is enough. More complex programs will of course use more than just a single step-collection.

Data entities

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< int, fib_type >  m_fibs;

Again, the C++ API provides a template class to define item-collections (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).

Steps: The Computation Units

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.

struct fib_step
{
    // declaration of execute method goes here
    int execute( const int & tag, fib_context & c ) const;
};

Note that the execute method must be "const" and is not allowed to have side-effects (other than on item-collections).

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.

Control Tags

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::tag_collection< int >             m_tags;

The CnC C++ API once achieves generality through templates; tags can be of any type, as long as it provides a copy-constructor.

The Context: Bringing it all together

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

struct fib_context : public CnC::context< fib_context > // derive from CnC::context
{
    // the step collection for the instances of the compute-kernel
    CnC::step_collection< fib_step >       m_steps;
    // item collection holding the fib number(s)
    CnC::item_collection< int, fib_type >  m_fibs;
    // tag collection to control steps
    CnC::tag_collection< int >             m_tags;

    // constructor
    fib_context();
};

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:

fib_context::fib_context()
        : CnC::context< fib_context >(),
          // pass context to collection constructors
          m_steps( *this ),
          m_fibs( *this ),
          m_tags( *this )
{
    // prescribe compute steps with this (context) as argument
    m_tags.prescribes( m_steps, *this );
    // step consumes m_fibs
    m_steps.consumes( m_fibs );
    // step also produces m_fibs
    m_steps.produces( m_fibs );
}

Writing the step

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:

int fib_step::execute( const int & tag, fib_context & ctxt ) const
{
    switch( tag ) {
        case 0 : ctxt.m_fibs.put( tag, 0 ); break;
        case 1 : ctxt.m_fibs.put( tag, 1 ); break;
        default : 
            // get previous 2 results
            fib_type f_1; ctxt.m_fibs.get( tag - 1, f_1 );
            fib_type f_2; ctxt.m_fibs.get( tag - 2, f_2 );
            // put our result
            ctxt.m_fibs.put( tag, f_1 + f_2 );
    }
    return CnC::CNC_Success;
}

Note:

A step does not care about where the input data comes from, nor does it care about were the output goes to. It only requests/gets the exact data instances it needs and puts the ones it produces. The CnC runtime will take care of all the coordination between producers and consumers. The programmer does not need to think about it (not even if it is run on distributed memory).

Writing main, the environment

Let's now complete the program by providing the "main", in which we instantiate our context

    fib_context ctxt; 

trigger the Fibonacci evaluation

    for( int i = 0; i <= n; ++i ) ctxt.m_tags.put( i );

You might have noticed that the fib(n-1) will not become available until a corresponding step-instances has been executed. Hence, it will not be sufficient to prescribe only the desired step-instances, that's why we need to put all tags up to that number.

Now we wait for the evaluation to complete

    ctxt.wait(); 

. The full main could read the desired input value from the command line and print it to stdout:

int main( int argc, char* argv[] )
{
    int n = 42;
    // eval command line args
    if( argc < 2 ) {
        std::cerr << "usage: " << argv[0] << " n\nUsing default value " << n << std::endl;
    } else n = atol( argv[1] );

    // create context
    fib_context ctxt; 

    // put tags to initiate evaluation
    for( int i = 0; i <= n; ++i ) ctxt.m_tags.put( i );

    // wait for completion
    ctxt.wait(); 

    // get result
    fib_type res2;
    ctxt.m_fibs.get( n, res2 );

    // print result
    std::cout << "fib (" << n << "): " << res2 << std::endl;

    return 0;
}

Here is the full example code: samples/fib/fib_tutorial/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