FDA125
Advanced Parallel Programming: Models, Languages, Algorithms

Papers for Student Presentations

Choose one paper from the following list for presentation and another (preferably related) one for opposition.

    NON-BLOCKING PARALLEL DATA STRUCTURES

  1. Maged M. Michael, Michael L. Scott:
    Non-Blocking Algorithms and Preemption-Safe Locking on Multiprogrammed Shared Memory Multiprocessors
    J. Parallel and Distr. Comput. 51(1): 1-26, May 1998.

  2. Ori Shalev, Nir Shavit:
    Split-Ordered Lists: Lock-Free Extensible Hash Tables
    J. of the ACM 53(3), May 2006, pp. 379-405.

    3. TRANSACTIONAL MEMORY

  3. Maurice Herlihy, J. Eliot B. Moss:
    Transactional memory: Architectural support for lock-free data structures.
    Proc. ISCA'93 20th Int. Symp. on Computer Architecture, pp. 289-300, 1993.

  4. Lance Hammond et al.:
    Transactional memory coherence and consistency.
    Proc. ISCA'04 31st Int. Symp. on Computer Architecture, pp. 102-113, 2004.

  5. Brian D. Carlstrom et al.:
    The ATOMOS Transactional Programming Language.
    Proc. PLDI'06 ACM Conf. on Progr. Languages Design and Implementation, p. 1-13, June 2006.

    6. PARALLEL LANGUAGES AND ENVIRONMENTS

  6. Kenjiro Taura, Kunio Tabata, Akinoro Yonezawa:
    StackThreads/MP: Integrating Futures into Calling Standards
    ACM PPoPP'99 Symposium on Principles and Practice of Parallel Programming, 1999.

  7. Hans-J. Boehm:
    Threads Cannot be Implemented as a Library,
    Proc. Conf. on Programming Language Design and Implementation (PLDI), June 2005.

  8. Bradford L. Chamberlain, David Callahan, Hans P. Zima:
    Parallel Programmability and the Chapel Language
    To appear in International Journal of High Performance Computing Applications, 2007. See also: Chapel homepage.

    9. SCHEDULING:

  9. Guy E. Blelloch, Phillip B. Gibbons, Yossi Matias:
    Provably Efficient Scheduling for Languages with Fine-Grained Parallelism
    J. of the ACM 46(2), March 1999, pp. 281-321.

  10. Alain Darte, Robert Schreiber:
    A Linear-Time Algorithm for Optimal Barrier Placement
    Proc. ACM PPoPP'06

  11. Katherine E. Coons, Xia Chen, Sundeep K. Kushawaha, Doug Burger, Kathryn S. McKinley:
    A Spatial Path Scheduling Algorithm for EDGE Architectures
    Proc. ACM ASPLOS-XII, pp. 129-140, Oct. 2006.

  12. Thomas Rauber, Gudula Rünger:
    Anticipated Distributed Task Scheduling for Grid Environments.
    20th Int. Parallel and Distributed Processing Symposium (IPDPS) 2006.

  13. Nimar S. Arora, Robert D. Blumofe, C. Greg Plaxton:
    Thread scheduling for multiprogrammed multiprocessors Proc. Tenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), 1998. ACM Press, New York, NY, pp. 119-129.

    14. PARALLEL ALGORITHMS

  14. Mattias Korch, Thomas Rauber:
    Optimizing locality and scalability of embedded Runge-Kutta solvers using block-based pipelining
    J. Parallel Distrib. Computing 66, 444-468, 2006.

  15. Jean-Louis Roch et al.:
    On-Line Adaptive Parallel Prefix Computation.
    Proc. Euro-Par 2006, Springer LNCS 4128, pp. 841-850, 2006.

Task: Prepare a 20 minutes presentation of your chosen paper and at least 3 questions on the other paper for opposition.
After the presentation, hand in a written summary of your presented paper on 2-3 pages.

This page is maintained by Christoph Kessler (chrke \at ida.liu.se)