Programação Paralela em Arquiteturas Multi-Core/Aplicações Internet: diferenças entre revisões

Origem: Wikilivros, livros abertos por um mundo aberto.
[edição não verificada][edição não verificada]
Conteúdo apagado Conteúdo adicionado
Nandopi (discussão | contribs)
Nandopi (discussão | contribs)
Linha 34: Linha 34:


Algoritmos paralelos para cada operação e organização das árvores de consultas podem ser usados para aumentar significativamente o número de otimizações possíveis encontradas a cada consulta, aumentando consideravelmente a velocidade das consultas.
Algoritmos paralelos para cada operação e organização das árvores de consultas podem ser usados para aumentar significativamente o número de otimizações possíveis encontradas a cada consulta, aumentando consideravelmente a velocidade das consultas.

=== Gerenciamento de tráfego ===


=== Protocolos paralelos ===
=== Protocolos paralelos ===

Revisão das 01h14min de 14 de dezembro de 2007


Este capítulo se encontra em construção    -   Previsão de Conclusão: 14/12   Progresso:


Introdução

Uma breve história e introdução sobre a necessidade de aplicações paralelas na internet e sobre o capítulo.

Aplicações para infra-estrutura

Banco de Dados

Sistemas de banco de dados altamente paralelos estão começando a substituir os tradicionais mainframes para maiores bancos de dados e tarefas de transações.

A partir da hegemonia do modelado de dados relacionais, sistemas de banco de dados relacionais começaram a aparecer no mercado. As consultas relacionais são idealmente convertidas para execução em paralelo, pois elas consistem em operações uniformes aplicadas a conjuntos de dados uniformes. Cada operação produz uma nova relação, então as operações podem ser decompostas em fluxos de dados altamente paralelos.

Ao utilizamos a saída de um operador na entrada de outro, os dois operadores podem trabalhar em série, o que gera um pipeline paralelo. Podemos também particionar os dados de entrada entre vários processadores e memórias, pois uma operação pode, com grande freqüência, ser dividida em várias operações independentes, cada um trabalhando em uma parte dos dados. Esta divisão de dados e execução gera um paralelismo particionado.

Esta técnica requer uma comunicação entre os sistemas de bancos de dados paralelos, seja através de mensagens, seja através de recursos compartilhados ou de outros métodos possíveis. Esses métodos se baseiam na arquitetura do sistema de banco de dados.

Apesar do grande número de arquiteturas de sistemas de banco de dados paralelos e distribuídos, há um consenso quanto ao uso da arquitetura sem compartilhamento. Nesses sistemas, as tuplas de cada relação no banco de dados são particionadas dentre as unidades de disco que estão ligadas diretamente a cada processador. Isso permite que vários processadores possam buscar em grandes relações paralelamente sem precisar de dispositivos de E/S sofisticados.

Otimização de consultas em paralelo

Os otimizadores de consultas a banco de dados não consideram todos as possíveis formas de otimização em uma consulta relacional devido a sua complexidade e, apesar dos modelos de custos para consultas relacionais executadas em um único processador serem bem conhecidos, eles ainda dependem de estimativas de custo, que no melhor caso, adivinham.

Algoritmos paralelos para cada operação e organização das árvores de consultas podem ser usados para aumentar significativamente o número de otimizações possíveis encontradas a cada consulta, aumentando consideravelmente a velocidade das consultas.

Protocolos paralelos

O aumento da demanda por conteúdo multimídia, atualizações dentre outros, tornaram os servidores distribuídos cada vez mais utilizados para suprir esta demanda, sem o congestionamento na transmissão e falha do servidor por falha em um ponto único, que são problemas comuns de servidores centralizados. Além disso, servidores centralizados só podem responder a um número limitado de clientes, devido ao limite de conexões.

Servidores distribuídos permitiram que recursos sejam disponibilizados em pontos de grande demanda, aliviando o problema de congestionamento em servidores centralizados. Apesar disso, as taxas de transferências continuam as mesmas dos servidores centralizados, pois apenas um nó no sistema distribuído realiza a transferência. Paralelismo podem melhorar a transmissão.

O objetivo dos protocolos paralelos é provê suporte a transferências de arquivos paralelas em servidores distribuídos.

Os protocolos têm que resolver problemas como:

  • descobrir aonde o arquivo existe no servidor distribuído
  • distribuir a tarefa entre os servidores selecionados
  • transmitir o arquivo em seguimentos paralelos
  • unir o arquivo automaticamente
  • recuperar seguimentos perdidos

