Threads et boost

Bonjour à tous,

Je ne sais pas si je suis sur le bon forum, mais je n'en trouve pas
de plus adapté. Toute redirection sera donc acceptée ;-)

Ma question porte sur la libboost qui est une bibliothèque écrite en
C++. J'utilise des fonctions de la boost_graph dans un bout de code
écrit en C et Fortran (toutes versions). Le code en question tourne en
environnement POSIX sur machines parallèles et la parallélisation
est faite actuellement à grands coups de fork(). Le fork() n'est pas
pénalisant parce que chaque calcul prend quelques minutes.

Problème : l'occupation mémoire. Chaque processus consommant un peu
plus d'un gigaoctet et la machine en question ayant 32 processeurs, il faut
soit que je limite le nombre de processus, soit que j'augmente la taille
mémoire. Vu le prix de la mémoire de la bête, je préfère trouver une
solution médiane... D'où l'idée d'utiliser des threads (la majeure
partie de la mémoire est utilisée par des données qui ne changent pas
d'un processus à un autre).

Pour raisons de portabilité, j'utilise gcc/gfortran/g++ sur toutes
mes architectures cibles (essentiellement du Solaris et du Linux).

La configuration de boost me renvoie :

Boost version 103700
BOOST_USER_CONFIG =<boost/config/user.hpp>
BOOST_COMPILER_CONFIG ="boost/config/compiler/gcc.hpp"
BOOST_STDLIB_CONFIG ="boost/config/stdlib/libstdcpp3.hpp"
BOOST_PLATFORM_CONFIG ="boost/config/platform/linux.hpp"
BOOST_HAS_THREADS [no value]

Je n'arrive pas à trouver d'information pertinente (des infos, j'en
ai trouvé, mais pas pertinentes, ou alors, je n'ai pas tout compris, ce
qui est fort possible...) sur le paramètre BOOST_HAS_THREADS.
D'après ce que j'ai compris, cette valeur est donnée par le couple
architecture et compilateur.

Sachant que j'utilise depuis pas mal de temps les threads sur ces
mêmes architectures sans problème, je ne vois pas trop pourquoi cette
valeur n'est pas définie.

Question : les fonctions de boost/graph sont-elles thread safe
malgré cette variable ? Je n'utilise que astar_search. Autrement dit,
puis-je appeler sans vergogne astar_search depuis plusieurs threads (sur
le même graphe bien entendu) mais avec des sommets de départ et
d'arrivée différents ?

JKB a écrit :

Bonjour à tous,

Je ne sais pas si je suis sur le bon forum, mais je n'en trouve pas
de plus adapté. Toute redirection sera donc acceptée ;-)

Les newsgroups de boost se trouvent sur gmane: news.gmane.org. Il faut
s'incrire sur le site http à la même adresse pour pouvoir poster.

Ma question porte sur la libboost qui est une bibliothèque écrite en
C++. J'utilise des fonctions de la boost_graph dans un bout de code
écrit en C et Fortran (toutes versions). Le code en question tourne en
environnement POSIX sur machines parallèles et la parallélisation
est faite actuellement à grands coups de fork(). Le fork() n'est pas
pénalisant parce que chaque calcul prend quelques minutes.

Problème : l'occupation mémoire. Chaque processus consommant un peu
plus d'un gigaoctet et la machine en question ayant 32 processeurs, il faut
soit que je limite le nombre de processus, soit que j'augmente la taille
mémoire. Vu le prix de la mémoire de la bête, je préfère trouver une
solution médiane... D'où l'idée d'utiliser des threads (la majeure
partie de la mémoire est utilisée par des données qui ne changent pas
d'un processus à un autre).

Et cette mémoire ne pourrait elle pas être mise dans une zone de mémoire
partagée ? Je crois même que boost en standard fourni une librairies
avec des conteneur et des mutex en mémoire partagée; je l'ai utilisée
lorsqu'elle était encore dans le vault et ça se passait pas mal.

Enfin, ça ne correspond peut être pas à ton architecture.

Pour raisons de portabilité, j'utilise gcc/gfortran/g++ sur toutes
mes architectures cibles (essentiellement du Solaris et du Linux).

La configuration de boost me renvoie :

Boost version 103700
BOOST_USER_CONFIG =<boost/config/user.hpp>
BOOST_COMPILER_CONFIG ="boost/config/compiler/gcc.hpp"
BOOST_STDLIB_CONFIG ="boost/config/stdlib/libstdcpp3.hpp"
BOOST_PLATFORM_CONFIG ="boost/config/platform/linux.hpp"
BOOST_HAS_THREADS [no value]

