Threads et boost

Le
JKB
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 ?

Merci de vos lumières,

JKB

--
Le cerveau, c'est un véritable scandale écologique. Il représente 2% de notre
masse corporelle, mais disperse à lui seul 25% de l'énergie que nous
consommons tous les jours.
Questions / Réponses high-tech
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses Page 1 / 3
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Michael DOUBEZ
Le #18021141
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_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.

--
Michael
JKB
Le #18021131
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_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...

Merci,

JKB

--
Le cerveau, c'est un véritable scandale écologique. Il représente 2% de notre
masse corporelle, mais disperse à lui seul 25% de l'énergie que nous
consommons tous les jours.
Michael DOUBEZ
Le #18021841
JKB a écrit :
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...).



La mémoire partagée est surtout utile si tu veux pouvoir lancer
plusieurs programmes qui travaillent sur les même données. C'est plus
pratique que de définir des interfaces via socket ou autre mais si ton
application ne concerne qu'un seul programme alors c'est logique.

De toutes façon, si il s'agit juste de paralléliser les calculs, c'est
quand mêm plus logique d'utiliser des threads (si ton OS les gère
correctement).


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_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 ?



Boost peux générer plusieur types de librairies (-mt -dgb ...). Mais
ici, ça ne te concerne pas puisque tu utilises Boost.Graph qui n'est pas
compilé.

Je parle ici de la compilation du programme. A voir avec ton
architecture: c'est peut être aussi -mt ou -threading=multi.

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...



Ça dépens, je suppose que tu fais beaucoup plus de consultations que
d'écriture donc c'est à toi d'adapter la politique de lock: comment
locker et avec quelle granularité.

Peut être en regardant du coté des upgradeable locks dans un premier
temps pour protéger toute ta structure.

--
Michael
James Kanze
Le #18022671
On Dec 2, 10:16 am, Michael DOUBEZ
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 le s
collections standard). En revanche, je ne crois pas qu'on en a
une garantie de ça en écrite.

--
James Kanze (GABI Software) email:
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
JKB
Le #18022811
Le 02-12-2008, ? propos de
Re: Threads et boost,
James Kanze ?crivait dans fr.comp.lang.c++ :
On Dec 2, 10:16 am, Michael DOUBEZ
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().

Cordialement,

JKB

--
Le cerveau, c'est un véritable scandale écologique. Il représente 2% de notre
masse corporelle, mais disperse à lui seul 25% de l'énergie que nous
consommons tous les jours.
Michel Decima
Le #18023271
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.
JKB
Le #18023401
Le 02-12-2008, ? propos de
Re: Threads et boost,
Michel Decima ?crivait dans fr.comp.lang.c++ :
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.



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.

Cordialement,

JKB

--
Le cerveau, c'est un véritable scandale écologique. Il représente 2% de notre
masse corporelle, mais disperse à lui seul 25% de l'énergie que nous
consommons tous les jours.
Michel Decima
Le #18023801
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 ;)

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.).



Non, il n'y a surement pas de difference. J'ai exposé les deux methodes
parce que je ne connais pas l'algo en question (j'ai surtout utilise les
recherches de plus court chemin), ni ta structure de graphe.

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.



Ok, donc les proprietes des aretes devraient etre constantes (ie pas
modifiees par l'algo) tout comme la structure du graphe.
Ca ne me dit pas si la

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 ?)
JKB
Le #18024091
Le 02-12-2008, ? propos de
Re: Threads et boost,
Michel Decima ?crivait dans fr.comp.lang.c++ :
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 ;)



Disons que je comprends le principe de fonctionnement. ;-)

<snip>

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.

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 ?



Le wrapper C++ que je modifie commence par :

#include #include #include #include
La fonction qui me sert à ajouter un point dans le graphe est la
suivante :

template <class G, class E>
static void
graph_add_edge(G &graph, int id, int source, int target,
double cost, double s_x, double s_y, double t_x, double t_y)
{
E e;
bool inserted;

if (cost < 0) // edges are not inserted in the graph if cost is
negative
return;

tie(e, inserted) = add_edge(source, target, graph);

graph[e].cost = cost;
graph[e].id = id;

typedef typename graph_traits<G>::vertex_descriptor Vertex;
Vertex s = vertex(source, graph);
Vertex t = vertex(target, graph);
graph[s].x=s_x;
graph[s].y=s_y;
graph[t].x=t_x;
graph[t].y=t_y;
}

L'algorithme est appelé par :

astar_search
(graph, source_vertex,
distance_heuristic<graph_t, float>(graph, target_vertex),
predecessor_map(&predecessors[0]).
weight_map(get(&Edge::cost, graph)).
distance_map(&distances[0]).
visitor(astar_goal_visitor<vertex_descriptor>(target_vertex)));

Le wrapper complet est disponible à

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



Parce que les graphes sont gros.

Cordialement,

JKB

--
Le cerveau, c'est un véritable scandale écologique. Il représente 2% de notre
masse corporelle, mais disperse à lui seul 25% de l'énergie que nous
consommons tous les jours.
Michel Decima
Le #18024401
JKB a écrit :

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.



no comment ;)


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 :


<snip>
Le wrapper complet est disponible à



Je suppose que tu reecrit la fonction boost_astar ? Rien de choquant
a premiere vue, a part l'affreux graph_t statique et la gestion de
l'initialisation. Si tu decoupe cette fonction en 3 parties (init,
calcul, recuperation des resultats) ca pourrait peut-etre marcher.

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



Parce que les graphes sont gros.



J'avais utilise dijkstra sur des graphes a plusieurs dizaines de
milliers de noeuds, ce que je trouvais gros, et ca allait suffisamment
vite (mais je crois qu'a l'epoque l'algo astar_search n'etait pas encore
dans Boost). Bref, les tiens doivent donc etre plus gros que ca ;)
Publicité
Poster une réponse
Anonyme