QoS-control of Structured Parallel Computations: A Predictive Control Approach

Autores: G. Mencagli e M. Vanneschi
Publicado em: 2011 IEEE Third International Conference on Cloud Computing Technology and Science (CloudCom)
DOI:10.1109/CloudCom.2011.47

Esse artigo apresenta uma metodologia para modelagem de aplicações paralelas utilizando técnicas control-theoretic. Essa abordagem é oriunda da teoria de controle de sistemas indústriais. O objetivo aqui é permitir a adaptação em tempo de execução de aplicações paralelas. O conceito de adaptive parallel module (ParMod) é definido como uma unidade independente responsável pela execução de uma computação paralela que possui uma estratégia de adaptação definida. O módulo é dividido em duas partes: Operating Part que executa a computação em si; Control Part responsável pela implementação da estratégia de adaptação. Desta forma, a Control Part é responsável por monitorar o progresso da computação na Operating Part. A adaptação a ser realizada pode ser não-funcional, envolvendo alterações no grau de paralelismo, ou funcional, tratando da adaptação do código em ambientes heterogêneos. Em seguida, o artigo apresenta uma modelagem para o comportamento da Operating Part. É utilizado o conceito de estados baseados nos valores de variáveis internas, que são adaptados de acordo com medidas de perturbação no ambiente que resultam em entradas de controle por parte da Control Part. Apesar da modelagem ser generalista, no estudo de caso apresentado os autores escolheram o esqueleto de paralelismo Task-Farm, no qual não há interação entre as tarefas workers. Para modelar esse exemplo, usaram um tratamento estatístico no tempo médio de execução de cada etapa do Task-Farm. Também consideram que a adaptação não poderia considerar o prazo completo da execução. Cada mudança tinha horizonte de apenas alguns passos no futuro. Isso serviu para limitar o custo da adaptação. A execução de simulações em um cluster demonstrou que a solução apresentou resultados próximos ao algoritmo ótimo e superior a heurísticas com estratégia de reação pura. Os autores planejam no futuro expandir o trabalho para controlar grafos de computação com múltiplos módulos paralelos com cada um exibindo uma estratégia de controle própria.

Chunks and Tasks: A programming model for parallelization of dynamic algorithms

Autores: Emanuel H. Rubensson e Elias Rudberg
Publicado em: Parallel Computing Volume 40, Issue 7, July 2014, Pages 328–343
DOI:10.1016/j.parco.2013.09.006

Esse trabalho apresenta um modelo de programação paralelo e distribuído no qual o desenvolvedor só necessita dividir o algoritmos em tarefas e os dados de entrada em chunks, cabendo ao ambiente de execução tratar a distribuição dos mesmos. No início da execução, um programa mestre serial fatia a entrada em chunks, que são objetos somente leitura com identificador único. O usuário também define objetos tarefas, informando qual o tipo de chunk é esperado como entrada e qual vai ser produzido na saída. Um escalonador distribui as tarefas entre os recursos (cores ou máquinas) junto com seus respectivos chunks, que são a partição dos dados na qual a tarefa irá executar. Um tarefa, ao executar, pode produzir um novo chunk ou uma nova tarefa. Seja qual for o objeto gerado, ele é registrado no programa mestre. Esse registro não involve a transferência total do chunk, apenas seus meta-dados. Se a tarefa seguinte for executada no mesmo recurso, o chunk já está no local, não havendo transferência. Caso a tarefa que vai precisar do chunk gerado esteja em outro recurso, a transferência é feita diretamente entre o recurso que executou a tarefa geradora e o recurso que irá executar a tarefa que consome o chunk. A arquitetura define dois serviços em execução em cada worker, o Chunk Service e o Task Service. O primeiro cuida da transferência e registro dos chunks. O segundo cuida da sincronização entre as tarefas. Toda comunicação é feita por MPI. Como os chunks e tarefas podem ser criados e registrados dinamicamente, esse paradigma se encaixa muito bem na implementação de algoritmos paralelos recursivos e hierárquicos. Não há comunicação direta entre as tarefas, mas sim transferências de chunks, que podem exigir comunicação com o processo mestre antes de acontecer. O que é interessante no contexto de nuvens e elasticidade é que como uma tarefa pode gerar uma nova tarefa, dependendo de como foi definida, seria possível criar máquinas virtuais para essas novas tarefas. Haveria o overhead de criação, mas no lugar de criar uma por tarefa, poderia ser utilizado um pool de VMs para lidar com novas tarefas. Esse pool cresceria ou diminuiria observado a utilização das máquinas atuais. A limitação é que aplicações fortemente acopladas, de granularidade fina, talvez não se encaixem no modelo. Enfim, parece um misto de Bag-Of-Tasks e Map-Reduce, mas com a possibilidade de comunicação (com overhead) entre as tarefas pela transferência de chunks, caso seja necessário.

A Framework for Elastic Execution of Existing MPI Programs

