Lost in the matrix

Introduction

Depuis l’avènement en 2005 des processeurs multi-cœurs dans nos appareils domestiques, nous, développeur, avons dû changer notre façon de concevoir les applications afin d’exploiter cette technologie. Tout le monde est concerné, directement ou indirectement. Les domaines d’utilisation sont vastes. Ils ne se limitent plus aux super calculateurs comme c’est le cas depuis plus de 20 ans, mais notamment aux jeux vidéos, et aux multimédias en générale. Ainsi nous avons vu apparaître un grand nombre de solution qui permette la parallélisation des traitements au sein d’un programme.

Mais en premier lieu, Il a fallu reconcevoir (ou concevoir) les kernels(noyaux) et les drivers(pilotes) des systèmes d’exploitation modernes pour supporter les nouvelles architectures multi-cœurs. Puis ce fut le tour des applications. Ce qui a par conséquent poussé Intel à développer TBB.

TBB en résumé

TBB est une bibliothèque de programmation portable écrite en C++ qui permet la parallélisation des données au sein d’un code C++ (ou compatible C++). TBB est arrivé en 2006 et fournit un haut niveau d’abstraction des threads grâce à sa conception qui combine le « Task Programming » et le « Data Parallelism ». De plus, TBB est compatible avec les autres bibliothèques de programmation telle qu’OpenMP, les POSIX Threads, les fibres, les (co)routines et les Protothreads.

Au niveau des compilateurs, il n’y a pas de restrictions particulières. N’importe quel compilateur compatible ISO C++ peut être utilisé (Intel Compiler, VC++, G++, DM, …) contrairement à Open MP qui est directement intégré au compilateur.

Au niveau des processeurs, seuls les processeurs IA 32/64, AMD 32/64 et Sparc sont supportés pour l’instant.

Au niveau de la licence, elle est « open source » sous licence GPL version 2.

Remarque : TBB n’est pas compatible avec Mono.

Quelle est la raison d’être de TBB ?

Intel s’est fixé plusieurs objectifs tels que :

Ø Donner aux développeurs la possibilité d’utiliser le Multithreading sans en être un expert.

Ø Obtenir des gains de performance sur les architectures multi-cœur.

Ø Privilégier le « Data Parallelism » plutôt que le « Functional Parallelism ».

Quelle est la différence entre le « Data Parallelism » et le « Functional Parallelism » ?

Supposons le code ci-dessous :

  
  
   
   
Func1() ;
Func2() ;
   
  
 
  

Le « Functional Parallelism » consiste à séparer chaque fonction dans un contexte différent.

Thread 1	Thread 2
Func1() ;	Func2() ;

Par opposition, si nous prenons le code ci-dessous :

  
  
   
   
For (i = 0 ; i < 42 ; ++i)
          Func(i);
   
  
  

Le « Data Parallelism » consiste à scinder un block de donnée en N block et de les traités dans un contexte différent.

  
  
   
   
Thread   1
   
   
   
Thread   2
   
  
  
   
   
for (i = 0 ;   i < 21 ; ++i)
         Func(i);
   
   
   
for (i = 21 ; i < 42 ; ++i)
         Func(i);
   
  
 
  

Le grand avantage du « Data Parallelism » c’est qu’il est beaucoup plus évolutif dans ma mesure que l’on peut changer la taille des blocks à traité, sans devoir réécrire le code. De plus on peut facilement imaginer un scheduler (ordonnanceur de tâches) qui va définir la taille des blocks et leurs contextes en fonction de l’architecture matérielle et logicielle (ce que fait TBB).

Architecture de TBB

L’architecture de TBB est composée de plusieurs couches dont la première est « les allocateurs de mémoire ». Chaque couche repose sur l’implémentation de la précédente à l’exception de la première. Voici le schéma de l’architecture de TBB (à lire de bas en haut) :

TBB par la pratique

La meilleure façon d’apprendre une technologie c’est par la pratique. Par conséquent, nous allons commencer par un cas simple. Pour notre exemple nous allons partir du code suivant :

  
  
   
   