Além disso, existem dois problemas básicos ao utilizar download distribuído: balanceamento de carga dinâmico e transparência ao usuário.

Enquanto o “download” está ocorrendo, a carga dos servidores deve ser checada para garantir que a carga continue baixa, senão o desempenho é reduzido. Quando um servidor ultrapassa sua capacidade, replicas são migradas para outros servidores até o servidor carregado atinga o nível adequado de carga. Se a demanda for muito alta, uma replica é criada ao invés de migrada e é destruída se a demanda for baixa.

Balanceamento dinâmico de carga é essencial para manter transmissões efetivas de arquivos. Apesar de manter a demanda no máximo parecer lógico, as vezes, isto atrapalha a transmissão. Focar somente na demanda gera outros problemas na rede como congestionamento, o que degenera o proposito dos sistemas distribuídos.

A transparência ao usuário, permite sistemas de software mudem sem alterar os sistemas ao redor, usando interfaces. A transparência é obtida ao construir uma interface para o sistema e depois construir os sistemas ao redor baseados na interface. Ao realizar isto, o sistema atrás da interface pode ser mudado sem afetar os sistemas em volta.

Os protocolos paralelos devem ser transparentes ao usuário e a outras aplicações, para que possam ser compatíveis com as aplicações atuais e outros protocolos.

Aplicações distribuídas

FAZER INTRODUÇÃO DO TÓPICO

  • WEB CRAWLWERS
    • CONFERIR LINKS
    • COLOCAR FIGURA
    • COLOCAR REFERENCIAS
  • GRID
    • FAZER
  • P2P
    • FAZER

Grid

Definição

Uma aplicação paralela consiste de diversas tarefas. Cada tarefa roda em um processador distinto, possibilitando que a aplicação compute em paralelo, desta forma executando mais velozmente do que se estivesse rodando em um único processador. Tarefas comunicam-se entre si para garantir o progresso consistente da aplicação. A intensidade da comunicação entre as tarefas de uma dada aplicação paralela estabelece a granularidade daquela aplicação. Aplicações que demandam intensa comunicação são ditas pesadas ou de fina granulariade. Aplicações cujas tarefas requerem pouca comunicação são ditas leves ou de grossa granularidade.

A granularidade de uma aplicação paralela estabelece requerimentos para a plataforma na qual a aplicação é executada. A plataforma de execução de uma aplicação paralela consiste dos processadores usados pela aplicação e também das redes que conectam estes processadores. Aplicações paralelas pesadas demandam plataformas dedicadas (tais como supercomputadores massivamente paralelos) para que o overhead de comunicação não anule os ganhos decorrentes do paralelismo. Aplicações paralelas leves, ao contrário, podem efetivamente utilizar processadores compartilhados e interconectados por redes de longa distância.

Aplicações paralelas leves têm sido foco de muita atenção em indústrias e universidades, devido principalmente a dois importantes fatores. Primeiro, as aplicações paralelas leves representam uma fração respeitável das aplicações paralelas, incluindo data mining, pesquisas massivas e várias aplicações de manipulação de imagens(como tumografia), por exemplo. Segundo, o projeto SETI@home [1] demonstrou que aplicações paralelas leves podem utilizar efetivamente um número grande de processadores conectados à Internet.

A computação em grade (do Inglês grid computing) é um modelo computacional capaz de alcançar uma alta taxa de processamento dividindo as tarefas entre diversas máquinas, podendo ser em rede local ou rede de longa distância, que formam uma máquina virtual. Esses processos serão executados no momento em que as máquinas não estão sendo utilizadas pelo usuário, evitando assim o desperdício de processamento da máquina utilizada. A metáfora adotada na computação em grade é a da rede eletrica (grid, em Inglês). Isto é, o poder computacional deveria estar disponível na Internet da mesma forma que energia elétrica está disponível na tomada: sob demanda e de maneira transparente.

Uma experiência de integração de processamento distribuído é o projeto SETI@home, uma continuação do projeto da NASA de busca de inteligência extraterrestre. Usando um software que pode ser baixado pela Internet, um microcomputador pode analisar sinais do rádio telescópio de Arecibo. Atualmente, existem 4 milhões de assinantes em 224 países, criando um computador virtual com uma performance de 20 Tflops.

