Projeto e implementação de aplicações

Nesta seção, primeiro apresentamos uma metodologia para a construção de aplicações big-data. Esta metologia se divide em cinco etapas, detalhadas nas seções a seguir. Após esse detalhamento, apresentamos alguns estudos de caso de desenvolvimento de aplicações de processamento de dados massivos desenvolvidas pelos alunos da disciplina no DCC/UFMG.

Descrição da aplicação

A primeira etapa da metodologia é a descrição da aplicação. Essa descrição tem por objetivo identificar claramente a aplicação a ser paralelizada e o contexto da paralelização. A descrição consiste das seguintes informações:

Denominação: Para fins de referência, é importante estabelecer uma denominação para a aplicação, a qual pode ser o nome do algoritmo, da família de algoritmos ou mesmo da aplicação como um todo que faz uso de um ou mais algoritmos.

Contexto: O contexto da aplicação apresenta informações históricas sobre a mesma, assim como a sua evolução em termos de propostas e cenários de aplicação. Informações sobre a sua relevância, impacto e aplicabilidade também são pertinentes. Essas informações podem subsidiar e explicar requisitos, cargas de trabalho e parâmetros de execução, além de prover indicações sobre qual algoritmo (se houver mais que um) é o mais apropriado para a paralelização.

Algoritmo(s): A descrição do algoritmo deve ser feita em alguma linguagem ou pseudo-linguagem de fácil entendimento, em geral com características imperativas. O nível de detalhe dessa descrição deve ser tal que seja possível replicar e reimplementar o algoritmo, mesmo que fazendo uso de tipos abstratos de dados conhecidos. Caso haja mais de um algoritmo aplicável, todos devem ser descritos e detalhados, o que se configura um importante subsídio para a paralelização.

Exemplo(s) de Funcionamento: A metodologia ora apresentada se baseia fortemente no entendimento do funcionamento dos vários algoritmos, o que é fundamental para capturar as interações entre os componentes de processamento, armazenamento e comunicação. Assim, exemplos didáticos mostrando o funcionamento de cada algoritmo descrito para entradas de pequena magnitude (toy problems) são um importante subsídio.

Requisitos: A elicitação dos requisitos a serem atendidos pela aplicação paralelizada é uma informação chave não apenas para o processo de paralelização em si, mas para a escolha dos componentes e plataformas a serem utilizados, assim como a sua integração. A seguir apresentamos alguns requisitos típicos, mas a lista não é exaustiva, devendo ser revisitada e estendida diante do contexto da aplicação, da sua paralelização e do seu uso. São eles: escalabilidade, armazenamento, latência e tolerância a falhas.

Escalabilidade é a propriedade de um sistema ou aplicação de aumentar a sua capacidade de processamento à medida que aumenta o volume de dados a serem processados. A informação de escalabilidade importante é a estimativa do volume de dados a ser processado e a expectativa de eficiência computacional esperada ao processá-los. A eficiência computacional é um aspecto determinante da infra-estrutura necessária para executar a aplicação paralelizada, além de afetar outros requisitos como latência.

Armazenamento se refere à expectativa de volume de dados a ser processado e gerado como resultado do processamento. Os requisitos de armazenamento podem ser divididos entre armazenamento em memória e em disco, ou outro dispositivo de armazenamento perene. Os requisitos de armazenamento também podem ser detalhados ao longo da execução de um algoritmo ou mesmo entre os vários algoritmos usados. Latência se refere aos limites em termos de tempo de execução para a aplicação, ou algoritmos que a compõem. Normalmente derivados do cenário de aplicação.

A tolerância a falhas especifica tanto as garantias a serem providas pelo algoritmo em relação a dados e resultados que sejam garantidamente preservados, assim como quanto da plataforma seja afetada sem que haja prejuízo em termos de processamento, armazenamento e comunicação.

Paralelizações existentes: Uma última informação relevante para a descrição da aplicação é a identificação e breve descrição das paralelizações existentes, com ênfase nos algoritmos, nas oportunidades de paralelização exploradas, cenários de aplicação e plataformas utilizadas. Neste caso, a intuição é que vários desses resultados possam ser reutilizados ou estendidos.

Projeto

Durante a fase de projeto é que são identificadas as oportunidades de paralelismo e sobreposição de computação, armazenamento e comunicação a serem exploradas. Identificamos quatro componentes no projeto:

Oportunidades de paralelização: As oportunidades de paralelização são as várias possibilidades de computação concorrente inerentes a cada algoritmo a ser paralelizado. A oportunidade de paralelização deve ser descrita em termos das porções de código a serem executadas em paralelo e os dados que elas acessam. Pode também ser interessante apresentar o grau de concorrência potencial em função do tamanho da entrada ou outro parâmetro de execução.

Padrões de acesso aos dados: Os padrões de acesso aos dados especificam como cada uma das oportunidades de paralelização elencadas acessam as várias estruturas de dados manipuladas em cada algoritmo a ser paralelizado. Esses padrões podem ser definidos em termos de distâncias entre acessos concorrentes e sua regularidade. Por exemplo, se temos um loop embaraçosamente paralelo que inicializa um vetor, o padrão de acesso ao mesmo apresenta distância 1 entre os acessos. Os padrões de acesso também devem considerar se os dados estão em memória ou em algum dispositivo de armazenamento. Para esse último caso, devemos também indicar quando os dados armazenados serão novamente utilizados e até que ponto a possibilidade de realizar operações assíncronas e sobrepostas com outras é interessante.

