Existe uma arquitetura para geoprocessamento distribuído?

24

Suponha que eu tenha 50 computadores na minha LAN. Cada computador possui um banco de dados geográfico para todos os polígonos de parcela em um estado específico nos EUA.

Eu gostaria de escrever uma tarefa de geoprocessamento que encontre todas as parcelas avaliadas em x $ / acre que estão a y pés de outra parcela avaliada em menos de z $ / acre.

Gostaria de formular e executar esta consulta sem saber ou se importar com a distribuição dos dados em 50 computadores. Lembre-se das condições de contorno: também quero que a consulta retorne casos em que parcelas caras em um estado estejam próximas a parcelas baratas em outro.

Existe uma arquitetura que suporte esse tipo de geoprocessamento distribuído?

A arquitetura pode ser descrita de forma abstrata ou como uma implementação específica para o Azure ou o Amazon Web Services. Ou, preferencialmente, como um escritório típico, onde os computadores ficam ociosos à noite com abundantes licenças de desktop ArcGIS.

Kirk Kuykendall
fonte
11
Boa pergunta. Neste exemplo em particular, você precisa de uma maneira de paralelizar automaticamente a construção e o uso de uma estrutura de dados espaciais, como um quadtree. Se você não fizer isso, e apenas distribuir uma pesquisa de força bruta por mais de 50 computadores, poderá reduzir a velocidade da consulta em vez de acelerar. Tenho certeza de que uma arquitetura geral como essa ainda não existe; portanto, você pode ter melhor sorte, primeiro contemplando que tipos de consulta provavelmente se beneficiarão do processamento distribuído e depois analisando as arquiteturas necessárias. Talvez poste esta pergunta no site do TCS?
whuber
@whuber Obrigado, qual é o site do TCS?
Kirk Kuykendall
@ Kirk desculpe por ser enigmático - eu era preguiçoso. cstheory.stackexchange.com
whuber
11
básica CS teoria provavelmente não ajuda, como os caras CS raramente get espacial :-)
Ian Turton
11
@iant Não há muitas pessoas de GIS por aí que vão saber muito sobre os detalhes da computação distribuída (eu não tenho nenhuma dúvida sobre os membros deste site que obviamente são excepcionais). Acredito que o pessoal do TCS terá o conhecimento necessário para responder à pergunta original sobre a existência de uma arquitetura. Minha única preocupação é se eles acham a pergunta interessante! Eu acho que se for colocado da maneira certa, eles podem. (Por exemplo, pode-se reformular em termos de estruturas de dados.)
whuber

Respostas:

13
  1. armazene todos os seus pacotes em um banco de dados central
  2. formule uma grade sobre os EUA feita de quadrados N pés de um lado, onde N é tal que o número de parcelas que se encaixam em N não exponha a memória de um de seus nós
  3. crie uma tabela no seu banco de dados com uma linha por quadrado da grade, uma coluna de identificação, uma coluna de geometria e uma coluna de status
  4. cada nó executa um pequeno programa que
    1. encontre a próxima praça não processada
    2. marca como em processo
    3. puxa todas as parcelas ST_DWithin (square, parcel, maxfeet)
    4. faz a consulta real
    5. escreve de volta a resposta da consulta a uma tabela de solução no banco de dados central
    6. marca o quadrado como completo
    7. retornar a 1

O caso óbvio de falha é que o seu raio de interesse na consulta de parcelas cresce o suficiente para que grandes partes do seu conjunto de dados sejam possíveis candidatos para corresponder a cada parcela.

Paul Ramsey
fonte
Obrigado Paul, eu precisaria de um nó atuando como coordenador dos outros nós?
Kirk Kuykendall
O banco de dados atua como um "coordenador" implícito, pois mantém o estado da fila, mas os nós não precisam ser coordenados além de serem inicializados e apontados para o banco de dados. Não tenho certeza se isso é uma resposta ou não.
Paul Ramsey
7

Havia um slot interessante no FOSS4G em setembro em Barcelona sobre isso: http://2010.foss4g.org/presentations_show.php?id=3584