Um outro exemplo são as famosas redes peer-to-peer, como Emule (Edonkey), Kazaa, Gnutella, em que se compartilham arquivos por exemplo, mas sem nenhum controle de acesso e não interoperam entre si. Com a evolução dessas aplicações elas acabaram por inter-operar e haverá uma convergência de interesses entre computação ponto a ponto, Internet e computação em grade.

A computação em grade é próxima geração da Internet – são protocolos adicionais construídos sobre a tecnologia da Internet. Qualquer recurso que esteja na Grade, também está na Rede.

A diferença existente entre a computação distribuída e computação em grade se dá pelo fato de que a computação distribuída é um conceito que vem dos anos 80 e 90, e consiste na possibilidade de resolver um determinado problema computacional através da utilização de diferentes recursos distribuídos geograficamente. A computação distribuída passa a ser uma “Computação em Grade” no momento em que existe uma infra-estrutura física e uma infra-estrutura lógica (software) que permita coordenar os trabalhos que vão ser processados e garantir a sua qualidade de serviço.

Grids são construídos como um grupamento de serviços básicos independentes. Um aspecto essencial dos serviços de Grid é que esses estão disponíveis uniformemente através dos ambientes distribuídos na Grid. Os serviços são agrupados em um sistema integrado, também chamado de middleware. Exemplos de ferramentas atuais de Grid incluem Globus, Legion, OpenGrid, AppLeS.

O Grid permite também o uso de técnicas de programação paralela por passagem de mensagens. O ambiente MPI (“Message Passing Interface”) está disponível no Grid através da versão MPICH-G2 (versão portátil do MPI para o Globus). O padrão MPI define uma biblioteca de rotinas que implementam uma comunicação ponto a ponto, em que a operação “send” é usada para iniciar uma transferência de dados entre dois programas concorrentes e a operação “receive” é usada para obter dados do sistema no espaço de memória da aplicação; existem ainda operações coletivas envolvendo múltiplos processos. Mas que devido a alta latência provocada na comunicação entre processos, as aplicações devem ser construídas com uma granularidade bem projetada de tal forma que se comuniquem o mínimo possível. Então, as aplicações mais adequadas ao Grid são as que possuem tarefas independentes (bag of tasks), pois as tarefas não dependem da execução de outras e podem ser executadas em qualquer ordem.

A Internet surgiu no início da década de 70 com o objetivo de interligar diferentes ambientes computacionais e geograficamente dispersos. Os web sites desenvolvidos pela indústria sempre foram interoperáveis em relação usuário-site, por meio de aplicações criadas neste contexto, em que o usuário dispõe de um menu de serviços fechados. O que ocorre em um ambiente de Grid é o inverso, onde o usuário tem de submeter suas aplicações para serem resolvidas dentro do ambiente por ele montado.

Um ambiente de cluster constitui em um sistema formado por hardware e software conectados em um local apenas, servindo a usuários que estão trabalho somente em um projeto, usado exclusivamente para resolver os problemas computacionais de uma determinada organização. Por outro lado, um Grid presta serviços de uma forma geograficamente distribuída. Em um cluster, os recursos são gerenciados por uma entidade central, e os computadores agem como se fosse um único dispositivo. Nas configurações em Grid, cada “organização virtual” faz o gerenciamento de seus recursos não tendo a visão de uma imagem única do sistema. Ou seja, o usuário tem consciência dos diversos serviços disponíveis e que deverá requisitá-los para sua utilização. Portanto, os Grids são mais heterogêneos, complexos e distribuídos.

COLOCAR FIGURA DA WIKIPEDIA

Benefícios

Um Grid possui muitos benefícios, entre os quais podemos citar:

  • Organizações podem agregar recursos - a computação em Grid permite que as organizações possam agregar recursos com toda a infraestrutura dos ITs, não importando localização global. Isso elimina situações onde um site esteja sendo executado com sua capacidade máxima, enquanto outros tenham ciclos disponíveis.
  • Poderosa plataforma de suporte a Organizações Virtuais - organizações podem melhorar dramaticamente sua qualidade e velocidade de produtos e serviços disponibilizados, enquanto os custos de IT são reduzidos por habilitar a colaboração transparente dos recursos compartilhados
  • Acesso distribuído a diversos tipos de recursos - permite que empresas acessem e compartilhem bases de dados de forma remota. Isto é essencialmente benéfico para as ciências da saúde ou comunidades de pesquisa, onde volumes grandiosos de dados são gerados e analisados durante todo dia.
  • Colaboração entre centro de pesquisas - possibilita a larga dispersão das organizações para que facilmente possam colaborar em projetos pela criação da habilidade do compartilhamento de tudo, desde aplicações a dados, até projetos de engenharia, etc.
  • Melhor utilização de largura de banda - pode-se criar a mais robusta e resistente infraestrutura de informações.
  • Aproveitamento de recursos ociosos – pode-se aproveitar os ciclos de processamento idle disponíveis dos PCs desktops que se encontram em várias localidades pelo planeta. Por exemplo, os computadores que se encontram tipicamente ociosos durante a noite de uma empresa em Tókio pode ser utilizado durante o dia para operações na América do Sul.

