Repositório Colecção:https://hdl.handle.net/1822/213112024-03-28T11:32:47Z2024-03-28T11:32:47ZDynamic end-to-end reliable causal delivery middleware for geo-replicated servicesYounes, Georgeshttps://hdl.handle.net/1822/861862023-08-30T14:32:13Z2023-08-30T14:32:13ZTítulo: Dynamic end-to-end reliable causal delivery middleware for geo-replicated services
Autor: Younes, Georges
Resumo: O crescimento da dependência de serviços baseados na Internet, durante as últimas duas décadas,
causou um aumento na adoção de sistemas geo-replicados. O desenho deste sistemas é enquadrado à
luz do teorema CAP. Neste contexto os modelos de coerência relaxada – Eventual Consistency – permitem
reduzir o tempo de resposta para com os utilizadores finais e, assim, aumentar a disponibilidade dos
sistemas e obter interações mais rápidas. O advento de novas técnicas de convergência como Conflictfree
Replicated Data Types, amplamente adotados na indústria de geo-replicação como seja no Facebook,
PayPal, Microsoft, SoundCloud, entre outros, permitiu também um maior enquadramento formal destas
técnicas. Em particular, o modelo de coerência causal, provou ser o modelo mais forte para sistemas
sempre disponíveis. Assim torna-se relevante revisitar as técnicas de comunicação causal em grupo,
e associado middleware de transmissão, pois sendo que muitos destes sistemas foram originalmente
construídas à perto de três décadas, precisam de ser adequados ao contexto actual de utilização. Esta
tese principia pela análise de novas abstrações para a garantia de propriedades end-to-end no registo e
entrega causal. Prossegue com a observação de anomalias e ineficiências resultantes de implementações
multi-threaded de entrega causal, e com a identificação de uma primeira abordagem para garantir
causalidade entres os dois extremos do sistema. Após a identificação de problemas na escalabilidade nas
implementações que se baseiam em vectores versão ou relógios lógicos, é proposta uma nova solução
baseada na manipulação de grafos de dependências e numa eficiente manutenção e simplificação dos
mesmos, recorrendo à observação de propriedades de estabilidade. É também proposta uma nova API
aos utilizadores do middleware de comunicação. A avaliação das soluções propostas foi feita com base
num sistema programado em Erlang e foi feita a sua avaliação de desempenho e aplicação a quatro casos
de estudo.; The reliance on Internet-based services during the past two decades caused a leap in geo-replicated
systems, as a means to target clients across the globe, in the light of the CAP theorem. Therefore,
relaxed consistency models got a lot of attention to reduce the response time to end users, and thus
boost the availability of the systems at the cost of delayed – Eventual Consistency–. Together with the
advent of new convergence techniques like Conflict-free Replicated Data Types—widely adopted in the georeplication
industry like Facebook, PayPal, Microsoft, SoundCloud, etc., this lead to the reliance on more
useful tradeoff consistency models like the causal consistency model, proven to be strongest model for
available systems. Intuitively, this suggested another visit to revise the causality techniques, broadcast
middleware, and abstractions, originally built three decades earlier for a different set of digital services,
i.e., applications, capabilities, and usage. The research in this thesis analyzes the end to end workflow of
causality-based services, leading to the identification of new problems and shortcoming in state of the art
causality techniques and abstractions, and proposing novel corresponding ones. First, this work discovers
that, given that many applications are today multi-threaded, handling causality while overlooking this fact
will lead into semantic pitfalls in some classes of applications. A corresponding technique is proposed
in this thesis to apply end-to-end time-stamping at the application level instead of the causal middleware.
Second, this thesis points out a scalability problem in state of the art causal broadcast middlewares
that rely on vector clocks for timestamping. This thesis proposes the first graph-based abstraction for
timestamping which is proven to be one order of magnitude more scalable and efficient than its state of
the art counterpart. Third, this work identifies existing redundancy in the time-stamping methods used
in both causal middleware and application logic, and thus proposes a slightly modified, but effective, API
that reduces the bandwidth metadata overhead by half. The API includes the notion of causal stability
that makes garbage collection fast and easy. Fourth, this thesis introduces the first technique for dynamic
causality middleware, crucial in elastic services, leading to guaranteed causal delivery under dynamic
membership. These contributions are then implemented in a comprehensive well-engineered codebase
in Erlang. To demonstrate its usefulness and feasibility, this work has been applied to four practical
use-cases and projects during the course of this thesis.
Descrição: Programa de doutoramento em Informática
<b>Tipo</b>: doctoralThesis2023-08-30T14:32:13ZUser-level software-defined storage data planesMacedo, Ricardo Gonçalveshttps://hdl.handle.net/1822/821352023-02-20T11:19:57Z2023-01-24T10:59:20ZTítulo: User-level software-defined storage data planes
Autor: Macedo, Ricardo Gonçalves
Resumo: Os sistemas centrados em dados como bases de dados, sistemas de armazenamento chave-valor, e motores de aprendizagem automática, são hoje componentes fundamentais para as infraestruturas de computação modernas. De forma a atingir bom desempenho, estes sistemas implementam várias otimizações de armazenamento, como escalonamento de E/S, diferenciação, e caching. Esta disserta-ção argumenta que estas otimizações têm vindo a ser implementadas de forma subótima. Em primeiro lugar, as otimizações estão fortemente acopladas à implementação do sistema, e requerem um conhe-cimento extenso do mesmo por parte de quem as implementa, bem como mudanças significativas no seu código, dificultando a sua manutenção e portabilidade. Em segundo lugar, estas otimizações são maioritariamente implementadas de forma isolada e com visibilidade parcial da infraestrutura, levando-as a competir por recursos de E/S partilhados, a contenção no sistema, e variabilidade no desempenho. Esta dissertação resolve estes desafios redefinindo a forma como as otimizações de E/S são imple-mentadas. Em especifico, as otimizações devem (1) ser desacopladas do sistema; (2) tomar decisões coordenadas sobre os recursos de E/S de forma a garantir controlo holistico; e (3) serem programáveis e adaptáveis de acordo com os requisitos do sistema. Para atingir estes objetivos, defendemos que o paradigma de Armazenamento Definido por Software (ADS) fornece um desenho adequado, embora in-completo, para implementar estas otimizações. Assim, começamos por sistematizar o trabalho em ADS, identificando os princípios de desenho comuns entre sistemas, discutimos as caracteristicas que impulsi-onaram a aplicabilidade de cada solução, e identificamos as causas que impossibilitam a solução destes desafios por parte dos sistemas atuais. Como contribuição principal, introduzimos o sistema PAIO, um novo plano de dados de ADS que permite construir optimizações de E/S portáveis e genéricas no espaço do utilizador. Por fim, demonstramos o desempenho e a eficácia de otimizações implementadas com o PAIO construindo três planos de dados: o primeiro garante controlo da latência nos percentis altos em sistemas de armazenamento chave-valor, o segundo gere a largura de banda de aplicações num ambiente de armazenamento partilhado, e o terceiro garante controlo na qualidade de serviço das operações de metadados num sistema de ficheiros paralelo. Com estas contribuições, mostramos que é possível cons-truir otimizações de E/S desacopladas do sistema, que atuam com visibilidade global, e que garantem resultados equiparáveis ou melhores que otimizações implementadas de forma tradicional.; Data-centric systems such as databases, key-value stores (KVS), and machine learning engines have become an integral part of modern I/O infrastructures. Good performance for these systems often requires implementing multiple storage optimizations such as I/O scheduling, differentiation, and caching. This dissertation argues that such optimizations are implemented in a sub-optimal manner. First, optimizations are tightly coupled to the system implementation, and require a deep understanding of the system's internal operation model and profound code refactoring, limiting their maintainability and portability across other systems that would equally benefit from them. Second, optimizations are often implemented in isolation and with partial visibility of the infrastructure, competing for shared I/O resources, and generating I/O contention and performance variation. This dissertation addresses these challenges by redefining how I/O optimizations are implemented. Specifically, optimizations should (1) be decoupled from the targeted system; (2) perform coordinated decisions over I/O resources to ensure holistic control; and (3) be programmable and adaptable to the requirements of the targeted system. We advocate that the Software-Defined Storage (SDS) paradigm provides a compelling but incomplete design for implementing such optimizations. As such, we start by surveying and systematizing the current body of work on SDS, identifying common design features shared between existing systems, discussing the characteristics that have driven the design and applicability of each solution under a given storage scenario, and uncovering why existing systems do not successfully address these challenges. Then, as our main contribution, we introduce PAIO, a new SDS data plane framework that enables building user-level, portable, and generally applicable storage optimizations. Fi-nally, we demonstrate the performance and effectiveness of complex I/O optimizations implemented with PAIO by building three data plane stages. Namely, the first stage ensures tail latency control in Log-Structured Merge tree KVSs, the second achieves per-application bandwidth control in shared storage settings, and the third ensures QoS control of metadata operations in parallel file systems. With these contributions, this dissertation demonstrates that it is possible to build complex I/O optimizations that are decoupled from the targeted system and actuate with global infrastructure visibility, while achieving similar or better results than traditionally implemented ones.
Descrição: Programa doutoral em Informática das Universidades do Minho, Aveiro e Porto
<b>Tipo</b>: doctoralThesis2023-01-24T10:59:20ZWeighted computations: semantics and program logicsGomes, Leandro Rafael Moreirahttps://hdl.handle.net/1822/779082022-05-25T13:00:09Z2022-05-25T13:00:09ZTítulo: Weighted computations: semantics and program logics
Autor: Gomes, Leandro Rafael Moreira
Resumo: Esta tese debruça-se sobre computações pesadas ou, por outras palavras, programas e asserções sobre
estes cuja execução ou avaliação tem alguma forma de peso associado. Por peso queremos dizer um
valor que pode representar, por exemplo, uma incerteza na execução, ou uma quantidade de recursos
consumidos, como energia ou tempo. Exemplos de sistemas que contêm alguma componente com pesos
variam desde comunicações entre dispositivos, processos biológicos em rede, sistemas de apoio à decisão
clínica ou controlo de robots, estando cada vez mais presentes no nosso quotidiano. Neste sentido, devido
à alta complexidade subjacente à introdução destes parâmetros, exige-se que a engenharia de software
recorra a metodologias de desenvolvimento rigorosas para garantir a alta fiabilidade de cada produto de
software. E se é verdade que o desenvolvimento, análise e verificação destes sistemas são cada vez mais
assentes nessa mesma abordagem formal, as práticas correntes de programação não são ainda capazes
de oferecer uma estrutura que seja, ao mesmo tempo, genérica o suficiente por forma a capturar estes
paradigmas e capaz de satisfazer os requisitos específicos para cada domínio de aplicação.
Nós queremos atacar este desafio através da apresentação de uma metodologia de desenvolvimento
sistemático de semânticas e lógicas para raciocinar sobre duas classes distintas de programas. Na
primeira classe, a que nós chamamos de computação de fluxo único, cada execução é uma única transição
com um peso associado. Na segunda classe, a que nós chamamos computação de fluxo múltiplo, cada
execução pode assumir múltiplos caminhos em simultâneo, cada um com um peso possivelmente distinto.
Nesta tese definimos, para cada classe de computação, uma semântica, e provamos que esta forma uma
álgebra apropriada para raciocinar sobre programas dessa classe. Para esse fim, definimos operadores
que interpretam as construções básicas de uma linguagem de programação imperativa: composição
sequencial, condicionais e iteração. A partir daqui construímos uma lógica, incluindo o respetivo sistema
axiomático, que permite verificar propriedades sobre estes programas.
Uma das virtudes desta metodologia é a sua parametricidade, que é dada por uma estrutura matemática
genérica que oferece tanto um modelo de computação para representar programas como um espaço de
verdade para avaliar asserções sobre eles.
Para a classe de computações de fluxo único, definimos também uma noção de bisimilaridade nos
modelos dos lógicas geradas, provando-se invariância modal para essas lógicas.; This thesis deals with weighted computations or, more precisely, programs and assertions about them
whose execution or evaluation has some form of weight associated. By weight we mean a value which
may represent, for example, an uncertainty in the execution, or a quantity of resources consumed, such as
energy or time. Examples of systems containing some component with weights range from device-to-device
communications, network biological processes, clinical decision support systems or robot control, being
these growingly present in our everyday life. In this sense, due to the complexity underlying the introduction
of these parameters, software engineering is forced to call upon rigorous development methodologies
which provides a high assurance of each software product. And if it is true that the development, analysis
and verification of these systems are increasingly laid on this exactly approach, the current programming
practices are not capable to offer a framework which is, at the same time, generic enough to capture such
paradigms, and able to satisfy the specific requirements for each application domain.
We intend to address this challenge by presenting a methodology for the systematic development of
semantics and logics to reason about two distinct classes of programs. In the first class, that we call
single-flow computation, each execution is a single transition with an associated weight. In the second
class, that we call multi-flow computation, each execution may assume multiple simultaneous execution
paths, each one of them with a, possible distinct, weight. In this thesis we define, for each class of
computation, a semantics, and we prove that it forms a suitable algebra to reason about programs of
that class. For that end, we define operators which interpret the basic constructions of an imperative
programming language: sequential composition, conditionals and iteration. From here we construct a
logic, including the respective axiomatic system, allowing to verify properties over those programs.
One of the merits of this methodology is its parametricity, which is given by a generic mathematical structure
offering both a computational model to represent programs and a truth space to evaluate assertions
over them.
For single-flow computations, we define as well a notion of bisimilarity on the models of the generated
logics, and prove the modal invariance property for those logics.
Descrição: Doctoral programme in Computer Science
<b>Tipo</b>: doctoralThesis2022-05-25T13:00:09ZSupporting software developers in making energy saving decisionsCouto, Marco Rafael Linhareshttps://hdl.handle.net/1822/770702022-04-20T11:34:29Z2022-04-20T11:34:29ZTítulo: Supporting software developers in making energy saving decisions
Autor: Couto, Marco Rafael Linhares
Resumo: In the last decade, energy consumption analysis and improvement in software has been
establishing as a new key concern for developers. Nevertheless, as recent studies demonstrate,
developers are still struggling to understand how to analyze and improve the energy efficiency of
their code. Aware of this, the research community has been continuously working on providing
new tools, techniques, and findings that developers can rely on.
With this thesis, our main target is to further extend the knowledge and mechanisms available
for developers to statically reason about the energy efficiency of their code. Our contributions can
be grouped in two topics: energy behavior prediction and energy-aware software evolution.
To tackle energy prediction, we developed a new approach which combines static program
analysis/verification with energy models, with the goal of providing accurate energy estimations
for worst-case execution scenarios, which we called Worst-Case Energy Consumption (WCEC)
prediction. We used SPLs as a case study, implementing the technique in a prototype tool and
evaluating it’s accuracy by performing an experiment using existing SPLs.
The energy-aware evolution topic was addressed in two ways. First, we studied the energy
impact of replacing energy-greedy coding patterns with less greedy alternatives. We did so by
performing a large-scale study, using hundreds of Android applications and testing them in several
different scenarios. This allowed us to find statistical evidence of what patterns provide the most
significant savings when replaced, and how replacing multiple patterns can affect such savings.
Finally, building on the previous study, we developed a new concept, called Energy Debt,
which goal is to help developers assess the impact of addressing (or retaining) energy-greedy
patterns in their code, in the short and in the long term, by considering a software’s different
releases. This concept is extensible to any target system and language, and we performed an
initial experiment using an Android application to properly explain it and motivate it.
We strongly believe that this thesis, in addition to addressing the existing lack of energy related
knowledge and tools, also provides novel and promising techniques and findings, which we hope
can be used by other researchers in the area to continue exploring these subjects.; Na última década, a análise e melhoria do consumo energético em software tem-se estabelecido
como uma nova preocupação chave para os desenvolvedores. Porém, como estudos recentes demonstram,
os desenvolvedores ainda mostram dificuldades em entender como analisar e melhorar a eficiência
energética do seu código. Cientes deste desafio, a comunidade académica tem continuamente trabalhado
para providenciar novas ferramentas, técnicas, e resultados em que se possa confiar.
Com esta tese, o foco principal é estender ainda mais o conhecimento e mecanismos disponíveis para
os desenvolvedores poderem raciocinar de forma estática sobre a eficiência energética do seu código. As
nossas contribuições podem ser agrupadas em dois tópicos: previsão do comportamento energético e
evolução orientada à redução de energia.
Para abordar a previsão de energia, desenvolvemos uma nova abordagem que combina análise estática
de programas e modelos de consumo energético, com o objetivo de providenciar estimativas precisas
de consumos em cenários de pior caso de execução, ao qual chamamos de Previsão de Consumo Energético
no Pior Caso. Usamos SPLs como caso de estudo, e implementamos esta técnica num protótipo
e avaliamos a sua precisão através de um estudo usando SPLs já existentes.
O tópico de evolução orientada à redução energética foi abordado de duas formas. Primeiro, foi estudado
o impacto inerente à substituição de padrões de código, conhecidos por serem energeticamente
ineficientes, por alternativas mais viáveis. Isso foi feito através de de um estudo em larga escala, usando
centenas de aplicações Android e testando-as em diferentes cenários. Isto permitiu encontrar evidência
estatística de quais os padrões que, quando substituídos, produzem maiores ganhos, mas também
perceber como múltiplas substituições afetam esses ganhos.
Por fim, e sustentando-nos no estudo anterior, desenvolvemos um novo conceito, chamado Débito
Energético, cujo objetivo é ajudar os desenvolvedores a avaliar o impacto de substituir (ou manter) no
seu código padrões reconhecidamente ineficientes do ponto de vista energético, quer a curto quer a
médio/longo prazo, através da análise combinada das diferentes versões de um software. Este conceito
é genérico e extensível para qualquer sistema ou linguagem, e para o explicar e motivar adequadamente
efetuamos um estudo inicial usando uma aplicação Android.
É nossa convicção de que esta tese, além de endereçar a questão relativa à falta de conhecimento
e de ferramentas relacionados com análise de energia, também fornece novas e promissoras técnicas e
descobertas, das quais esperamos que possam ser usados por outros investigadores nesta área.
Descrição: Programa de Doutoramento em Informática (MAP-i) das Universidades do Minho, de Aveiro e do Porto
<b>Tipo</b>: doctoralThesis2022-04-20T11:34:29ZLocality optimisation techniques for platformsSilva, Rui António Sabino Castiçohttps://hdl.handle.net/1822/767852022-04-05T14:02:18Z2022-04-05T14:02:17ZTítulo: Locality optimisation techniques for platforms
Autor: Silva, Rui António Sabino Castiço
Resumo: Aplicações científicas simulam o mundo real através de modelos matemáticos. As simulações destes
modelos necessitam de grande poder computacional, existente nas arquiteturas atuais. Contudo, para
aceder a esse poder computacional, o programador necessita de desenvolver a aplicação de acordo com
a plataforma de execução, o que introduz complexidade no desenvolvimento da aplicação. Nas abordagens
tradicionais estas adaptações/otimizações estão misturadas no código do domínio originando dois
problemas: primeiro, o código fica dependente da plataforma, sendo que a execução numa plataforma
distinta obriga a uma reescrita do código; segundo, o código relativo à otimização mistura-se com o código
do domínio, dificultando a perceção do mesmo.
As linguagens orientadas ao objeto são reconhecidas por explicitar os conceitos do domínio no código.
Porém, a sua utilização introduz tipicamente uma elevada sobrecarga na execução da aplicação limitando
a sua utilização em aplicações cientificas. Isso explica o motivo pelo qual o Java, uma das linguagens
orientadas ao objeto mais utilizadas, não é usada neste tipo de aplicações. Java utiliza a compilação
dinâmica para remover as sobrecargas das linguagens orientadas ao objeto, quando os conceitos mais
avançados não são utilizados (exemplo polimorfismo), como é, frequente, no caso das aplicações científicas.
A abordagem apresentada nesta tese permite adiar a implementação das otimizações para fases posteriores
do desenvolvimento, escondendo o mapeamento de dados. Por outro lado, permite especificar
nas fases finais do desenvolvimento várias optimisações: o processamento em subdomínios, empacotamento
de dados e ordenação dos dados em memória. Por fim, permite a execução paralela ocultando
detalhes de implementação. Para isso separa o desenvolvimento em duas fases distintas: escrita do
código de domínio e fase de otimização. A fase de otimização é adiada para fase final do desenvolvimento,
o que permite uma fácil adaptação à plataforma de execução.
A abordagem permite aplicar estas otimizações através de dois mecanismos: primeiro, alteração
do mapeamento das coleções; e segundo, decomposição do problema em subproblemas. Ambas as
otimizações são introduzidas no programa pelo programador de uma forma simples (pequeno custo de
desenvolvimento) mantendo os conceitos de domínio. Primeiro, a alteração do layout baseia-se no conceito
de procurador, cria um objeto temporário o que permite ao utilizador usar vários mapeamentos com
a mesma API. Em segundo lugar, o mecanismo de decomposição de domínio suporta outras otimizações
comuns: processamento de dados em blocos, empacotamento, execução paralela e dados privados aos
fios de execução. O mecanismo é implementado por anotações de código, evitando alterações mais
invasivas. A abordagem foi avaliada com um conjunto de casos de estudo: soma de um vector, daxpy, JECoLi,
simulação de dinâmica molecular e multiplicação de matrizes. Este conjunto permitiu validar a abordagem
em diferentes casos e a sobrecarga introduzida na execução. A adaptação do código de domínio para
suportar a abordagem foi mais simples do que alterar o mapeamento de dados no código de domínio.
Em todos os casos, a abordagem obteve uma performance similar às abordagens tradicionais. No caso
do MD, exemplo que suporta mais otimizações, o uso da abordagem proporcionou um ganho de 50X no
tempo de execução. Os outros casos de estudos obtiveram ganhos entre 20x e 40x. A JECoLi teve um
ganho mais baixo (1,6x), já que neste caso apenas foi possível aplicar a otimização do mapeamento dos
dados. Esses ganhos mostram a viabilidade da abordagem que permitiu obter códigos eficientes.; Scientific applications simulate the real world through mathematical models. The simulation of these
models requires all the computational power available in current architectures. However, to take advantage
of this computational power, the simulation code must be optimised, bringing it closer to the execution
platform. This adaptation introduces a lot of complexity in application development. Traditionally the
code is written according to the platform on which it will be executed. This approach has two problems:
first, the code is dependent on the execution platform, and changing the execution platform requires code
rewriting; second, the optimisation code is mixed with the domain code, making it difficult to understand.
The Object-Oriented Paradigm (OOP) is known for bringing the code closer to the domain. However, its
use typically introduces an overhead, preventing its use in scientific applications. This explains why Java,
one of the most widely used OOP languages is not commonly used to develop scientific applications. On
the other hand, modern OOP languages that rely on dynamic compilation (e.g., Java) can remove many
overheads typical of OOP, when more advanced features are not used (e.g. polymorphism), which is the
case of many scientific applications.
This dissertation introduces an approach that allows developers to perform optimisation in the final
development step. The approach enables multiple data layouts and allows the selection of the best layout
according to the execution platform. On the other hand, the approach supports tiling, packing and sorting
optimisations. Additionally, the approach supports parallel execution, hiding the implementation details
related to optimisation. The approach separates the development of the domain code from its optimisation.
The optimisation step is delayed until the final development step, which allows an easy adaptation to the
execution platform.
The supported optimisations rely on two mechanisms: first, changing the data collection layout and
second, decomposing the problem into subproblems. Both optimisations are introduced in the program by
the developer in a simple way (low development cost) and maintaining the domain concepts in the code.
First, for hiding the data layout, the approach is based on the proxy pattern, creating a temporary object that
accesses the data using the same API. Second, the domain decomposition mechanism enables several
common optimisations: processing data in tiles, packing, parallel execution and thread private data. The
technique was implemented by code annotations avoiding more invasive code changes.
The approach was evaluated with a set of case studies: Sum, daxpy, JECoLi, MD and Matrix multiplication.
This set allowed to verify the approach effectiveness in different cases and its execution overhead.
The adaptation of the domain code to support the approach was simpler than transforming the layout in
the domain code. In all cases, the approach obtained a performance similar to traditional approaches. In the MD case, the example that supports more optimisations, the use of the approach provided a gain
of 50x in execution time. Other cases studies provided gains from 20x to 40x. The JECoLi case has
the lowest gain (1.6x) since the gain was only due to layout change. These gains show the feasibility of
the approach that delivered efficient optimised codes, adding low additional cost when compared with
traditional approaches.
Descrição: Tese de doutoramento em Informática
<b>Tipo</b>: doctoralThesis2022-04-05T14:02:17Z