Christopher B. Colohan

Applying Thread Level Speculation to Database Transactions Degree Type: Ph.D. in Computer Science
Advisor(s): Todd Mowry, Anastassia Ailamaki
Graduated: December 2005

Abstract:

Thread-level speculation (TLS) is a promising method of extracting parallelism from both integer and scientific workloads. In this thesis we apply TLS to exploit intra-transaction parallelism in database workloads. Exploiting intra-transaction parallelism without using TLS in existing database systems is difficult, for two reasons: first, significant changes are required to avoid races or conflicts within the DBMS, and second, adding threads to transactions requires a high level of sophistication from transaction programmers. In this thesis we show how dividing a transaction into speculative threads (or epochs) solves both problems - it minimizes the changes required to the DBMS, and the details of parallelization are hidden from the transaction programmer. Our technique requires a limited number of small, localized changes to a subset of the low-level data structures in the DBMS. We also show that previous hardware support for TLS is insufficient for the resulting large speculative threads and the complexity of the dependences between them. In this thesis we extend previous TLS hardware support in three ways to facilitate large speculative threads: (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-thread 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.

Thesis Committee:
Todd C. Mowry (Chair)
Anastassia Ailamaki (Chair)
Seth C. Goldstein
David O’Hallaron
Kunle Olukotun (Stanford University)

Jeannette Wing, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

Keywords:
TLS, Threads, Speculation, Architecture, Database Systems, Transactions, Intra-Transaction Parallelism, Chip Multiprocessors, Cache design