Autores: A. Raveendran, T. Bicer e G. Agrawal
Publicado em: 2011 IEEE International Symposium on Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW)
DOI:10.1109/IPDPS.2011.240

Esta proposta analisa as aplicações MPI como uma sequência de iterações. A cada número X de iterações, é avaliado o tempo médio de execução de uma iteração. Caso esse valor esteja acima do desejado pelo usuário, os processos são terminados, os valores das variáveis (estado da computação) são salvos em arquivos e a computação é reiniciada com um número maior de processos (VMs). O mesmo ocorre se o tempo de execução médio de uma iteração esteja muito abaixo do desejado pelo usuário, só que neste caso a computação é reiniciada com menos processos (VMs) para poupar custos. Uma possível contribuição seria imaginar “esqueletos” de estruturas de dados que facilitassem a consolidação e distribuição dos dados entre as adaptações.

Visão Geral de um Supercomputador Moderno

Nesta postagem, vou apresentar o que considero a fundamentação teórica básica sobre os supercomputadores modernos utilizados para computação de alto desempenho. Não irei me aprofundar em todos os detalhes, mas é um texto com informações suficientes para quem não é da área e deseja ter uma noção básica do funcionamento dessas máquinas. Ao final do texto, espero que o leitor tenha entendimento da arquitetura do hardware e do ambiente de software fornecido pelo gerenciador de recursos.

As plataformas de computação paralela evoluíram de forma radical no decorrer dos anos. A partir dos supercomputadores vetoriais da década de 1970, passando pelos MPPs (Massive Parallel Processors) (Massive Parallel Processors) na década de 1980 até o Cluster Beowulf nos anos 90, temos nos dias de hoje uma arquitetura híbrida baseada em clusters com nós de processamento com processadores de vários núcleos e aceleradores. Um supercomputador moderno é uma evolução dos primeiros clusters. Em outras palavras, arquiteturas baseadas em clusters são predominantes, mas alguns elementos dos supercomputadores clássicos ainda persistem. Apresentamos aqui as principais características de um supercomputador moderno. Baseamos nossa descrição nos sistemas descritos na lista TOP500 e na máquina instalada no CENAPAD-UFC.

A menor parte de um supercomputador moderno que executa uma imagem do sistema operacional é chamada de nó de processamento. A figura abaixo é uma representação em alto nível da arquitetura interna. Nessa figura, podemos observar dois processadores (CPU0 e CPU1). Essa quantidade de chips pode variar. Cada processador tem acesso ao banco de memória, que apesar de aparecer como duas entidades separadas na imagem, trata-se de um espaço de endereçamento global. Além disso, dentro de cada processador existem vários núcleos (cores) que compartilham memória cache (oculta na ilustração para efeito de simplificação). Os processadores podem se comunicar entre si através de um protocolo proprietário.

Os processadores se comunicam com outros periféricos através de barramentos PCI Express (alto desempenho), PCI apenas ou SATA. No caso dos dois últimos barramentos, a comunicação é feita por intermédio de um chip especializado para controlar E/S (Ponte E/S). A comunicação entre a ponte e as CPUs é feita por acesso direto à memória. Os aceleradores são componentes dedicados capazes de executar certos cálculos com melhor desempenho do que CPUs tradicionais. Existe toda uma área de estudo dedicada a aceleradores, mas não vou me aprofundar aqui. Ao mais interessados, sugiro uma busca por NVIDIA CUDA no Google ;).

Para otimizar a execução de aplicações paralelas que fazem uso de troca de mensagens, a configuração de rede em um cluster para computação de alto desempenho pode apresentar duas redes (interfaces NIC0 e NIC1), com tecnologias diferentes. A rede de gerência utiliza tecnologia ethernet e é usada para login remoto e sistemas de arquivos distribuídos. Ela não tem nenhuma diferença em relação a redes locais tradicionais, exceto que costuma utilizar a última versão do padrão ethernet (atualmente, 100-Gigabit_Ethernet) e utiliza comutadores (switches) de qualidade superior. O padrão ethernet só determina os protocolos de acesso ao enlace. Os outros protocolos necessários para comunicação (IP para rede e TCP/UDP para transporte) são implementados por software no kernel do sistema operacional. A camada de software entre a aplicação e o enlace não é motivo de preocupação para as aplicações tradicionais. Porém, para aplicações de computação de alto desempenho, o software implica uma latência que é prejudicial ao desempenho dessas aplicações. Em busca de diminuir a latência, a rede de computação utiliza protocolos que minimizam a presença de software na pilha, tentando implementar o máximo possível em hardware. Um exemplo é a tecnologia Infiniband, na qual até a camada de transporte a comunicação é tratada diretamente pelo adaptador. Dessa forma, mais do que a largura de banda, a latência é otimizada, requisito crucial para o desempenho de aplicações de computação de alto desempenho. A desvantagem é que o adaptador se torna mais complexo, aumentando o custo de implantação de redes Infiniband

