Computer Science Department
School of Computer Science, Carnegie Mellon University


Supporting Large Speculative Threads
for Databases and Beyond

Christopher B. Colohan, Anastassia Ailamaki,
J. Gregory Steffan*, Todd C. Mowry**

July 2005

Keywords: Thread level speculation, TLS, database systems, chip multiprocessors, OLTP, TPC-C, subepochs

Thread level speculation (TLS) has proven to be a promising method of extracting parallelism from both integer and scientific workloads. In this paper we use TLS to exploit intra-transaction parallelism in database workloads, and demonstrate that previous hardware support for TLS is insufficient for the resulting large speculative threads (or epochs) and the complexity of the dependences between them. In this paper we extend previous TLS support in three ways to facilitate large epochs: (i) we propose a method for buffering speculative state in the L2 cache, instead of solely using an extended store buffer, L1 data cache, or specialized table to track speculative changes; (ii) we tolerate cross-epoch data dependences through the use of sub-epochs, significantly reducing the cost of mis-speculation; and (iii) with programmer assistance we escape speculation for database operations which can be performed non-speculatively. With this support we can effectively exploit intra-transaction parallelism in a database and dramatically improve transaction performance: on a simulated 4-processor chip-multiprocessor, we improve the response time by 46 66% for three of the five TPC-C transactions.

63 pages

*Department of Electrical & Computer Engineering, University of Toronto, Ontario, Canada
**School of Computer Science and Intel Research Pittsburgh, Pittsburgh, PA

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by