Existe-t-il une architecture pour le géotraitement distribué?

24

Supposons que j'ai 50 ordinateurs sur mon LAN. Aux États-Unis, chaque ordinateur possède une géodatabase pour tous les polygones de parcelles dans un état particulier.

Je voudrais écrire une tâche de géotraitement qui trouve tous les colis d'une valeur plus x $ / acre qui sont à y pieds d' une autre parcelle qui est évaluée à moins de z $ / acre.

Je voudrais formuler et exécuter cette requête sans savoir ni se soucier que les données sont réparties sur 50 ordinateurs. Gardez à l'esprit les conditions aux limites: je souhaite également que la requête renvoie les cas dans lesquels des colis coûteux dans un État sont proches de colis bon marché dans un autre.

Existe-t-il une architecture qui prend en charge ce type de géotraitement distribué?

L'architecture peut être décrite de manière abstraite ou comme une implémentation spécifique à Azure ou Amazon Web Services. Ou, de préférence, comme un bureau typique où les ordinateurs restent inactifs la nuit avec de nombreuses licences de bureau ArcGIS.

geoprocessing cloud-gis amazon-web-services Kirk Kuykendall
la source
1
Bonne question. Dans cet exemple particulier, vous avez besoin d'un moyen de paralléliser automatiquement la construction et l'utilisation d'une structure de données spatiales telle qu'un quadtree. Si vous ne le faites pas et distribuez simplement une recherche par force brute sur 50 ordinateurs, vous risquez en fait de ralentir la requête plutôt que de l'accélérer. Je suis sûr qu'une architecture générale comme celle-ci n'existe pas encore, vous pourriez donc avoir plus de chance en envisageant d'abord les types de requêtes susceptibles de bénéficier d'un traitement distribué, puis en examinant les architectures dont elles ont besoin. Peut-être poster cette question sur le site TCS?
whuber
@whuber Merci, quel est le site TCS?
Kirk Kuykendall du
@Kirk désolé d'être cryptique - j'étais paresseux. cstheory.stackexchange.com
whuber
1
la théorie CS de base n'aidera probablement pas car les gars CS obtiennent rarement de l'espace :-)
Ian Turton
1
@iant Il n'y a pas trop de personnes SIG qui vont en savoir beaucoup sur les écrous et les boulons de l'informatique distribuée (je ne jette aucune objection sur les membres de ce site qui sont évidemment exceptionnels). Je crois que les gens du TCS auront les connaissances pour répondre à la question initiale concernant l'existence d'une architecture. Ma seule préoccupation est de savoir s'ils trouveraient la question intéressante! Je pense que si c'est bien fait, ils le pourraient. (Par exemple, on pourrait le recadrer en termes de structures de données.)
whuber

Réponses:

13
  1. stocker tous vos colis dans une base de données centrale
  2. formuler une grille sur les États-Unis composée de carrés N pieds sur un côté, où N est tel que le nombre de parcelles qui s'inscrivent dans N ne fera pas exploser la mémoire sur l'un de vos nœuds
  3. créer une table dans votre base de données avec une ligne par carré de grille, une colonne id une colonne géométrie et une colonne status
  4. chaque nœud exécute un petit programme
    1. trouver la prochaine place non transformée
    2. le marque comme en cours
    3. tire toutes les parcelles ST_DDans (carré, colis, maxfeet)
    4. fait la requête réelle
    5. réécrit la réponse à la requête dans une table de solution dans la base de données centrale
    6. marque le carré comme terminé
    7. retour à 1

Le cas d'échec évident est que votre rayon d'intérêt dans la requête de parcelle augmente suffisamment pour que de grandes parties de votre ensemble de données soient des candidats potentiels pour correspondre à chaque parcelle.

Paul Ramsey
la source
Merci Paul, aurais-je besoin d'un nœud agissant comme coordinateur pour les autres nœuds?
Kirk Kuykendall,
La base de données agit comme un "coordinateur" implicite dans la mesure où elle contient l'état de la file d'attente, mais les nœuds n'ont pas besoin d'être coordonnés au-delà du démarrage et pointés vers la base de données. Je ne sais pas si c'est une réponse ou non.
Paul Ramsey
7

Il y avait une fente intéressante sur FOSS4G en septembre à Barcelone à ce sujet: http://2010.foss4g.org/presentations_show.php?id=3584