void            Func1(float *tab, int size)
{
      for (int i = 0; i < size; ++i)
           tab[i] = Func2(i);
}
   
  
 
  
 
      

Dans ce code, nous devons traités un tableau de nombre flottant et effectuer un traitement sur chacun des membres de ce tableau. Comme nous avons vu précédemment, TBB fonctionne autour du « Data Parallelism » et du « Task Programming ». Ainsi, nous allons considérer trois choses :

Ø Notre tableau de nombre flottant constitue un block de donnée.

Ø Notre bloque de donnée peut être découpé en sous block.

Ø Le traitement sur un block constitue une tâche.

La première étape est de créer la « class » qui va représenter le traitement sur un block de donnée. Cette « class » prendra dans un constructeur public un pointeur sur notre tableau de nombre flottant (notre block) et le stockera.

  
  
   
   
class             CalcFloat
{
      public:
                  CalcFloat(float *tab)   : _tab(tab) {  }

      private:
           float  *_tab ;
} ;
   
  
 
  

Remarque : Le pointeur passé en paramètre dans le constructeur de « CalcFloat » sera l’adresse du tableau (du block) au complet.

Maintenant, il faut rajouter une méthode qui effectuera le traitement sur le block qu’elle contient. En réalité TBB n’utilise pas une méthode mais la surcharge de l’opérateur (). De plus, cet opérateur n’effectuera pas le traitement sur l’intégralité du block mais sur une portion (range). Sous TBB, une portion est définie par un « blocked_range ». Ainsi à chaque appel de l’opérateur on reçoit en paramètre la portion sur laquelle il faut effectuer un traitement.

Les « blocked_range »

Il existe 3 types de blocked_range :

Ø Unidimensionnel: blocked_range

Ø Bidimensionnel: blocked_range

Ø Tridimensionnel: blocked_range

La particularité des blocked_range c’est qu’ils implémentent un « Split Constructor » que nous détaillerons un peu plus loin.

Dans notre cas, nous avons un conteneur unidimensionnel représenté par notre tableau de nombre flottant. Par conséquent nous allons utiliser un blocked_range

  
#include <tbb/blocked_range.h>

class               CalcFloat
{
      public:
                    CalcFloat(float   *tab) : _tab(tab) {  }
               void   operator () (const   tbb::blocked_range &range) const
             {
             }
      private:
             float  *_tab;
} ;
   
  
 
  

Il ne nous reste plus qu’à ajouter notre traitement :

  
  
   
   
#include <tbb/blocked_range.h>

class               CalcFloat
{
      public:
                    CalcFloat(float   *tab) : _tab(tab) {  }
             void   operator () (const   tbb::blocked_range &range) const
             {
                      for (int i = range.begin(); i != range.end(); ++i)
                        this->_tab[i]   = Func2(i);
             }
      private:
             float  *_tab;
} ;
   
  
 
  
 
  

Enfin, la dernière étape consiste à utiliser l’algorithme « parallel_for » à la place du « for » dans « Func1 ».

  
  
   
   
void      Func1(float *tab, int size)
{
      tbb::parallel_for(tbb::blocked_range(0,   size),
                 CalcFloat(tab))
}
   
  
 
  

On remarque que le constructeur du blocked_range prend la taille du block à traiter (0 -> size).

Grâce à ce code, TBB va découper le blocked_range en plusieurs morceaux puis appeler la surcharge de l’opérateur () pour chacun de ces morceaux (qui sont aussi des blocked_range).
Bien entendu ce découpage n’est pas aléatoire, il sera détaillé dans la section « granularité ».

Voici le code final :

  
  
   
   
#include <tbb/blocked_range.h>
#include <tbb/parallel_for.h>

class               CalcFloat
{
      public:
                    CalcFloat(float   *tab) : _tab(tab) {  }
             void   operator () (const   tbb::blocked_range &range) const
             {
                    for (int i =   range.begin(); i != range.end(); ++i)
                          this->_tab[i] = Func2(i);
             }
      private:
             float  *_tab;
} ;

