COMP 522 Multi-core Computing Fall 2009 Tentative Paper Schedule

August 25: Introduction

• Software and the Concurrency Revolution, Herb Sutter and James Larus in ACM Queue Special Issue on Multiprocessors, 3(7), September, 2005.

August 27: Simultaneous Multithreading and the Case for Chip Multiprocessing

• Simultaneous multithreading: maximizing on-chip parallelism, Dean Tullsen, Susan Eggers, and Henry Levy, In 25 Years of the International Symposia on Computer Architecture (Selected Papers) (Barcelona, Spain, June 27 - July 02, 1998). G. S. Sohi, Ed. ISCA '98. ACM Press, New York, NY, 533-544. (First published in ISCA '95.) DOI= http://doi.acm.org/10.1145/285930.28601
• The case for a single-chip multiprocessor, Kunle Olukotun, Basem Nayfeh, Lance Hammond, Ken Wilson, and Kunyung Chang, In Proceedings of the Seventh international Conference on Architectural Support For Programming Languages and Operating Systems (Cambridge, Massachusetts, United States, October 01 - 04, 1996). ASPLOS-VII. ACM Press, New York, NY, 2-11. DOI=http://doi.acm.org/10.1145/237090.237140
• A single-chip multiprocessor, Lance Hammond, Basem Nayfeh, Kunle Olukotun. Computer 30(9):79-85, September 1997. DOI=http://dx.doi.org/10.1109/2.612253

September 1: Fine-grain Multithreading: Sun Niagara and Eldorado

• Niagara: A 32-Way Multithreaded SPARC Processor, Poonacha Kongetira, Kathirgamar Aingaran, and Kunle Olukotun, IEEE Micro, pp. 21-29, March-April 2005.
• Niagara2: A Highly Threaded Server-on-a-Chip. Robert Golla. Sun Microsystems Slides, Oct. 10, 2006.
• ELDORADO. John Feo, David Harper, Simon Kahan, Petr Konecny. Proceedings of the 2nd Conference on Computing Frontiers (Ischia, Italy, May 04 - 06, 2005). CF '05. ACM, New York, NY, 28-34.
• Evaluating the Potential of Multithreaded Platforms for Irregular Scientific Computations, Jarek Nieplocha, Andrés Márquez, John Feo, Daniel Chavarría-Miranda, George Chin, Chad Scherrer, Nathaniel Beagley. Proceedings of the 4th Intl. Conference on Computing Frontiers, Ischia, Italy, 2007, pages 47 - 58.

September 3: Tiled Manycore Processors

• Integration Challenges and Tradeoffs for Tera-scale Architectures. Mani Azimi,Naveen Cherukuri, D. N. Jayasimha, Akhilesh Kumar, Partha Kundu, Seungjoon Park, Ioannis Schoinas, Aniruddha S. Vaidya. Intel Technology Journal, August 2007. ftp://download.intel.com/technology/itj/2007/v11i3/1-integration/vol11-i3-art01.pdf
• An 80-Tile 1.28TFLOPS Network-on-Chip in 65 nm CMOS. In Proceedings of ISSCC 2007 (IEEE International Solid-State Circuits Conference), Feb. 12, 2007.
• Achieving Predictable Performance Through Better Memory Controller Placement in Many-Core CMPs. Dennis Abts, Natalie Enright Jerger, John Kim, Dan Gibson, Mikko Lipasti In Proceedings of the 36th Annual International Symposium on Computer Architecture. June 2009.

September 8: Shared Cache

• Victim Replication: Maximizing Capacity while Hiding Wire Delay in Tiled Chip Multiprocessors, M. Zhang and K. Asanovic. In Proceedings 32nd International Symposium on Computer Architecture, Madison, WI, June 2005.
• Cooperative Caching for Chip Multiprocessors, J. Chang and G. S. Sohi. In Proceedings of the 33rd International Symposium on Computer Architecture, Boston, MA, June 2006.

September 10: From Multicore to Multisocket - Kamal Sharma

• Piranha: A Scalable Architecture Based on Single-Chip Multiprocessing, L. A. Barroso, K. Gharachorloo, R. McNamara, A. Nowatzyk, S. Qadeer, B. Sano, S. Smith, R. Stets, and B. Verghese in Proceedings of the International Symposium on Computer Architecture (ISCA), pp. 282-293, June 2000.
• A First Look at the Intel QuickPath Interconnect, Robert A. Maddox, Gurbir Singh and Robert J. Safranek. In Weaving High Performance Multiprocessor Fabric: Architectural Insights to the Intel QuickPath Interconnect, Intel Press, 2009.
• The AMD Opteron Northbridge Architecture. P. Conway and B. Hughes. IEEE Micro 27, 2 (Mar. 2007), 10-21. DOI=http://dx.doi.org/10.1109/MM.2007.43

