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.