MPTL: MultiProcessing Template Library

Version imprimable

10/03/2007, 22h46
alskaar

MPTL: MultiProcessing Template Library

Salut,

pas de question pour une fois, juste pour filer un lien d'une lib qui me semble sympas ;)

http://spc.unige.ch/mptl
11/03/2007, 01h17
Charlemagne

J'ai regardé 5 minutes le code (car il se fait tard), et ça me paraît effectivement intéressant.

Ca me fait penser sur le principe de la programmation générique à la librairie d'Intel: Threading Buiding Blocks (TBB). J'ai eu la version test beta, gratuite pendant plusieurs mois.
Cette dernière est beaucoup plus aboutie (même si j'aime pas complètement la syntaxe adoptée un peu lourde à mon goût), mais elle est payante...
16/04/2007, 17h25
Charlemagne

Finalement je révise sérieusement à la baisse ma première appréciation hâtive.
J'ai essayé vite fait la bibliothèque avec le programme livré en exemple de tri, et voici mes observations:

-Ca ne compile pas avec la STL de Visual ni avec STLport (conflits de surcharges de fonctions). Ca compile uniquement avec GCC et la STL par défaut.

-L'algorithme de tri est à vue de nez 10000 fois plus lent (si si, dix mille!) que l'algo livré avec la STL. Je vois pas l'intérêt dans ces conditions à multithreader un projet.

Edit: une faute d'orthographe!
16/04/2007, 17h40
Alp

Comparé à Boost.Thread, ca donne quoi?
16/04/2007, 18h42
Charlemagne

Aucune idée. C'est aux fans de Boost à faire l'expérience s'ils le désirent.
Y'a un algorithme de tri multithreadé dans boost? Il sait diviser les algos de la STL en threads?
16/04/2007, 18h58
Alp

Non, mais j'voulais dire faire une opération dans un thread pour chacun, par exemple, ce que ça donne niveau perfs.
16/04/2007, 19h21
Charlemagne

Je sais pas non plus.
De toute façon ça serait pas comparable.

en dehors du tri je trouve la lib plutot sympas
pour effectuer des traitements identiques sur les N objets

Pour ce qui est du tri c'est pas terrible
leur algo est pas adapte au multithread
j'ai réécris une version pour 2 threads

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
 
 
 
#include <vector>
 
#include <mptl.h>
#include <mptl_algo.h>
#include <mptl_qsort.h>
#include <iterator>
#include <iostream>
 
 
#include <time.h>
using namespace std;
 
 
namespace mptl
{
 
template <typename Iterator>
class MPTLqsort
{
private:
    Iterator first, last; // Intervalle
 
public:
    // D´efinition des caract´eristiques
    typedef Iterator iterator1;
    typedef TwoIterators nIterators;
 
    // Constructeur de la classe MPTLqsort
    MPTLqsort(Iterator first_, Iterator last_): first(first_), last(last_) { }
    // Retourne les it´erateurs (pour rendre accessible
    // `a la librairie l’intervalle `a distribuer aux threads)
    Iterator getFirst1() { return first; }
    Iterator getLast1() { return last; }
    // Permet d’appliquer l’algorithme uniquement sur le sous-intervalle
    // [first , last ). Remarquons qu’il s’agit toujours du mˆeme
    // algorithme.
    void applyAlgorithm(Iterator first_, Iterator last_){ std::sort(first_,last_);}
 
};
 
 
template <typename Iterator>
MPTLqsort<Iterator> qsort(Iterator first, Iterator last)
{
    return MPTLqsort<Iterator>(first, last);
}
 
}
 
 
 
int main (int argc, char * const argv[])
{
    mptl::setNumThreads(2);
    std::vector<int> ::iterator it;
    int i=0;
    time_t deb,fin;
 
 
   std::vector<int> v1(100000000);
   std::vector<int> v2(100000000);
	for(it=v1.begin();it!=v1.end();++it)
	*it=i--;
 
 
 
    int pos=v1.size()/2;
 
    time(&deb);
	//sort mptl par defaut
	//mptl::sort(v1.begin(), v1.end());
 
	// new sort
	/*mptl::execute(mptl::qsort(v1.begin(),v1.end()));
    merge(v1.begin(),v1.begin()+pos,
          v1.begin()+pos,v1.end(),
          v2.begin());*/
 
    // sort STL
    //sort(v1.begin(), v1.end());
    time(&fin);
 
    cout<< "temps:"<<(fin-deb)<<endl;
}

16/04/2007, 22h22
Charlemagne

oui oui, y'a un coté sympa qui m'intéresse aussi
Dommage que ça marche pas sous Visual ou STLport. Je n'ai pas vraiment cherché à comprendre ce qui collait pas.
Dommage que l'algorithme de tri qui soit si lent.
J'ai pas testé le reste.

Sans avoir trop réfléchi au problème, j'aurais préféré une interface plus générale, un peu comme la Intel TBB mais sans sa lourdeur.

C'est le genre de chose qu'aurait dû implémenter Boost, et qui m'aurait convaincu de l'adopter. Car j'ai l'impression que le multithread de Boost se cantonne à faire des wrappers de <pthread> et d'autres librairies, mais il va peut-être "réinventer la roue"...
16/04/2007, 23h03
alskaar

le pb c'est qu il n y a pas de notion de mutex ou de conteneurs protégés
j'ai de tres bon resultats sur mon AMD 64 X2

niveau perfs ( Vista,Cygwin,gcc)
STL: 45s
MPTL: 155s
avec mon tri: 38s (~23s pour le trie des 2 ensembles, ~15s pour le merge des 2 resultats

c'est avant tout un pb d'algo y a certainement des tris adaptés au multithreads
style baquets enfin si quelqun en connait un performant
16/04/2007, 23h40
Luc Hermitte

boost.thread me parait reprendre lentement ACE et moderniser des petits morceaux. Il manque encore diverses choses utiles si on compare à tous les services fournis par l'enclume qui est ACE.
Elle reste très bas niveau. Donc encore loin de ce qu'a fait intel, ou la bibliothèque discutée dans ce fil.
17/04/2007, 00h35
Charlemagne

Citation:

Envoyé par alskaar

le pb c'est qu il n y a pas de notion de mutex ou de conteneurs protégés

Je suis pas convaincu que les mutex soient indispensables dans ce genre de programmation et puis c'est peut-être pas le rôle d'une telle librairie de faire du bas niveau.

C'est vrai que des containers compatibles avec le multithread seraient assez utiles. La aussi ça sort de l'objectif de cette petite librairie. La TBB a reprogrammé tous les containers de la STL.
Si vous connaissez une bonne implémentation gratuite de la STL qui soit multithreadable: dites le moi SVP.
Il faudrait que je me renseigne sur STLport, mais j'en doute.
Boost n'implémente sûrement pas de tels containers non plus...

Citation:

Envoyé par alskaar

c'est avant tout un pb d'algo y a certainement des tris adaptés au multithreads
style baquets enfin si quelqun en connait un performant

Personnellement c'est pas l'algo de tri qui m'intéresse vraiment dans une telle librairie, mais plutôt les algorithmes mathématiques. J'ai testé avec le tri de la MPTL car c'était le seul exemple dispo.
Utiliser l'algo de base de la STL (comme tu sembles l'avoir fait) paraît être une honnête solution (rapport efficacité/temps de programmation), même si il existe probablement des algorithmes efficaces pour le multithreading. De toute façon un algorithme très optimisé utiliserait les instructions vectorielles des processeurs (même si c'est a priori pas franchement évident).

bin le for_each et le fill marche plutot bien
j'ai testé avec ca:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
 
 
#include <vector>
 
#include <mptl.h>
#include <mptl_algo.h>
#include <mptl_qsort.h>
#include <iterator>
#include <iostream>
 
 
#include <time.h>
using namespace std;
 
void f(int & v)
{
    cout << v<<endl;
    //sleep(5);
    for(int i=0;i<10000;++i)
    for(int j=0;j<10000;++j);
}
 
 
void g(int & v)
{
    cout << v<<endl;
    for(int i=0;i<100000;++i)
    for(int j=0;j<10000;++j);}
 
 
int main (int argc, char * const argv[])
{
    mptl::setNumThreads(2);
    std::vector<int> ::iterator it;
    int i=0;
    time_t deb,fin;
 
 
    vector<int> v(4);
    for(it=v.begin();it!=v.end();++it)*it=i++;
 
    time(&deb);
    mptl::execute(mptl::for_each(v.begin(),v.end(),g));
    mptl::execute(mptl::for_each(v.begin(),v.end(),f));
    //for_each(v.begin(),v.end(),g);
    //for_each(v.begin(),v.end(),f);
    time(&fin);
 
 
    cout<< "temps:"<<(fin-deb)<<endl;
}

17/04/2007, 00h54
Charlemagne

Il faut espérer que de telles fonctions simplissimes marchent bien, car sinon c'est franchement à douter du multi-threading.

De toute façon je sens que je vais reprogrammer moi même dans les mois à venir ma propre librairie multi-thread, comme je l'entends.

PS:Mais t'arrives vraiment à chronométrer quelque chose avec des vecteurs de longueur 4? Je te suggère d'augmenter considérablement leurs tailles, de passer en paramètre aux algorithmes des foncteurs triviaux, afin de mesurer la capacité réelle de la librairie.
17/04/2007, 01h00
alskaar

bin pour le tri j'ai un vecteur de 100 000 000
pour les for_each c'est plutot les fonctor f() et g() que j'ai ralenti
18/04/2007, 03h45
loufoque

Citation:

-L'algorithme de tri est à vue de nez 10000 fois plus lent (si si, dix mille!) que l'algo livré avec la STL. Je vois pas l'intérêt dans ces conditions à multithreader un projet.

Bah a priori, le seul algo qu'on peut paralléliser, c'est merge sort.
Ce qui n'est vraiment intéressant qu'avec les listes.

Citation:

Envoyé par Charlemagne

De toute façon je sens que je vais reprogrammer moi même dans les mois à venir ma propre librairie multi-thread, comme je l'entends.

Voilà, j'ai consacré quelques journées à faire un premier jet de ma propre librairie multi-thread. Vous trouverez les sources ci-jointes (license GPL)
Je me suis surtout inspiré de la Intel TBB. J'ai quand même repris le concept de 'processus maître' de la MPTL (finalement ça s'imposait).

Le multi-threading ne permet pas des gains en vitesse aussi important que les instructions vectorielles SIMD, mais c'est bon à prendre en complément, et puis le multi-threading est à la mode...

-ma librairie détecte automatiquement le nombre de processeurs logiques, à condition de compiler avec VC/ICL/GCC et d'exécuter le programme avec un processeur Intel ou AMD.
-en échangeant une ligne dans la classe 'task_shedulder_init', on peut initialiser avec le nombre de cores, plutôt que de processeurs logiques (c'est pas la même chose pour les CPUs hyper-thread)
-Il est possible de déterminer soi-même le nombre de processus (fonction set_num_threads)

J'ai réimplémenté les fonctions 'ParallelFor' et 'ParallelReduce' de la TBB. Je trouve ma syntaxe beaucoup plus fluide mais c'est une bonne idée de lire le tutoriel et les références de la TBB pour comprendre les concepts.
http://www.intel.com/support/perform.../win/index.htm

En guise d'exemple, j'obtiens ces temps d'exécution sur mon vieux P4 HT 2.6GHz au programme suivant.
Code:

1 2 19.156s 13.625s
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 #include <vector> #include <ctime> #include <numeric> #include "threads.h" using namespace std; inline double get_time() { return double(clock())/CLOCKS_PER_SEC; } template<class V> struct fill_function { V val; fill_function(const V &v) : val(v) {} template<class It> void operator()(It begin, It end) const { fill(begin,end,val); } }; template<class V> struct accumulate_function { V val; accumulate_function() : val(0) {} template<class It> void operator()(It begin, It end) { val=accumulate(begin,end,val); } void join(const accumulate_function &x) { val+=x.val; } }; int main() { typedef int value_type; vector<value_type> X(25000000); fill(X.begin(),X.end(),1); //gmt::parallel_for(X.begin(),X.end(), fill_function<value_type>(1)); double t0=0; value_type*psum = new value_type; t0=get_time(); for (int i=0; i<500; ++i) *psum=accumulate(X.begin(),X.end(),0); cout << get_time()-t0 << "s" << endl; t0=get_time(); for (int i=0; i<500; ++i) { accumulate_function<value_type> func; gmt::parallel_reduce(X.begin(),X.end(),func,50000); *psum=func.val; } cout << get_time()-t0 << "s" << endl; }
Faites moi part de vos commentaires, et de vos temps d'exécution.