Discussion :

[ol9245]

Bonjour,

J'ai un algo assez simple de marcheur qui se promène sur une grille. La grille représente un relief terrestre. Le marcheur fait ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
tant que la file d'attente n'est pas vide {
<div style="margin-left:40px">prendre x : la maille de tête dans la file
si la maille x n'a jamais été visitée, alors {
<div style="margin-left:40px">aller x
marquer que x a été visitée
pousser en queue de file toutes les mailles voisines de x qui sont non visitées et qui sont d'altitude supérieure à celle de x</div>}</div>}

On voit qu'il suffit d'initialiser la file avec une maille graine G pour que ce marcheur explore l'ensemble des mailles accessibles par un chemin strictement montant depuis G. Dans l'algo complet, j'initialise la pile avec toutes les mailles de la périphérie du maillage. Le résultat est que les mailles non visitées représentent l'intérieur des dépressions : il n'existe pas de chemin continuellement montant pour les atteindre depuis le bord du maillage.

Mon but est de mettre en concurrence plusieurs de ces marcheurs pour diminuer le temps d'exploration de la grille. D'ou une première question au forum : ce problème a-t'il déja été résolu ?

En attendant d'explorer ce qui se fait déjà, mon idée de départ est de constituer plusieurs files et de confier chacune à un thread séparé. D'où ma deuxième question au forum : Quelle stratégie adopter pour éviter à la fois une "race condition" et des bloquages entrecroisés ?

L'algo s'adresse à des grilles très grandes (jusqu'à des centaines de millions de mailles). Il ne faut pas que les besoins en mémoire des objets de synchronisation soient aussi gros que les données elle-même. je dois donc assembler les mailles en dalles, et synchroniser des dalles entières, pas des cellules (enfin, je crois...).

Pour l'instant, je vois deux stratégies :
1/ marcheurs indépendants
chaque marcheur à toute la liberté d'explorer l'ensemble de la grille. Avant de faire ses entrée-sortie, il locke les dalles qui contiennent les 9 points qu'il a besoin de consulter. (donc entre 1 et 4 dalles lockées). Si les dalles dont il a besoin dont déjà lockées par un autre marcheur, il renvoie la maille à traiter au fond de sa file d'attente, débloque le cas échéant les dalles qui avaient été réservées, et essaie de traiter la maille suivante.
=> avantage :
assez simple à concevoir
la fin du travail est simple à détecter : les threads meurent quand leur file est vide, don un simple 'join' dans le main suffit.
=> inconvénient :
perte d'efficacité dans la concurrence entre les threads pour accéder aux mêmes mailles
j'ai peur de générer des blocages croisés : deux threads ou plus ont besoin des deux mêmes dalles. Chacun en bloque une en espérant avoir l'autre, puis la relâche quand il voir qu'il ne l'aura pas. Si c'est la dernière maille dans sa file, il recommence aussitôt. Les concurrents peuvent jouer comme ça longtemps avant que l'un réussisse enfin à bloquer les deux dalles à la fois.

2/ marcheurs localisés
j'ai une file d'attente par dalle, et un thread associé à cette file d'attente.
chaque thread dépile ce qu'il y a dans sa file d'attente. par contre, les mailles à empiler sont empilées dans la file de la dalle à laquelle elles appartiennent.
=> avantage :
la perte d'efficacité ne se fait qu'aux frontières des dalles
=> inconvénient :
plus complexe à implémenter (un thread attaché à une dalle du centre peut attendre longtemps que sa file soit peuplée)
Les files elle-même deviennent des objets partagés qu'il faut synchroniser
la fin du travail est plus complexe à détecter : fin du travail quand toutes les files sont vident en même temps. Il faut détecter cela sans créer un golot d'étranglement au niveau synchronisation

Merci de partager vos idées. Le temps que je passerai sur ce fil grâce à vous sera gagné au centuple au moment de débugger l'engin

[souviron34]

Salut

Je vois (à mon avis) un inconvénient avec chacune des approches :

chacune impose que le nombre de thread soit égal soit aux dalles soit aux marcheurs.

D'une part ça peut faire beaucoup d'overhead et dépasser la capacité du nombre de process (ou sous-process), d'autre part c'est pas vraiment du "//" modulable, au sens où tu obliges N -> N.

Il faudrait que ce soit paramétrable (par exemple si tu as un mulitcoeurs, si tu es sur un environnement contraint, si tu es multi-machines avec du // style MPI, etc etc)

Evidemment la solution la plus facilement paramétrable est par rapport au nombre de archeurs.

Maintenant, c'est juste ma première impression. Je vais y réfléchir plus longuement.. car je crois que je ne saiss pas tout le problème..

[M.Max]

Bonjour,

J'ai un algo assez simple de marcheur qui se promène sur une grille. La grille représente un relief terrestre.
On voit qu'il suffit d'initialiser la file avec une maille graine G pour que ce marcheur explore l'ensemble des mailles accessibles par un chemin strictement montant depuis G

Quel est l'objectif de l'algo ? Découvrir tous les sommets de la grille ?

[ol9245]

Quel est l'objectif de l'algo ? Découvrir tous les sommets de la grille ?

l'algo "remplit" les dépression. La surface finale est celle qu'aurait une surface naturelle après un déluge : toute l'eau qui a pu couler a coulé. Le reste est retenu dans les dépressions. A la sortie de l'algo, les anciennes dépressions sont donc comblées.

Les marcheurs font le gros du boulot : assécher les mailles qui peuvent l'être "facilement" (donc par exemple pas des îles au milieu d'un lac, etc.).

L'algo en mono-thread, je l'ai et il marche. La version 2001 est ici : nosink.cpp
La version 2012 est dans mon disque dur. très différente, mais utilise les mêmes marcheurs et de la même manière.

La seule question restante est donc de passer en multithread le travail des marcheurs.

[Aleph69]

Bonsoir,

je pense avoir compris le principe de ton algorithme mais il y a une chose que je ne comprends pas.

j'ai peur de générer des blocages croisés : deux threads ou plus ont besoin des deux mêmes dalles. Chacun en bloque une en espérant avoir l'autre, puis la relâche quand il voir qu'il ne l'aura pas. Si c'est la dernière maille dans sa file, il recommence aussitôt. Les concurrents peuvent jouer comme ça longtemps avant que l'un réussisse enfin à bloquer les deux dalles à la fois.

Je ne vois pas pourquoi un marcheur bloquerait une dalle ou pourquoi plusieurs marcheurs ne pourraient pas occuper la même dalle.

Sinon, la solution 1 me semble bien gourmande en communications.

Dans un premier temps, pour faire simple et sans se préoccuper de la rapidité, imaginons que tu coupes ta grille en quatre grosses dalles; pour visualiser, ton relief terrestre est un carré que tu découpes en quatre parts égales en joignant les milieux des arêtes opposées. Chaque dalle possède donc deux arêtes correspondant à des (moitiés de) bords du relief et deux autres correspondant à (des moitiés de) la coupure. Est-ce que cela pose un problème pour toi de lancer en parallèle un marcheur par dalle? Je pense au fait que la coupure peut passer par une dépression par exemple ou tout autre chose qui ferait que le résultat obtenu n'est pas le bon.

[ol9245]

Bonsoir,

Est-ce que cela pose un problème pour toi de lancer en parallèle un marcheur par dalle? Je pense au fait que la coupure peut passer par une dépression par exemple ou tout autre chose qui ferait que le résultat obtenu n'est pas le bon.

Je peux éventuellement lancer un marcheur par dalle mais je crois que je vais éviter car si le marcheur de la dalle A et celui de la dalle B arrivent tous les deux de leur propre côté de la frontière entre A et B, alors ils vont chacun avoir besoin de lire les altitudes dans l'autre dalle, ce qui crée une "data race".

EDIT: en plus, accéder à l'état de la maille voisine peut nécessiter l'accès à la file de cette dalle pour marquer la maille voisine en question comme étant à visiter. En bref, on ne peut pas marcher le long d'une frontière sans bloquer la ou les dalles (jusqu'à 3 pour un coin) auxquelles appartiennent les mailles du voisinage 3x3. S'il y a des marcheurs dans ces dalles, ils devront patienter le temps que j'en finisse avec la frontière.

J'explore une autre voie : créer une tâche par dalle. la tâche consiste essentiellement en une liste de mailles à parcourir dans la dalle, + quelques variables annexes, + un accès à l'état des dalles voisines : libres, non libres, ou bloquées par la tâche elle-même.

Puis il y aurait des threads, en nombre limité, qui "butineraient" de tâche en tâche en exécutant ce qu'il est possible de faire en fonction, en particulier, de la liberté ou non de bloquer temporairement telle ou telle frontière à une dalle voisine pour consulter l'état des mailles qui se trouvent de l'autre côté.

Dans ce paradigme de thread butineur, si un thread sort de sa liste une maille dont le traitement nécessite l'accès à une frontière inaccessible, il laisserait la tâche en plan, libèrerait les frontières éventuellement bloquées, et irait butiner une autre tâche.

Ainsi, le problème de synchronisation fait un saut d'échelle : au lieu de synchroniser les mailles, ou même les dalles qui sont très nombreuses, il suffit de synchroniser les threads : un seul thread peut changer de tâche à la fois, les autres attendent leur tour. avec suffisamment de threads par rapport au nombre de processeurs, on devrait pouvoir gérer ces attentes sans impacter l'activité globale des threads au travail.

Plus je continue à réfléchir, plus j'ai l'impression d'essayer d'inventer le mur mitoyen. Ça ne me parait pas vraisemblable que ce problème ne soit pas un schéma classique en parallélisation.

[Aleph69]

Je peux éventuellement lancer un marcheur par dalle mais je crois que je vais éviter car si le marcheur de la dalle A et celui de la dalle B arrivent tous les deux de leur propre côté de la frontière entre A et B, alors ils vont chacun avoir besoin de lire les altitudes dans l'autre dalle, ce qui crée une "data race".

Justement, c'est le sens de ma question. On restreint bien chaque marcheur à sa dalle. Si une dépression est contenue dans une dalle, j'imagine que le marcheur associé va permettre de la détecter. En revanche, je m'interroge sur le cas où une dépression est coupée sur au moins deux dalles. Une fois le boulot des quatre marcheurs terminé, peut-on détecter ces dépressions? L'idée que j'ai derrière la tête est de t'amener vers une stratégie divide&conquer nécessitant très peu de communications en utilisant un raffinement de ta grille façon "quadtree".

[ol9245]

Pour l'approche hiérarchique, j'y ai pensé sans encore décider de l'étudier, mais c'est certainement intéressant.

Pour les dépressions, ce n'est pas le sujet. Les dépressions seront trouvées et traitées par la suite quand tous les marcheurs auront fini leur travail. L'algo de traitement des dépressions après le travail des marcheurs ne nécessite pas de connaitre la topologie des dépressions, ce qui est très précieux. Pense par exemple à l'enchevêtrement d'îles et de lacs dans un relief constitué d'un bruit blanc. Bref, pour l'instant, on oublie les dépressions et on se concentre sur les marcheurs. Quand toutes les files d'attente de toutes les dalles sont vides, le travail est fini.