Parallel Fibonacci

This guide demonstrates the basics of task parallelism by parallelizing the Fibonacci algorithm (just for the illustration purpose). The Fibonacci number N is recursively defined as F(N) = F(N-1) + F(N-2). The following image depicts an execution graph for Fibonacci number 5, where it can be noticed that the Fibonacci number of every node can be added to the child nodes in parallel.

1. On the Project menu, select the Add New Item...
2. In the Add New Item dialog, select the Visual C++ and then select Header File (.h)
3. Enter the Name HelloFibonacci and click the Add button.
4. Add the following code to the file:

   #pragma once
   #include "tef/Tentity.h"
   
   class HelloFibonacci : public tef::RequestHandler
   {
   public:
   	HelloFibonacci();
   	virtual ~HelloFibonacci();
   	virtual const char* Path() const override;
   	virtual void Process(tef::RequestContext& context) const override;
   };
                   

5. On the Project menu, select the Add New Item...
6. In the Add New Item dialog, select the Visual C++ and then select C++ File (.cpp)
7. Enter the Name HelloFibonacci and click the Add button.
8. Add the following code to the file:

   #include "stdafx.h"
   #include "HelloFibonacci.h"
   
   static HelloFibonacci Instance;
   
   HelloFibonacci::HelloFibonacci()
   {
   	tef::Register(this);
   }
   
   HelloFibonacci::~HelloFibonacci()
   {
   }
   
   const char* HelloFibonacci::Path() const
   {
   	return "/getfib";
   }
   
   struct fib
   {
   	int sum;
   	int number;
   	tef::RequestContext context;
   
   	fib(int sum, int number, tef::RequestContext& context)
   		: sum(sum), number(number), context(context) {}
   
   	void operator()(gpc::mutex<int,int>& state)
   	{
   		if( state.count() == 1 ) {
                           // this is the first one of previous 2 Fibonacci numbers.
   			state.setData(sum);
                           // the result is not complete yet.
                           return;
   		}
                   // this is the second one of previous 2 Fibonacci numbers.
                   sum += state.getData();
                   // the result is complete, continue.
   
                   if( state.key() != number ) {
                           // the result must be propagated further.
   			int value = state.key() + 1;
   			gpc::qumex<int,int> d(state);
   			d.join(value, fib(sum, number, context));
   			if( value < number ) {
   				d.join(++value, fib(sum, number, context));
   			}
                   } else {
                           // done. Sending HTTP response.
   			tef::JsonOutput<128> json(context.Output);
   			json.startObject();
   			json.writeNumberProperty(L"Fibonacci", sum);
   			json.endObject();
      			context.Output.End();
   		} 
   	}
   };
   
    // the HTTP entry
   void HelloFibonacci::Process(tef::RequestContext& context) const
   {
           int number = context.Input[L"num"];
   	if( number < 2 ) {
   		tef::JsonOutput<128> json(context.Output);
   		json.startObject();
   		json.writeNumberProperty(L"Fibonacci", number);
   		json.endObject();
   		return;
   	} 
           // note: in GPC the joins are non-blocking and parallelized based on join keys
           // functions with the same join keys are queued and executed one after another, otherwise in parallel
           gpc::qumex<int,int> d;
   	d.join(1, fib(0, number, context));
   	d.join(1, fib(1, number, context));
   	d.join(2, fib(0, number, context));
   }
                   

9. Compile (F7) and run the project (F5).
10. In a browser, enter http://127.0.0.1:42580/getfib?num=38. The following image depicts the output:
    
    
11. In a browser, go to http://127.0.0.1:42580/websqlgui.html page.
12. On the websqlgui.html page, click Monitor and then find and click the /getfib event record:
    
    
    You can traverse the execution flow of parallel tasks:
    
    
13. Use Ctrl+C in the command prompt window to stop the server.
14. Next Deployment

See Also:

Parallel Reduction