Prerequisites: CS 401 and CS 466 or equivalents, or permission of instructor

Required Textbooks/ Sources:

1. Main text: Introduction to Parallel Computing, by V. Kumar, A. Grama, A. Gupta, G. Karypis, Benjamin-Cummins, 2nd edition, 2003.
   All Chapters except Chapter 7.
2. Selection of papers to be studied in class. Will be announced around week 4.

1. The Argo Beowulf Cluster at UIC, and its MPI tutorial
2. Interconnection Networks
3. Overhead slides used in class.
   • Models
   • Basic Communication operations - 1
   • Basic Communication operations - 2
   • Performance and Scalability
   • Sorting
   • Graph Problems
   • Discrete Optimization
   • Dynamic Programming
4. MPI tutorial at Argonne National Lab

Supplemental References and sources:

1. Introduction to Parallel Algorithms and Architectures, by Thomas Leighton, Morgan Kaufman, latest edition.
   Chapters 1.1, 1.5, 1.6, 1.7, 2.1, 2.2, 2.7, 3.1 - 3.7
2. Parallel Computation : Models and Methods, by Selim G. Akl / Prentice Hall / April 1997
3. Highly Parallel Computing (The Benjamin/Cummings Series in Computer Science and Engineering) by George S. Almasi, Allan Gottlieb / Addison-Wesley Pub Co / February 1994
4. The best and the fastest supercomputers! Overview of Recent Supercomputers! Study these sites, including the report on HPC benchmarks.
5. MPI Notes from ARGO Sys Admin
6. Shared memory Chapter

Course Description:

1. Various parallel topologies and algorithms on such topologies
2. Parallel algorithms for counting, sorting, routing, and graphs
3. Parallel matrix multiplication, Fast Fourier Transforms
4. Shared memory parallel systems
5. Programming using MPI (Message Passing Interface); case studies of systems/platforms
6. Special topics

Grading: Grading will be on the curve. The following is only a tentative breakup of the evaluation scheme and is subject to (reasonable) changes as the course progresses. Also depends on the class size.

• Midterm (25%)
• Exam (30%)
• MPI programming assignments (20%)
• Class presentation and term paper (25%)

Course progress chart:

• Week 1 (Jan 09 -): Introduction; processors; classification; platforms
• Week 2 (Jan 16 -): PRAM model; Architectures
• Week 3 (Jan 23 -): Architectures; embeddings
• Week 4 (Jan 30 -): Embeddings, Performance & scalability
• Week 5 (Feb 06 -): Introduction to MPI. Scalability. Programming Assignment 1
• Week 6 (Feb 13 -): Parallel Sorting. Parallel graph algorithms - routing, counting. Discrete optimization problems
• Week 7 (Feb 20 -): Dynamic programming
• Week 8 (Feb 27 -): parallel matrix multiplication, parallel FFT.
• Week 9 (Mar 06 -): Shared memory basics -- coherence, consistency models, Wait-freedom, register constructions, Simulations of Read/Write objects
• Week 10 (Mar 13 -): Assignment 1 due. (postponed to April 3. please use the mpd ring as described here to collect your data)
  Atomic snapshot objects, Consensus numbers, universal objects
• SPRING BREAK
• Week 11 (Mar 27 -):
  March 27: Midterm 3-5pm Syllabus: Chapters 1-6, 8-10
  Programming Assignment 2
  March 29 - Presentation 1: (VK, IL) PPT.
  Zipf, Power-laws, and Pareto - a ranking tutorial. Lada Adamic, HP Labs [60]
  Classification of scale-free networks. K.I. Goh, E. Oh, H. Jeong, B. Kahng, D. Kim. Proceedings of the National Academy of Sciences, 2002 [61]
• Week 12:
  April 3: Assignment 1 extended due date
  Presentation 2: (JI, FA) PPT.
  "On Power-Law Relationships of the Internet Topology". Michalis Faloutsos, Petros Faloutsos, Christos Faloutsos, ACM SIGCOMM'99, Boston, 1999 [979]
  Power-Laws and the AS-level Internet Topology. G. Siganos, M. Faloutsos, P. Faloutsos, C. Faloutsos IEEE/ACM Transactions on Networking, volume 11, no. 4, pp. 514-524, 2003. [36]
  April 5: Presentation 3: (NK, NM) PPT.
  Topology of Evolving Networks: Local Events and Universality. R. Albert and A. Barabasi. Physics Review Letters, 85, p. 5234, 2000. [271]
  Error and Attack Tolerance of Complex Networks, R. Albert, H. Jeong, A. Barabasi, Nature 406, 378-382, July 2000 (Use the "cached" PDF or PS link to the right) [763]