September 15: Cilk and Cilk++ - Sagnak Tasirlar

• The Implementation of the Cilk-5 Multithreaded Language by Matteo Frigo, Charles E. Leiserson, and Keith H. Randall. 1998 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), Montreal, Canada, June 1998.
• Reducers and other Cilk++ hyperobjects. M. Frigo, P. Halpern, C.E. Leiserson, and S. Lewin-Berlin. Proceedings of the Twenty-First Annual Symposium on Parallelism in Algorithms and Architectures (Calgary, AB, Canada, August 11 - 13, 2009). SPAA '09. ACM, New York, NY, 79-90.

September 17: NESL

• Programming parallel algorithms, G. E. Blelloch, in Commun. ACM 39, 3 (Mar. 1996), 85-97.

September 22: Intel's Thread Building Blocks - Sagnak Tasirlar

• The Foundations for Scalable Multi-core Software in Intel Threading Building Blocks, Alexey Kukanov, Michael J. Voss. Intel Technology Journal, Volume 11, Issue 4, 2007.

September 24: Ct - Dragos Sbirlea

• Ct: A Flexible Parallel Programming Model for Tera-scale Architectures, Anwar Ghuloum, Eric Sprangle, Jesse Fang, Gansha Wu, and Xin Zhou. Intel White Paper, 2008.
• Future-Proof Data Parallel Algorithms and Software on Intel® Multi-Core Architecture, Anwar Ghuloum et al. Intel Technology Journal, Volume 11, Issue 4, 2007.

September 29 : Shared Memory Consistency Models - Arnold Schwaighofer

• Shared Memory Consistency Models: A Tutorial, Sarita V. Adve. Kourosh Gharachorloo. Technical Report 95-7, Digital Western Research Laboratory, Palo Alto, CA.

October 1: Java Memory Model - Sanjay Chatterjee

• The Java Memory Model, J. Manson, W. Pugh, and S. V. Adve, in Proceedings of the Symposium on Principles of Programming Languages (PoPL), January 2005.

October 8-9: C++ Concurrency Memory Model - Arnold Schwaighofer

• Foundations of the C++ concurrency memory model, H. Boehm, and S. V. Adve, in Proceedings of the 2008 ACM SIGPLAN Conference on Programming Language Design and Implementation (Tucson, AZ, USA, June 07 - 13, 2008). PLDI '08. ACM, New York, NY, 68-78. DOI= http://doi.acm.org/10.1145/1375581.1375591

October 16: Implementing Nested Data Parallelism - Kamal Sharma

• Implementation of a Portable Nested Data-Parallel Language. Guy E. Blelloch, Siddhartha Chatterjee, Jonathan C. Hardwick, Jay Sipelstein, and Marco Zagha. Technical Report CMU-CS-93-112, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA. 1993. (An earlier version of this paper appeared in "Proceedings of the 4th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming", San Diego, May 1993.)

October 20: Data Race Detection: Locksets and Happens-before

Eraser: A Dynamic Data Race Detector for Multithreaded Programs. Savage, S., Burrows, M., Nelson, G., Sobalvarro, P., and Anderson, T. 1997. ACM Trans. Comput. Syst. 15, 4 (Nov. 1997), 391-411. DOI= http://doi.acm.org/10.1145/265924.265927
• On-the-fly maintenance of series-parallel relationships in fork-join multithreaded programs, M. A. Bender, J. T. Fineman, S. Gilbert, and C. E. Leiserson, in Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures (Barcelona, Spain, June 27 - 30, 2004). SPAA '04. ACM, New York, NY, 133-144.

October 22: Data Race Detection: Integrated Approaches

• Detecting data races in Cilk programs that use locks, G. Cheng, M. Feng, C.E. Leiserson, K. Randall, and A.F. Stark, in Proceedings of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures (Puerto Vallarta, Mexico, June 28 - July 02, 1998). SPAA '98. ACM, New York, NY, 298-309. DOI=
• SigRace: Signature-Based Data Race Detection. Abdullah Muzahid, Dario Suárez, Shanxiang Qi, Josep Torrellas. The 36th International Symposium on Computer Architecture June 20-24, 2009, Austin, Texas, USA

October 27: Scheduling - Dragos Sbirlea

• Thread scheduling for multiprogrammed multiprocessors, Nimar S. Arora and Robert D. Blumofe and C. Greg Plaxton, in Proceedings of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures (Puerto Vallarta, Mexico, June 28 - July 02, 1998). SPAA '98. ACM Press, New York, NY, 119-129.
• Process Scheduling Challenges in the Era of Multi-core Processors, Suresh Siddha Venkatesh Pallipadi Asit Mallick. Intel Technology Journal, Volume 11, Issue 4, 2007.