Tornou-se mais um painel de discussão do que uma apresentação.

No meio deste post, Paul Ramsey faz algum tipo de resumo disso.

Nicklas Avén
fonte
Isso parece promissor, eles postaram a apresentação em algum lugar?
Kirk Kuykendall 25/10/10
Bem, desde que Schuyler Erle se tornou moderador do painel de discussão, em vez de odiar a apresentação planejada, não acho que haverá muito mais informações sobre isso. Mas desde que Erle planejou a apresentação, ele provavelmente tem algumas informações sobre isso. Ele está em toda parte, se você fizer uma pesquisa no google. Pode ser uma ideia perguntar diretamente a ele. Eu não sei. A maioria das discussões estava acima do meu entendimento, então não posso dar um currículo melhor do que Paul em seu blog.
Nicklas Avén 25/10/10
4

Talvez dê uma olhada no white paper "Servidor ArcGIS na Série Prática: Geocodificação de Lotes Grandes" nos white papers da esri .

Trata-se de geocodificação, mas o processo geral de uso de um serviço de geoprocessamento assíncrono pode ser aplicável ao seu caso.


fonte
Parece bom, eu me pergunto se isso poderia ser generalizado para outras formas de geoprocessamento. Parece que eu precisaria se sobrepor entre meus conjuntos de dados.
Kirk Kuykendall
3

A primeira coisa a se preocupar com esse problema é quais dados são necessários, onde e quando. Para fazer isso, geralmente começo com a versão estúpida e serial do problema.

Encontre todas as parcelas no valor de x $ / acre que estão a y pés de outra parcela avaliada em menos de 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)
      }
    }
  }
}

Embora esse algoritmo não seja otimizado, ele resolverá o problema.

Resolvi um problema semelhante para minha tese de mestrado, que encontrou a parcela mais próxima para cada ponto de um conjunto de dados. Eu implementei a solução no PostGIS , Hadoop e MPI . A versão completa da minha tese está aqui , mas vou resumir os pontos importantes que se aplicam a esse problema.

O MapReduce não é uma boa plataforma para resolver esse problema, pois requer acesso a todo o conjunto de dados (ou a um subconjunto cuidadosamente selecionado) para processar um único pacote. O MapReduce não lida bem com conjuntos de dados secundários.

O MPI, no entanto, pode resolver isso com bastante facilidade. A parte mais difícil é determinar como dividir os dados. Essa divisão é baseada na quantidade de dados existentes, em quantos processadores você precisa executá-los e em quanta memória você tem por processador. Para obter o melhor dimensionamento (e, portanto, desempenho), você precisará ter várias cópias do conjunto de dados das parcelas na memória (em todos os computadores) de uma só vez.

Para explicar como isso funciona, assumirei que cada um dos seus 50 computadores possui 8 processadores. Atribuirei a cada computador a responsabilidade de verificar 1/50 das parcelas. Essa verificação será executada por 8 processos no computador, cada um com uma cópia da mesma parte 1/50 das parcelas e 1/8 do conjunto de dados da parcela. Observe que os grupos não estão limitados a uma única máquina, mas podem cruzar os limites da máquina.

O processo executará o algoritmo, obtendo as parcelas para p do conjunto 1/50 de parcelas e as parcelas para q do conjunto 1/8. Após o loop interno, todos os processos no mesmo computador conversarão juntos para determinar se a parcela deve ser emitida.

Eu implementei um algoritmo semelhante a este para o meu problema. Você pode encontrar a fonte aqui .

Mesmo com esse tipo de algoritmo não otimizado, eu era capaz de obter resultados impressionantes altamente otimizados para o tempo do programador (o que significa que eu poderia escrever um algoritmo simples estúpido e a computação ainda seria rápida o suficiente). O próximo ponto a otimizar (se você realmente precisar) é configurar um índice quadtree do segundo conjunto de dados (de onde você obtém q) para cada processo.


