Obstruction-Free Software Transactional Memory for GPUs

• Tiago Perlin UFPel
• Andre Rauber Du Bois UFPel
• Gerson Cavalheiro UFPel

Resumo

Transactional memory is a concurrency abstraction, where shared memory is accessed through transactions, similar to database transactions, that guarantee consistency of accessed data. Transactional memory can be implemented in hardware or software and has been explored in different architectures, e.g., CPUS, Distributed Systems, and GPUs. Software Transactional Memory, including the ones designed for GPUs, is usually implemented using blocking algorithms. At some point, either at the first encounter or at commit time, the transactional system has to lock the memory areas to be written by a transaction. After all locks are acquired, the transaction validates its reads, copies its modifications into to memory and then commits by realizing the locks. Many variations of this scheme have been proposed in the literature, including in the context of GPUs. Before transactional memory was implemented using locks, non-blocking, including obstruction-free algorithms, were proposed. Such algorithms must be implemented in languages that support garbage-collection as they rely on a structure called locator, that must be used to acquire ownership of a memory area. As these locators can be created at any time, and might be present in the read set of different transactions, such algorithms rely on a garbage-collector to safely recycle those structures. This paper presents AccelerateSTM, an obstruction-free Transactional Memory implemented for GPUs. The system relies on a garbage-collector that is only activated when at least one of the threads of a warp is in need of more memory. Hence, garbage-collection is activated per warp, and the threads of that warp individually clean their own memory. Experiments comparing AccelerateSTM with 3 other STMs for GPU using 2 benchmarks available in the literature for comparing STM systems demonstrate that AccelerateSTM is faster than other systems in many cases, and in others it presents performance that is compatible with other STM systems for GPU.

Palavras-chave: Context, Concurrent computing, Databases, Instruction sets, High performance computing, Software algorithms, Graphics processing units, Software, Hardware, Recycling, Transactional Memory, GPU, Obstruction-Free