• Week 13:
  April 10: Presentation 4: (YC, YS) PPT.
  Graph Structure in the Web, by Andrei Border, Ravi Kumar, Farzin Maghoul, Prabhakar Raghavan, Sridhar Rajagopalan, Raymie Stata, Andrew Tomkins, Janet Weiner, Computer Networks 33(1-6): 309-320 (2000) [686]
  The PageRank Citation Ranking: Bringing Order to the Web, by Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd (Stanford University) [774]
  A Stochastic Model for the Evolution of the Web, by Mark Levene, Trevor Fenner, George Loizou, Richard Wheeldon (University of London)[22]
  The diameter of the World Wide Web. R. Albert, H. Jeong, A. Barabasi, Nature 401, 130-131, 1999. [854]
  Exploiting the Block Structure of the Web for Computing PageRank. By Sepandar Kamvar, Taher Haveliwala, Christopher Manning, Gene Golub. 2003[64]
  April 12: Presentation 5: (SK, SC) PPT.
  A Survey of Web Caching Schemes for the Internet. J Wang - ACM SIGCOMM Computer Communication Review, 1999 [237] Click on the PDF file to the right
  Web Cache Replacement Policies: A Pragmatic Approach. K. Wong, IEEE Network, Feb 2006, pages 28-34. Access via IEEE Explore from a UIC IP address.
  Caching and Prefetching for Web Content Distribution. 1. Jianliang Xu et al., Computing in Science and Engineering, pages 54-59, July/Aug 2004
  Web Search for a Planet: The Google Cluster Architecture. Barroso, Dean, Holzle, IEEE Micro, 2003 [47]
• Week 14:
  April 17: Presentation 6: (ST, SV) PPT.
  S. Madden, M.J. Franklin, and J.M. Hellerstein, and W. Hong, The Design of an Acquisitional Query Processor For Sensor Networks, SIGMOD'03, June 2003 [472]
  W. Heinzelman, A. Chandrakasan, and H. Balakrishnan, "An Application-Specific Protocol Architecture for Wireless Microsensor Networks,'' IEEE Transactions on Wireless Communications, Vol. 1, No. 4, October 2002, pp. 660-670 [317]
  April 19: Presentation 7: (RS, KJ) PPT.
  N. Sadagopan, B. Krishnamachari, and A. Helmy, The ACQUIRE Mechanism for Efficient Querying in Sensor Networks, IEEE International Workshop on Sensor Network Protocols and Applications (SNPA'03), May 2003[31]
  B. Krishnamachari, D. Estrin, and S. Wicker, The Impact of Data Aggregation in Wireless Sensor Networks, International Workshop on Distributed Event-Based Systems, (DEBS '02), July 2002 [150]
• Week 15:
  April 24: Presentation 8: (JC, ZX) PPT.
  S. Madden, R. Szewczyk, M.J. Franklin, and D. Culler, Supporting Aggregate Queries Over Ad-Hoc Wireless Sensor Networks, Mobile Computing Systems and Applications, June 2002 [130]
  S. Madden, M.J. Franklin, J.M. Hellerstein, and W. Hong, TAG: a Tiny AGgregation Service for Ad-Hoc Sensor Networks, 5th Symposium on Operating System Design and Implementation (OSDI 2002), December 2002[472]
  April 26: Presentation 9: (PS, JL) PPT. PPT .
  The Earth Simulator Center
  S. Habata, M. Yokokawa, and S. Kitawaki, "The Earth Simulator System", NEC Res. & Develop., Vol. 44, No.1, pp. 21-26, January 2003.
  T. Sato, S. Kitawaki, and M. Yokokawa, "Earth Simulator Running", ISC, June 2002.
  LLNL's BlueGene page
  A. Gara et al, "Overview of the Blue Gene/L system architecture", IBM J. Res. & Dev., Vol. 49, No. 2/3, pp. 195-212, 2005.
  "Early Experience with Scientific Applications on the Blue Gene/L Supercomputer", Euro-Par 2005, LNCS 3648, pp. 560-570, 2005.
• Assignment 2 due on May 1
  Term paper due on May 1
  Final exam on Wed, May 3, 3:30pm-5:30pm as per university timetable
  Syllabus: papers, Module 6 (shared memory), Chapters 4, 5 from book
  Thursday May 4: Lab evaluations from 1pm-4:30pm in SEL 2260

Literature sources: The following is a listing of journals and confernewce proceedings (in roughly decreasing order of relevance to this course 566) that you may find useful in your literature search.

1. IEEE Transactions on parallel and distributed systems
2. ACM Symp. on Parallel Algorithms and Architectures (SPAA)
3. ACM-SIAM Symp. on Discrete Algorithms (SODA)
4. ACM Symp. on Principles of Distributed Computing (PODC)
5. IEEE Symp. on Parallel and Distributed Processing (SPDP)
6. Inter. Conf. on Structure Information and Communication Complexity (SIRROCCO)
7. Distributed Computing
8. IEEE/ACM transactions on networking
9. Information Processing Letters
10. Inter. Conference on Distributed Computing Systems (ICDCS)
11. Inter. Conference on Parallel Processing (ICPP)
12. IEEE Transactions on Computers