C'est devenu plus une table ronde qu'une présentation.

Au milieu de ce billet de blog, Paul Ramsey en donne une sorte de résumé.

Nicklas Avén
la source
Cela semble prometteur, ont-ils posté la présentation quelque part?
Kirk Kuykendall
Eh bien, depuis que Schuyler Erle est devenu modérateur de la table ronde au lieu de hoding la présentation prévue, je ne pense pas qu'il y aura beaucoup plus d'informations à ce sujet. Mais depuis qu'Erle avait prévu cette présentation, il a probablement quelques informations à ce sujet. Il est partout si vous effectuez une recherche Google. Ce pourrait être une idée de lui demander directement. Je ne sais pas. La plupart des discussions étaient au-dessus de ma compréhension, donc je ne peux pas donner de meilleur curriculum vitae que Paul dans son blog.
Nicklas Avén
4

Consultez peut-être le livre blanc «ArcGIS Server in Practice Series: Large Batch Geocoding» sur les livres blancs esri .

Il s'agit de géocodage, mais le processus général d'utilisation d'un service de géotraitement asynchrone peut s'appliquer à votre cas.


la source
Ça a l'air bien, je me demande si cela pourrait être généralisé à d'autres formes de géotraitement. Il semble que j'aurais besoin d'un chevauchement entre mes ensembles de données.
Kirk Kuykendall,
3

La première chose à se préoccuper de ce problème est de savoir quelles données sont nécessaires où et quand. Pour ce faire, je commence généralement par la version série stupide du problème.

Trouvez toutes les parcelles d'une valeur supérieure à x $ / acre qui se trouvent à moins de y pieds d'une autre parcelle d'une valeur inférieure à z $ / acre.

foreach p in parcels {
  if value(p) > x {
    foreach q in parcels {
      if (dist(p,q) <= y) and (value(q) < z) {
        emit(p)
      }
    }
  }
}

Bien que cet algorithme ne soit pas optimisé, il résoudra le problème.

J'ai résolu un problème similaire pour ma thèse de maîtrise qui a trouvé la parcelle la plus proche pour chaque point d'un ensemble de données. J'ai implémenté la solution dans PostGIS , Hadoop et MPI . La version complète de ma thèse est ici , mais je vais résumer les points importants en ce qui concerne ce problème.

MapReduce n'est pas une bonne plate-forme pour résoudre ce problème car il nécessite l'accès à l'ensemble de données (ou à un sous-ensemble soigneusement sélectionné) pour traiter une parcelle unique. MapReduce ne gère pas bien les jeux de données secondaires.

MPI, cependant, peut résoudre ce problème très facilement. La partie la plus difficile consiste à déterminer comment diviser les données. Cette répartition est basée sur la quantité de données, le nombre de processeurs sur lesquels vous devez les exécuter et la quantité de mémoire dont vous disposez par processeur. Pour une meilleure mise à l'échelle (et donc des performances), vous devrez disposer de plusieurs copies du jeu de données de parcelles en mémoire (sur tous vos ordinateurs) à la fois.

Pour expliquer comment cela fonctionne, je suppose que chacun de vos 50 ordinateurs possède 8 processeurs. J'attribuerai ensuite à chaque ordinateur la responsabilité de contrôler 1/50 des colis. Cette vérification sera exécutée par 8 processus sur l'ordinateur, chacun ayant une copie de la même partie 1/50 des colis et 1/8 du jeu de données de colis. Veuillez noter que les groupes ne sont pas limités à une seule machine, mais peuvent traverser les limites des machines.

Le processus exécutera l'algorithme, obtenant les parcelles pour p à partir du 1 / 50e ensemble de parcelles, et les parcelles pour q à partir du 1 / 8e ensemble. Après la boucle interne, tous les processus sur le même ordinateur parleront ensemble pour déterminer si le colis doit être émis.

J'ai implémenté un algorithme similaire à celui-ci pour mon problème. Vous pouvez trouver la source ici .