Je n'arrive pas à trouver d'information pertinente (des infos, j'en
ai trouvé, mais pas pertinentes, ou alors, je n'ai pas tout compris, ce
qui est fort possible...) sur le paramètre BOOST_HAS_THREADS.
D'après ce que j'ai compris, cette valeur est donnée par le couple
architecture et compilateur.

Ca dépends du compilateur, de l'architecture et des paramètres de
compilation. Normalement avec g++, il est défini lorsque -pthread est
inséré sur la ligne de commande.

Sachant que j'utilise depuis pas mal de temps les threads sur ces
mêmes architectures sans problème, je ne vois pas trop pourquoi cette
valeur n'est pas définie.

>

Question : les fonctions de boost/graph sont-elles thread safe
malgré cette variable ? Je n'utilise que astar_search. Autrement dit,
puis-je appeler sans vergogne astar_search depuis plusieurs threads (sur
le même graphe bien entendu) mais avec des sommets de départ et
d'arrivée différents ?

Je n'en sait rien. Je suppose que non: Graph doit fournir les mêmes
garanties que la STL, c'est à dire aucune.

Le 02-12-2008, ? propos de
Re: Threads et boost,
Michael DOUBEZ ?crivait dans fr.comp.lang.c++ :

JKB a écrit :

Bonjour à tous,

Je ne sais pas si je suis sur le bon forum, mais je n'en trouve pas
de plus adapté. Toute redirection sera donc acceptée ;-)

Les newsgroups de boost se trouvent sur gmane: news.gmane.org. Il faut
s'incrire sur le site http à la même adresse pour pouvoir poster.

Je vais aller regarder par là...

Ma question porte sur la libboost qui est une bibliothèque écrite en
C++. J'utilise des fonctions de la boost_graph dans un bout de code
écrit en C et Fortran (toutes versions). Le code en question tourne en
environnement POSIX sur machines parallèles et la parallélisation
est faite actuellement à grands coups de fork(). Le fork() n'est pas
pénalisant parce que chaque calcul prend quelques minutes.

Problème : l'occupation mémoire. Chaque processus consommant un peu
plus d'un gigaoctet et la machine en question ayant 32 processeurs, il faut
soit que je limite le nombre de processus, soit que j'augmente la taille
mémoire. Vu le prix de la mémoire de la bête, je préfère trouver une
solution médiane... D'où l'idée d'utiliser des threads (la majeure
partie de la mémoire est utilisée par des données qui ne changent pas
d'un processus à un autre).

Et cette mémoire ne pourrait elle pas être mise dans une zone de mémoire
partagée ? Je crois même que boost en standard fourni une librairies
avec des conteneur et des mutex en mémoire partagée; je l'ai utilisée
lorsqu'elle était encore dans le vault et ça se passait pas mal.

Enfin, ça ne correspond peut être pas à ton architecture.

Pas exactement (c'est un peu le problème, d'ailleurs...).

Pour raisons de portabilité, j'utilise gcc/gfortran/g++ sur toutes
mes architectures cibles (essentiellement du Solaris et du Linux).

La configuration de boost me renvoie :

Boost version 103700
BOOST_USER_CONFIG =<boost/config/user.hpp>
BOOST_COMPILER_CONFIG ="boost/config/compiler/gcc.hpp"
BOOST_STDLIB_CONFIG ="boost/config/stdlib/libstdcpp3.hpp"
BOOST_PLATFORM_CONFIG ="boost/config/platform/linux.hpp"
BOOST_HAS_THREADS [no value]

Je n'arrive pas à trouver d'information pertinente (des infos, j'en
ai trouvé, mais pas pertinentes, ou alors, je n'ai pas tout compris, ce
qui est fort possible...) sur le paramètre BOOST_HAS_THREADS.
D'après ce que j'ai compris, cette valeur est donnée par le couple
architecture et compilateur.

Ca dépends du compilateur, de l'architecture et des paramètres de
compilation. Normalement avec g++, il est défini lorsque -pthread est
inséré sur la ligne de commande.

Lors de la compilation de boost ?

Sachant que j'utilise depuis pas mal de temps les threads sur ces
mêmes architectures sans problème, je ne vois pas trop pourquoi cette
valeur n'est pas définie.

Question : les fonctions de boost/graph sont-elles thread safe
malgré cette variable ? Je n'utilise que astar_search. Autrement dit,
puis-je appeler sans vergogne astar_search depuis plusieurs threads (sur
le même graphe bien entendu) mais avec des sommets de départ et
d'arrivée différents ?