void      Func1(float *tab, int size)
{
        tbb::parallel_for(tbb::blocked_range(0, size),
                 CalcFloat(tab))
}
   
  
 
  

Split Constructor

Comme nous avons vu à la section précédente, chaque block de donnée est découpé et traité séparément. Ce découpage est réalisé par l’intermédiaire d’un « Split Constructor » que le blocked_range implémente. Ainsi les blocks sont récursivement découpés dans les algorithmes de parallélisation de TBB tels que le « parallel_for ».

  
  
   
   
Range::~Range()  // Destructeur.
Range::Range(Range &r, split)  //   Coupe r en deux.
bool Range::empty() const  // vrai si   il est vide.
bool Range::is_divisible() const  //   vrai si il peut être découpé.
   
  
 
  

Remarque : de préférence, on essai toujours que lorsque l’on coupe un « range » en deux, les deux parties soient égales pour ne pas tromper le scheduleur (ordonnanceur de tâches).

Le découpage des blocks est réalisé par l’intermédiaire du « Partitioner » qui s’appui entre-autre sur la valeur de la granularité du block.

Granularité

Pour que le « Partitioner » découpe de façon optimisé les blocks, il à besoin de connaître la granularité de chaque block. La granularité constitue l’unité d’itération. Elle peut être explicite ou implicite. En effet, nous n’avons pas précisé de granularité dans notre exemple avec le parallel_for. Sous TBB la granularité est représenté par un entier non-signé.

On peut expliciter la granularité grâce au troisième paramètre du blocked_range :

  
  
   
   
void      Func1(float *tab, int size)
{
        tbb::parallel_for(tbb::blocked_range(0, size, 42),
                 CalcFloat(tab))
}
   
  
 
  

La valeur de la granularité a une très grande influence sur les performances du programme. Mais si elle est mal calculée, elle peut avoir des conséquences désastreuses.

Voici un graphique fournit pas Intel qui illustre l’importance de la granularité :

Calcul de A[i] = B[i] * C sur 1 million de float avec une machine à 4 sockets et 8 hard-threads.

On remarque que le graphique est en forme de baignoire. En effet, le temps d’exécution du programme diminue jusqu'à que la granularité atteint 100000 puis remonte assez brusquement. On peu considérer que les performances sont correctes quand la granularité est comprise entre 100 et 100000.

Mais quelle est la valeur optimale pour la granularité dans notre cas ?

En réalité c’est très simple, il suffit de prendre la plus grande valeur de l’intervalle ou les performances sont correctes.

Pourquoi ?

Plus la valeur de la granularité est petite, plus les blocks sont petits. Par conséquent il est inutile de surchargé le scheduler (ordonnanceur de tâches) avec des petits fragments. D’autant plus que cela n’apporte aucun grain de performance par rapport à une granularité fixé à 100000.

Pourquoi ne pas laisser TBB décider de la valeur de la granularité ?

Même si la valeur que l’on définit est identique à celle qu’il calcul, il est préférable d’expliciter la granularité car cela évite qu’il la calcule (donc gain de temps). De plus la granularité dépend aussi du traitement que l’on va effectuer sur le block. Par conséquent, TBB ne peut pas toujours calculer de façon fiable la granularité à tous les coups.

Partitioner

Le « Partitioner » est le dispositif de TBB qui est chargé de découper les « Range » en « SubRange ». Il intervient pour deux algorithmes :

Ø parallel_for

Ø parallel_reduce

Il existe 3 types de « partitioner » :

Ø simple_partitioner : taille des blocks = valeur de la granularité.

Ø auto_partitioner : taille des blocks automatiques (calculé en interne).

Ø affinity_partitioner : auto_partitioner + gestion du « cache affinity ».

Il est tentant d’utiliser le « affinity_partitioner » dans tous les cas, car celui-ci est le plus complet. Pourtant il faut bien faire attention à son emploi.

Voici un graphique fournit par Intel qui illustre la différence entre le «auto_partitioner » et le « affinity_partitioner » :

