CS 233A Parallel & Distributed Programming
Winter 2008

Instructor	Rajive Bagrodia (rajive@cs.ucla.edu) 3531F Boelter Hall (310) 825-0956
Meeting Time	MW 10-12; BH 4283
Office Hours	W 9-10 AM or by appointment
Course URL	http://pcl.cs.ucla.edu/courses/233a (available as of Jan 9, 2008)
Prerequisites	CS 111 and CS 131 or CS 133, or by consent of instructor
Texts References:	No single text-book Selected readings from list given below. Design and Build Parallel Programs, Ian Foster, Addison Wesley, 1995. Concurrent and Distributed Computing in Java, Vijay K. Garg ISBN: 0-471-43230-X, January 2004, Wiley-IEEE Press Introduction to Parallel Computing, Kumar, Grama, Gupta, and Karypis, Benjamin Cumings, 1994. Computer Architecture, Hennessy and Patterson, 1995. High Performance Compilers for Parallel Computing, Wolfe; Addison-Welsey; 1996. In Search of Clusters, Pfister; Prentice-Hall; 1998

Overview

The purpose of this course is to teach fundamental concepts of the design and implementation of parallel and distributed languages and systems. Target architectures covered in the course include clusters, distributed and shared memory architectures, and mobile/nomadic computing systems. The course begins with coverage of a few traditional topics in parallel and distributed computing (focusing on language issues); the latter half of the course covers infrastructure & middleware services for distributed computing as well as topics in the area of mobile computing.

Work Requirement

Students will be expected to read a number of papers (approximately 15), and complete a term project.

Grading

Grades will be based on one exam (50%), term project (40%), and class participation (10%). Detailed requirements for the term project will be distributed subsequently. Group term projects are possible and encouraged.

Work Schedule

• Week 4: submit topic for term project.
• Week 9: term project due.

Course Outline

The major topics that will be discussed in class are indicated. This outline is tentative and subject to change.

• Week 1,2: Overview of Parallel Computing
• Architecture, language and theoretical models: Notes
• Applications:
• distributed programs: Dining Philosophers
• scientific applications: Gaussian Elimination
• Weeks 3-6: Parallel Computing Paradigms
• Shared Nothing Programming Model – CSP,MPC, MPI, Linda
• Messaging overheads
• Cluster/Grid programming
• Shared Everything Programming Model
• Consistency & coherence models for distributed shared memory
• Data Parallel Programming – Open MP
• Week 7: Nomadic/Pervasive Computing
• Distributed, Mobile, and Ubiquitous Computing
• Vision and architecture for mobile computing
• Weeks 8-9: Middleware Infrastructure Services
• Jini, CORBA
• Proxies
• Transcoding
• Content Migration
• Context Awareness
• Week 10: Project Presentations

Parallel Programming Languages

• Using Parsec/MPC
• All about MPI
• Java Threads
• Open MP

Conferences and Journals

Almost every conference or journal will invariably have papers pertaining to some aspect of concurrent computation! The following is a partial list of conferences and journals that are primarily concerned with parallel/distributed computing. It is a useful exercise to go through the latest issues of some of the following publications to identify possible topics for your term paper.

• International Conference on Distributed Computer Systems: Deals primarily with systems issues of message-passing concurrent systems.
• International Conference on Parallel Processing : Huge conference; deals with hardware, software and algorithmic issues of all types of concurrent systems and their applications.
• International Parallel Processing Symposium: Has very similar interests to ICPP.
• Supercomputing: Massive conference with lots of exhibits of state-of-the-art architectures and systems; the broadest coverage of areas including many supercomputer applications.
• ACM Principles of Distributed Computing: Emphasizes theoretical results, algorithms and their proofs; proof techniques.
• ACM Principles of Programming Languages: Emphasizes issues pertaining to language semantics, proof rules, programming paradigms, compiler design issues.
• Principles and Practice of Parallel Programming: Good conference devoted to practical considerations of parallel program design.
• ASPLOS: Highlights interactions between architectures and software systems for parallel programming.
• IEEE Trans. on Software Engineering, IEEE Trans on Parallel and Distributed Systems, IEEE Trans. on Computers.
• ACM Trans. on Programming Languages and Systems, ACM Trans. on Computer Systems
• Sigplan Notices
• Journal of Parallel and Distributed Computing.
• Mobicom
• Mobisys
• Mobihoc
• Int Conf on Dist Computing Systems
• Ubicomp
• Pervasive Computing

Readings