Même avec ce type d'algorithme non optimisé, j'ai pu obtenir des résultats impressionnants qui étaient hautement optimisés pour le temps du programmeur (ce qui signifie que je pouvais écrire un algorithme simple stupide et que le calcul serait encore assez rapide). Le point suivant à optimiser (si vous en avez vraiment besoin), est de configurer un index quadtree du deuxième ensemble de données (d'où vous obtenez q) pour chaque processus.

Pour répondre à la question d'origine. Il existe une architecture: MPI + GEOS. Ajoutez un peu d'aide de mon implémentation ClusterGIS et beaucoup peut être fait. Tous ces logiciels peuvent être trouvés en open source, donc pas de frais de licence. Je ne sais pas à quel point il est portable pour Windows (peut-être avec Cygwin) car j'ai travaillé dessus sous Linux. Cette solution peut être déployée sur EC2, Rackspace ou tout autre cloud disponible. Quand je l'ai développé, j'utilisais un cluster de calcul dédié dans une université.

Nathan Kerr
la source
2

La méthodologie de programmation parallèle de la vieille école consiste à simplement stocker un état + les parcelles qui le touchent sur chaque processeur, puis il est embarrassamment facile de paralléliser. Mais étant donné la variation de la taille des États américains, vous obtiendrez de meilleures performances en divisant le pays en cellules de grille (encore une fois avec le halo touchant des parcelles) et en envoyant chaque cellule de grille aux processeurs en utilisant une configuration maître-esclave.

Ian Turton
la source
Au lieu de colis qui se touchent, j'aurais besoin de colis des États adjacents à une distance y.
Kirk Kuykendall
Je suppose que Y est suffisamment petit pour qu'il ne soit pas significativement plus grand qu'un petit nombre de colis. S'il s'agit d'une grande partie d'un état, il serait probablement préférable d'utiliser simplement une grille arbitraire pour effectuer les calculs.
Ian Turton
2

Vous voudrez peut-être jeter un œil à Appistry . Il prétend permettre la migration des applications existantes vers des infrastructures de cloud privé. Il peut y avoir d'autres projets avec un objectif similaire: plutôt que de trouver encore et encore pour chaque application l'écrou très complexe de la décomposition et de la distribution des tâches au traitement parallèle, créer une bibliothèque ou une plate-forme qui le fait automatiquement.

Matt Wilkie
la source
Merci Matt, cela semble prometteur. Googler J'ai trouvé cette présentation de FedUC 2008 procedure.esri.com/library/userconf/feduc08/papers/… Je serais curieux de voir une mise à jour sur ce qu'ils ont fait depuis lors.
Kirk Kuykendall du
2

Pour ce type de problème, j'utiliserais un cadre de carte / réduire. Le cadre d'application "brut" est idéal pour les problèmes "embarrassamment parallèles", dont celui-ci est proche. Les conditions de bord ne le permettent pas. Map / Reduce (l'approche de Google pour l'informatique distribuée) est parfait pour ce type de problème.

La plus grande avancée d'Appistry depuis la publication du 08 est la sortie du produit CloudIQ Storage. Cela permet une installation de stockage de type «s3» en utilisant les disques sur vos serveurs locaux. Ensuite, le produit CloudIQ Engine peut activer des services à volume élevé ou des applications de style diffusion / collecte de toute sorte (nous avons prouvé l'évolutivité en utilisant le runtime ESRI et d'autres bibliothèques open source). Si vous utilisez des données basées sur des fichiers, vous les distribuez à l'aide de CloudIQ Storage et acheminez les travaux de traitement vers les réplicas de fichiers locaux afin qu'ils n'aient pas à être déplacés sur le réseau. (donc chaque nœud n'a pas besoin de toutes les données)

Pour Map / Reduce, vous pouvez superposer quelque chose comme Hadoop (framework open source M / R) sur CloudIQ Storage. Je regarderais Hadoop pour le problème tel que décrit, mais vous avez vraiment besoin de plonger, ce n'est pas facile de commencer, et M / R est un casse-tête. Cloudera propose également une distribution commerciale. Il existe un autre produit Appistry, CloudIQ Manger, qui est un bon complément à Hadoop (Cloudera ou autre) pour la distribution et la gestion.

Je commencerais par Hadoop (système de fichiers M / R et HDFS), et si vous avez besoin d'une solution évolutive prise en charge plus commercialement, regardez Appistry CloudIQ Manager and Storage, en conjonction avec la distribution Cloudera Hadoop.

Si vous voulez une architecture plus simple pour des tâches "parallèlement embarrassantes", regardez également CloudIQ Engine. (les approches décrites dans l'article référencé par Kirk sont toujours valides)


la source