On remarque que le « affinity_partitioner » est utile lorsque l’on a un nombre important d’élément. Attention, l’abus du « affinity_partitioner » peut avoir des effets très négatifs sur la performance du code. Seule l’expérience peut déterminer si son emploi est justifié.

Les conteneurs

Le gros défaut des conteneurs de la STL (Standard Template Library) c’est qu’ils ne sont pas « Thread-Safe » et que par conséquent, (dans la plupart des cas) on encapsule chaque accès du conteneur dans une section critique par l’intermédiaire de mutex, sémaphores, barrières, etc. Quant à lui, TBB fournit 4 conteneurs qui répondent à la plupart des besoins :

Ø concurrent_hash_map : Quasi similaire à la std::map de la STL.

Ø concurrent_vector : Similaire au std::vector de la STL.

Ø concurrent_queue : Une FIFO non bloquante.

Ø concurrent_bounded_queue : Une FIFO bloquante avec possibilité de définir une capacité.

Remarque : Les conteneurs de type « queue » supporte les itérateurs de la STL.

Mutex

Malgré que cela ne soit pas conseillé, TBB fournit néanmoins plusieurs implémentations des mutex dans le cas ou une opération nécessite un accès exclusif.

Voici un tableau des différents mutex que l’on retrouve dans TBB :

Opérations atomiques

Parallèlement aux mutex, TBB fournit une implémentation des types atomiques qui a l’avantage d’être beaucoup plus rapide que les mutex. De plus il n’y a pas de risque de « Deadlock ». D’une manière générale les opérations atomiques sont préférables aux mutex.

Syntaxe : atomic<T>

Remarque : T doit être un type de base : int, float, long, enum depuis la version 2.2.

Exemples :

= x // lit la valeur de x. x = // écrit la valeur de x et la retourne. x.fetch_and_store(y) // y = x et renvoi l’ancienne valeur de x. x.fetch_and_add(y) // x += y et renvoi l’ancienne valeur de x. x.compare_and_swap(y,z) // si x == z, alors x = y. sinon il renvoi l’ancienne valeur de x.

Liens utiles :

Ø http://www.threadingbuildingblocks.org

Ø http://koalab.epitech.net/

Øhttp://software.intel.com/en-us/blogs/2008/12/16/compare-windows-threads-openmp-intel-threading-building-blocks-for-parallel-programming

Bonsoir,

Vous avez probablement déjà voulu faire une requête qui recherche
des éléments dans une table avec une clause de type LIKE.
Cependant, comment peut-on faire pour rendre le LIKE non sensible
aux accents. Voici donc la méthode pour effectuer cette recherche
avec Microsoft SQL Server.

En un mot la solution est : COLLATE.

La clause COLLATE permet (entre-autre) la conversion du classement
d'une expression. Cette clause doit être combinée avec une chaîne
spécifiant le nom d'un classement SQL Server.

Dans notre cas j'ai choisi : SQL_Latin1_General_Cp437_CI_AI.

C'est à dire:

Latin1_General: identifiant l'alphabet ou la langue dont les
règles de tri sont appliquées.
Cp437: page de code 437.
CI: ne distingue pas la casse.
AI: ne distingue pas les accents.

-----

Cela donne cette requête:

-----

Par consequent, cette commande renverra les entrées dans
la table si le champ STR est égale aux valeurs ci-dessous:

libelle
LiBeLlE
libéllE
Libellé

Pour notre démonstration, nous allons créer un plugin qui permet
d'ouvrir un onglet contenant un UserControl de votre choix.
Cette démonstration sera réalisée en C# sous visual studio 2008.

Grace à cet exemple vous pourrez étendre de façon exponentielle
les possibilités de Visual Studio.

1) Ouvrez Visual Studio et créez un nouveau projet.

2) Sélectionnez “Complément Visual Studio

3) Cliquez sur “Suivant”

4) Sélectionnez “C#” et cliquez sur “Suivant”

5) Sélectionnez “Microsoft Visual Studio 200X” et
cliquez sur “Suivant”

6) Entrez les informations sur votre plugin et
cliquez sur “Suivant”.

7) Selectionnez les élements comme ci-dessous et
cliquez sur “Suivant”

