[talks] Q Xi general exam

[Melissa M Lawson]

 Qian Xi will present her research seminar/general exam on Monday May 14 at 10:30AM 
in Room 402.  The members of her committee are JP Singh (advisor), David August, and 
Vivek Pai.  Everyone is invited to attend her talk, and those faculty wishing to remain
for 
the oral exam following are welcome to do so.  Her abstract and reading list follow below.
-----------------------------------------------------------------------------

Abstract:

Writing multi-threaded programs on chip multi-processors is a challenge. Because of the
runtime unpredictability, access to shared data should be arranged carefully to guarantee
correctness and efficiency. Lock-based mechanisms are conventional ways to provide mutual
exclusion, but locks aren't easy to manage and they can cause serious problems such as
deadlock. Maurice Herlihy et al. proposed a lock-free data structure called Transactional
Memory (TM) to eliminate the problems induced by locks. TM systems have received a lot of
interest recently due to advent of  multi-core processors, and due to a widespread belief
that TM  provides a higher-level and less error-prone parallel programming  model than
locks, while still achieving comparable performance.

Most TM implementations have used toy or kernel benchmarks to measure performance, and
almost exclusively small data structures. This benchmarks gave little insight into how
real applications will behave with TM. In this project, we present a CMP benchmark suite
implemented in software TM (STM), containing both kernel and real application level
programs, from scientific computing and multimedia domains.  We aim not only to understand
performance profiles under STM relative to the more conventional threads+locks programming
model, but more importantly, to understand whether STM is a preferable interface for
programming  on CMP. In the current experimental study, we find that STM achieves good
performance, nearly the same as lock-based mechanisms, for small sizes of shared data. On
the other hand, programs with large shared data size incur a loss of performance for
several reasons in STM.  Then, from a programmer's aspect of view, we summarize the
benefits and drawbacks of current STM systems while writing parallel programs.  We also
compare interfaces of different STM implementations and comment on appropriate STM
primitives for parallel programming.

Readling list:

Book:

David E. Culler, Jaswinder Pal Singh, Anoop Gupta. Parallel Computer
Architecture: A Hardware/Software Approach (2nd edition)

Papers:

- Maurice Herlihy, J. Eliot B. Moss. Transactional Memory: 
Architectural Support for Lock-Free Data Structures. Proceedings of the 20th International
Symposium in Computer Architecture, 1993, pp. 289300.

- Nir Shavit, Dan Touitou. Software Transactional Memory. Proceedings of the 14th Annual
ACM Symposium on Principles of Distributed Computing , 1995, pp. 204-213.

- Kunle Olukotun, Basem A. Nayfeh, Lance Hammond, Ken Wilson, and Kunyung Chang. The Case
for a Single-Chip Multiprocessor. ACM SIGOPS Operating Systems Review, 1996, pp. 2-10.

- Austen McDonald et al. Characterization of TCC on Chip-Multiprocessors. Proceedings of
the 14th International Conference on Parallel Architecture and Compilation Techniques,
2005.

- Kevin E. Moore et al. LogTM: Log-based Transactional Memory. 
Proceedings of the 12th Annual International Symposium on High Performance Computer
Architecture, 2006.

- Tim Harris, Simon Marlow, Simon Peyton Jones, Maurice Herlihy. 
Composable Memory Transactions. ACM Conference on Principles and Practice of Parallel
Programming 2005.

- Maurice Herlihy, Victor Luchangco, Mark Moir, William Scherer. 
Software Transactional Memory for Dynamic-Sized Data Structures. 
Proceedings of the 22nd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed
Computing, 2003.

- Austen McDonald et al. Architectural Semantics for Practical Transactional Memory.
Proceedings of the 33rd annual international symposium on Computer Architecture, 2006.