Courses:

Theory of Parallel Systems (SMA 5509) >> Content Detail



Study Materials



Readings

Any number of development tools can be used to read the .asm files in this section. These files contain assembly source code. Any number of development tools can also be used to compile and run the .c files in this section.

LEC #TOPICSREADINGS
Week 1
1Dynamic MultithreadingCilk Manual 5.3.2 (PDF)

Minicourse on Multithreaded Programming (PDF) (Courtesy of Harald Prokop. Used with permission.)
Week 2
3Serial Performance and CachingSorting Code Handout (PDF)

C Code for Sorting (C)

ASM Code for Sorting (Excerpt) (ASM)

Cache-Oblivious Algorithms

Prokop's Masters Thesis (PDF)
FOCS Paper (PDF)
Week 3
4Determinacy Detection and Race DetectionFeng, Mingdong, and Charles E. Leiserson. Efficient Detection of Determinacy Races in Cilk Programs.

Cheng, Guang-Ien, Mingdong Feng, Charles E. Leiserson, Keith H. Randall, and Andrew F. Stark. "Detecting Data Races in Cilk Programs that Use Locks." In Proceedings of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures (1998): 298-309.

The LCA Problem Revisited (PDF) (Courtesy of Martin Farach-Colton and Michael Bender. Used with permission.)
5Consistency of the Memory Sub-SystemGoodman, James R. Using Cache Memory To Reduce Processor-Memory Traffic. Department of Computer Sciences, University of Wisconsin-Madison Madison, WI: 19883, pp. 255-262.

Lamport, Leslie. "How to Make a Correct Multiprocess Program Execute Correctly on a Multiprocessor." IEEE Trans. Computers 46 (February 14, 1993).

Frigo, Matteo, and Victor Luchangco. "Computation-Centric Memory Models." To appear in Proceedings of the Tenth Annual ACM Symposium on Parallel Algorithms And Architectures (SPAA). MIT Laboratory for Computer Science, Massachusetts Institute of Technology. June 28-July 2, 1998.

Herlihy and Moss. Transactional Memory: Architectural Support for Lock-Free Data Structures. (PDF) (Courtesy of Maurice Herlihy and J. Eliot Moss. Used with permission.)

Huang, Kai. Data-Race Detection In Transaction Everywhere Parallel Programming. (PDF)
Week 4
6Analyzing Space BoundsBlumofe, Robert D., Charles E. Leiserson. "Space-Efficient Scheduling of Multithreaded Computations." SIAM Journal on Computing 27, 1: 202-229. MIT Laboratory for Computer Science, Massachusetts.

Berger, Emery D., Kathryn S. McKinley, Robert D. Blumofe, and Paul R. Wilson. "Hoard: A Scalable Memory Allocator for Multithreaded Applications." In Proceedings of the Ninth International Conference on Architectural Support for Programming Languages and Operating Systems. Cambridge, MA: November 2000. Department of Computer Sciences, The University of Texas at Austin Austin, Texas. Department of Computer Science, University of Massachusetts Amherst, Massachusetts.

Blumofe, Robert D., Matteo Frigo, Christopher F. Joerg, Charles E. Leiserson, and Keith H. Randall. "An Analysis of Dag-Consistent Distributed Shared-Memory Algorithms." In Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA). Department of Computer Sciences, The University of Texas at Austin, Texas. MIT Laboratory for Computer Science, Massachusetts.

Narlikar, Girija J., and Guy E. Blelloch. "Space-Efficient Scheduling of Nested Parallelism." ACM Transactions on Programming Languages and Systems (TOPLAS) 21, 1 (January 1999): 138-173. Carnegie Mellon University.

Vee and Hsu. A Scalable and Efficient Storage Allocator on Shared-Memory Multiprocessors.Singapore, Nanyang Avenue: Center for Advanced Information Systems, SAS Nanyang Technological University.
Week 5
8Cilk SchedulerExecuting Multithreaded Programs Efficiently
Week 9
14Competitive Snoopy CachingKarlin, Anna R., Mark S. Manasse, Larry Rudolph, and Daniel D. Sleator. "Competitive Snoopy Caching." Algorithmica 3. Springer-Verlag, New York Inc., 1988, pp. 79-119.

Karlin, Anna R., Mark S. Manasse, Lyle A. McGeochj, and Susan Owicki. "Competitive Randomized Algorithms for Non-Uniform Problems" In Proceedings, Symposium on Discrete Algorithms. 1990, chapter 33, pp. 301-309.
Week 13
22Pick a WinnerAwerbuch, Baruch, Yossi Azar, Amos Fiat, and Tom Leighton. "Making Commitments in the Face of Uncertainty: How to Pick a Winner Almost Every Time." In Proceedings of the 28th Annual ACM Symposium on Theory of Computing (1996): 519-530.

 








© 2010-2021 OpenCollege.com, All Rights Reserved.
Open College is a service mark of AmeriCareers LLC.