(short notice - scheduling conflict, exam will be today) Prakash Prabhu will present his research seminar/general exam **today, Monday May 11** at 1PM in Room 402. The members of his committee are: David August, advisor, David Walker, and JP Singh. Everyone is invited to attend his talk and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ----------------------------------------------------- Enabling Implicit Parallel Programming on Multi-Core Architectures With the advent of multi-core architectures in mainstream computing, the importance of thread-level parallelism in delivering application performance has become critical. Existing thread-centric programming paradigms like pthreads and OpenMP are explicit. Today, programmers explicitly specify parallelization techniques and manage access to data using locking constructs. Such explicitly written parallel programs, plagued by race conditions, deadlocks, and performance problems, are difficult to write, debug, and maintain. Even worse, they are also fragile and intimately tied to assumptions about the underlying parallel architecture. In contrast, automatic thread extraction is a promising alternative that does not suffer from these problems, but whose benefits are yet to be realized on real hardware for large programs. Recently, Bridges et al., proposed two extensions to a sequential programming language, showing substantial amounts of thread-level parallelism can be automatically extracted from sequential codes, while relying on state-of-the-art profiling and speculation techniques. These extensions are not explicitly parallel and change program semantics. Since these extensions may change a program's output, they cannot be automatically inferred. Following on the lines of Bridges et al., this work proposes a generalized set of implicitly parallel programming extensions to the C language, which enables a programmer to write correct code and reason sequentially. At the same time, it considerably enhances a compiler's ability to extract thread-level parallelism. This talk explains the semantics of these extensions and demonstrates their use in manual parallelization of several benchmark programs. [Text Books] [1] Modern Compiler Implementation in ML, by A. W. Appel, Cambridge University Press, 1998 [2] Compilers: Principles, Techniques, and Tools (2nd Edition) by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman, Addison Wesley, 2006. [Papers] [3] M. J. Bridges, N. Vachharajani, Y. Zhang, T. Jablin, and D. I. August. Revisiting the sequential programming model for multi-core. In Proceedings of the 40th Annual ACM/IEEE International Symposium on Microarchitecture (MICRO), December 2007. [4] Neil Vachharajani, Ram Rangan, Easwaran Raman, Matthew J. Bridges, Guilherme Ottoni and David I. August. Speculative Decoupled Software Pipelining. In Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques (PACT), September 2007 [5] Christoph von Praun, Luis Ceze, Calin Caşcaval. Implicit parallelism with ordered transactions. In Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming (PPoPP), 2007 [6] Wen-mei Hwu et al., Implicitly Parallel Programming Models for Thousand-Core Microprocessors, In Proceedings of the 44th Design Automation Conference (DAC), 2007 [7] Robert Bocchino, Vikram Adve, Sarita Adve and Marc Snir. Parallel Programming Must Be Deterministic By Default. First USENIX Workshop on Hot Topics in Parallelism (HotPar), March 2009. [8] Monica S. Lam and Martin C. Rinard. Coarse-grain parallel programming in Jade. In Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming (PPoPP), pages: 94-105, 1991. [9] Eduard Ayguad´e et al., The Design of OpenMP Tasks, IEEE Transactions on Parallel and Distributed Systems (TPDS), March 2009 [10] David J. Pearce, Paul H.J. Kelly and Chris Hankin. Efficient field-sensitive pointer analysis of C. ACM Transactions on Programming Languages and Systems (TOPLAS), 2007 [11] R. Ghiya, L. J. Hendren and Y. Zhu. Detecting Parallelism in C Programs with Recursive Data Structures, Proceedings of the 7th International Conference on Compiler Construction (CC), page 159-173, 1998. [12] Chris Lattner, Andrew Lenharth, Vikram Adve. Making context-sensitive points-to analysis with heap cloning practical for the real world. In the Proceedings of the 2007 Programming Languages Design and Implementation conference, 2007. [13] Justiani and Laurie J. Hendren. Supporting Array Dependence Testing for an Optimizing/Parallelizing C Compiler. In the Proceedings of the 5th International Conference on Compiler Construction (CC), pages 309-323, 1994. [14] A. Tineo, F. Corbera, A. Navarro, R. Asenjo, and E.L. Zapata. A Novel Approach for Detecting Heap-based Loop-carried Dependences, Proceedings of the International Conference on Parallel Processing(ICPP), 2005