Je n'en sait rien. Je suppose que non: Graph doit fournir les mêmes
garanties que la STL, c'est à dire aucune.

Flute... Si je colle un mutex avant l'appel, je perds l'avantage du
parallélisme...

JKB a écrit :

> Question : les fonctions de boost/graph sont-elles thread
> safe malgré cette variable ? Je n'utilise que astar_search.
> Autrement dit, puis-je appeler sans vergogne astar_search
> depuis plusieurs threads (sur le même graphe bien entendu)
> mais avec des sommets de départ et d'arrivée différents ?

Je n'en sait rien. Je suppose que non: Graph doit fournir les
mêmes garanties que la STL, c'est à dire aucune.

On Dec 2, 10:16 am, Michael DOUBEZ <michael.dou...@free.fr> wrote:

JKB a écrit :

> Question : les fonctions de boost/graph sont-elles thread
> safe malgré cette variable ? Je n'utilise que astar_search.
> Autrement dit, puis-je appeler sans vergogne astar_search
> depuis plusieurs threads (sur le même graphe bien entendu)
> mais avec des sommets de départ et d'arrivée différents ?

Je n'en sait rien. Je suppose que non: Graph doit fournir les
mêmes garanties que la STL, c'est à dire aucune.

En ce qui concerne la STL, il y a des garanties importantes ;
tant qu'on ne modifie rien, par exemple, on peut accéder depuis
plusieurs threads sans mutex. Le vrai question ici, je crois,
c'est ce qui se passe si dans un std::vector, par exemple, je
modifie un élément dans un thread, et un autre dans un autre
thread. Dans la pratique (et en sachant comment est implémenté
std::vector), ça doit marcher, tant qu'on ne modifie pas la
topologie du containeur et qu'il n'y a jamais plus d'un thread
qui accède à un élément donné (et ça doit valoir pour toutes les
collections standard). En revanche, je ne crois pas qu'on en a
une garantie de ça en écrite.

En fait, mon problème est assez simple. J'initialise le graphe
une fois pour toute et la seule chose qui changerait d'un thread à un
autre sont les vertices source et destination. L'ennui, c'est que je ne
connais pas assez le C++ pour comprendre comment fonctionne
astar_search().

JKB a écrit :

En fait, mon problème est assez simple. J'initialise le graphe
une fois pour toute et la seule chose qui changerait d'un thread à un
autre sont les vertices source et destination. L'ennui, c'est que je ne
connais pas assez le C++ pour comprendre comment fonctionne
astar_search().

Pour commencer, tu devrais regarder dans la doc de Boost.Graph
la definition du concept PropertyMap, qui modélise l'ajout de
proprietes sur les noeuds et les aretes du graphe (le nom de
chaque noeud, le poids des aretes, etc).

Grosso modo, il y a deux facons d'associer une propriete a un
element du graphe : soit elle est interne, portee par une variable
membre du graphe, soit elle est externe, dans un container a part.
Par exemple, si je veux un graphe avec des noms sur les noeuds et
des poids sur les aretes, je peux choisir entre:

typedef adjacency_list <
listS, // les aretes dans une std::list
vecS, // les noeuds dans un std::vector
directedS, // graphe oriente
property< vertex_name_t, std::string >, // nom des noeuds
property < edge_weight_t, int > // poids des aretes
> graph_t;

graph_t G ;

Ici, les propriétes sont internes, et chaque fois que j'insere
un element, le graphe cree automatiquement l'entree correspondante
dans les table de proprietes associees.

La deuxieme possibilite:

typedef adjacency_list <
listS, // les aretes dans une std::list
vecS, // les noeuds dans un std::vector
directedS, // graphe oriente
no_property, // pas de proprietes sur les noeuds
no_property // pas de propriete sur les aretes
> graph_t;

typedef std::map< graph_t::vertex_descriptor, std::string >
vertex_name_pmap ;

typedef std::map< graph_t::edge_descriptor, int >
edge_weight_map ;

graph_t G ;
vertex_name_pmap G_names ;
edge_weight_t G_weights ;

Ici, le graphe ne contient pas de proprietes sur les elements,
c'est juste une liste d'adjacence "de base", et les proprietes
sont externes. L'inconvenient, c'est que je doit gerer moi-meme
l'insertion des valeurs dans les proprietes correspondantes lorsque
j'ajoute un element dans le graphe.

Pour revenir au probleme des threads, je suppose que astar_search()
travaille sur une structure de graphe, avec des proprietes en entree
(donnees) et d'autres en sortie (temporaire, resultat).
Si les proprietes en sortie son internes au graphe, tu ne pourra pas
appeler l'algo depuis deux threads. En revanche, si elles sont externes,
locales a chaque thread, ca devrait passer, en supposant que tout le
reste (structure, propriete, algo) est compatible avec les threads.

