Self-adaptive abstractions for efficient high-level parallel computing in multi-cores

Abstract

Atualmente, uma parte significativa dos sistemas computacionais e aplicações do mundo real demandam paralelismo para acelerar suas execuções. Embora a programação paralela estruturada e de alto nível tenha como objetivo facilitar a exploração do paralelismo, ainda há questões a serem abordadas para melhorar as abstrações existentes na programação paralela, onde os desenvolvedores de aplicações usualmente precisam definir configurações de paralelismo não intuitivas ou complexas. Nesse contexto, a autoadaptação é uma alternativa potencial para fornecer um nível mais alto de abstrações autonômicas e capacidade de resposta em tempo de execução em aplicações paralelas. No entanto, um problema recorrente é que a autoadaptação ainda é limitada em termos de flexibilidade, eficiência e abstrações. Por exemplo, faltam mecanismos para aplicar ações de adaptação e estratégias eficientes de decisão sobre quais configurações devem ser aplicadas em tempo de execução. Este trabalho é focado em abstrações alcançáveis com autoadaptação gerenciando de forma transparente as execuções enquanto os programas paralelos estão sendo executados. Os principais objetivos são: aumentar o espaço de adaptação para ser mais representativo para aplicações e tornar a autoadaptação mais eficiente com metodologias de avaliação abrangentes, que podem fornecer casos de uso que demonstrem os verdadeiros potenciais da autoadaptação.Portanto, esta tese de doutorado traz as seguintes contribuições científicas: I) Uma revisão sistemática da literatura fornecendo uma taxonomia do estado da arte. II) Um framework conceitual para apoiar a concepção e abstração do processo de tomada de decisão dentro de soluções autoadaptativas, o que é utilizado nas contribuições técnicas para ajudar a tornar as soluções mais modulares e potencialmente generalizáveis. III) Mecanismos e estratégias para réplicas autoadaptáveis em aplicações com estágios paralelos simples e múltiplos, suportando múltiplos requisitos não-funcionais. IV) Mecanismo, estratégia e otimizações para autoadaptação dos Padrões Paralelos/topologias de grafos de aplicações. Aplicamos as soluções propostas ao contexto de aplicações de processamento de streams, um paradigma representativo presente em várias aplicações do mundo real que computam dados em tempo real (por exemplo, feeds de vídeo, imagem e análise de dados). Uma parte das soluções propostas é avaliada com a SPar e outra parte com o framework de programação FastFlow. Os resultados demonstram que a autoadaptação pode fornecer abstrações de paralelismo eficientes e responsividade autonômica em tempo de execução e alcançando um desempenho competitivo em comparação com as melhores execuções estáticas. Além disso, quando apropriado, a solução proposta é comparada com soluções relacionadas, demonstrando que as estratégias de decisão propostas neste trabalho são altamente otimizadas e alcançam ganhos significativos de desempenho e eficiência.

Nowadays, a significant part of computing systems and real-world applications demand parallelism to accelerate their executions. Although high-level and structured parallel programming aims to facilitate parallelism exploitation, there are still issues to be addressed to improve existing parallel programming abstractions. Usually, application developers still have to set non-intuitive or complex parallelism configurations. In this context, self-adaptation is a potential alternative to provide a higher-level of autonomic abstractions and runtime responsiveness in parallel executions. However, a recurrent problem is that self-adaptation is still limited in terms of flexibility, efficiency, and abstractions. For instance, there is a lack of mechanisms to apply adaptation actions and efficient decisionmaking strategies to decide which configurations to be enforced at run-time. In this work, we are interested in abstractions achievable with self-adaptation transparently managing the executions while the parallel programs are running (at run-time). Our main goals are to increase the adaptation space to be more representative of real-world applications and make self-adaptation more efficient with comprehensive evaluation methodologies, which can provide use-cases demonstrating the true potentials of self-adaptation.Therefore, this doctoral dissertation provides the following scientific contributions: I) An Systematic Literature Review (SLR) providing a taxonomy of the state-of-the-art. II) A conceptual framework to support designing and abstracting the decision-making process within selfadaptive solutions, such a conceptual framework is then employed in the technical contributions to assist in making the solutions more modular and potentially generalizable. III) Mechanisms and strategies for self-adaptive replicas in applications with single and multiple parallel stages, supporting multiple customizable non-functional requirements. IV) Mechanism, strategy, and optimizations for self-adaptation of Parallel Patterns/applications’ graphs topologies. We apply the proposed solutions to the context of stream processing applications, a representative paradigm present in several real-world applications that compute data flowing in the form of streams (e.g., video feeds, image, and data analytics). A part of the proposed solutions is evaluated with SPar and another part with the FastFlow programming framework. The results demonstrate that self-adaptation can provide efficient parallelism abstractions and autonomous responsiveness at run-time, yet achieve a competitive performance w.r.t. the best static executions. Moreover, when appropriate, we compare state-of-the-art solutions and demonstrate that our highly optimizeddecision-making strategies achieve significant performance and efficiency gains.