8) Cliquez sur “Suivant”

9) Cliquez sur “Suivant”

10) Ouvrez le fichier “Connect.cs”

Ce fichier contient une classe “Connect” qui est le point
d’entrer de notre plugin. Attention, c’est du C#.Net 1.0.
Par conséquent le code généré est plutôt moche.

Cette classe contient 7 méthodes:

Methode	Action
OnConnection	Appelée lors du chargement du plugin.
OnDisconnection	Appelée lors du déchargement du plugin.
OnAddInsUpdate	Appelée lorsque des plugins on été chargés ou déchargés
OnStartupComplete	Appelée lorsque le Visual est en cours de lancement
OnBeginShutdown	Appelée lorsque le Visual est en cours de fermeture
QueryStatus	Appelée lorsque le paramétrage d’une commande a changé
Exec	Appelée lors de l’exécution d’une commande dans le plugin

Pour l’instant, nous n’allons pas modifier ce fichier.

Remarque : un plugin est en réalité qu’une bibliothèque
de classes compilée (MyFirstAddIn.dll dans notre cas)

11) Allez dans les propriétés du projet.

Notre plugin est destiné à être utilisé avec Visual Studio. C’est-à-dire
que pour déboguer notre plugin, nous allons lancer une instance de
Visual Studio qui sera l’hôte de notre application.
Ainsi, nous allons indiquer à Visual Studio qu’il doit lancer une instance
de Visual “devenv.exe” en mode Debug.

12) Dans l'onglet “Déboguer” Sélectionnez “Démarrer le programme externe”
dans “Action de démarrage”.

Assurez-vous que le chemin vers le programme “devenv.exe” est
correct. Normalement les paramètres par défaut sont corrects.

13) Lancez l’application en mode “Debug”.

Comme nous pouvons le voir Visual va lancer une instance Visual.
Nous pouvons aussi remarquer qu’un nouveau bouton “"MyFirstAddIn”
est apparu dans “Outils”. Si nous cliquons dessus, il se passe
bien entendu rien du tout, car nous n’avons rien implémenté dans
le fichier “Connect.cs”.

14) Ajoutez un nouveau UserControl.

Nous avons vu que le plugin est parfaitement chargé par Visual Studio.
Il faut maintenant créer le Contrôle utilisateur(UserControl)
pour notre démonstration.

15) Entrez un nom puis cliquez sur “Ajouter”.

Pour notre exemple, j’ai appelé le UserControl “MyUserControl”

16) Ajoutez les éléments que vous desirez dans ce UserControl.

Dans notre exemple j’ai ajouté une PictureBox.

17) Implémentez le fichier “Connect.cs”

Nous sommes maintenant en mesure d’implémenter notre plugin.
Pour des raisons pratiques, je vais seulement indiquer les lignes à rajouter dans ce fichier afin
de ne pas nuire à la visibilité de ce tutoriel (le code complet est disponible en bas du tutoriel).

A) Ajoutez un “using” dans l’entête du fichier pour indiquer que nous allons utiliser les “Windows Forms”:

using System.Windows.Forms;

B) Ajoutez deux attributs privés dans la classe:

// Instance de notre UserControl
private UserControl _UserControl;
// Instance sur la fenêtre qui contient notre UserControl
private Window _toolWindow;

C) Ajoutez à la fin de la méthode “OnConnection” le code ci-dessous:

else if  (connectMode != ext_ConnectMode.ext_cm_UISetup)
{
   try
   {
        object  obj = null;// Instance du  contrôle renvoyé par CreateToolWindow2
        Windows2 windows2 = this._applicationObject.Windows as Windows2;
        this._toolWindow = windows2.CreateToolWindow2(this._addInInstance,
                        Assembly.GetExecutingAssembly().Location,
                        "MyFirstAddIn.MyUserControl", // Nom du  contrôle
                           "MyFirstAddIn", // Nom du plugin
                      // Identificateur unique pour la nouvelle fenêtre.
                      "{84A3675C-CDA0-4c8b-858F-8F00BEACF199}",
                      ref obj);
        this._UserControl = obj as  UserControl;
        this._toolWindow.Linkable = false;
        this._toolWindow.IsFloating = false;
  }
  catch  (Exception) // A  implémenter
  {
  }
}

