Transactional memory inspired lock-free synchronization for a Crit-bit Tree

Arquiteturas de processamento paralelo têm se apresentado como a principal proposta de atendimento da crescente demanda por poder de processamento. Ao multiplicar o número de unidades de processamento, tais arquiteturas prometem, em teoria, multiplicar a taxa de execução de instruções. Na prática, contudo, este comportamento é difícil de ser alcançado. Múltiplos desafios impedem que desenvolvedores consigam extrair o máximo potencial das arquiteturas paralelas. A fim de auxiliar no melhor aproveitamento deste potencial este trabalho propõe, desenvolve e analisa uma nova estratégia de sincronização elaborada sobre uma estrutura de dados em formato de árvore binária. Tal estratégia permite a execução paralela das operações de inserção, busca e remoção na estrutura. Além disso, a estratégia foi desenvolvida de maneira a apresentar baixa concorrência entre as operações e, consequentemente, alcançar um alto grau de paralelismo. Os testes desenvolvidos sobre a implementação da estrutura apresentam medidas de concorrência, desempenho e escalabilidade. Os dados obtidos permitem avaliar o benefício do uso da estratégia de sincronização proposta em um ambiente multiprocessado.Parallel processing architectures have been shown as the major proposed solution for the increasing demand for processing power. By multiplying the number of processing units such architectures promise, in theory, to multiply the rate of instruction execution. In practice, however, this behavior is not reached easily. Multiple challenges prevent developers from extracting the full potential of parallel architectures. In order to help reaching this potential this paper proposes, develop and analyses a new synchronization strategy developed over a binary tree data structure. This strategy allows parallel insertion, search and removing from the structure. Furthermore, the strategy was developed in a way to avoid concurrency among operations and, consequently, reach a high level of parallelism. The tests executed over the data structure present measures on concurrency, performance and scalability. The data obtained allow us to evaluate the advantage of using the proposed synchronization strategy over a multiprocessed environment