Optimistic intra-transaction parallelism on chip multiprocessors

ABSTRACT

With the advent of chip multiprocessors, exploiting intra-transaction parallelism is an attractive way of improving transaction performance. However, exploiting intra-transaction parallelism 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 paper we show how dividing a transaction into speculative threads 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. Through this method of parallelizing transactions we can dramatically improve performance: on a simulated 4-processor chip-multiprocessor, we improve the response time by 36-74% for three of the five TPC-C transactions.

References

1. C. B. Colohan, A. Ailamaki, J. G. Steffan, and T. C. Mowry. Extending Thread Level Speculation Hardware Support to Large Epochs: Databases and Beyond. Technical Report CMU-CS-05-109, School of Computer Science, Carnegie Mellon University, March 2005.
2. IBM Corporation. IBM DB2 Universal Database Administration Guide: Performance. IBM Corporation, 2004.
3. E. D. Berger and K. S. McKinley and R. D. Blumofe and P. R. Wilson. Hoard: A Scalable Memory Allocator for Multithreaded Applications. In Proceedings of the 9th ASPLOS, 2000.
4. H. Garcia-Molina and K. Salem. Sagas. In Proceedings of the 1987 ACM SIGMOD international conference on Management of data, pages 249--259. ACM Press, 1987.
5. S. Gopal, T. Vijaykumar, J. Smith, and G. Sohi. Speculative Versioning Cache. In Proceedings of the 4th HPCA, February 1998.
6. J. Gray. The Benchmark Handbook for Transaction Processing Systems, Morgan-Kaufmann Publishers, Inc., 1993.
7. L. Hammond, B. Hubbert, M. Siu, M. Prabhu, M. Chen, and K. Olukotun. The Stanford Hydra CMP. IEEE Micro Magazine. March-April 2000.
8. M. Herlihy and J. Moss. Transactional memory: Architectural support for lock-free data structures. In Proceedings of the 20th ISCA, 1993.
9. H. Kaufmann and H. J. Schek. Extending tp-monitors for intra-transaction parallelism. In Proceedings of the 4th PDIS, 1996.
10. H. T. Kung and J. T. Robinson. On optimistic methods for concurrency control. ACM TODS, pages 213--226, June 1981.
11. J. H. Miller and H. Lau. Microsoft SQL Server 2000 Resource Kit, chapter RDBMS Performance Tuning Guide for Data Warehousing, pages 575--653. Microsoft Press, 2001.
12. C. Mohan, D. Haderle, B. Lindsay, H. Pirahesh, and P. Schwarz. ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging. ACM TODS, March 1992.
13. Michael Olson, Keith Bostic, and Margo Seltzer. Berkeley db. In Proceedings of the Summer Usenix Technical Conference, June 1999.
14. M. K. Prabhu and K. Olukotun. Using thread-level speculation to simplify manual parallelization. In The ACM SIGPLAN 2003 Symposium on Principles & Practice of Parallel Programming, June 2003.
15. M. Rys, M. C. Norrie, and H. J. Schek. Intra-transaction parallelism in the mapping of an object model to a relational multi-processor system. In Proceedings of the 22nd VLDB, 1996.
16. D. Shasha, F. Llirbat, E. Simon, and P. Valduriez. Transaction chopping: Algorithms and performance studies. ACM TODS, 20(3):325--363, 1995.
17. A. Silberschatz, P. B. Galvin, and G. Gagne. Operating System Concepts. John Wiley & Sons, Inc., 2002.
18. J. G. Steffan, C. B. Colohan, A. Zhai, and T. C. Mowry. A Scalable Approach to Thread-Level Speculation. In Proceedings of the 27th ISCA, June 2000.
19. M. Tremblay. MAJC: Microprocessor Architecture for Java Computing. HotChips '99, August 1999.
20. K. Yeager. The MIPS R10000 superscalar micro-processor. IEEE Micro, April 1996.
21. C. Zuzarte. Personal communication, 2005.

Index Terms

• Computing methodologies

  • Modeling and simulation

    • Simulation evaluation

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Information systems

  • Data management systems

    • Database management system engines

      • Database transaction processing

      • Parallel and distributed DBMSs

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Process management

          • Multiprocessing / multiprogramming / multitasking

    • Software system structures

      • Software architectures

        • Simulator / interpreter