CSC 572:
Seminar on Pervasive Parallelism

Technological advances have resulted in increasing levels of on-chip functionality. Multi-core architectures pervade all levels of computing platforms, from smart phones to servers and high-performance computers. Extraction of parallelism from mainstream applications is thus even more imperative than in the past. This seminar will examine new developments in the concurrency space - common (and new) programming platforms (languages and runtimes), scalable architectures that support concurrency, support for heterogeneous computing, energy and power-aware concurrency, and performance in the presence heterogeneity and imperfect reliability. Here is a tentative list of papers I put together. We will expand on and modify this list as the semester progresses.

Class time: Wednesdays, 10-12 a.m.; in case of conflict with ECE seminar etc., alternative time at 4.50 p.m.
Class location: CSB 632.

Instructor:

Sandhya Dwarkadas
e-mail: sandhya at cs
Office: CSB 717, 275-5647
Office hours by appointment, but don't be afraid to drop by. If you want to be sure I'm in my office, use e-mail to contact me.

Prerequisites:

CSC 2/458, CSC 254, and CSC 256, or equivalent, and/or instructor's permission.

Assignments and Grading

The course will examine the latest papers in the chosen topics, and will consist of presentation and discussion of the papers. Grading will be based on class participation, class presentations, paper summaries, and a term project.

Paper Reading List

