Transaction scheduling for Software Transactional Memory

Abstract

© 2017 IEEE. Over the last two decades, researchers developed many Software Transactional Memories (STMs) with various APIs and semantics. However, reduced performance when exposed to high contention loads is still the major disadvantage of all the STMs. Designing a good transaction scheduling algorithm for a STM is challenging because it has to satisfy the three confronting requirements: (i) speed comparable with the speed of the simple Round Robin algorithm, (ii) good load balancing of processing units, and (iii) low contention among transactions. In this paper we developed the three transaction scheduling algorithms for the Python STM (PSTM), namely: (i) the Round Robin algorithm (RR), (ii) the Execution Time based Load Balancing algorithm (ETLB), and (iii) the Avoid Conflicts algorithm (AC) that uses information about t-variables used by individual transactions. Experimental results presented in this paper show that in the case of low contention and dual-core multicore, the RR's performance is worst, the ETLB's relative speedup over RR is 1.12 on average, and the AC's relative speedup over RR is 1.53 on average - from 1.12 in the worst case and up to 2.03 in the best case. Alternatively, experiments show that in the case of very short conflict-free transactions and in the case of high contention, all the three algorithms have comparable performance.