A quand une AI capable de compiler du code séquentiel, et de le transformer en code parallèle quand c'est possible ?
Il y a des ébauches, certes, mais c'est toujours très primitif. (Genre en utilisant les SIMDs ... il faudrait des AIs, capable de comprendre le code dans sa sémantique, et de le transformer en code parallèle.)
Mais on peut encore rêver.
Le code parallèle sur CPU (ou calcul distribué) est une vraie corvée, d'autant plus que maintenant c'est une obligation physique de paralléliser, de distribuer les calculs sur plusieurs cœurs (ou processeurs, ce qui revient au même).
Les deadlocks, venant d'une synchronisation des tâches male conçue, engendrent des freezes (blocage des processeurs à cause de deux tâches qui s'attendent mutuellement), des résultats faux, et le débogage est extrêmement difficile pour le calcul parallèle.
De plus, un usage mauvais des mécanismes de synchronisation peut engendrer tout l'inverse d'une optimisation multi threads. Mal employés, les threads peuvent passer plus de temps à s'attendre qu'à exécuter le code.
C'est une corvée à cause de l'obligation d'utiliser des mutexes, des sections critiques, des sémaphores, qui permettent de synchroniser les tâches entre elles. C'est très difficile de gérer ces mécanismes. Et sources de bugs ou de blocages, carrément.
La seule solution qu'on ait c'est d'être d'une rigueur stalinienne quand on les utilise. Il ne faut pas compter sur le débogage.
Et quand ça plante, c'est pas juste une image mal placée, c'est carrément le plantage fatal de l'application. Ou bien l'application ne plante pas, mais freeze (elle se gèle, se bloque), et dans ce cas on ne peut pas utiliser le débuggeur car l'appli ne plante pas à proprement parler, mais les OS détectent dans ce cas que l'application ne répond pas, et la seule chose à faire c'est de la shooter, de l'arrêter brutalement, ce qui n'est jamais bon pour la stabilité de l'OS.
(Après on peut quand même déboguer les deadlocks en suivant les piles d'appels (call stacks) de chaque thread pour voir où ils ont lieu, mais c'est franchement galère)
En Java, il y a trois possibilités pour synchroniser des tâches parallèles :
-La première, c'est le préfixe synchronized devant une méthode.
C'est comme si la méthode était encapsulée dans une section critique : seul un thread à la fois peut exécuter cette méthode.
-La deuxième, c'est le préfixe volatile devant la déclaration d'une variable (appelée aussi attribut ou propriété) de classe.
La variable ne peut être manipulée que par un thread à la fois. Cela reviendrait à utiliser une unique section critique sur les accesseurs de ladite variable. (une seule section critique pour les 2 accesseurs (getter et setter))
D'ailleurs dans ce cas il faudrait plutôt parler de mutex que de section critique, même si c'est la même chose finalement. Conceptuellement, une section critique ne s'applique qu'a une portion de code. En fait c'est plus puissant que ça, la section critique synchronise en utilisant son adresse, et non celle du code. Donc elle peut être utilisée pour des portions de code différentes en même temps, à la fois. On peut l'utiliser de manière unique pour plusieurs portions de codes. Le mutex n'est qu'une simple mise en forme objet d'une section critique.
-Enfin, tous les objets Java ont une méthode join(), qui permet d'attendre, et de savoir quand une tâche est terminée. Cette dernière solution n'est pas encore très claire pour moi, donc je ne peux pas
développer. Mais je vais me renseigner car j'en ai besoin actuellement. Tout ce que je sais, c'est que ça permet d'attendre que plusieurs tâches aient fini leur besogne avant de continuer le programme.
L'API C de Windows implémente les fonctions WaitForSingleObject() et WaitForMultipleObjets(), pour lesquelles il faut préciser le ou les thread(s) concerné(s). C'est équivalent : ça bloque le processus principal jusqu'à ce que tous les threads envoient un événement comme quoi ils ont fini.
Il y a aussi une solution alternative à volatile, c'est le préfixe atomic, quand on est sûr que la variable n'est accédée qu'en lecture. C'est beaucoup plus léger, et cela assure que la variable soit toujours lue en intégralité par chaque thread.
C'est comme si on mettait une section critique sur seulement l'accesseur getter.
Comment se passe la synchronisation de tâches ?
Quand un thread entre dans une section critique, il prévient l'OS que cette portion de code est "occupée" et si d'autres threads veulent l'exécuter, ils sont mis en pause. Et quand le thread sort de la section critique, l'OS réveille un nouveau thread, celui qui a le plus attendu en général, ou celui de priorité supérieure, ou les deux combinés (mais cela dépend de l'heuristique de l'OS), et qui était en attente.
C'est comme pour nous quand on va faire les courses en ce moment de confinement : un client à la fois dans le commerce.
Le client entre et fait sa popotte, tous les autres attendent. Dès qu'il sort du commerce, on laisse entrer un autre.
Juste pour préciser, c'est l'OS qui gère les sections critiques, mais c'est au développeur de les définir.
Le développeur n'a juste qu'à dire quand on entre et sort d'une section critique. Même bas-niveau, c'est l'OS qui gère tout en se débrouillant avec ça.
Sans rentrer dans les détails, on peut faire des objets appelés mutexes avec (je crois qu'en français on appelle ça des verrous), qui permettent de réguler l'accès aux différentes ressources partagées par plusieurs threads.
Le mot mutex est un mot valise pour "mutually exclusive" ( tasks), une tache exécute et rejette toute autre, qui est placée en attente. L'OS réveille l'une des tâches selon son heuristique quand la première tâche débloque le mutex.
C'est comme le portique dans le métro.
Un exemple d'implémentation C++ pour Windows :
Code : Tout sélectionner
#pragma once
#include <windows.h>
class Mutex
{
protected:
CRITICAL_SECTION cs;
public:
Mutex(void)
{
InitializeCriticalSection(&cs);
}
void lock()
{
EnterCriticalSection(&cs);
}
void unlock()
{
LeaveCriticalSection(&cs);
}
~Mutex(void)
{
DeleteCriticalSection(&cs);
}
};
Edit:
Il y a le langage OCAM, qui permet de coder en parallèle comme en série, sans s'embarrasser de ces mécanismes de synchronisation, mais il est trop bas niveau pour l'employer pour faire des jeux, ou des applications grand public...
Un exemple d'implémentation de boucle parallèle en C++ pour Windows :
Code : Tout sélectionner
#pragma once
#include <windows.h>
#include <vector>
using namespace std;
#include "criticalsection.h"
typedef void (*LOOP_FUNC)(int index,void * params);
typedef bool (*FIND_FUNC)(int index,void * params);
class MultiThreadedLoop
{
protected:
bool exitRequested;
bool indexFound;
HANDLE doneEvent;
int doneCount;
int foundIndex;
CriticalSection CScount;
struct ThreadParams
{
int firstIndex;
int firstOutIndex;
HANDLE threadHandle;
HANDLE startEvent;
MultiThreadedLoop * pool;
};
static void find(ThreadParams * params)
{
FIND_FUNC f=params->pool->findFunction;
void * p=params->pool->findFunctionParams;
for (int i=params->firstIndex;i<params->firstOutIndex && !params->pool->indexFound;i++)
if (f(i,p))
{
params->pool->foundIndex=i;
params->pool->indexFound=true;
}
}
static UINT threadFunction(ThreadParams * params)
{
while (true)
{
WaitForSingleObject(params->startEvent,INFINITE);
if (params->pool->exitRequested) return 0;
int i;
switch(params->pool->mode)
{
case FIND:
find(params);
break;
case LOOP:
for (i=params->firstIndex;i<params->firstOutIndex;i++)
params->pool->loopFunction(i,params->pool->loopFunctionParams);
break;
};
params->pool->CScount.lock();
params->pool->doneCount--;
if (!params->pool->doneCount) SetEvent(params->pool->doneEvent);
params->pool->CScount.unlock();
}
return 0;
}
vector<ThreadParams> threadParams;
LOOP_FUNC loopFunction;
FIND_FUNC findFunction;
void * loopFunctionParams;
void * findFunctionParams;
enum MODE {LOOP,FIND} mode;
public:
MultiThreadedLoop()
{
};
~MultiThreadedLoop()
{
release();
};
bool init(int nbThreads=0)
{
if (!threadParams.empty()) release();
SYSTEM_INFO systemInfo;
GetSystemInfo(&systemInfo);
if (nbThreads<1) nbThreads=systemInfo.dwNumberOfProcessors;
doneEvent=CreateEvent(NULL,FALSE,FALSE,NULL);
if (doneEvent==NULL) return false;
exitRequested=false;
threadParams.resize(nbThreads);
for (int i=0;i<nbThreads;i++)
{
threadParams[i].startEvent=CreateEvent(NULL,FALSE,FALSE,NULL);
threadParams[i].pool=this;
threadParams[i].threadHandle=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)threadFunction,&threadParams[i],0,NULL);
if (threadParams[i].threadHandle==NULL || threadParams[i].startEvent==NULL)
{
exitRequested=true;
for (int j=0;j<i;j++)
{
SetEvent(threadParams[j].startEvent);
WaitForSingleObject(threadParams[j].threadHandle,INFINITE);
CloseHandle(threadParams[j].threadHandle);
CloseHandle(threadParams[j].startEvent);
}
if (threadParams[i].threadHandle!=NULL) CloseHandle(threadParams[i].threadHandle);
if (threadParams[i].startEvent!=NULL) CloseHandle(threadParams[i].startEvent);
threadParams.clear();
exitRequested=false;
CloseHandle(doneEvent);
return false;
}
SetThreadPriority(threadParams[i].threadHandle,THREAD_PRIORITY_HIGHEST);
SetThreadIdealProcessor(threadParams[i].threadHandle,i%systemInfo.dwNumberOfProcessors);
}
return true;
}
void release()
{
if (threadParams.empty()) return;
exitRequested=true;
for (int i=0;i<(int)threadParams.size();i++)
{
SetEvent(threadParams[i].startEvent);
WaitForSingleObject(threadParams[i].threadHandle,INFINITE);
CloseHandle(threadParams[i].threadHandle);
CloseHandle(threadParams[i].startEvent);
}
threadParams.clear();
exitRequested=false;
CloseHandle(doneEvent);
}
void loop(LOOP_FUNC function,void * functionParams,int firstIndex,int firstOutIndex)
{
if (firstIndex>=firstOutIndex) return;
mode=LOOP;
int nbElements=firstOutIndex-firstIndex;
int nbTasks=min((int)threadParams.size(),nbElements);
int chunkSize=nbElements/nbTasks;
int index=firstIndex;
for (int i=0;i<nbTasks;i++)
{
threadParams[i].firstIndex=index;
index+=chunkSize;
threadParams[i].firstOutIndex=index;
}
threadParams.back().firstOutIndex=firstOutIndex;
loopFunction=function;
loopFunctionParams=functionParams;
doneCount=nbTasks;
ResetEvent(doneEvent);
for (int i=0;i<nbTasks;i++)
SetEvent(threadParams[i].startEvent);
WaitForSingleObject(doneEvent,INFINITE);
}
bool find(FIND_FUNC function,void * functionParams,int firstIndex,int firstOutIndex,int * foundIndex=NULL)
{
if (firstIndex>=firstOutIndex) return false;
mode=FIND;
indexFound=false;
int nbElements=firstOutIndex-firstIndex;
int nbTasks=min((int)threadParams.size(),nbElements);
int chunkSize=nbElements/nbTasks;
int index=firstIndex;
for (int i=0;i<nbTasks;i++)
{
threadParams[i].firstIndex=index;
index+=chunkSize;
threadParams[i].firstOutIndex=index;
}
threadParams.back().firstOutIndex=firstOutIndex;
findFunction=function;
findFunctionParams=functionParams;
doneCount=nbTasks;
ResetEvent(doneEvent);
for (int i=0;i<nbTasks;i++)
SetEvent(threadParams[i].startEvent);
WaitForSingleObject(doneEvent,INFINITE);
if (foundIndex!=NULL) *foundIndex=this->foundIndex;
return indexFound;
}
};
Cet objet permet d'exécuter une boucle sur des calculs indépendants, sur plusieurs threads. On a une boucle de 12 itérations, et bien on la dispatche sur 4 threads par exemple, chacun exécutant seulement 3 itérations. Donc un gain de 400% en performance. Bien sur, c'est seulement rentable pour des grosses (longues) boucles de calcul indépendant.
Je l'avais créé pour trier les polygones transparents en 3D.
