Estimating parallelism of transactional memory programs

Abstract

Transactional Memory (TM), a promising concurrency control mechanism that enables easier and more productive parallel/distributed programming, become a standard part of the latest multicores rolled out by IBM, Intel, AMD, and other IC manufacturers. Many TM aspects have been intensively researched, e.g. semantics of various possible implementations, TM safety and liveness properties, and TM performance. Some researchers suggested some novel measures for the amount of concurrency in TM programs. Alternatively, we in this paper propose an approach to analysis of TM programs by using a well-established methodology, which is based on modeling programs as DAGs, and calculating their work, span, parallelism, and speedup. In the paper we present an approach to application of this methodology in order to calculate the parallelism of a typical TM program for processing a group of transactions on a set of bank accounts. As a result of this approach we established some simple theorems that may be used for analysis of a broader class of TM programs. © 2013 IEEE.