A figura abaixo apresenta a organização de rede do cluster do CENAPAD-UFC. Nesse projeto, os nós de processamentos são construídos em blades, que são agrupados em chassis, gabinetes com comutadores ethernet e infiniband embutidos. Além dos nós que executam a computação em si, temos um nó de gerência que serve como porta de entrada para o cluster. É nesse nó que os usuários realizam login e configuram as submissões para o sistema.

Cada chassi possui comutadores para as duas tecnologias (infiniband e ethernet), mas como um chassi suporta ao máximo 16 blades, mais dois switches infiniband e um switch ethernet são necessários para conectar os chassis e completar os 48 blades do cluster. É possível observar porque o custo da Infiniband é maior. As duas redes são conectadas à um nó de gerência, no qual os jobs dos usuários são submetidos. Importante notar que o sistema de storage é ligado apenas na rede de gerência, na qual é acessado através de sistema de arquivos distribuído. Um nó do cluster possui uma imagem própria do sistema operacional. O sistemas operacionais mais utilizados são aqueles derivados do UNIX. Até o final da década de 1990, era comum que cada fabricante tivesse sua versão própria do UNIX. Com a popularização do Linux, os fabricantes encontraram um sistema UNIX robusto de baixo custo capaz de substituir as soluções proprietárias. O custo de manutenção do Linux é dividido por uma comunidade de vários desenvolvedores autônomos e empresas. Para os fabricantes de supercomputadores, resta desenvolver apenas drivers específicos e otimizações do kernel para sua máquinas. O kernel do Linux por si próprio não é o suficiente para um sistema funcional. Distribuições são coleções de aplicativos que formam um sistema completo para o usuário final. As distribuições Linux para supercomputadores apresentam customizações para executar aplicações de alto desempenho, mas são baseadas em distribuições já existentes no mercado. O Red Hat Enterprise Linux e o SUSE são escolhas populares.

Sistemas gerenciadores de recursos permitem que vários usuários utilizem um supercomputador com menor esforço administrativo e diminuição da ociosidade. Através de um sistema de filas, usuários submetem aplicações como tarefas no nó de gerência. Além de ponto de submissão, o nó de gerência também controla o acesso ao sistema de arquivos distribuído instalado no storage. Na listagem abaixo, temos um exemplo de um arquivo definição de tarefa baseado no SLURM (Simple Linux Utility for Resource Management). Nesse arquivo, o usuário dá um nome a tarefa (CALCULO_PI), define a quantidade de nós processamentos utilizados (4) e quantos processos são criados (48). Neste caso específico, são criados 12 processos em cada nó de processamento. O tempo máximo de execução da tarefa é determinado (1 hora). Por último, uma linha definindo o binário a ser executado é informada (./pi).

#!/bin/bash
#SBATCH -J CALCULO_PI
#SBATCH --partition particao_0 
#SBATCH --nodes 4
#SBATCH --ntasks 48
#SBATCH --time 1:00:00

srun --resv-ports ./pi 

Ao ser submetido no nó de gerência, a tarefa entra numa fila inicial que analisa para qual partição ela está destinada. O conceito de partição corresponde a um subconjunto dos recursos do cluster. Essa divisão auxilia a definir prioridades. Por exemplo, um partição pode ser destinada apenas aos pesquisadores sênior de um instituição, incluindo todos os recursos disponíveis. Uma outra partição menor pode incluir apenas os recursos menos poderosos, destinada aos alunos de graduação. A listagem a seguir apresenta os parâmetros para definição de uma partição chamada partição_0 no SLURM. Observa-se que além que configurar quais usuários têm acesso e quais nós de processamento fazem parte da partição, um limite máximo para o tempo de execução das aplicações é informado.

PartitionName=particao_0 
Nodes=Processamento_[0-3] 
Default=NO 
MaxTime=240:00:00 
AllowGroups=ufc,ufrgs,uespi,utfpr,ufpb,ufsc,ufma,ufpe,ufal 
State=UP 

A próxima figura apresenta um exemplo do sistema de filas em gerenciador de recursos. O usuário submete tarefas para um partição escolhida, de acordo com seus privilégios. O sistema encaminha a tarefa para a fila adequada, na qual aguarda a execução. Uma vez que existem recursos livres, a tarefa é executada. O usuário não precisa monitorar todo o processo. O gerenciador de recursos se responsabiliza por todos os passos entre a submissão e a conclusão da execução.

Apesar de controlar vários blades distintos, o gerenciador de recursos atua dentro de um mesmo domínio administrativo. O cluster é um sistema distribuído controlado. O acesso externo só é permitido ao nó de gerência, sendo que várias restrições de firewall são utilizadas para proteger o supercomputador de acesso indevido. Para permitir a utilização de clusters de instituições diferentes, outras tecnologias de computação distribuída mais amplas são necessárias, fornecendo controle de autorização e autenticação, além de um serviço de transferência de dados de alto desempenho.