1. E. Amir, S. McCanne, and R. Katz. ``An Active Service Framework and Its Application to Real-Time Multimedia Transcoding,'' ACM SIGCOMM 1998 Conference: Applications, Technologies, Architectures, and Protocols for Computer Communication, 1998, Vancouver, BC, Canada.
2. G. R. Andrews, F. Schneider. "Concepts and Notations for Concurrent Programming", Computing Surveys, March 1983: 3-43.
3. O. Angin, A. Campbell, M. Kounavis, and R. Liao. ``The Mobiware Toolkit: Programmable Support for Adaptive Mobile Networking,'' IEEE Personal Communications, August 1998.
4. R. Bagrodia, S. Bhattacharyya, F. Cheng, S. Gerding, G. Glazer, R. Guy,Z. Ji, J. Lin, T. Phan, E. Skow, M. Varshney, and G. Zorpas. "iMASH: Interactive Mobile Application Session Handoff," In Proceedings of Mobisys 2003.http://www.usenix.org/events/mobisys03/tech/full_papers/bagrodia/bagrodia.pdf
5. M. Baker, R. Buyya, and D. Laforenza. "The Grid: International Efforts in Global Computing", In Proceedings of the Intl. Conf. on Advances in Infrastructure for Electronic Business, Science, and Education on the Internet, 2000.
6. H.E. Bal, J. Steiner, and A.S. Tanenbaum. Programming languages for distributed computing systems. ACM Computing Survey, 21(3):261-322, September 1989.
7. K. Birman, A. Schiper, and P. Stephenson, Lightweight Causal and Atomic Group Multicast, ACM TOCS, Aug 1991
8. Birrell and Nelson, Implementing Remote Procedure Calls; ACM Transaction on Computing Systems, Feb 1984
9. A. Bond, M. Gallagher, and J. Indulska. ``An Information Model for Nomadic Environments,'' IEEE Proceedings of the Ninth International Workshop on Database and Expert Systems Applications, 1998.
10. E. Brewer, R. Katz, E. Amir, H. Balakrishnan, Y. Chawathe, A. Fox, S. Gribble, T. Hodes, G. Nguyen, V. Padmanabhan, M. Stemm, S. Seshan, and T. Henderson. ``A Network Architecture for Heterogeneous Mobile Computing,'' IEEE Personal Communications, September 1998 http://www.cs.berkeley.edu/~brewer/papers/Barwan-IEEE.pdf
11. Y. Chawathe, S. Fink, S. McCanne, and E. Brewer. ``A Proxy Architecture for Reliable Multicast in Heterogeneous Environments,'' in Proceedings of the 6th ACM International Multimedia Conference, 1998.
12. N. Davies and H-W. Gellerson. "Beyond Prototypes: Challenges in Deploying Ubiquitous Systems," IEEE Pervasive Computing magazine, 1(1), Jan/March 2002
13. X. D’Fago, A. Shiper, P. Urban: Total Order Broadcast and Multicast Algorithms: Taxonomy & Survey; ACM Computing Surveys, Dec 2004
14. E.W. Dijkstra. Guarded commands, nondeterminacy, and formal derivation of programs. Communications of the ACM, 18(8):453-457, August 1975.
15. M. Dubois, C. Scheurich, and F. Briggs. Synchronization, coherence, and event ordering in multiprocessors. Computer, 21(2):9-21, 1988.
16. Thorsten von Eicken, D. Culler, G. Goldstein, and K. Schauser. Active messages: A mechanism for integrating computation and communication. In 19th ISCA, 1992.
17. I. Foster. "What is the Grid? A Three Point Checklist", GRIDToday, July 20, 2002.
18. G. Forman, J. Zahorjan, "The Challenges of Mobile Computing," IEEE Computer, vol. 27, no. 4, pp. 38-47, 1994.
19. A. Fox, S. Gribble, Y. Chawathe, and E. Brewer. ``Adapting to Network and Client Variation Using Infrastructural Proxies: Lessons and Prospectives,'' IEEE Personal Communications, 1998.
20. S. Gribble et al. "The Ninja Architecture for Robust Internet-Scale Systems and Services," IEEE Computer Networks Special Issue on Pervasive Computing
21. S. Gribble, M. Welsh, E. Brewer, and D. Culler. ``The Multispace: an Evolutionary Platform for Infrastructural Services,'' USENIX 1999.
22. William Gropp and Ewing Lusk. The mpi communication library: Its design and a portable implementation. In Proceedings Scalable Parallel Libraries Conference, IEEE Computer Society Press, October 1993.
23. M. Haahr, R. Cunningham, V. Cahill, "Supporting CORBA Applications in a Mobile Environment," Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking, ACM, pp. 36-47, 1999.
24. C. A. R. Hoare. "Communicating Sequential Processes", in Communications of the ACM 21(8), 1978.
25. A. Joseph, and M. Kaashock. ``Building Reliable Mobile-Aware Applications Using the Rover Toolkit,'' Second ACM International Conference on Mobile Computing and Networking (MoBiCom), 1996.
26. Vijay Karamcheti and Andrew A. Chien. Software overhead in messaging layers: Where does the time go? In Proceedings of ASPLOS-VI, San Jose, CA, October, 1994.
27. D. Lenoski, J. Laudon, K. Gharachorloo, W. Weber, A. Gupta, J. Hennessy, M Horowitz, and M. S. Lam. The Stanford DASH multiprocessor. IEEE Computer, March 1992.
28. Kai Li and Paul Hudak. Memory coherence in shared virtual memory systems. ACM Transactions on Computer Systems, 7(4):321-359, November 1989.
29. T. Mowbray, W. Ruh, Inside CORBA: Distributed Object Standards and Applications, Addison Wesley Longman, Inc., 1997.
30. MPI Forum. Mpi: A message passing interface. In Proceedings of 1993 Supercomputing Conference, Portland, Washington, November 1993.
31. B. Noble, M. Satyanarayanan, D. Narayanan, J. Tilton, J. Flinn, and K. Walker. ``Agile Application-Aware Adaptation for Mobility,'' in Proceedings of the 16th ACM Symposium on Operating System Principles, 1997.
32. T. Phan, G. Zorpas, and R. Bagrodia, "The Convergence of Heterogeneous Internet-connected Clients within IMASH," IEEE Wireless Communications, June 2002.
33. T. Phan, G. Zorpas, and R. Bagrodia, "Middleware Support for Reconciling Client Updates and Data Transcoding," In Proceedings of Mobisys 2004. http://pcl.cs.ucla.edu/papers/files/mobisys04.pdf
34. Thomas Phan, Lloyd Huang, and Chris Dulan. "Challenge: Integrating Mobile Wireless Devices into the Computational Grid", In Proceedings of the 8th ACM International Conference on Mobile Computing and Networking (Mobicom 2002), September 2002.
35. D. Ridge, D. Becker, P. Merkey, and T. Sterling. "Beowulf: Harnessing the Power of Parallelism in a Pile-of-PCs", In Proceedings of IEEE Aerospace, 1997.
36. R. Sarvas, E. Herrarte, A. Wilhelm, and M. Davis. "Metadata Creation System for Mobile Images," In Proceedings of Mobisys 2004. http://fusion.sims.berkeley.edu/GarageCinema/pubs/pdf/pdf_6C19FBDD-ED79-4E9C-87AAF80D9AFA828F.pdf
37. D. Saha, A. Mukherjee, "Pervasive Computing: A Paradigm for the 21st Century," IEEE Computer, March 2003. http://www.ece.rutgers.edu/~parashar/Classes/02-03/ece572/perv-reading/pc-overview.pdf
38. M. Satyanarayanan. "Pervasive Computing: Vision and Challenges," IEEE Personal Communications, August 2001.http://www-2.cs.cmu.edu/~aura/docdir/pcs01.pdf
39. M. Snir, P. Hochschild, D.D. Frye, and K.J. Gildea. The communication software and parallel environment of the ibm sp2. IBM Systems Journal, 34(2):205-221, 1995.
40. P. Sudame and B. Badrinath. ``Transformer Tunnels: A Framework for Providing Route-Specific Adaptations,'' USENIX 1998.
41. Sun Microsystems, Jini Technology Architectural Overview, January 1999.
42. B. Thorstensen, T. Syversen, T. Walseth, and T-A. Bjornvold."Electronic Shepherd - a Low-Cost, Low-Bandwidth, Wireless Network System," In Proceedings of Mobisys 2004. http://portal.acm.org/citation.cfm?id=990064.990094
43. J. Waldo, Remote Procedure Calls and Java RMI, IEEE Concurrency, July 1998.
44. J. Waldo, "The Jini Architecture for Network-Centric Computing," Communications of the ACM, Vol. 42, No. 7, p.76-82, 1999.
45. M. Weiser. "The Computer for the 21st Century," Scientific American, Sept. 1991.