Software Transactional Memory provides programmers with promising high flexibility and potential scalability compared to the lock-based mechanisms for designing concurrent programs. Unfortunately, the contention among transactions is a critical problem that could harm scalability. It is caused by multiple transactions concurrently attempting to modify the same memory address. Only one transaction could be successfully committed, causing dispensable waste. When the number of participant threads increases, the contention worsens.
Although different approaches have been developed for addressing contention, such as contention managers and schedulers, most of them only alleviate it, namely, constraining the concurrency degree for reducing abort ratio, failing to unleash the full power of a multi-core system. Therefore, we present Romeo as a dynamic task scheduling framework for software transnational memory that (1) provides a novel programming model to unroll the conventional loop iteration into tasks for not only improving schedulability but removing the redundant transaction usage, and (2) implementing Ant Colony Optimization (ACO) algorithm to schedule transactional tasks by predicting the probability of conflicts with history data. Our experimental evaluation demonstrates that Romeo can significantly produce up to 4.15x speedup and reduce the 13.7% abort ratio on high-contention applications while maintaining less than 11.9% overhead on low-contention applications compared to the state-of-the-art.
I am a PhD candidate in the Graduate Institute of Electrical Engineering of National Taiwan University now. My research area is task parallelism, synchronization optimization, and system software design. The open-source community helps me a lot on my studies, so I want to do my best to help others in return.