Nous poursuivons ce mois-ci les raisons pour passer à la programmation parallèle et
surtout les pièges à éviter et à maîtriser. Et ils sont nombreux !
Deadlock

Parfois nommé étreinte fatale, le deadlock est provoqué par des threads mutuellement verrouillés. Cette situation peut être comparée à deux personnes dessinant des diagrammes tout en se partageant un crayon et une règle. Si une personne prend le crayon et l'autre prend la règle, un blocage se produit lorsque la personne avec le crayon a besoin de la règle pour terminer son travail alors que la personne avec la règle a besoin du crayon pour terminer son travail à son tour. Les deux demandes ne peuvent être satisfaites, un blocage se produit. Pour de nombreux développeurs l'ouvrage sur les Design Patterns du fameux Gang of Four est sans aucun doute un ouvrage de référence pour tous les développeurs. Avezvous déjà tenté de passer en parallèle un des patterns du GoF ? Par exemple l'Observer. Lors d'une présentation chez Microsoft Research, Edward A. Lee, chercheur et professeur en informatique à l'université UC Berkeley, a montré que l'utilisation de mutex peut rapidement aboutir à des étreintes fatales potentielles. Voici le fragment Java illustrant ce problème.

public synchronized void addListener(listener listener)
{
myListeners.add(listener);
}
public synchronized void setValue(String newValue) {
myValue = newValue;
for (int i = 0; i < myListeners.length; i++) {
myListeners[i].valueChanged(newValue);
}
}

En protégeant les méthodes addListener et setValue à l'aide du mot clef synchronized, on pourrait croire que le code ci-dessous supporte une utilisation partagée par plusieurs threads. Mais supposons que la méthode valueChanged () cherche à obtenir un verrou sur un autre objet. Si le titulaire de ce verrou appelle la méthode addListener(), alors nous tombons dans le cas d'une étreinte fatale ! Cet exemple illustre une recommandation en programmation parallèle : conservez des sections synchronisées les plus courtes possibles.

Livelock

Le livelock provoque une situation de famine entre des threads qui
se disputent des ressources partagées limitées souvent illustré par
le fameux Dîner des philosophes. La situation est la suivante : cinq
philosophes se trouvent autour d'une table. Chacun des philosophes
a devant lui un plat de spaghetti et à gauche de chaque assiette se trouve une baguette. Un philosophe n'a que trois états possibles :
• Penser pendant un temps indéterminé
• Etre affamé (pendant un temps déterminé et fini sinon il y a famine)
• Manger pendant un temps déterminé et fini