Padrões de comunicação: Os padrões de comunicação materializam os fluxos de dados entre unidades de processamento, novamente considerando cada uma das oportunidades de paralelização elencadas. Dada uma configuração de processos e a distribuição da computação entre eles, queremos determinar se há alguma regularidade nas origens e destinos de dados trafegados entre processos. Mais ainda, identificamos o quanto é possível antecipar o envio dos dados no contexto da oportunidade de paralelização, de forma a explorar as possibilidades de sobreposição entre computação e comunicação.

Linha do tempo integrada: A linha do tempo integrada também é construída por oportunidade de paralelização, identificando, para um conjunto de unidades de processamento, armazenamento e comunicação a sua atuação ao longo da execução. A linha do tempo resultante permite avaliar a aplicação paralelizada de forma integrada, entender compromissos entre as várias oportunidades de paralelização e identificar potenciais fontes de degradação de desempenho.

Desenvolvimento

Durante a etapa de desenvolvimento, as estratégias em cada dimensão são escolhidas e detalhadas. Este detalhamento visa subsidiar a sua implementação eficiente em diferentes plataformas tanto em termos de primitivas (ambientes de programação) quanto de eficiência das operações (ferramentas).

Estratégias de paralelização: devem detalhar, para cada oportunidade de paralelização escolhida, os seus detalhes de implementação, o que pode variar considerando se a paralelização é por dados ou tarefas, por exemplo. A implementação também inclui detalhes das operações de armazenamento e comunicação. Em termos de armazenamento, devemos detalhar as estruturas de dados utilizadas e a sua distribuição temporal. Em termos de comunicação, os dados a serem comunicados, quando eles podem e/ou devem ser enviados e recebidos e outros aspectos como roteamento. A partir destas informações, detalhamos as estratégias de armazenamento e comunicação.

Estratégias de armazenamento: definem os requisitos das plataformas e mecanismos a serem utilizadas. No caso de armazenamento em memória volátil, além das estruturas de dados, consideramos estruturas de sincronização, seu escopo e sua natureza. Já para armazenamento em plataformas perenes, os requisitos em termos de armazenamento e principalmente recuperação dos dados armazenados devem ser considerados. Mais ainda, devemos considerar estratégias que utilizem armazenamento como estratégia de compartilhamento de dados.

Estratégias de comunicação: avaliam quais dados devem ser enviados quando. Aspectos como buffering, marshalling, e prefetching devem ser considerados e avaliados para fins de eficiência. A adequação das primitivas de comunicação e a a eficiência das implementações deve também ser considerada. Por exemplo, multicast é frequentemente uma operação de alto custo em várias plataformas.

Em suma, ao fim da etapa de desenvolvimento, temos os requisitos da aplicação paralelizada detalhados nas várias dimensões.

Implementação

A etapa de implementação visa detalhar como a aplicação paralelizada vai funcionar em uma plataforma computacional alvo.

Plataformas e ferramentas: Devem ser indicadas as plataformas e ferramentas a serem utilizadas, assim como justificadas as escolhas em termos dos requisitos elicitados nas etapas anteriores.

Integração de plataformas e ferramentas: Deve ser detalhado como as várias plataformas e ferramentas serão integradas, por exemplo, mapeando a linha do tempo integrada no ambiente de execução e verificando a sua adequação e completude.

Detalhes de implementação: Aqui são indicados outros detalhes de implementação, como características das plataformas computacionais e mesmo mecanismos adicionais que devem ser incorporados para alcançar o modelo de funcionamento desejado.

Avaliação

A fase de avaliação tem por objetivo verificar se as várias premissas se confirmam e se a paralelização atingiu os seus objetivos. Caso não tenha sido o caso, permite identificar as fontes de degradação de desempenho que são o ponto de partida para a reavaliação do processo de paralelização.

Carga de trabalho: O primeiro passo do processo de avaliação é a definição de uma ou mais cargas de trabalho que permitam uma avaliação tão realista quanto possível de quão bem os requisitos da aplicação foram atingidos. A carga de trabalho pode consistir de dados de entrada para aplicação ou um conjunto de tarefas a serem executadas, entre outras possibilidades. A carga de trabalho também define os conjuntos de parâmetros a serem utilizados, assim como a justificativa da pertinência da avaliação do seu impacto.

Avaliação experimental: A avaliação experimental consiste em realizar o plano experimental que permita exercitar as várias dimensões da carga de trabalho. É importante mencionar que a aplicação paralelizada deve ser instrumentada para obter as medidas necessárias para a avaliação.

Análise de resultados: Uma vez que os experimentos tenham sido concluídos, deve-se avaliar o quanto os vários requisitos foram satifeitos e as limitações da paralelização. Uma lista não exaustiva de aspectos a serem avaliados seria: $(i)$ identificação de gargalos, $(ii)$ tendências, $(iii)$ escalabilidade e $(iiii)$ nível de aderência a requisitos.

Análise Crítica: O estágio final da avaliação deve discutir as prioridades em termos das decisões de projeto e implementação a serem reavaliadas e retificadas se for o caso, subsidiando um novo ciclo de desenvolvimento.

Estudos de caso

Durante o segundo semestre de 2012, o material deste wikilivro foi usado como base para a disciplina de Processamento de Dados Massivos do DCC/UFMG. Durante o curso, alunos desenvolveram trabalhos na área com base em alguns problemas sugeridos e também seus interesses pessoais. As seções a seguir detalham a experiência de cada aluno/grupo.