Partager via

Parallélisme avec Visual Studio 2010 : Introduction

  • Article

parallel computingBruno boucard

Bruno Boucard (boucard.bruno@free.fr) est spécialisé dans les technologies Microsoft, anime avec d'autres spécialistes le blog Développement parallèle de Microsoft France.

Cet article a été écrit sur la base de la version Community Technology Preview (CTP) d’Octobre 2008 de Visual Studio 2010.

 

 

 

 

L’évolution du matériel

Depuis déjà quelques années, nous constatons une évolution significative de l’offre processeurs proposée par les grands acteurs du marché. Les vagues successives des processeurs bi-cœurs et dernièrement quad-cœurs au détriment des processeurs mono-cœur se sont imposées sur le marché généraliste sans que personne ne s’en inquiète. Pourquoi les constructeurs ont-ils choisi de démocratiser des matériels qui ont longtemps été réservés aux serveurs applicatifs ? Y a-t-il derrière cette nouvelle donne des éléments profonds qui auraient échappé à la majorité des informaticiens ?

En 1965, Gordon Moore (co-fondateur d’Intel) observait que le nombre de transistors contenus dans un semi-conducteur disponible sur le marché, doublait tous les 18-24 mois. En d’autres termes les capacités techniques des ordinateurs s’amélioraient régulièrement, permettant aux programmes informatiques d'en tirer partie sur le plan de la rapidité d’exécution sans grandes modifications (souvent aucune). Ce constat a fait le bonheur de plusieurs générations d'informaticiens, au point que certains appelaient ce phénomène le « free lunch ».

Cependant, depuis quelques années les constructeurs ont été confrontés à des contraintes physiques fortes (chaleur & consommation) qui ne permettaient plus de respecter la loi de Moore. Ne pouvant plus croitre sur le plan de la puissance au même rythme, les constructeurs ont choisi de multiplier sur les cartes mères le nombre de cœurs (architecture multi-cœurs) afin de retrouver une croissance en puissance mais cette fois répartie sur les différents cœurs. Cependant, les programmes n’étant généralement pas adaptés pour exploiter plusieurs processeurs simultanément, les informaticiens ne peuvent plus bénéficier de l'avantage matériel (The Free Lunch Is Over: http://www.gotw.ca/publications/concurrency-ddj.htm) pour espérer des gains de rapidité significatifs. En d'autres mots, nos bon vieux programmes séquentiels ne gagneront plus autant en vitesse avec les prochains matériels. Dans ce contexte, pouvons-nous affirmer que le « free lunch » est définitivement révolu ? Pour enrayer cette catastrophe devons-nous engager une révision radicale de nos pratiques de développement ?

Conséquences chez les développeurs