D) Ajoutez dans la méthode “Exec” le code ci-dessous
juste avant le “handled = true;”:

this._toolWindow.Visible = true;

E) Compilez, exécutez, puis cliquez dans le bouton “MyFirstAddIn”
dans “Outils”.

Remarque: ne lancez jamais le plugin dans l’instance du Visual que vous
utilisez pour développer le plugin, sinon vous devrez redémarrer Visual.

Notre plugin est maintenant fonctionnel. Il ne reste qu’à implémenter
notre UserControl. Vous pouvez ainsi réaliser une multitude d’outil
pour améliorer la productivité dans votre organisation comme:

- Un client VIM intégré dans visual.
- Un client de messagerie instantané.
- Des outils de diagnostiques.
- Des “Profiler” de code.
- Un gestionnaire de documentation colaboratif.

Afin de gagner du temps, vous pouvez assigner un raccourcis clavier à
votre commande. Pour cela il suffit d’aller dans “Outils” puis “Options”.

Sélectionnez “Environnement –> Clavier”. Faites une recherche afin de retrouver
la commande. Dans notre cas la commande s’appelle “MyFirstAddIn.
Connect.MyFirstAddIn”. Il ne vous reste plus qu’à assigner un raccourcis.

18) Déployment du plugin.

Pour Déployer le plugin, il suffit de fournir la bibliothèque de classe
qui se trouve dans le répertoire de sortie du projet (Dans notre cas
“MyFirstAddIn.dll” ) Ainsi qu’un fichier XML avec l’extension “.AddIn”.

Ce fichier XML est visible dans l’explorateur de la solution.
Dans notre cas il s’appelle “MyFirstAddIn.AddIn”. Il suffit de le copier
dans le répertoire “Addins” de l’utilisateur voir ci-dessous:

Remarque: Un fichier est déjà existant dans votre répertoire.
Il s’agit du fichier utiliser par Visual pour déboguer votre application.

Attention, la seule réstriction c’est que la valeur contenue dans la
balise “Assembly” soit correct. La valeur doit pointer sur le chemin du
plugin que vous deployer. Ainsi le choix de l’emplacement du plugin
est à votre discretion.

Merci d’avoir suivi ce tutoriel.

Dans le prochain article, nous exploiterons un peu plus les possibilités
de Visual Studio (Lancement de compilation, automatisation de tâches,
parsing de code).

Code source du tutoriel : ICI

/// <summary>
/// String2Stream
/// </summary>
/// <param name="str">la chaine</param>
/// <returns>le flux</returns>
public static Stream String2Stream(string str)
{
  MemoryStream memStream = new MemoryStream();
  byte[] data = Encoding.Unicode.GetBytes(str);
  memStream.Write(data, 0, data.Length);
  return (memStream as Stream);
}

/// <summary>
/// CSVsplitter
/// </summary>
/// <param name="str">la chaine</param>
/// <param name="delimiter">le séparateur</param>
/// <param name="hasQuote">utilise les quotes</param>
/// <returns>tableau de chaines</returns>
public static string[] CSVsplitter(string str, char delimiter, bool hasQuote)
{
    if (!hasQuote) // Si il n'y a pas de "quote"
        return (str.Split(delimiter));
    // On remplace le séparateur pour éviter les conflits 
    // avec l'expression régulière
    str = str.Replace(delimiter, '¤');
    string[] tab = (new Regex('¤' + "(?=(?:[^\"]*\"\"[^\"]*\"\")*(?![^\"]+\"\"))",
                    RegexOptions.IgnorePatternWhitespace)).Split(str);
    // On retire les "quotes"
    for (int i = 0; i < tab.Length; ++i)
        tab[i] = (new StringBuilder(tab[i], 1,
                  tab[i].Length - 2, tab[i].Length - 2)).ToString();
    return (tab);
}