25th January: Application Trends/Examples, and Composability (Brandon and Sandhya), Slides (applications, TBB, GCD, Lithe)

  • Composing Parallel Software Efficiently with Lithe, Heidi Pan, Benjamin Hindman, and Krste Asanovic, International Conference on Programming Language Design and Implementation (PLDI), 2010.
  • Intel Threading Building Blocks 4.0, Intel September 2011.
  • Apple's Grand Central Dispatch (GCD) Reference, Apple Inc., August 2009.
  • Challenges of Scaling Algebraic Multigrid across Modern Multicore Architectures, A. Baker, T. Gamblin, M. Schulz, and U. Yang, IPDPS, 2011.
  • ``Hierarchical Parallelization of Gene Differential Association Analysis'', M. Needham, R. Hu, S. Dwarkadas, and X. Qiu, BMC Bioinformatics, 12:374, September 2011.

    1st and 8th February: Many-Core Architectures (Raj and Hongzhou)

  • Rigel: An Architecture and Scalable Programming Interface for a 1000-core Accelerator, John H. Kelm, Daniel R. Johnson, Matthew R. Johnson, Neal C. Crago, William Tuohy, Aqeel Mahesri, Steven S. Lumetta, Matthew I. Frank, Sanjay J. Patel, in Proceedings of the International Symposium on Computer Architecture (ISCA), 2009.
  • Cohesion: A Hybrid Memory Model for Accelerators, John H. Kelm, Daniel R. Johnson, William Tuohy, Steven S. Lumetta, Sanjay J. Patel, International Symposium on Computer Architecture (ISCA'10), June 2010.
  • Exploring the Tradeoffs between Programmability and Efficiency in Data-Parallel Accelerators, Yunsup Lee, Rimas Avizienis, Alex Bishara, Richard Xia (University of California, Berkeley), Derek Lockhart, Christopher Batten (Cornell University), Krste Asanovic (University of California, Berkeley), ISCA 2011.

    15th February: Adaptive Threading (Xiaochen)

  • Feedback-driven threading: power-efficient and high-performance execution of multi-threaded workloads on CMPs, M. Aater Suleman, Moinuddin K. Qureshi, and Yale N. Patt, ASPLOS 2008.
  • Thread tailor: dynamically weaving threads together for efficient, adaptive parallel applications, Janghaeng Lee, Haicheng Wu, Madhumitha Ravichandran, and Nathan Clark, ISCA 2010.
  • Thread Reinforcer: Dynamically Determining Number of Threads via OS Level Monitoring, Kishore Kumar Pusukuri, Rajiv Gupta, and Laxmi N. Bhuyan, IISWC 2011.

    22nd February: Operating Systems Support (Kostas and Shantonu)

    (slides)
  • PTask: Operating System Abstractions To Manage GPUs as Compute Devices, Christopher J. Rossbach, Jon Currey, Mark Silberstein, Baishakhi Ray, and Emmett Witchel, SOSP 2011.
  • Pegasus (Coordinated Scheduling in Virtualized Accelerator-based Platforms), Visakha Gupta, Karsten Schwan, Niraj Tolia, Vanish Talwar, and Parthasarathy Ranganathan, Usenix Annual Technical Conference 2011.

    29th February: Pegasus (Shantonu), Scalable OS-based Coherence (Raj)

  • Pegasus (Coordinated Scheduling in Virtualized Accelerator-based Platforms), Visakha Gupta, Karsten Schwan, Niraj Tolia, Vanish Talwar, and Parthasarathy Ranganathan, Usenix Annual Technical Conference 2011. (slides)
  • An OS-based Alternative to Full Hardware Coherence on Tiled CMPs, C. Fensch and M. Cintra, HPCA 2008. (slides)

    6th March: Disciplined Parallelism: Hardware and Software Design (Hongzhou and Li)

  • DeNovo: Rethinking the Memory Hierarchy for Disciplined Parallelism, Byn Choi, Rakesh Komuravelli, Hyojin Sung, Robert Smolinski, Nima Honarmand, Sarita V. Adve, Vikram S. Adve, Nicholas P. Carter, and Ching-Tsun Chou, PACT 2011.
  • Parallel Programming Must Be Deterministic by Default, R. Bocchino, V. Adve, S. Adve, and M. Snir, First USENIX Workshop on Hot Topics in Parallelism (HotPar), 2009.

    Additional reading -
  • A Type and Effect System for Deterministic Parallel Java, R. Bocchino, V. Adve, D. Dig., S. Adve, S. Heumann, R. Komuravelli, J. Overbey, P. Simmons, H. Sung, and M. Vakilian, OOPSLA 2009.
  • Toward a Formal Semantic Framework for Deterministic Parallel Programming, L. Lu and M. L. Scott, 25th Intl. Symp. on Distributed Computing (DISC), Rome, Italy, Sep. 2011. Earlier version presented at the 2nd Wkshp. on Determinism and Correctness in Parallel Programming (WoDet), Newport Beach, CA, Mar. 2011 (in conjunction with ASPLOS XVI).

    14th March: Synchronization combining (Lingxiang)

  • Flat Combining and the Synchronization-Parallelism Tradeoff, Danny Hendler, Itai Incze, Nir Shavit, and Moran Tzafrir, in Proceedings of the 22nd SPAA, Santorini, Greece, June 2010.
  • Revisiting the Combining Synchronization Technique, Panagiota Fatourou and Nikolaos D. Kallimanis, PPoPP, Mar. 2012.
  • Accelerating Critical Section Execution with Asymmetric Multicore Architecture, Aater Suleman, Onur Mutlu, Moinuddin K. Qureshi, and Yale N. Patt, IEEE MICRO (Micro Top Picks paper from ASPLOS 2009), Jan/Feb 2010.

    21st March: Programming platforms for heterogeneous systems (Ananya)

  • Twin peaks: a software platform for heterogeneous computing on general-purpose and graphics processors, Jayanth Gummaraju, Laurent Morichetti, Michael Houston, Ben Sander, Benedict R Gaster, and Bixia Zheng, in Proceedings of the 19th International Conference on Parallel Architectures and Compilation Techniques, 2010.
  • Enabling Legacy Applications on Heterogeneous Platforms, Michela Becchi, Srihari Cadambi, and Srimat Chakradhar, In HotPar, 2010.
  • Programming Model for a Heterogeneous x86 Platform, Bratin Saha, Xiaocheng Zhou, Hu Chen, Ying Gao, Shoumeng Yan, Mohan Rajagopalan, Jesse Fang, Peinan Zhang, Ronny Ronen, and Avi Mendelson, PLDI 2009.

    28th March: Geo-replication/consistency (Li Lu)

  • Transactional storage for geo-replicated systems, Yair Sovran, Russell Power (NYU), Marcos K. Aguilera (MSR), and Jinyang Li (NYU), SOSP 2011.
  • Don't Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS, Wyatt Lloyd, Michael J. Freedman (Princeton), Michael Kaminsky (Intel Labs), and David G. Andersen (CMU), SOSP 2011.

    4th April: Hardware acceleration of queues (Li Shen)

  • HAQu: Hardware Accelerated Queueing for Fine-grained Threading on a Chip Multiprocessor, Sanghoon Lee, Devesh Tiwari, Yan Solihin, and James Tuck, HPCA 2011.

    11th April: Hardware acceleration of threads and reader-writer locks (Brandon and Lingxiang)

  • Architectural Support for Fair Reader-Writer Locking, Enrique Vallejo, Ramon Beivide, Adrian Cristal, Tim Harris, Fernando Vallejo, Osman Unsal, and Mateo Valero, MICRO 2010.
  • Carbon: Architectural Support for Fine-Grained Parallelism on Chip Multiprocessors , Sanjeev Kumar, Christopher J. Hughes, and Anthony Nguyen, ISCA 2007.

    18th April: 572 Spring Break


    25th April: Architectural support for concurrency (Sandhya)

  • Flexible Architectural Support for Fine-Grain Scheduling, Daniel Sanchez, Richard M. Yoo, and Christos Kozyrakis, ASPLOS 2010.
  • HICAMP: Architectural support for efficient concurrency-safe shared structured data access, David Cheriton (Hicamp Systems, Inc.), Alex Solomatnikov (Hicamp Systems, Inc.), Amin Firoozshahian (Hicamp Systems, Inc.) and John Stevenson (Hicamp Systems, Inc.), ASPLOS 2012.

    2nd May: Concurrency bug detection and memory fence insertion (Li Lu and Weixing Ji)

  • Dynamic Synthesis for Relaxed Memory Models, Feng Liu, Nayden Nedev, Nedyalko Prisadnikov, Martin Vechev, and Eran Yahav (Princeton, Sofia, ETH Zurich, Technion), PLDI 2012.
  • SigRace: Signature-Based Data Race Detection, Abdullah Muzahid, Dario Suarez, Shanxiang Qi, and Josep Torrellas, ISCA 2009.
  • ... and an additional paper for reference Detecting Concurrency Bugs from the Perspectives of Synchronization Intentions, Shan Lu, Soyeon Park and Yuanyuan Zhou, IEEE Transactions on Parallel and Distributed Systems, June 2012.

    THIS WILL BE THE LAST MEETING FOR THE SEMESTER