Melhorando a transição de modo em implementações de memória transacional em fases

Autor: Muñoz Morales, Catalina, 1989
Přispěvatelé: Araújo, Guido Costa Souza de, 1962, Francesquini, Emilio de Camargo, Cavalheiro, Gerson Geraldo Homrich, França, Breno Bernard Nicolau de, Buzato, Luiz Eduardo, Universidade Estadual de Campinas. Instituto de Computação, Programa de Pós-Graduação em Ciência da Computação, UNIVERSIDADE ESTADUAL DE CAMPINAS
Rok vydání: 2022
Předmět:
Zdroj: Biblioteca Digital de Teses e Dissertações da Universidade Estadual de Campinas (UNICAMP)
Universidade Estadual de Campinas (UNICAMP)
instacron:UNICAMP
Popis: Orientador: Guido Costa Souza de Araújo Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Memória transacional (TM) é uma abstração de programação desenvolvida para arquiteturas de memória compartilhada, que permite ao usuário escrever programas paralelos sem ter que se preocupar com acessos simultâneos a objetos compartilhados. Esta abstração de programação é especialmente projetada para programas com acessos irregulares à memória e comportamento data-driven, para os quais o desenvolvimento de implementações paralelas usando mecanismos de controle de concorrencia de bloqueios, como locks, é complicado, tornando-os propensos a erros de lógica como deadlocks ou livelocks. Várias implementações de memória transacional foram desenvolvidas. Essas implementações podem usar hardware disponível em arquiteturas de computadores modernas ou runtimes que fornecem toda a sincronização de concorrencia necessária. As implementações de software e hardware têm uma série de vantagens e desvantagens que as tornam abaixo do óptimo como uma solução única para todos os aplicativos em geral. Phased Transactional Memory (Phased TM), é uma implementação de TM que busca explorar os benefícios das implementações HW e SW executando transações em fases HW/SW (modos), selecionadas de acordo com as características de cada transação. Um problema específico de implementações de TM em fases é o processo de tomada de decisão necessário para decidir (em run time) o modo de execução e o momento adequado para alternar para outro modo. Esta Tese propõe novos mecanismos de tomada de decisão que não só tiram vantagem do HW (ou seja, o fast-path), mas também procuram reduzir o número de transições de modo, evitando assim overheads desnecessários. Para isso, dois mecanismos de transição foram desenvolvidos considerando uma implementação de TM de três modos: Hardware (HW), Software (SW) e modos de Bloqueio Global (GLOCK). A primeira implementação apresentada nesta Tese, Graph-oriented TM (GoTM), foi inspirada no comportamento data-driven e monotonicamente convergente de programas de grafos. GoTM usa uma medição de taxa commit throughput de cada modo de execução (HW ou SW) como a métrica principal, para acelerar aplicativos típicos em análises de grafos em grande escala. O segundo mecanismo, Commit throughput TM (CTM), elabora ainda mais a métrica de commit throughput, para desenvolver uma solução geral que visa evitar os problemas de over-fitting. CTM é baseado em: (a) uma métrica de commit throughput relativa que compara a evolução do desempenho do programa (aumento ou diminuição) em cada modo de execução; e (b) uma simulação de capacidade de cache que estima o requisito de armazenamento especulativo de transações em execução, que é usada para evitar aborts persistentes relacionados à capacidade en HTM. Nossos resultados experimentais, obtidos usando aplicativos para análise de grafos em grande escala e o benchmark STAMP, mostram que o Phased TM é um mecanismo que melhora o desempenho e a escalabilidade de vários aplicativos da vida real, desde que ofereça mecanismos eficientes de transição de modo Abstract: Transactional memory (TM) is a programming abstraction developed for shared memory architectures, which allows the user to write parallel programs without having to worry about concurrent access to shared objects. This programming abstraction is specially designed for programs with irregular memory accesses and data-driven behavior, for which developing parallel implementations using blocking concurrency control mechanisms such as locks is complicated, making them prone to logic errors such as deadlocks or livelocks. Various implementations of transactional memory have been developed. These implementations can use hardware available in modern computer architecture, or software runtimes that provide all the concurrent synchronization needed. Both software and hardware implementations have a series of benefits and drawbacks that make them suboptimal as a single solution for all applications in general. Phased Transactional Memory (Phased TM), is a TM implementation that seeks to exploit the benefits of both HW and SW implementations by executing transactions in HW/SW phases (a.k.a. modes), selected according to the characteristics of each transaction. A particular problem of Phased TM implementations is the decision-making process that is required to decide (at runtime) the execution mode and the proper moment to switch to another mode. This Thesis proposes novel decision-making mechanisms that not only take advantage of the HW (i.e. fast-path mode) but also seek to reduce the number of mode transitions thus avoiding unnecessary overheads. For this, two transitioning mechanisms were developed considering a three-mode Phased TM implementation: Hardware, Software, and Global Lock modes. The first implementation presented in this Thesis, Graph-oriented TM (GoTM) was inspired by the data-driven and monotonically convergent behavior of graph applications. It uses a commit throughput measurement of each execution mode (HW or SW) as the main metric, to accelerate typical applications in large-scale graph analytics. The second mechanism, Commit throughput TM (CTM), elaborates further on the commit throughput metric, to develop a general solution that aims to avoid over-fitting. CTM is based on two new proposed metrics: (a) a relative commit throughput metric that compares the program performance evolution (increase or decrease) at each execution mode; and (b) a (simulated) cache capacity evaluation that estimates the speculative storage requirement of currently executing transactions, which is used to avoid persistent capacity-related aborts. Our experimental results, obtained using applications for large-scale graph analytics and the STAMP benchmark show that Phased TM is a mechanism that improves performance and scalability of various real-life applications, provided it offers efficient mode transitioning mechanisms Doutorado Ciência da Computação Doutora em Ciência da Computação FAPESP 2017/15236-0
Databáze: OpenAIRE