October 29 : Scheduling and Shared Cache - Alina Simion

• Provably efficient scheduling for languages with fine-grained parallelism. Blelloch, G. E., Gibbons, P. B., and Matias, Y. 1995. In Proceedings of the Seventh Annual ACM Symposium on Parallel Algorithms and Architectures (Santa Barbara, California, United States, June 24 - 26, 1995). SPAA '95. ACM Press, New York, NY, 1-12.
• Effectively sharing a cache among threads, Guy E. Blelloch and Phillip B. Gibbons, in Proceedings of the 16th Annual ACM Symposium on Parallelism in Algorithms and Architectures (Barcelona, Spain, June 27 - 30, 2004). SPAA '04. ACM Press, New York, NY, 235-244.

November 3: Wait-free Synchronization - John Mellor-Crummey

• Wait-free synchronization, Maurice Herlihy, ACM Trans. Program. Lang. Syst. 13, 1 (Jan. 1991), 124-149.

November 5: Synchronization Primitives: Locks and Barriers - Thomas Barr

• Algorithms for scalable synchronization on shared-memory multiprocessors, John Mellor-Crummey and Michael L. Scott, ACM Trans. Comput. Syst. 9, 1 (Feb. 1991), 21-65.

November 10: Transactional Memory Overview - Sanjay Chatterjee

• Transactional memory, J. Larus, J. and C. Kozyrakis, Communications of the ACM 51, 7 (Jul. 2008), 80-88.

November 12: Software Transactional Memory

• Software transactional memory for dynamic-sized data structures, Maurice Herlihy, Victor Luchangco, Mark Moir, and William N. Scherer, III, In Proceedings of the Twenty-Second Annual Symposium on Principles of Distributed Computing (Boston, Massachusetts, July 13 - 16, 2003). PODC '03. ACM Press, New York, NY, 92-101.
• Understanding Tradeoffs in Software Transactional Memory, Dice, D. and Shavit, N. 2007. In Proceedings of the international Symposium on Code Generation and Optimization (March 11 - 14, 2007). Code Generation and Optimization. IEEE Computer Society, Washington, DC, 21-33.

November 17: Practical Non-blocking Concurrent Objects

• Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. Maged M. Michael and Michael L. Scott. In Proceedings of the 15th ACM Symposium on Principles of Distributed Computing (PODC), May 1996.
• Nonblocking Concurrent Objects with Condition Synchronization, William N. Scherer III and Michael L. Scott, in Proceedings of the 18th International Symposium on Distributed Computing, Amsterdam, The Netherlands, Oct, 2004.

November 24: Hardware Support for Transactional Memory - Thomas Barr

• Transactional Memory: Architectural Support for Lock-free Data Structures, Maurice Herlihy and J. Eliot B. Moss in Proceedings of the 20th Annual International Symposium on Computer Architecture, San Diego, California, 1993, ACM Press, New York, NY, USA, 289-300. ISCA most influential paper award, 2008.
• Nonblocking transactions without indirection using alert-on-update, Michael Spear, Arrvindh Shriraman, Luke Dalessandro, Sandhya Dwarkadas, and Michael . In Proceedings of the Nineteenth Annual ACM Symposium on Parallel Algorithms and Architectures (San Diego, California, USA, June 09 - 11, 2007). SPAA '07. ACM Press, New York, NY, 210-220.

December 1: Performance Analysis of Multithreaded Programs - Alina Simion

• Effective performance measurement and analysis of multithreaded applications. Tallent, N. R. and Mellor-Crummey, J. M. Proceedings of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (Raleigh, NC, USA, February 14 - 18, 2009). PPoPP '09. ACM, New York, NY, 229-240. DOI= http://doi.acm.org/10.1145/1504176.1504210
• Analyzing Lock Contention in Multithreaded Applications Nathan R. Tallent John M. Mellor-Crummey. Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, January 2010. To appear.

December 3: Wrap up - John Mellor-Crummey

Other Possible Papers

• OpenCL 1.0 Specification, Khronos OpenCL Working Group, Editor: Aaftab Munshi, May 16, 2009.
• MUVI: Automatically Inferring Multi-Variable Access Correlations and Detecting Related Semantic and Concurrency Bugs. Shan Lu, Soyeon Park, Chongfeng Hu, Xiao Ma, Weihang Jiang, Zhenmin Li, Raluca A. Popa, Yuanyuan Zhou. The 21st ACM Symposium on Operating Systems Principles, October 2007.
• AVIO: Detecting Atomicity Violations via Access-Interleaving Invariants. Shan Lu, Joseph Tucek, Feng Qin, and Yuanyuan Zhou. 12th International Conference on Architectural Support for Programming Languages and Operating Systems, October 2006.