Evidemment, si l'algorithme modifie la structure du graphe (ajout ou
suppression de noeud/arete), alors ca ne va pas etre possible.

Grosso modo, il y a deux facons d'associer une propriete a un
element du graphe : soit elle est interne, portee par une variable
membre du graphe, soit elle est externe, dans un container a part.
Par exemple, si je veux un graphe avec des noms sur les noeuds et
des poids sur les aretes, je peux choisir entre:

Jusque-là, je comprends.

Pour revenir au probleme des threads, je suppose que astar_search()
travaille sur une structure de graphe, avec des proprietes en entree
(donnees) et d'autres en sortie (temporaire, resultat).
Si les proprietes en sortie son internes au graphe, tu ne pourra pas
appeler l'algo depuis deux threads. En revanche, si elles sont externes,
locales a chaque thread, ca devrait passer, en supposant que tout le
reste (structure, propriete, algo) est compatible avec les threads.

Par contre, ici, ça coince. Mon graphe est une cartographie avec
comme poids des arêtes la durée du trajet sur cette arête. Cette durée
est toujours la même quelle que soit l'appel. Je ne vois donc pas ici la
différence entre les deux approches (mais j'ai peut-être raté quelque
chose.).

Evidemment, si l'algorithme modifie la structure du graphe (ajout ou
suppression de noeud/arete), alors ca ne va pas etre possible.

Le graphe est tellement statique qu'il est déclaré une fois pour
toute comme :

static graph_t graph;

et il n'est initialisé qu'une seule fois. Les différents points sont
ajoutés par :

graph_add_edge<graph_t, edge_descriptor>(graph,
edges[j].id, edges[j].target,
edges[j].source, cost,
edges[j].s_x, edges[j].s_y,
edges[j].t_x, edges[j].t_y);

edges[] étant lui-aussi un tableau statique.

JKB a écrit :

Grosso modo, il y a deux facons d'associer une propriete a un
element du graphe : soit elle est interne, portee par une variable
membre du graphe, soit elle est externe, dans un container a part.
Par exemple, si je veux un graphe avec des noms sur les noeuds et
des poids sur les aretes, je peux choisir entre:

[snip]

Jusque-là, je comprends.

tu as du merite, parce que Boost.Graph n'est pas un modele de
simplicite ;)

Que deviens edges[] apres l'initialisation du graphe ? Si tu ne le vide
pas, alors tu as deux copie des proprietes des aretes, une dans edges[],
et une dans le graphe (en interne). Ca peut etre une piste pour
economiser de la memoire.

Pour en revenir aux proprietes internes/externes, dans la documentation
de l'algorithme, je vois un certain nombre de proprietes en sortie:

OUT: predecessor_map(PredecessorMap p_map)
UTIL/OUT: distance_map(DistanceMap d_map)
UTIL/OUT: rank_map(CostMap c_map)
UTIL/OUT: color_map(ColorMap c_map)

Si ces proprietes sont portees par ton graphe, alors tu ne pourra
pas faire d'appel concurrent a l'algo. C'est ces proprietes-la qu'il
faut rendre externes, si l'algo ne le fait pas automatiquement lui-meme
(En gros, l'algo va detecter que les proprietes de travail ne sont ni
portees par le graphe, ni fournies en parametres, et il va les creer
en tant que variable locales dans la portee de la fonction).

Est-ce que tu peux donner la definition de ton typedef graph_t, et
l'invocation de l'algorithme ?

(et par curiosite, pourquoi astar plutot que dijkstra ?)

Que deviens edges[] apres l'initialisation du graphe ? Si tu ne le vide
pas, alors tu as deux copie des proprietes des aretes, une dans edges[],
et une dans le graphe (en interne). Ca peut etre une piste pour
economiser de la memoire.

La fonction appelante (C) fait un sauvage :

munmap((void *) edges, edges_size * size(edge_astar_t));

C'est un unmap() et non un malloc() parce que sous Solaris, free()
renvoie la mémoire à l'application et non au système.

Est-ce que tu peux donner la definition de ton typedef graph_t, et
l'invocation de l'algorithme ?

Le wrapper C++ que je modifie commence par :

Le wrapper complet est disponible à
<http://www.bertrand-lecarpentier.net/~bertrand/astar_boost_wrapper.cpp>

(et par curiosite, pourquoi astar plutot que dijkstra ?)

Parce que les graphes sont gros.