Lorsqu'un philosophe a faim, il va se mettre dans l'état affamé et attendre que les baguettes soient libres pour manger. Un philosophe a besoin de deux baguettes : celle qui se trouve à gauche de sa propre assiette et celle qui se trouve à gauche de celle de son voisin de droite (c'est-à-dire les deux baguettes qui entourent sa propre assiette). Si un philosophe n'arrive pas à s'emparer d'une baguette, il reste affamé pendant un temps déterminé, en attendant de renouveler sa tentative. Le problème consiste à trouver un ordonnancement des philosophes tel qu'ils puissent tous manger, chacun à leur tour. Une solution à base de sémaphores, énoncée par Dijkstra, est souvent utilisée en programmation parallèle. Le dîner des philosophes est souvent l'objet d'examens informatiques. Voici une implémentation Java du dîner des philosophes soumis dans le cadre d'un examen informatique en 2005.

import java.util.ArrayList;
import java.util.Random;
class Dining {
Random r;
ArrayList p;
ArrayList c;
static final int NUM_PHIL=5;
Dining() {
p = new ArrayList();
c = new ArrayList();
r=new Random();
for (int i=0;i c.add(new Baguette());
}
for (int i=0;i p.add(new Philosophe(i));
}
}
public void eat() {
for (Philosophe phil : p) {
phil.start();
}
}
class Philosophe extends Thread {
Baguette gauche;
Baguette droite;
int idx;
Philosophe(int idx) {
super();
gauche=c.get(idx);
droite=c.get((idx+1)%NUM_PHIL);
this.idx=idx;
}
public void run() {
while (1==1) {
try {
sleep(r.nextInt(1000));
gauche.get();
System.out.println("Le philosophe " + (idx+1) + " a pris
la baguette a gauche");
sleep(r.nextInt(1000));
droite.get();
System.out.println("Le philosophe " + (idx+1) + " a pris
la baguette a droite");
System.out.println("Le philosophe " + (idx+1) + " a mange!");
sleep(r.nextInt(1000));
gauche.put();
System.out.println("Le philosophe " + (idx+1) + " a remis
la baguette a gauche");
droite.put();
System.out.println("Le philosophe " + (idx+1) + " a remis
la baguette a droite");
} catch (Exception e) {
System.out.println(e);
}
}
}
}
class Baguette {
private boolean taken=false;
private int identity;
Baguette () {
}
synchronized void put() {
taken=false;
notify();
}
synchronized void get() throws java.lang.InterruptedException {
while (taken) wait();
taken=true;
}
}
public static void main(String [] args) {
Dining d = new Dining();
d.eat();
}

Cette question est en 2 parties :
• Définissez clairement le concept de deadlock dans les systèmes multi threads. Expliquez comment un deadlock pourrait se produire dans le programme. Soyez très précis et expliquez clairement où le deadlock se produirait dans le programme (rapportez les lignes exactes de cela dans le code vu plus haut) et pourquoi (l'ordonnancement des évènements qui causerait le blocage.)
• Faites les changements nécessaires à public void run() et à la classe Baguette de manière à ce qu'il n'y ait plus de deadlock. Il se peut que vous trouviez cela difficile. Si vous n'y arrivez pas, assurez-vous au moins d'expliquer clairement votre stratégie.

L'intérêt ici n'est pas de répondre aux questions posées mais de
juger de la difficulté pour y répondre. Malheureusement il existe bien d'autres problèmes encore un peu plus subtils dont les conséquences peuvent être désastreuses. Tous ces problèmes rendent la programmation parallèle très difficile et souvent repoussante pour les développeurs.

Pourquoi les codes parallèles sont-ils difficile à maintenir ?

Un autre point regrettable avec l'usage des technologies actuelles est la complexité d'écriture pour implémenter du code parallèle. Pour illustrer ce point, prenons deux exemples. Le premier implémente une méthode naïve en C++0x 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];
}
}
}
}

Le second exemple implémente cette fois en C# une méthode dédiée à la recherche multicritères dans une liste mémoire de bébés.

IEnumerable Search(IEnumerable babies, Query
Info qi)
{
var results = new List();
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 ces codes afin d’exploiter les technologies parallèles actuelles. En premier le code C++.

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);
}

En second le code C#.

IEnumerable Search(IEnumerable babies, Query
Info qi)
{
var results = new List();
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();
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;
}

Sans être un expert du multithreading, vous conviendrez que ces nouvelles versions sont bien plus compliquées et regorgent de défauts importants : 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 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 (1 Mo de mémoire par thread). On note que 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++. Par nature, le code géré est plus simple à appréhender, cependant il reste compliqué lorsqu'on parle de parallélisme.
"Des logiciels écrits avec des threads, des sémaphores, et des mutex sont incompréhensibles pour les humains et ne devraient pas être dignes de confiance.": Edward A. Lee chercheur/professeur en informatique à l'université UC Berkeley.

Pourquoi les entreprises boudent-elles le parallélisme ?

Du côté des entreprises, la crise actuelle n'est pas forcément propice pour tenir compte de cette évolution matérielle. Nous venons d'un univers où les Hertz nous apportaient régulièrement un surplus de puissance et le récent passage à des matériels multi-coeurs pour tous les postes de travail, passe relativement inaperçu auprès des DSI. Pour les entreprises, les développeurs doivent avant tout se concentrer sur leur métier en conjuguant technique et fonctionnel, et non sur des problèmes de programmation parallèle qui sont incompatibles avec leurs attentes. En effet, les problèmes de multithreading sont chronophages et risqués. Comment être certain que les tests seront fiables alors que le multithreading est par nature indéterminisme ? Comment s'assurer que la qualité du produit final est conforme aux attentes de toutes les plates-formes d'exécution que le produit rencontrera au cours de son existence ? Pour toutes ces raisons, les entreprises, en général, ne sont pas encore prêtes pour que les équipes de développement tirent parti des nombreux coeurs qui équiperont leurs prochains achats. Quelques rares cas, où traditionnellement les besoins fonctionnels réclament des performances élevées (moteurs de recherche, éditeurs de bases de données, site web d'une audience mondiale, Imagerie médicale ...), font exception car ils disposent déjà d’experts sur le sujet. Notons que la société Evans Data, cabinet d'analyse, rapporte, dans une étude sur les habitudes des développeurs mondiaux, que sur les six derniers mois de 2008, seulement 3 % des développeurs auraient introduit dans leur code des instructions capables de gérer le parallélisme des multi-coeurs.

Les entreprises se tourneront vers le parallélisme lorsque le marché sera mature

Le passage à la programmation parallèle pour l'essentiel des entreprises sera sans doute long et coûteux. La mise à niveau des développeurs applicatifs est essentielle mais elle ne se fera que lorsque les offres de programmation permettront de développer du code parallèle sans être un expert du sujet. Les offres actuelles sont à la fois trop rugueuses et trop compliquées pour qu'un développeur applicatif puisse en tirer parti facilement. Enfin, même en disposant de nouvelles offres de programmation moins élitistes, le besoin de formation sera sans doute nécessaire. D'un côté, les universités et les écoles devront augmenter la part des cours consacrés à la programmation parallèle. D'un autre côté, les établissements de formation devront ajouter à leur catalogue des formations permettant de développer en parallèle efficacement. L'objectif sera de permettre à une large audience de développeurs d’acquérir des connaissances suffisantes pour produire du code parallèle de bonne qualité sans être un expert du sujet.
Il est parfaitement imaginable que de nombreuses entreprises décident de se lancer dans des projets de migration pour adapter leurs codes séquentiels au monde parallèle. Lorsque ce moment viendra, les offres logicielles permettant de développer plus facilement du code parallèle devront être disponibles pour une large population de développeurs. Ces prochaines offres devront non seulement proposer de nouveaux modèles de programmation, mais aussi de nouveaux outils afin de faciliter la mise au point, les tests, le profilage des codes parallèles. Naturellement, ces prochains outils devront être accessibles au plus grand nombre de développeurs. C'est donc un énorme challenge que doivent résoudre les éditeurs de logiciels de développement.

En conclusion

Comme nous l’avons mentionné, la banalisation des processeurs multi-coeurs sur le marché grand public a rendu urgent le besoin d’une démocratisation des technologies de programmation parallèle. Les développeurs ne pourront pas développer à grande échelle des applications parallèles avec les offres actuelles. La balle est donc bien dans le camp des éditeurs logiciels qui se doivent de faciliter la programmation parallèle. Les langages plus populaires que sont Java, .NET et C++ doivent recevoir de la part des éditeurs de langages des solutions qui adressent un public large. Dans un premier temps, ces nouvelles offres ne suffiront néanmoins pas à rendre autonomes des millions de développeurs. Sur le plan de l'architecture logicielle, de nouvelles règles devront êtres apprises sur la manière de modéliser ou de penser les algorithmes parallèles. Les écoles, les universités et les établissements de formation devront accompagner cette mutation technologique qui s'étalera sans doute sur plusieurs décennies. Nous sommes donc face à un point d'inflexion qui engage toute l'industrie informatique à réviser ses modèles techniques. Les conséquences sur notre économie sont difficiles à prévoir, mais faisons confiance à l'imagination humaine pour trouver de nouveaux usages tirant parti de cette nouvelle donne technologique.

Ressources

• Loi de Moore: http://fr.wikipedia.org/wiki/Loi_de_Moore
• Intel micro architecture Netburst: http://fr.wikipedia.org/wiki/NetBurst
• The Free Lunch is Over: http://gotw.ca/publications/concurrency-ddj.htm
• Intel processeur Nehalem: http://fr.wikipedia.org/wiki/Nehalem
• Principe d'incertitude: http://fr.wikipedia.org/wiki/Principe_d'incertitude
• Dîner des philosophes: http://fr.wikipedia.org/wiki/D%C3%AEner_des_philosophes
• Making Concurrency Mainstream: http://ptolemy.eecs.berkeley.edu/~eal/videos/EALatMSR_Jan07/lecture.htm
• Résolution de 11 problèmes possibles dans votre code multithread:
http://msdn.microsoft.com/fr-fr/magazine/cc817398.aspx
• Windows 7 capable de gérer 256 coeurs: http://blogs.msdn.com/devpara/
archive/2009/03/09/windows-7-et-le-concurrency-runtime.aspx
• Le b-a ba du développement parallèle avec la plate-forme .NET:
http://msdn.microsoft.com/fr-fr/vcsharp/dd582579.aspx
• Pourquoi les développeurs boudent le multi-coeur: http://www.lemagit.fr/article/processeur-developpement-parallelisme/2369/1/pourquoi-les-developpeurs-boudent-multi-coeur/

? 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: http://blogs.msdn.com/devpara
/default.aspx

IntelliJ IDEA 12.1

Intel : vers de meilleurs expériences mobiles

Arrêtez le chasse-neige, programmez parallèle avec TBB
Threading Building Block est une librairie qui a pour but d'offrir une interface agréable pour les développeurs en C++ qui souhaitent paralléliser leur code. Agréable, car vous avez la liberté de rester à un haut niveau d'abstraction, garder une formulation objet fonctionnelle et de ne pas vous intéresser aux détails d'implémentation. Le croirez-vous, modélisation objet et performance ne sont cette fois-ci pas incompatibles, bien au contraire. Le fait de définir avec précision les données du problème en mode objet sans entrer dans les détails techniques donne à la librairie tout ce dont...

Pourquoi passer à la programmation parallèle ? (2ème partie)
Nous poursuivons ce mois-ci les raisons pour passer à la programmation parallèle et surtout les pièges à éviter et à maîtriser. Et ils sont nombreux ! Deadlock Parfois nommé étreinte fatale, le deadlock est provoqué par des threads mutuellement verrouillés. Cette situation peut être comparée à deux personnes dessinant des diagrammes tout en se partageant un crayon et une règle. Si une personne prend le crayon et l'autre prend la règle, un blocage se produit lorsque la personne avec le crayon a besoin de la règle pour terminer son travail alors que la personne avec la règle a besoin...

Pourquoi passer à la programmation parallèle
A l’occasion de la sortie d’Intel Parallel Studio et des nombreuses avancées que les éditeurs préparent pour 2009 et 2010, Programmez ! vous propose de mieux comprendre la programmation adaptée aux processeurs à plusieurs coeurs. C’est ce que l’on appelle la programmation parallèle. C’est- à-dire capable d’exécuter plusieurs opérations, instructions, parallèlement sur plusieurs processeurs ou plusieurs coeurs. Complexe à maîtriser, le parallélisme est le mont Everest du développement. Nous vous proposons de l’aborder méthodiquement en posant les fondamentaux pour bien l’assimiler et éviter...

Version finale : Intel Parallel Studiodébarque
La programmation est l’art de schématiser et simplifier un processus pour l’automatiser. Nous aboutissons donc le plus souvent à un code sériel. Avec l’arrivée de puces multi-core, et bientôt massivement multi-core cette approche atteint ses limites : Il vous faut passer à la programmation parallèle. N’ayez crainte, Intel est là pour vous aider avec un ensemble logiciel aussi convivial que complet : Intel Parallel Studio. Le parallélisme se conçoit à plusieurs niveaux, mais celui qui nous intéresse ici est le " thread ". Intel Parallel Studio est un ensemble de logiciels pour vous aider à...

Intel Parallel Studio : Vous ne reconnaîtrez plus votre C++
Dans les deux précédents articles sur Intel Parallel Studio, nous nous sommes intéressés aux outils Inspector et Amplifier qui permettent respectivement de corriger et accélérer vos logiciels parallèles. Mais nous n'avons pas encore abordé Composer, qui est le compilateur associé à diverses librairies comme Intel Threading Building Blocks et Intel Performance Primitives (TBB et IPP). De nos jours, un compilateur ne peut se contenter de produire un binaire minimaliste, même optimisé. Il doit vous aider à adopter une syntaxe plus claire, apporter un éclairage nouveau sur votre code et...

Plus de coeurs, plus rapide, plus scalable : du multi-core au " many-core ”
Ecrire des applications parallèles se simplifie, et nous avons vu précédemment que chasser les bugs parallèles était rapide et intuitif avec Intel Parallel Inspector. Reste maintenant le principal problème : utiliser pleinement tous les coeurs simultanément. Une station de travail multi-core a typiquement 8 coeurs, 16 vus par l’OS avec la nouvelle technologie SMT (Simultaneous Multi Threading) et dans l’avenir beaucoup plus. Le consensus actuel dans l’industrie des processeurs est que les gains de performance viendront essentiellement par l’ajout de coeurs : nous sommes à l’orée de l’ère...

La chasse aux bogues parallèles avec Intel Parallel Inspector
Nous avons été formés à programmer en mode sériel et passer à la programmation parallèle n'a rien d'évident, mais plusieurs technologies existent pour vous faciliter la vie : Intel Threading Building Blocks ou le standard OpenMP par exemple. Une fois les concepts de base assimilés, implémenter un programme parallèle qui utilise à peu près efficacement un processeur à deux ou quatre coeurs va assez vite si votre algorithme s'y prête. Mais il est surtout très facile de transformer un logiciel sériel sans bogue en un logiciel multithreadé fortement bogué sans que ce soit évident, ni à...

Intel Parallel Studio: simplifier le développement parallèle !
Alors que les processeurs multi-cores (multi-coeurs) prolifèrent, améliorer les performances logicielles, et mieux utiliser la puissance processeur, demeure un enjeu important pour rester compétitif, surtout pour les applications développées en C ou C++. Mais jusqu’à présent le développement parallèle restait complexe à aborder pour le développeur. Programmez ! vous invite à découvrir en avant-première la nouvelle solution Intel, avec un tout nouveau plug-in Visual Studio, qui va radicalement changer votre vision du développement parallèle. L’année 2009 sera non seulement l’année de la...