Desafios

A computação em grade, por ser uma tecnologia ainda muito recente, possui muitos desafios operacionais e de pesquisa a serem combatidos. Apenas para exemplificar, citamos alguns deles:

  • Localização dos recursos
  • Reserva de recursos
  • Capacidade para adaptar- se a mudanças no ambiente
  • Criação e escalonamento das tarefas
  • Autonomia de cada grupo participante para definir suas próprias políticas de segurança
  • Recursos requisitados podem estar em diferentes localidades
  • Qualidade de serviço exigida por cada aplicação

Conclusão

O Grid Computing é um desafio bem maior do que formas mais simples de computação paralela e distribuída. Hoje, a maioria dos projetos de Grid permanecem localizados nos centros de supercomputação e laboratórios universitários. Os centros de pesquisa são ligados a conexões em rede cerca de 20 vezes mais rápidas do que as conexões de banda largas normais, são equipadas com sistemas de armazenamento capazes de lidar com vastos arquivos de dados e com computadores de alta performance. O Grid Computing é um conceito sobre o qual existe ainda uma grande expectativa e que poderá evoluir em diferentes direções, mas que é já hoje entendido como a próxima geração da Web para a comunidade científica.

P2P

FAZER

Web Crawlers

Uma outra aplicação interessante do paralelismo na internet é na construção de Web crawlers, também conhecidos como robôs [2]. Um crawler é um programa que coleta e armazena páginas da Internet, sendo muito utilizados em máquinas de busca.

Definição

Um crawler geralmente começa a funcionar a partir de um conjunto inicial de URLs [3], , armazenadas numa fila. Partindo do conjunto inicial, o crawler pega alguma URL, em alguma ordem pré-definida, coleta a página, extrai novas URLs encontradas a partir da página coletada, e insere essas novas URLs na fila. O processo se repete até que o crawler decide parar. As páginas coletas podem ser utilizadas para aplicações como em máquinas de busca, em Web caches ou em estudos científicos, por exemplo.

Com a expansão diária do tamanho da Web, fica cada vez mais difícil coletar toda ou uma significante parte da Web em um só processo. Então, a paralelização dos Web crawlers se tornam uma medida essencial para maximizar a taxa de captura dos dados.

A construção de Web crawlers paralelos tem muitas vantagens mas trazem também alguns problemas e desafios interessantes. Entre eles, podemos citar:

  • Sobreposição: com muitos processos rodando em paralelo para coletar páginas, é possível que diferentes processos coletem uma mesma página múltiplas vezes.
  • Qualidade: geralmente é mais interessante coletar as páginas mais "importantes" primeiro, a fim de maximizar a "qualidade" dos dados coletados. Em crawlers paralelos, cada processo pode não ter conhecimento da imagem de toda a rede coletada, tomando decisões de acordo com a imagem local da parte que coletou.
  • Banda de Comunicação: periodicamente os processos precisam se comunicar para prevenir a sobreposição de dados ou melhorar a qualidade da coleta. Entretando, essa comunicação pode crescer bastante à medida em que o número de processos aumentam.

A paralelização dos web crawlers nos trazem importantes vantagens em relação aos crawlers não paralelizados, como:

  • Escalabilidade: devido ao enorme tamanho da Web, é quase que uma obrigação utilizar crawlers paralelos. Um crawler de um único processo simplesmente pode não atingir a taxa de coleta desejada em certos casos.
  • ```NETWORK-LOAD DISPERSION```: os múltiplos processos de um crawler paralelo podem rodar em lugares geograficamente distantes, cada um coletando dados de locais próximos geograficamente. Por exemplo, um processo no Brasil pode coletar páginas dos países da América do Sul, enquanto um outro processo na Alemanha coleta dados da Europa. Essa dispersão pode ser necessária quando um crawler serial não consegue lidar com uma carga pesada de uma coleta em larga escala.
  • ```NETWORD-LOAD REDUCTION```: um crawler paralelo pode também reduzir a carga na rede. Por exemplo, assuma que um crawler na América do Norte precise coletar uma página da Europa. Primeiramente, a página deve ir pela rede na Europa, passando pela rede inter-continental Europa-para-América do Norte, e finalmente passa pela rede na América do Norte. Se um processo de um crawler paralelo coleta todas as páginas européias, e outro processo coleta as páginas da América do Norte, então o tráfego total na rede será reduzido.

