Abortos Falsos em Sistemas de Memória Transacional em Software
Abstract: Transactional memory (TM) continues to be the most promising approach replacing locks in concurrent programming, but TM systems based on software (STM) still lack the desired performance when compared to fine-grained lock implementations. It is known that the critical operation in TM systems is to ensure the atomicity and isolation of concurrently executing threads. This task is known as the read/write-set validation. In attempt to make this process as fast as possible, STM systems usually use ownership tables to perform conflict detection, but this approach generates false positive occurrences, which result in false aborts. This paper shows the real impact of false aborts and how its relevance increases along with the number of concurrent threads, showing it is an essential factor for TM systems. We propose two different techniques to avoid false aborts, consequently improving the TM performance. The first is a collision list attached to the existing hash table. The second is a novel and efficient technique to detect conflicts between transactions. This technique makes use of SSE technology to detect conflicts and replaces the commonly used hash table. Due to its memory mapping scheme, the technique avoids false positive occurrences. With fast collision detection, free of false conflicts, we achieved significant performance improvements in some STAMP benchmark programs. The speedup obtained was up to 1.63x. We also show that speedups become higher when the number of parallel threads increases. Finally, based on the results obtained, we characterize which programs are most benefited by the two techniques.
Resumo: Memória transacional (MT) continua a ser a abordagem mais promissora para substituir locks em programação concorrente, mas sistemas de MT em software (MTS) ainda não possuem desempenho satisfatório quando comparados a implementações utilizando \textit{locks} bem refinados. Sabe-se que a operação crítica em sistemas de MT é garantir a atomicidade e o isolamento das \textit{threads} que estejam executando concorrentemente. Essa tarefa é conhecida como a validação dos conjuntos de leitura/escrita. Na tentativa de realizar esse processo o mais rápido possível, sistemas de MTS costumam utilizar uma tabela de posse para realizar a detecção de conflitos, mas essa abordagem gera ocorrência de falsos positivos, os quais resultam em abortos falsos. Este trabalho mostra o verdadeiro impacto dos abortos falsos e como sua relevância aumenta à medida que o número de \textit{threads} concorrentes também aumenta, mostrando que este fator é essencial para sistemas de MTS. Nós propomos duas diferentes técnicas para evitar abortos falsos e conseqüentemente melhorar o desempenho de MTS. A primeira é uma lista de colisão anexada à já existente tabela \textit{hash}. A segunda è uma técnica completamente nova e eficiente para detectar conflitos entre transações. Esta nova técnica faz uso de tecnologia SSE para detectar conflitos [...]
2009