Modelagem de desempenho de sistemas com paralelismo pipeline

AUTOR(ES)
FONTE

IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia

DATA DE PUBLICAÇÃO

29/07/2011

RESUMO

Em uma era onde o paralelismo é imperativo (commodity clusters, multi-processadores, múltiplos núcleos, GPGPU) o entendimento do consumo de recursos (CPU, disco, etc.) de uma aplicação paralela, em diferentes circunstâncias, é chave para tomar decisões em planejamento de capacidade e gerenciamento de carga de trabalho, tais como: (1) quantas e quais tipos de máquinas são necessárias, em um cluster de um data center, para atender os limites de tempos de resposta e throughput contratados no acordo de nível serviço (Service Level Agreement - SLA)? Como ajustar os parâmetros para tirar melhor proveito dos recursos e aumentar o desempenho e a escalabilidade do sistema. No entanto, técnicas de modelagem de desempenho tradicionais, como a Análise do Valor Médio (Mean Value Analysis - MVA) não podem ser aplicadas diretamente em cargas de trabalho que possuam relações de precedência, como as sincronizações entre tarefas produtoras e consumidoras em jobs que posuam paralelismo pipeline. Soluções exatas, utilizando cadeias de Markov para representar os possíveis estados do sistema foram propostas, mas não são escaláveis pois o espaço de estados cresce exponencialmente com o aumento do número de tarefas. A metodologia utilizada é baseada em uma solução aproximada, mas eficiente, proposta em um trabalho anterior, o qual chamamos de modelo referência. Esta solução utiliza um modelo hierárquico, onde o nível mais alto (software) é representado por um grafo de precedência e o nível mais baixo (hardware) por um modelo de rede de filas fechado. O grafo de precedência captura os atrasos de sincronização e a sobreposição média do tempo de execução de tarefas de um mesmo job (intra-job) e de tarefas de jobs diferentes (inter-job), enquanto que o modelo de rede de filas captura a contenção média nos recursos. O modelo de rede de filas é resolvido através da técnica Analise do Valor Médio aproximado (approximate Mean Value Analysis - aMVA). Para introduzir o efeito das regras de precedências no algoritmo aMVA, o tamanho médio das filas, que usualmente só captura a contenção dos recursos, foram inflacinados por fatores de sobreposição, estimados pelo grafo de precedência. O modelo referência permite diversos tipos de relações de precedências, entretanto nenhum de seus operadores capturam as sincronizações de um pipeline, não sendo portanto aplicável diretamente à cargas de trabalho que possuam paralelismo pipeline. A nossa principal contribuição consiste em mostrar como construir o grafo de precedência, utilizando os operadores primitivos proposto no modelo referência, para capturar as sincronizações inerentes do paralelismo pipeline. Esta metodologia foi aplicada em dois estudos de casos: (1) consultas simples de Business Intelligence (BI), que contém um pipeline na troca de mensagens entre seus operadores; e (2) jobs do Hadoop Online Prototype (HOP), uma extensão do Hadoop (arcabouço de computação paralela inspirado no modelo de programação MapReduce) que provê um paralelismo pipeline entre as tarefas map e reduce. Os principais resultados encontrados foram: (1) obtivemos uma boa aproximação na validação do modelo de consulta de BI, obtendo um erro relativo máximo de 11,5% para o tempo de resposta do job (na literatura, o máxima aceito para tempo de resposta é 30%) em relação a um simulador da rede de filas e a um emulador do sistema, para seis cenários diferentes; (2) observamos que o paralelismo pipeline teve um ganho maior (no tempo de resposta do job) com carga leve, ou seja, antes do sistema saturar. Após a saturacao o tempo de resposta do job é dominado pelos o atrasos de filas e, um aumento no paralelismo pipeline, ao invés de aumentar o speedup, gera mais contenção; (3) verificamos que as previsões de desempenho do modelo analítico para os jobs HOP teve boa acurácia para vários cenários, entretanto alguns cenários foram muito super-estimados, o que nos levou a avaliar estes cenários, através de simulações, buscando identificar se havia alguma característica do sistema que não foi capturada, ou que não estava sendo bem modelada. Desenv olvemos simuladores específicos para avaliar algumas premissas do modelo e identificamos que a principal fonte de erro foi devido a uma premissa do modelo referência que assume que a média do tempo de resposta das tarefas são exponencialmente distribuídas. Fizemos uma avaliação das limitações do modelo devido às implicações desta premissa e introduzimos um novo operador primitivo usado na construção da árvore, que utiliza o método fork/join, proposto anteriormente, para estimar os fatores de sobreposição. A acurácia do modelo utilizando o método fork/join melhorou, ficando o erro relativo máximo do tempo de resposta do job abaixo de 15%.

ASSUNTO(S)

computação teses. análise de desempenho teses.

ACESSO AO ARTIGO

Documentos Relacionados