Mathias Brandewinder on .NET, F#, VSTO and Excel development, and quantitative analysis / machine learning.
by Mathias 5. September 2011 14:20

Back in April, inspired by an MSDN article, I began looking into converting a Simulated Bee Colony algorithms from C# to F#; I thought this would be an interesting exercise on my slow path to learning F#, and I got a rough implementation going. Attention-disorder deficit and life in general got me side-tracked, but, better late than never, I am now ready to get back to it.

One aspect I am interested in, is to figure out how the original algorithm could be modified for parallelization. In its original form, the algorithm followed a turn-based approach: given the current state of the hive, process sequentially every bee (active, inactive, and scout bees), and repeat until the pre-set number of iterations is reached.

How could we approach parallelization? At a high level, two operations are taking place:

  • some bees are searching from new solutions to the problem, either by creating brand-new solutions (Scout bees), or by finding a solution close to an initial Solution (Active bees),
  • bees that have completed a search come back to the Hive, and share the Solution they found to the Inactive bees via a Waggle Dance; Inactive bees can update their state based on that new information.

The first part, the Search, is easily parallelizable: while searching, a Bee shares no data with other bees. Therefore, multiple bees could be searching for new solutions, each on its own thread. On the other hand, the information sharing part is trickier: if multiple bees were to share their new solution with inactive bees at the same time, concurrency problems would likely arise.

One approach to resolve the issue is to avoid the concurrency problem, and make sure that by design, the information-sharing part is taking place sequentially, one bee at a time. Here is how we will achieve this:

ParallelBees

A queue will hold bees returning from a Search with a new Solution, and process bees from the queue one by one, passing their information to the current inactive bees. Once it has shared its information with the inactive bees, the bee (or one of the inactive bees) is sent to Search again in parallel – and when its search completes, it returns to the queue, where it goes back in line and wait until it can be processed.

More...

by Mathias 26. June 2011 17:06

I have been digging into the Task Parallel library lately, and enjoying it a lot. As an exercise, I wondered if I could implement the classic FizzBuzz problem, using only Tasks, no loop-related keyword, and no method or property. To enforce this is, we’ll get FizzBuzz to run in the Main() method of a simple console, using only variables created locally.

Note: this is clearly a totally preposterous way to use the Task Parallel library. There is absolutely no benefit in using it in this context, I am doing this only for the sake of exploring how tasks work.

So how would we go about that?

A Task represents an asynchronous operation; it wraps a block of code, waiting to be executed. For instance, the following code queues up work to print out “Starting” to the console, and begins execution when we request the Task to start:

private static void Main(string[] args)
{
   var rootTask = new Task(
      () =>
         {
            Console.WriteLine("Starting");
         });
   rootTask.Start();
   Console.ReadLine();
}

We clearly need something more for FizzBuzz. If we want to avoid looping constructs, we need to have a form of recursion going on, so that we can work on increasing integers, until we reach the limit we set to our FizzBuzz.

Fortunately, Tasks are about more than simply executing a block of code; they can be composed, defining what tasks can be started when some precursor tasks are finished. In particular, Tasks allow Continuations: what to do once a specific task terminates can be defined, by using Task.ContinueWith(), as in this example:

private static void Main(string[] args)
{
   var rootTask = new Task(
      () =>
      {
         Console.WriteLine("Starting");
      });

   var nextTask = new Task(
      () =>
      {
         Console.WriteLine("Next task!");
      });

   rootTask.ContinueWith(it => nextTask.Start());

   rootTask.Start();
   Console.ReadLine();
}

Here we define our root task, still printing “Starting”, and another task, which will print “Next task!”, and we pass that nextTask as a follow-up task to the rootTask via ContinueWith. Running this code will execute first the rootTask, and upon completion, kickstart the second one, and print both expected lines to the Console.

More...

Comments

Comment RSS