Note que as páginas coletadas devem ser transferidas para uma central de comando, a fim de se construir um indice geral. Essa transferência de dados pode ser bastante reduzida usando algum dos seguintes métodos:

  • Compressão: as páginas coletas e armazenadas podem ser comprimidas antes de serem enviadas a uma localização central.
  • Diferença: ao invés de mandar uma imagem inteira de todas as páginas coletadas por um processo, é possível mandar apenas a diferença entre a imagem corrente e a anterior. Isso pode reduzir o tráfego porque muitas páginas são estáticas e não costumam ser atualizadas com muita frequência.
  • Sumarização: em muitos casos é necessário apenas um indice central, e não as páginas originais. Nesses casos, apenas as informações relevantes precisam ser enviadas ao centro de comando.

Fica claro que para a construção de Web crawlers efetivos é necessário muito mais do que apenas uma simples paralelização.

Arquitetura de um crawler paralelo

A figura [[Image: | Arquitetura geral de um crawler paralelo]] nos mostra a arquitetura geral de um crawler paralelo, que consiste de múltiplos processos, referidos por . Cada é responsável por executar uma tarefa básica de um crawler não paralelo. Ele coleta páginas da Web, armazena as páginas localmente, extrai todas as URLs que encontrar e segue os links. Dependendo da forma com que as tarefas são divididas entre os , pode ser necessário a troca de dados entre os processos. A distribuição de tarefas entre os pode ser feita numa rede local (como uma LAN), ou em localizações geograficamente distantes (como uma WAN).

  • Intra-site crawler: quando todos os processos rodam em uma mesma rede local e se comunicam em alta velocidade. Na figura anterior, isso pode ser observado no caso onde todos os rodam na rede local da parte de cima.
  • Crawler distribuido: quando todos os processos rodam em localizações geograficamente distantes. Quando os processos nessas localizações distantes se conectam via Internet, se torna importante determinar a frequência e a quando os processos devem se comunicar.

Em um crawler que roda com múltiplos processos, é possível ocorrer o problema da sobreposição. Para evitar esse problema, os processos devem ser coordenados entre eles para saber quais páginas cada um deve coletar. Essa coordenação pode ser feita seguindo algum dos caminhos:

  • Independência: os podem coletar páginas de uma maneira completamente independente um dos outros sem qualquer coordenação. Cada processo começa com um conjunto de URLs e vai seguindo os links sem consultar outro processo. Neste cenário, o problema da sobreposição pode ocorrer.
  • Assinalamento Dinâmico: ocorre quando existe uma central de comando que divide a Web em partições pequenas, usando para isto alguma função pré-estabelecida, e dinamicamente assinala cada partição a um processo. Essas partições podem ser feitas em diferentes granularidades, o que afeta a comunicação entre os processos e a central de comando.
  • Assinalamento Estático: ocorre quando a Web é particionada e assinalada a cada antes de começar a coleta. Neste caso, cada sabe qual é responsável por qual página, não precisando de uma central de comando para isto.

Conclusão

Estudos mais detalhados sobre crawlers paralelos podem ser encontrados em diversas referências, como [] MAIS REFERENCIAS - PEGAR NO RELATED WORK DO PAPER.

Web crawlers vem sendo utilizados com cada vez mais frequência para coletar dados da Web para máquinas de busca, caches e mineração de dados. Como o tamanho da Web aumenta a cada dia que passa, o uso de crawlers paralelos vem se tornando cada vez mais importante. Conforme observado nessa subseção, construir um crawler paralelo eficiente é muito mais complicado do que uma simples paralelização.

Programação paralela na web

  • Ambientes de programação
  • Bibliotecas de programação
  • Linguagens de programação
    • PHP
    • Java
  • Tecnologias
    • AJAX
    • CGI

Conclusão

Referências

A Parallel Downloading Protocol for the Internet

Preparing PHTTP for the Real World

Implementing a parallel file transfer protocol

Parallel Database Systems: The Future of High Performance Database Processing

Using parallel Oracle for high-speed e-commerce systems