Para responder à pergunta original. Existe uma arquitetura: MPI + GEOS. Dê uma pequena ajuda da minha implementação do ClusterGIS e muito pode ser feito. Todo esse software pode ser encontrado como código aberto, sem taxas de licenciamento. Não tenho certeza de como é portátil para o Windows (talvez com Cygwin), pois trabalhei nele no Linux. Esta solução pode ser implantada no EC2, Rackspace ou em qualquer nuvem disponível. Quando o desenvolvi, estava usando um cluster de computação dedicado em uma universidade.

Nathan Kerr
fonte
2

A metodologia de programação paralela da velha escola é apenas armazenar um estado + as parcelas que o tocam em cada processador, então é embaraçosamente fácil paralelizar. Mas, dada a variação no tamanho dos estados dos EUA, você obteria melhor desempenho dividindo o país em células da grade (novamente com o halo tocante das parcelas) e enviando cada célula da grade aos processadores usando uma configuração de escravo mestre.

Ian Turton
fonte
Em vez de parcelas que tocam, eu precisaria de parcelas dos estados adjacentes a uma distância de y.
Kirk Kuykendall
Presumo que Y seja menor o suficiente para que não seja significativamente maior que um pequeno número de parcelas. Se é uma grande fração de um estado, é melhor você usar apenas uma grade arbitrária para fazer os cálculos.
Ian Turton
2

Você pode dar uma olhada no Appistry . Pretende permitir a migração de aplicativos existentes para infraestruturas de nuvem privada. Pode haver outros projetos com um objetivo semelhante: em vez de descobrir repetidamente para cada aplicativo a porca muito complexa de decompor e distribuir tarefas para processamento paralelo, crie uma biblioteca ou plataforma que faça isso automaticamente.

Matt Wilson
fonte
Obrigado Matt, isso parece promissor. No Google, encontrei esta apresentação nos procedimentos do FedUC 2008.esri.com/library/userconf/feduc08/papers/… Gostaria de ver uma atualização sobre o que eles fizeram desde então.
Kirk Kuykendall
2

Para esse tipo de problema, eu usaria uma estrutura de mapa / redução. A estrutura Appistry "bruta" é ótima para problemas "embaraçosamente paralelos", dos quais este se aproxima. As condições da borda não permitem que seja. Mapear / Reduzir (a abordagem do Google para a computação distribuída) é ótimo nesse tipo de problema.

O maior avanço na Appistry desde o artigo 08 é o lançamento do produto CloudIQ Storage. Isso permite o recurso de armazenamento "s3", utilizando os discos nos servidores locais. Em seguida, o produto CloudIQ Engine pode habilitar serviços de alto volume ou aplicativos de estilo de dispersão / coleta de qualquer tipo (comprovamos a escalabilidade usando o tempo de execução ESRI e outras bibliotecas de código aberto). Se você estiver operando com dados baseados em arquivos, distribua-os usando o CloudIQ Storage e roteie os trabalhos de processamento para as réplicas de arquivos locais, para que eles não precisem ser movidos pela rede. (para que cada nó não precise de todos os dados)

Para Mapear / Reduzir, é possível colocar em camadas algo como o Hadoop (estrutura M / R de código aberto) no CloudIQ Storage. Eu procuraria no Hadoop o problema conforme descrito, mas você realmente precisa se aprofundar, não é fácil começar, e o M / R é um dobrador de cérebros. Há também uma distribuição comercialmente suportada oferecida pela Cloudera. Há outro produto Appistry, o CloudIQ Manger, que é um ótimo complemento para o Hadoop (Cloudera ou não) para distribuição e gerenciamento.

Eu começaria com o Hadoop (sistema de arquivos M / R e HDFS) e, se você precisar de uma solução escalável com suporte comercial, consulte o Appistry CloudIQ Manager and Storage, em conjunto com a distribuição Cloudera Hadoop.

Se você deseja uma arquitetura mais simples para tarefas "embaraçosamente paralelas", consulte também o CloudIQ Engine. (as abordagens descritas no artigo de Kirk ainda são válidas)


fonte