Schedule for Witchel's Spring 2007 CS395T: Hardware and Software for Multicore Systems

(Syllabus, Project ideas, Presentations)

Note: Papers are ONLY accessible from domain.

Wk Date Discussion Topic Homework/
Extra Reading
1 1/15 No meeting: Martin Luther King Jr. day 

2 1/22
1) Niagara: A 32-Way Multithreaded SPARC Processor, Poonacha Kongetira, Kathirgamar Aingaran, and Kunle Olukotun IEEE MICRO Magazine, March-April 2005.
2) Software and the concurrency revolution, Herb Sutter and James Larus, ACM Queue, Sept 2005.
3) Transactional memory: architectural support for lock-free data structures, Maurice Herlihy and J. Eliot B. Moss, ISCA 1993.
3 1/29 Overview of multiprocessors, thread-level parallelism, and cache-coherency mechanisms.
1) Read: Sections 6.1 to 6.5 from Hennessy and Patterson, Computer Architecture: A Quantiative Approach, THIRD edition.
Answer: H&P 6.5
List of 5 papers you can present, in perference order due Monday 1/29.  It can include papers not on the schedule. Email list to Witchel.

H&P 6.5
4 2/05 Overview of multiprocessing continued
1) Read: Sections 6.6 to 6.9 (not including 6.9), 6.10, 6.14, 6.15 from Hennessy and Patterson, Third edition.
2) Read: Appendix I from H&P3
Answer: H&P 6.6, I.3
H&P 6.6, I.3
5 2/12 Hardware transactional memory
1) LogTM: Log-based Transactional Memory,
Kevin E. Moore, Jayaram Bobba, Michelle J. Moravan, Mark D. Hill & David A. Wood, HPCA 2006.
2) Supporting nested transactional memory in logTM
Michelle J. Moravan, Jayaram Bobba, Kevin E. Moore, Luke Yen, Mark D. Hill, Ben Liblit, Michael M. Swift, David A. Wood, ASPLOS, 2006

6 2/19 1) Transactional Coherence and Consistency: Simplifying Parallel Hardware and Software
Lance Hammond, Brian D. Carlstrom, Vicky Wong, Michael Chen, Christos Kozyrakis, Kunle Olukotun, IEEE Micro November/December 2004.
2) Tradeoffs in Transactional Memory Virtualizations,
JaeWoong Chung, Chi Cao Minh, Austen McDonald, Chafi Hassan, Brian D Carlstrom, Travis Skare, Christos Kozyrakis and Kunle Olukotun, ASPLOS 2006.
Try not to exceed 1 page, due in class.
1) List and explain two advantages TCC has over LogTM.
2) List and explain two advantages LogTM has over TCC
3) Explain TCC's biggest weakness
4) State and explain two disadvantages of allowing a distinguished transaction to become unabortable.
7 2/26 Software transactional memory
1) Compiler and Runtime Support for Efficient Software Transactional Memory (PLDI '06)
Ali-Reza Adl-Tabatabai, Brian T.Lewis, Vijay Menon, Brian R.Murphy, Bratin Saha, Tatiana Shpeisman
2) Composable memory transactions,
Tim Harris, Simon Marlow, Simon Peyton Jones, and Maurice Herlihy. ACM Conference on Principles and Practice of Parallel Programming 2005 (PPoPP'05).
Two questions, not to exceed 1 page, due in class
1) What are the two primary disadvantages of STM systems relative to HTM systems?

2) Why does an STM system need to validate its read set on commit, while LogTM does not?
Project proposal due (2/26)
4 pages maximum, a crisp description of your project that addresses these issues.
1. What are you trying to show?
2. What will you build to show it?
3. What experiments will you run, and how will they make your point?
8 3/05 1) Read: Forward and chapter 2 from Lenoski and Weber, "Scalable Shared-Memory Multiprocessing"
2) Read: Chapter 6 from Lenoski and Weber, "Scalable Shared-Memory Multiprocessing"
3) Catchup H&P and other topics
4) The Convoy Phenomena
Mike Blasgen, Jim Gray, Mike Mitoma, Tom Price (Operating System Review 1979)
5) Lock convoys and how to recognize them
Sue Loh's blog
6) Extending Hardware Transactional Memory to Support Non-busy Waiting and Non-transactional Actions Craig Zilles, Lee Baugh, (Transact 2006)
Not to exceed 1 page
1. What does it mean for a barrier implementations to reverse sense?  Why is this useful?
2. What is the difference between a transactional pause (a la Zilles) and an open nested transaction?
9 3/12 No meeting: Spring break
10 3/19 1) Efficient Synchronization: Let them eat QOLB,
Alain Kagi, Doug Burger, and James R. Goodman, ISCA 1997.
2) Shared Memory Consistency Models: A Tutorial
Sarita V. Adve, Kourosh Gharachorloo, Computer 1996

11 3/26 1) Wait-free Synchronization
Maurice Herlihy TOPLAS 1991
2) Linearizability: A Correctness Condition for Concurrent Objects,  (Herlihy and Wing TOPLAS 1990)
3) Obstruction-free Synchronization: Double-ended Queues as an Example,M.P. Herlihy, V. Luchangco, and M. Moir ICDCS 2003

12 4/02 1) MapReduce: Simplified Data Processing on Large Clusters (Dean and Ghemawat 2004)
2) Evaluating MapReduce for Multi-core and Multiprocessor Systems, Colby Ranger, Ramanan Raghuraman, Arun Penmetsa, Gary Bradski, Christos Kozyrakis. Proceedings of the 13th Intl. Symposium on High-Performance Computer Architecture (HPCA), Phoenix, AZ, February 2007

13 4/09 Database transactions
Chap 1 (optional) Concurrency Control and Recovery in Database Systems (Bernstein, Hadzilacos & Goodman 1987)
Transaction Processing: Concepts and Techniques (Jim Gray and Andreas Reuter 1993)
1.1 - 1.2.5 (optional)
4.2, 4.6, 4.7, 4.9
7.1-7.6 (not including 7.6, but including table 7.9)

14 4/16 1) MetaTM/TxLinux: Transactional Memory For An Operating System
Hany E. Ramadan, Christopher J. Rossbach, Donald E. Porter, Owen S. Hofmann, Aditya Bhandari, Emmett Witchel,  ISCA 2007
2) The Landscape of Parallel Computing Research, UC Berkeley TR 2006

15 4/23
Project Presentations
16 4/30 Project presentations Project writeup due Friday (5/4)

To top of page

Copyright Notice: These lecture notes, homeworks, and lab assignments are part of a graduate course on multicore systems. You must ask me permission to use these materials.  I do not grant to you the right to publish these materials for profit in any form.
Emmett Witchel, The University of Texas at Austin