Programmation parallèle : calcul de Pi

Introduction
Dans mon précédent post, j'ai présenté un algorithme simple permettant d'estimer la valeur de Pi, afin d'évaluer les performances de l'AppEngine, le cloud de Google.

Dans ce nouvel article, je vais adapter cet algorithme afin de l'exécuter en parallèle sur un processeur multi-coeurs. L'environnement de développement utilisé pour cet exemple est le Framework .NET 4.0 et Visual C# Express 2010.

Pour rappel, voici l'algorithme original réécrit en C# :

static double SerialPi()
{
 double sum = 0.0;
 double step = 1.0 / (double)num_steps;
 for (int i = 0; i < num_steps; i++)
 {
  double x = (i + 0.5) * step; 
  sum = sum + 4.0 / (1.0 + x * x);
 }
 return step * sum;
}

Parallel.For() 
Le Framework .NET 4.0 nous offre de nouvelles instructions dédiées aux traitements parallèles dans le namespace System.Threading.Tasks. La plus simple à utiliser est le Parallel.For, qui offre l'immense avantage de préserver pratiquement la structure de notre code original.

Le premier argument indique la valeur de départ de notre itération. Le second est la valeur de fin (exclusive). Nous allons donc boucler num_steps-1 fois. Le troisième argument est moins anodin. Il s'agit d'un delegate vers une fonction qui va initialiser l'état de chacuns des threads qui seront exécutés par les différents coeurs du processeurs. Pour simplifier l'écriture, il est possible, comme dans cet exemple, d'utiliser une fonction anonyme.

Le second argument est un delegate vers une fonction qui sera exécutée lors de chaque itération. Nous retrouvons la logique du code source original, à la différence que la fonction reçoit la valeur i en argument et stocke son résultat dans une variable baptisée local, dont la portée sera, comme son nom l'indique, locale au thread.

Enfin, le dernier argument est une nouvelle fois un delegate vers une fonction qui sera appelée à la fin de l'exécution de chaque thread. Nous utilisons ici une variable de type object en guise de sémaphore pour effectuer la somme des valeurs de retour de chaque thread en évitant les problèmes d'accès concurrents. 

Voici le code adapté :

static double ParallelPi()
{
 double sum = 0.0;
 double step = 1.0 / (double)num_steps;
 object monitor = new object();
 Parallel.For(0, num_steps, () => 0.0, (i, state, local) =>
 {
  double x = (i + 0.5) * step;
  return local + 4.0 / (1.0 + x * x);
 }, local => { lock (monitor) sum += local; });
 return step * sum;
}

La classe Partitioner
Le Framework .NET permet également un autre type d'exécution parallèle qu'on appelle le "data partitioning". Au lieu d'exécuter des tâches différentes sur chaque coeur, on va ici morceller les données en paquets et les traiter en parallèle. Pour plus de détails, veuiller vous référer à l'objet Partioner dans la MSDN.

Voici le code adapté en conséquence :

static double ParallelPartitionerPi()
{
 double sum = 0.0;
 double step = 1.0 / (double)num_steps;
 object monitor = new object(); 
 Parallel.ForEach(Partitioner.Create(0, num_steps), () => 0.0, (range, state, local) =>
 {
  for (int i = range.Item1; i < range.Item2; i++)
  {
   double x = (i + 0.5) * step; local += 4.0 / (1.0 + x * x);
  }
  return local;
 }, local => { lock (monitor) sum += local; });
 return step * sum;
}