Vue d'ensemble
editCette page décrit comment exécuter des procédures simples en parallèle à l'aide de l'unité MTProcs, qui simplifie l'exécution de procédures en parallèle et la mise en œuvre d'algorithmes parallèles.
Les procédures et méthodes parallèles sont souvent présentes dans les algorithmes parallèles et certains langages de programmation fournissent un support intégré pour celles-ci (par exemple OpenMP dans gcc). Voir OpenMP support pour les projets d'ajout de telles fonctionnalités de langage à FPC. Intégrer ces éléments dans le langage permet d'économiser du typage et permet au compilateur de générer du code avec moins de surcharge. D'autre part, il existe de nombreuses façons de convertir un morceau de code à un seul thread en code parallèle. En fait, les approches simples ralentissent souvent le code. Pour obtenir de bons résultats, il faut spécifier certains paramètres qu'un compilateur ne peut pas deviner. Pour des exemples, voir la grande quantité de paramètres et de discussions sur OpenMP etOpenCL. Vous avez besoin d'algorithmes parallèles. MTProcs aide à mettre en œuvre des algorithmes parallèles.
Obtenir MTProcs
editL'unité mtprocs.pas fait partie du paquet multithreadprocslaz.lpk, qui ne nécessite aucun autre paquet, seulement si version FPC >= 2.6.0.
Vous pouvez trouver ses sources soit sur sourceforge
svn co https://lazarus-ccr.svn.sourceforge.net/svnroot/lazarus-ccr/components/multithreadprocs multithreadprocs
Ou dans Lazarus Paquet/Installer désinstaller des paquets.
Comme toujours : Ouvrez le package multithreadprocslaz.lpk dans l'IDE une fois, afin qu'il se configure selon votre installation. Pour utiliser le package dans votre projet : Soit utiliser IDE Menu / paquet / Ouvrir un paquet récent / .../multithreadprocslaz.lpk et ensuite / Utiliser / Ajouter au projet pour l'utiliser dans votre projet actuel. Ou l'ajouter via l'inspecteur de projet.
Exemple simple
editVoici un court exemple, qui ne fait rien d'utile, mais qui montre à quoi ressemble une procédure parallèle et comment elle est appelée :
program Test;
{$mode objfpc}{$H+}
uses
{$IFDEF UNIX}
cthreads, cmem,
{$ENDIF}
MTProcs;
// une procédure parallèle simple
procedure DoSomethingParallel(Index: PtrInt; Data: Pointer; Item: TMultiThreadProcItem);
var
i: Integer;
begin
writeln(Index);
for i:=1 to Index*1000000 do ; // do some work
end;
begin
ProcThreadPool.DoParallel(@DoSomethingParallel,1,5,nil); // address, startindex, endindex, optional data
end.
The output will be something like this:
2
3
1
4
5
Voici quelques brèves notes. Les détails suivront plus tard.
- Le multithreading nécessite sous Unix l'unité cthreads comme expliqué dans Multithreaded Application Tutorial/fr.
- Pour des raisons de rapidité, il est recommandé d'utiliser le gestionnaire de tas cmem , bien que cela ne fasse aucune différence dans cet exemple.
- La procédure parallèle DoSomethingParallel reçoit certains paramètres fixes et prédéfinis.
- Index définit la partie du travail qui doit être effectuée par cet appel.
- Data est le pointeur qui a été donné à ProcThreadPool.DoParallel comme quatrième paramètre. Il est facultatif et vous êtes libre de l'utiliser à votre guise.
- Item peut être utilisé pour accéder à certaines des fonctions les plus sophistiquées du pool de threads.
- ProcThreadPool.DoParallel fonctionne comme un appel de procédure normal. Elle revient lorsqu'elle s'est complètement exécutée, c'est-à-dire lorsque tous les threads ont terminé leur travail.
- La sortie montre le comportement typique du multithreading : l'ordre des appels n'est pas déterminé. Plusieurs exécutions peuvent donner lieu à des ordres différents.
Caractéristiques
editL'exécution d'une procédure en parallèle signifie que
- une procédure ou une méthode est exécutée avec un index allant d'un StartIndex arbitraire à un EndIndex arbitraire.
- Un ou plusieurs threads exécutent cet index en parallèle. Par exemple, si l'index va de 1 à 10 et qu'il y a 3 threads disponibles dans le pool, alors 3 threads exécuteront trois index différents en même temps. Chaque fois qu'un thread termine un appel (un index), il alloue l'index suivant et l'exécute. Le résultat peut être le suivant : Le thread 1 exécute les index 3,5,7, le thread 2 exécute les index 1,6,8,9 et le thread 3 exécute les index 2,4,10.
- Le nombre de threads peut varier au cours de l'exécution et il n'y a pas de garantie pour un minimum de threads. Dans le pire des cas, tous les index seront exécutés par un seul thread - le thread lui-même.
- Le nombre maximum de threads est initialisé avec une bonne estimation pour le système actuel. Il peut être défini manuellement à tout moment via
ProcThreadPool.MaxThreadCount := 8;
- Vous pouvez définir le nombre maximal de threads pour chaque procédure.
- Une procédure (ou méthode) parallèle peut appeler des procédures (ou méthodes) récursivement parallèles.
- Les threads sont réutilisés, ce qui signifie qu'ils ne sont pas détruits et créés pour chaque index, mais qu'il existe un pool global de threads. Sur un processeur à deux cœurs, il y aura deux threads qui feront tout le travail - le thread principal et un thread supplémentaire dans le pool.
Surcharge, Ralentissement
editLa charge dépend fortement de l’architecture du système (nombre et types de cœurs, nature de la mémoire partagée, latence des sections critiques, taille du cache, etc.). Quelques recommandations générales :
- Chaque bloc de travail (index) devrait durer au moins quelques millisecondes.
- La charge est indépendante du nombre de niveaux récursifs des procédures parallèles.
La surcharge du multithreading, qui est indépendant des unités MTProcs, mais qui résulte simplement des architectures informatiques actuelles :
- Dès qu'un thread est créé, votre programme devient multitâches et les gestionnaires de mémoire doivent utiliser des sections critiques, ce qui ralentit le programme. Ainsi, même si vous ne faites rien avec le thread, votre programme peut devenir plus lent.
- Le gestionnaire de tas cmem est, sur certains systèmes, beaucoup plus rapide pour le multithreading. Dans mes benchmarks, en particulier sur les systèmes Intel et surtout sous OS X, la différence de vitesse peut être de plus de 10 fois.
- Les chaînes de caractères et les interfaces sont globalement comptées par référence. Chaque accès nécessite une section critique. Le traitement des chaînes de caractères dans plusieurs threads n'apportera donc guère de gain de vitesse. Utilisez plutôt des PChars.
- Chaque morceau de travail (index) devrait fonctionner sur une partie disjointe de la mémoire pour éviter les mises à jour croisées des caches.
- Ne fonctionne pas sur de grandes volume de mémoire. Sur certains systèmes, un seul thread est suffisamment rapide pour atteindre la vitesse du bus mémoire. Lorsque la vitesse maximale du bus mémoire est atteinte, tout autre thread ralentira la vitesse au lieu de l'accélérer.
Définition du nombre maximum de threads pour une procédure
editVous pouvez spécifier le nombre maximum de threads pour une procédure en tant que cinquième paramètre.
begin
ProcThreadPool.DoParallel(@DoSomethingParallel,1,10,nil,2); // address, startindex, endindex,
// optionnel : données (ici : nil), optionnel: numbre maximum de threads (ici: 2)
end.
Cela peut s'avérer utile lorsque les threads travaillent sur les mêmes données et qu'un trop grand nombre de threads crée tellement de conflits de cache qu'ils se ralentissent mutuellement. Ou lorsque l'algorithme utilise beaucoup de WaitForIndex, de sorte que seuls quelques threads peuvent réellement travailler. Les threads peuvent alors être utilisés pour d'autres tâches
Attendre l'index / exécuter dans l'ordre
editParfois, un index dépend du résultat d'un index précédent. Par exemple, une tâche courante consiste à calculer d'abord le bloc 5, puis à combiner le résultat avec celui du bloc 3. Utilisez la méthode WaitForIndex pour cela :
procedure DoSomethingParallel(Index: PtrInt; Data: Pointer; Item: TMultiThreadProcItem);
begin
... Calculer le no du bloc 'Index' ...
if Index=5 then begin
if not Item.WaitForIndex(3) then exit;
... calculer ...
end;
end;
WaitForIndex prend comme argument un indice inférieur à l'indice actuel ou une plage. S'il renvoie true, tout a fonctionné comme prévu. S'il renvoie false, cela signifie qu'une exception s'est produite dans l'un des autres threads.
Il existe une fonction étendue WaitForIndexRange qui attend sur une plage de l'index :
if not Item.WaitForIndexRange(3,5) then exit; // attend pour 3,4 et 5
Exceptions
editSi une exception survient dans l'un des threads, les autres threads se termineront normalement, mais ne commenceront pas un nouvel index. Le pool attend que tous les threads se terminent et lève alors l'exception. C'est pourquoi vous pouvez utiliser “'try..except”' comme toujours :
try
...
ProcThreadPool.DoParallel(...);
...
except
On E: Exception do ...
end;
S'il y a plusieurs exceptions, seule la première exception sera levée. Pour gérer toutes les exceptions, ajoutez un try..except à l'intérieur de votre méthode parallèle.
Synchronisation
editLorsque vous souhaitez appeler une fonction dans le thread principal, par exemple pour mettre à jour un élément de l'interface utilisateur, vous pouvez utiliser la méthode de classe “'TThread.Synchronize”'. Elle prend comme arguments le TThread courant et l'adresse d'une méthode. Depuis la version 1.2, mtprocs fournit une threadvar CurrentThread, qui simplifie la synchronisation :
When you want to call a function in the main thread, for example to update some gui element, you can use the class method TThread.Synchronize. It takes as arguments the current TThread and the address of a method. Since 1.2 mtprocs provides a threadvar CurrentThread, which makes synchronizing simple:
TThread.Synchronize(CurrentThread,@YourMethod);
Cela permet de poster un événement dans la file d'attente principale et d'attendre que le fil d'exécution principal ait exécuté votre méthode. Gardez à l'esprit qu'un programme fpc simple n'a pas de file d'attente d'événements. Un programme LCL ou fpgui en dispose.
Si vous créez vos propres descendants TThread, vous devez définir la variable dans votre méthode Execute. Par exemple :
procedure TYourThread.Execute;
begin
CurrentThread:=Self;
...work...
end;
Exemple : Boucle parallèle
editCet exemple explique pas à pas comment convertir une boucle en une procédure parallèle. L'exemple calcule le nombre maximum d'un tableau d'entiers BigArray.
La boucle originale
edittype
TArrayOfInteger = array of integer;
function FindMaximum(BigArray: TArrayOfInteger): integer;
var
i: PtrInt;
begin
Result:=BigArray[0];
for i:=1 to length(BigArray)-1 do begin
if Result<BigArray[i] then Result:=BigArray[i];
end;
end;
Répartir le travail
editLe travail doit être réparti de manière égale sur n threads. Pour ce faire, le BigArray est divisé en blocs de taille égale et une boucle extérieure s'exécute sur chaque bloc. Typiquement, n est le nombre de cpus/cores dans le système. MTProcs dispose de quelques fonctions utilitaires pour calculer la taille et le nombre de blocs :
function FindMaximum(BigArray: TArrayOfInteger): integer;
var
BlockCount, BlockSize: PtrInt;
i: PtrInt;
Index: PtrInt;
BlockStart, BlockEnd: PtrInt;
begin
Result:=BigArray[0];
ProcThreadPool.CalcBlockSize(length(BigArray),BlockCount,BlockSize);
for Index:=0 to BlockCount-1 do begin
Item.CalcBlock(Index,BlockSize,length(BigArray),BlockStart,BlockEnd);
for i:=BlockStart to BlockEnd do begin
if Result<BigArray[i] then Result:=BigArray[i];
end;
end;
end;
Les lignes ajoutées peuvent être utilisées pour n'importe quelle boucle. Un outil pourra éventuellement être écrit pour automatiser cette opération.
Le travail est maintenant divisé en plus petits morceaux. Ces morceaux doivent maintenant devenir plus indépendants.
Variables locales et partagées
editPour chaque variable utilisée dans la boucle, vous devez décider s'il s'agit d'une variable partagée utilisée par tous les threads ou si chaque thread utilise sa propre variable locale. Les variables partagées BlockCount et BlockSize sont seulement lues et ne changent pas, donc aucun travail n'est nécessaire pour elles. En revanche, une variable partagée telle que Resultat sera modifiée par toutes les threads. Cela peut être réalisé par synchronisation (par exemple, la section critique), ce qui est va ralentir les threads, ou alors chaque thread utilise une copie locale et ces variables et elles sont combinées plus tard.
Voici une solution qui remplace la variable “'Resultat”' par un tableau, qui est combiné à la fin :
function FindMaximum(BigArray: TArrayOfInteger): integer;
var
// shared variables
BlockCount, BlockSize: PtrInt;
BlockMax: PPtrInt;
// local variables
i: PtrInt;
Index: PtrInt;
BlockStart, BlockEnd: PtrInt;
begin
ProcThreadPool.CalcBlockSize(length(BigArray),BlockCount,BlockSize);
BlockMax:=AllocMem(BlockCount*SizeOf(PtrInt)); // allocate space for local variables
// compute maximum for each block
for Index:=0 to BlockCount-1 do begin
// compute maximum of block
Item.CalcBlock(Index,BlockSize,length(BigArray),BlockStart,BlockEnd);
BlockMax[Index]:=BigArray[BlockStart];
for i:=BlockStart to BlockEnd do begin
if BlockMax[Index]<BigArray[i] then BlockMax[Index]:=BigArray[i];
end;
end;
// compute maximum of all blocks
// (if you have hundreds of threads there are better solutions)
Result:=BlockMax[0];
for Index:=1 to BlockCount-1 do
Result:=Max(Result,BlockMax[Index]);
FreeMem(BlockMax);
end;
This approach is straightforward and could be automated. The process will need some hints from the programmer though. Cette approche est simple et pourrait être automatisée. Le processus nécessitera toutefois quelques attentions de la part du programmeur.
Rendre parallèle
editLa dernière étape consiste à déplacer la boucle interne dans une sous-procédure et à remplacer la boucle par un appel à DoParallelNested.
...
{$ModeSwitch nestedprocvars}
uses mtprocs;
...
function TMainForm.FindMaximum(BigArray: TArrayOfInteger): integer;
var
BlockCount, BlockSize: PtrInt;
BlockMax: PPtrInt;
procedure FindMaximumParallel(Index: PtrInt; Data: Pointer;
Item: TMultiThreadProcItem);
var
i: integer;
BlockStart, BlockEnd: PtrInt;
begin
// calculer le maximum du bloc
Item.CalcBlock(Index,BlockSize,length(BigArray),BlockStart,BlockEnd);
BlockMax[Index]:=BigArray[BlockStart];
for i:=BlockStart to BlockEnd do
if BlockMax[Index]<BigArray[i] then BlockMax[Index]:=BigArray[i];
end;
var
Index: PtrInt;
begin
// diviser le travail en blocs de taille égale
ProcThreadPool.CalcBlockSize(length(BigArray),BlockCount,BlockSize);
// allouer des variables locales/thread
BlockMax:=AllocMem(BlockCount*SizeOf(PtrInt));
// calculer le maximum pour chaque bloc
ProcThreadPool.DoParallelNested(@FindMaximumParallel,0,BlockCount-1);
// calculer le maximum de tous les blocs
Result:=BlockMax[0];
for Index:=1 to BlockCount-1 do
Result:=Max(Result,BlockMax[Index]);
FreeMem(BlockMax);
end;
Il s'agissait essentiellement de copier-coller, ce qui, là encore, pourrait être automatisé.
Exemple : tri parallèle
editL'unité mtputils contient la fonction ParallelSortFPList qui utilise mtprocs pour trier une TFPList en parallèle. Une fonction de comparaison doit être fournie.
procedure ParallelSortFPList(List: TFPList; const Compare: TListSortCompare; MaxThreadCount: integer = 0; const OnSortPart: TSortPartEvent = nil);
Cette fonction utilise l'algorithme parallèle MergeSort. Le paramètre MaxThreadCount est passé à DoParallel. Un 0 signifie l'utilisation de la valeur par défaut du système.
En option, vous pouvez fournir votre propre fonction de tri (OnSortPart) pour trier la partie de chaque fil. Par exemple, vous pouvez trier les blocs via QuickSort, qui sont ensuite fusionnés. On obtient alors un QuickSort parallèle. Voir TFPList.Sort pour un exemple d'implémentation de QuickSort.
Utilisation d'une procédure imbriquée
editprocedure DoSomething(Value: PtrInt);
var
p: array[1..2] of Pointer;
procedure SubProc(Index: PtrInt; Data: Pointer; Item: TMultiThreadProcItem);
begin
p[Index]:=Pointer(Value); // l'accès aux variables et paramètres locaux est possible !
end;
var
i: Integer;
begin
ProcThreadPool.DoParallelNested(@SubProc,1,2);
end;
Cela permet d'économiser beaucoup de travail de refonte et rend la procédure parallèle beaucoup plus lisible.