Pour les développeurs, la prise en compte effective de ce changement technologique peut se révéler compliquée. Rappelons qu'il y a déjà une petite vingtaine d’années que les techniques de multithreading se sont intégrées dans un écosystème fortement séquentiel. Néanmoins, les détracteurs du parallélisme peuvent trouver de nombreuses raisons pour ne pas s'adapter à cette nouvelle donne. La culture séquentielle à l’origine de l’informatique peut être considérée comme la plus légitime. Nous sommes aussi certains que le cerveau humain éprouve des difficultés à raisonner en multitâches (même si c'est effectivement le cas) ce qui peut être vu comme un frein pour le passage en mode parallèle.

Cependant, même si le parallélisme reste complexe, nous disposons de quelques moyens pour  mieux le maîtriser. Dans son ouvrage Concurrent Programming on Windows, Joe Duffy nous explique que la mise en place de traitements parallèles dans une application ou un service, devrait donner lieu à des réflexions sur le découpage par contextes en fonction de leurs granularités respectives afin de cerner au plus tôt l’isolation des données éventuellement partageables. De plus nous disposons d'un vocabulaire pour qualifier nos données vis à vis de leurs affinités vis à vis du parallélisme. Par exemple les notions d'immuabilité ou de pureté permettent de désigner dans un sens plus fonctionnel le niveau d'adhérence  au parallélisme. Une structure de données immuable ne change pas après sa construction. Il s'agit d'une caractéristique très importante pour garantir des exécutions parallèles de bonne facture, car si les données ne subissent pas de mutation, il n'existe alors aucun risque de conflit si plusieurs threads y accèdent en même temps. Cela signifie que la synchronisation ne constitue plus un problème.

La motivation première de structurer ses applications de manière à circonscrire les portions de code potentiellement incompatible avec le parallélisme vis à vis de celles qui ne posent pas de problème. Pour ceux qui ont déjà pratiqué ces technologies, vous conviendrez qu'elles peuvent être très délicates à manipuler. Vous avez surement rencontré du code faisant une utilisation abusive de verrous exclusifs d'une zone mémoire (exécution ralentie par trop de contention), du code ne protégeant pas une zone mémoire partagée entre plusieurs threads (corruption des données débouchant sur des résultats aléatoires), des problèmes de cohérence du cache (entrainant des latences substantielles), ou bien des soucis d'inversion de priorité. Nous ne pouvons malheureusement pas éviter systématiquement tous ces problèmes, mais nous pouvons structurer nos applications afin de classifier la granularité des contextes identifiés en fonction du degré d’isolation exigé et du mode de communication impliqué au moment de la phase de modélisation. Ce découpage donne lieu à une taxonomie permettant de hiérarchiser en trois niveaux de granularité en fonction du type de contexte rencontré : Agent, Tâche, Données.

Modelisation

  • Agent. La plupart des programmes sont décomposables en agents indépendants. Un agent est un contexte fonctionnel ou un rôle/un acteur d’une granularité importante dont l’isolation de l’état est assurée par un système de communication asynchrone, comme un service communiquant via WCF ou bien une application comme Excel communicant via COM.
  • Tâche. Il arrive parfois qu’un contexte ait besoin de traiter plusieurs fois un jeu d’opérations. Bien que les tâches partagent des notions communes avec les agents, elles sont bien différentes sur le plan de l’isolation de l’état, car les tâches partagent intimement la notion d’état. En d’autres mots les tâches représentent des contextes d’une granularité plus fine que les agents et sont parfaitement adaptées pour subdiviser des traitements sur une architecture multi-cœurs. [ajouter la notion d'immuabilité ou de pureté]
  • Données. Les opérations sur les données sont généralement candidates à la parallélisassions lorsque celles-ci sont longues à traiter. On entend par traitement, des notions de transformation, de tri, de compression … Plus il y a de données à traiter, plus long sera le temps pour traiter l’ensemble. La parallélisassions des données est donc particulièrement efficace sur une architecture multi-cœurs offrant la granularité de plus petite taille.

Etre capable de discerner le bon niveau de granularité vis à vis des besoins fonctionnels est sans doute indispensable pour obtenir un logiciel correctement parallélisé. Néanmoins l'élégance de cette taxonomie ne doit pas nous contraindre dans notre structuration. Il est donc parfaitement envisageable qu'une tâche puisse communiquer avec un agent et vice versa. La motivation est la facilité de l'intégration du parallélisme et non de contraindre l'architecture logicielle.

Aujourd’hui, nous pouvons reconnaitre que les environnements de programmation comme les outils, les librairies offrent peu d’adhérence avec ces concepts. Comment s’assurer que la mise en parallèle de certaines parties du système est à la fois fiable et pertinente vis-à-vis du langage de programmation et de l’infrastructure matérielle. Définir avec certitude que les notions d’isolation, d’immuabilité ou de synchronisation sont correctement exprimées vis-à-vis du problème posé au regard des environnements, des langages, des outils sont des préoccupations essentielles que nous abordons difficilement faute d’un outillage adapté.

Dans le cas des langages C & C++ où l’héritage d’une culture séquentielle se comprend facilement (Les langages C puis C++ sont issus d’une philosophie très système inspirée par la plateforme UNIX AT&T originelle où la notion de multithreads n’existait pas), mais dont l’adaptation au multithreading est venue se superposer à un existant séquentiel, donnant lieu à un jeu d’APIs rudimentaires difficilement compréhensibles pour le développeur non système (les threads ont été introduits pour offrir un moyen de paralléliser du code sans avoir à créer un processus système, très couteux sur le plan des ressources du système d'exploitation). On constate avec le recul que de nombreux environnements se sont inspirés des interfaces vétustes originelles, plaçant le multithreading au rang des technologies réservées aux experts. Pour illustrer notre point, prenons l’exemple naïf d’une méthode dédiée à la multiplication de matrices.

void MatrixMult(int size, double** m1, double** m2, double** result)
{
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            result[i][j] = 0;
            for (int k = 0; k < size; k++) {
                result[i][j] += m1[i][k] * m2[k][j];
            }
        }
    }
}

Adaptons ce code afin d’exploiter les technologies actuelles de parallélisme en C++0x.

void MatrixMult(int size, double** m1, double** m2, double** result) {
  int N = size;                           
  int P = 2 * NUMPROCS; 
  int Chunk = N / P;                  
  HANDLE hEvent = CreateEvent(NULL, TRUE, FALSE, NULL);
  long counter = P;                     
  for (int c = 0; c < P; c++) {
    std::thread t ([&,c] {   
      for (int i = c * Chunk;
           i < (c + 1 == P ? N : (c + 1) * Chunk); i++) {
        for (int j = 0; j < size; j++) {
          result[i][j] = 0;
          for (int k = 0; k < size; k++) {
            result[i][j] += m1[i][k] * m2[k][j];
          }
        }
      }
      if (InterlockedDecrement(counter) == 0)
        SetEvent(hEvent);
    }); 
  }
  WaitForSingleObject(hEvent,INFINITE);
  CloseHandle(hEvent);
}

Sans être un experts du multithreading, vous conviendrez que cette nouvelle version est bien plus compliquée et regorge de défauts importants (Nous ne parlerons pas ici de l’expression lambda du C++0x similaire au lambda en C# 3.0 quoique plus puissante, ni de l'implémentation standard des threads actuellement non disponible dans la version de la CTP d'octobre de Visual Studio 2010): le partitionnement statique du traitement sans adhérence avec le nombre de CPU présents sur la machine courante, un mécanisme de synchronisation trop intrusif et très coûteux sur le plan des ressources (surcharge CPU provoquée par des passages fréquents du mode utilisateur en mode noyau), un usage direct de l’entité thread couplée au système d’exploitation entraînant des coûts substantiels pour le système d’exploitation (1 Mo de mémoire par thread).

Du côté de la plateforme .NET, le constat est quasi similaire. Le Framework .NET n'échappe pas à l’héritage de la culture séquentielle, mais son incarnation est relativement moins rugueuse qu'en langage C/C++. Par nature le code géré est plus simple à appréhender, cependant il reste compliqué lorsqu'on parle de parallélisme. Pour illustrer notre point, prenons l’exemple naïf d’une méthode dédiée à la recherche de bébés.

IEnumerable<BabyInfo> Search(IEnumerable<BabyInfo> babies, QueryInfo qi) 
{
    var results = new List<BabyInfo>();
    foreach(var baby in babies)
    {
        if (baby.Name == qi.Name &&
            baby.State == qi.State &&
            baby.Year >= qi.YearStart &&
            baby.Year <= qi.YearEnd)
        {
            results.Add(baby);
        }
    }
    results.Sort((b1, b2) => 
        b1.Year.CompareTo(b2.Year));

    return results;
}

Adaptons ce code afin d’exploiter les technologies actuelles de parallélisassions.

IEnumerable<BabyInfo> Search(IEnumerable<BabyInfo> babies, QueryInfo qi) 
{
    var results = new List<BabyInfo>();
    int partitionsCount = Environment.ProcessorCount;
    int remainingCount = partitionsCount;
    var enumerator = babies.GetEnumerator();

    try {
      using (var done = new ManualResetEvent(false)) {
        for(int i = 0; i < partitionsCount; i++) {
          ThreadPool.QueueUserWorkItem(delegate {
            var partialResults = new List<BabyInfo>();
            while(true) {
              BabyInfo baby;
              lock (enumerator) {
                if (!enumerator.MoveNext()) break;
                baby = enumerator.Current;
              }
              if (baby.Name == qi.Name && baby.State == qi.State &&
                  baby.Year >= qi.YearStart && baby.Year <= qi.YearEnd) {
                partialResults.Add(baby);
              }
            }
            lock (results) results.AddRange(partialResults);
            if (Interlocked.Decrement(ref remainingCount) == 0) done.Set();
          });
        }
        done.WaitOne();
        results.Sort((b1, b2) => b1.Year.CompareTo(b2.Year));
      }
    }
    finally 
    { 
      if (enumerator is IDisposable) ((IDisposable)enumerator).Dispose(); 
    }

    return results;
}

Encore une fois sans être un expert du multithreading, vous conviendrez que cette nouvelle version est bien plus compliquée et regorge de défauts importants: un mécanisme de synchronisation trop intrusif et très coûteux sur le plan des ressources (surcharge CPU provoquée par des passages fréquents du mode utilisateur au mode noyau), un usage direct de l’entité thread couplée au système d’exploitation entraînant des coûts substantiels pour le système d’exploitation.

Pour conclure, ces deux exemples montrent que le besoin d'améliorer l'offre programmatique à la fois en .NET et natif est complètement justifiée. Nous ne pourrons pas développer à grande échelle des applications parallèles avec ce type de technologies.

Si nous abordons l’offre multitâche sur le plan des outils, comme les débuggeurs ou les profileurs, les difficultés s’épaississent. Les outils du marché adaptés au multithreading offrent une acuité réservée aux experts du domaine. Comprendre qui fait quoi ou qui attend quoi, relève souvent d’une enquête policière parfois même du cauchemar.

Tous ces éléments ont élevé la programmation multitâche au rang de pratiques obscures, difficiles et complexes pour de nombreux développeurs. Comme nous l’avons mentionné précédemment la standardisation des processeurs multi-cœurs sur le marché grand public à rendu urgent le besoin d’une démocratisation des technologies de programmation parallèle.

L’initiative parallèle de Visual Studio 2010

Pour répondre aux problèmes énoncés précédemment, Microsoft s’est engagé à travers une initiative globale afin de transformer l'écosystème Microsoft en monde parallèle : Parallel Computing Initiative. L’objectif est de fournir une suite logicielle  (langages, outils, plateformes) de grande envergure permettant de satisfaire les demandes les plus courantes dans le contexte du parallélisme, allant des traitements sur le poste client au super calculateur sur des matériels spécialisés.  

L’objectif de cet article n’est pas d’illustrer l'ensemble de l’offre Parallel Computing Initiative, mais plutôt de souligner l’engagement très important des équipes Microsoft qui marque le début d'une nouvelle ère pour les plateformes Microsoft. Dans le cadre plus restreint de Visual Studio, l’objectif est simple : offrir l’accès à la programmation parallèle pour tous. En d'autres termes, la prochaine version de Visual Studio devrait permettre d’écrire des applications qui exploitent au mieux la croissance des multi-cœurs sans que nous ayons besoin de modifier une seule ligne de code.

Pour réussir un tel pari, Microsoft prépare, au sein de Visual Studio, une suite logicielle permettant de développer,  de déboguer et d’analyser des applications parallèles à la fois en natif et en .NET sans que cela tourne au cauchemar ou réclame une expertise spécifique. C’est naturellement un énorme challenge, mais c’est aussi une grosse attente des développeurs d’aujourd’hui. Pour apprécier cette prochaine offre au mieux, il est important de comprendre le découpage de l'offre de parallélisassions.

Plateforme d’execution parallèle**
Plateforme d’exécution parallèle, librairies et outils de Visual Studio 2010**

L’offre programmatique se divise en deux catégories, les librairies disponibles : Native (C++) et .NET (tous les langages ciblant le Framework .NET 4.0), sachant que l’outillage est mutualisé pour les deux catégories. Nous déclinons les services fournis en fonction des différents niveaux de granularité afin de clarifier l’usage des librairies proposées.

Granularité Librairie Native Librairie .NET
Agent Agent Library  
Tâche Parallel Pattern Library Task Parallel Library
Données   Task Parallel Library,
Parallel LINQ

Dans la version actuelle, c'est-à-dire la CTP courante de Visual Studio 2010, nous ne disposons pas de librairies couvrant tous les cas de granularité. Cependant c’est essentiellement le niveau Tâche, présent dans les deux cas, qui est le plus souvent réclamé pour réaliser des programmes parallèles sur une architecture multi-cœurs. Reprenons l’exemple C++ étudié précédemment. Nous pouvons illustrer l’usage de la librairie « Parallel Pattern Library » afin de paralléliser élégamment ce code.

void MatrixMult(int size, double** m1, double** m2, double** result)
{
   parallel_for(0, size, 1, [&](int i) {
        for (int j = 0; j < size; j++) {
            double temp = 0;
            for (int k = 0; k < size; k++) {
                temp += m1[i][k] * m2[k][j];
            }
            result[i][j] = temp;
        }
   });
}

Le code parle de lui-même, il est à fois plus court et plus simple à comprendre. La sémantique fonctionnelle n’est pas altérée par une plomberie technologique intrusive. L’instruction parallel_for nous offre une abstraction suffisante pour ne plus avoir besoin de gérer de threads natifs.  Le partitionnement n’existe plus, car le moteur d’exécution sous-jacent adaptera le nombre de threads physiques nécessaires.

Reprenons l’exemple C# étudié précédemment. Nous pouvons illustrer l’usage de la librairie « Parallel LINQ » afin de paralléliser élégamment ce code.

IEnumerable<BabyInfo> Search(IEnumerable<BabyInfo> babies, QueryInfo qi)
{

    var results = from baby in babies.AsParallel()
                  where baby.Name == qi.Name &&
                        baby.State == qi.State &&
                        baby.Year >= qi.YearStart &&
                        baby.Year <= qi.YearEnd
                  orderby baby.Year ascending
                  select baby;
    
    return results.ToList();
}

La libraire PLINQ est particulièrement adaptée pour paralléliser des données. Dans notre cas le résultat est flagrant. En d’autres mots notre programme à la fois plus simple à maintenir et plus performant, tiendra compte automatiquement des processeurs présents et augmentera sa vitesse de traitement en fonction du nombre de processeurs disponibles.

Conclusion

Vis-à-vis de la question posé en ce début d'article, on peut noter que nos exemples C++ et C# une fois adaptés à la prochaine version de Visual Studio semblent être capables d’augmenter leurs performances en fonction de la puissance disponible (aujourd'hui le nombre de cœurs). Ce comportement n’est pas sans rappeler l’époque où la loi de Moore offrait un diner gratuit à tous.

Néanmoins, l'introduction des technologies parallèles au sein d'une nouvelle application ou d’une application existante reste une tâche délicate. L'effort de structuration de vos programmes vis à vis des contraintes qu'apportent le parallélisme doit être pris en compte au plus tôt. Cependant, les pièges rencontrés seront malgré tout  plus faciles à déjouer avec la prochaine version de Visual Studio 2010, mais nous aurons l'occasion d'y revenir prochainement.

Ressources