King Fahd University of Petroleum & Minerals
College of Computer Sciences and Engineering
Computer Engineering Department
COE 502 Parallel Architectures

CSE 661 Parallel and Vector Architectures

Course Syllabus

• Instructor: Professor Mayez Al-Mouhamed
• Email: mayez@kfupm.sa.edu
• Office Time: From 10 to 11 am on S.M.W and from 11 to 12 am on S.T.
• Location:  Room 22-400-3 (Tel. 2934) and Lab 22-339 (Tel. 3536).
• Text Book and references:
  • Parallel Computer Architecture (PCA): A Hardware/Software Approach, David E. Culler, Jaswinder P. Singh, Morgan Kaufmann Publishers, 1999
  • Selected topics and papers from other books, the IEEE T.C., IEEE T.P.D.S., etc.:
    • D.E. Culler and J.P. Singh, Parallel Computer Architecture: A Hardware/Software Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999, ISBN 1-55860-343-3.
    • Designing and Building Parallel Programs, Ian Foster, Addison-Wesley, 1995, complete textbook online, ( includes a chapter on MPI).
    • Parallel Programming (PP): Techniques and Applications Using Networked Workstations and Parallel Computers, Second Edition, Barry Wilkinson, Michael Allen, Prentice Hall, 2004.
    • PVM (Parallel Virtual Machine) Home Page
    • PVM: Parallel Virtual Machine: A Users' Guide and Tutorial for Networked Parallel Computing, Al Geist(Editor), et al, MIT Press, 1994, complete online version , PDF version , postscript version.
    • Advanced Tutorial on PVM 3.4 New Features and Capabilities,  Al Geist, Presented at EuroPVM-MPI'97, 1997.
       
    • Message-Passing Interface (MPI): MPI Home Page. MPICH Home Page A Portable Implementation of MPI. Beginner's Guide to MPI , University of Delaware. MPI: The Complete Reference , Marc Snir et al., First Edition, 1995 (html version of book).
    • Heterogeneous Computing: Challenges and Opportunities, PDF,
      Ashfaq A. Khokhar, Viktor K. Prasanna, Muhammad E. Shaaban, Cho-Li Wang
      IEEE Computer, June 1993 (Vol. 26, No. 6), pp. 18-27.
    • Heterogeneous Distributed Computing , PDF,
      Muthucumaru Maheswaran, Tracy D. Braun, Howard Jay Siegel,
      Edited version of a chapter appearing in the Encyclopedia of Electrical and Electronics Engineering, J. G. Webster, editor, John Wiley & Sons, New York, NY, 1999 Vol. 8, pp. 679-690.
    • A Comparison Study of Static Mapping Heuristics for a Class of Meta-tasks on Heterogeneous Computing Systems, PDF,
      Tracy D. Braun, Howard Jay Siegel, Noah Beck, Ladislau L. Boloni, Albert I. Reuther, Mitchell D. Theys, Bin Yao, Richard F. Freund
      Proceedings 8th Heterogeneous Computing Workshop, 1999. (HCW 1999), 1999, pp. 15-29.
    • Segmented min-min: a static mapping algorithm for meta-tasks on heterogeneous computing systems, PDF,
      Min-You Wu, Wei Shu, H. Zhang,
      Proceedings. 9th Heterogeneous Computing Workshop, 2000. (HCW 2000), 2000, pp. 375 -385.
    • Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing, PDF,
      H. Topcuoglu, S. Hariri, M.Y. Wu,
      IEEE Transactions on Parallel and Distributed Systems, March 2002 (Vol. 13, No. 3).
    • Greedy Heuristics for Resource Allocation in Dynamic Distributed Real-Time Heterogeneous Computing Systems, PDF,
      S. Ali, J. Kim, H. J. Siegel, A. Maciejewski, Y. Yu, S. Gundala, S. Gertphol, V. K. Prasanna,
      Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA '02), June 2002, (Volume 2), pp. 519-530.
    • Computer Architecture and Parallel Processing, K. Hwang and F. Briggs, Mc-Graw-Hill.
    • Readings in Computer Architecture, Mark Hill (Editor), Norman Jouppi (Editor), Gurindar Sohi (Editor), Morgan Kaufmann Publishing Co., Menlo Park, CA. 1999
    • Computer Organization and Design: The Hardware / Software Interface", Patterson and Hennessy, Morgan-Kaufmann, 1998.
    • M.J. Quinn, Parallel Programming in C with MPI and OpenMP, McGraw-Hill, New York, NY, 2004, ISBN 0-07-282256-2.
    • P.S. Pacheco, Parallel Programming with MPI, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997, ISBN 1-55860-339-5.
    • J.M. May, Parallel I/O for High Performance Computing, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001, ISBN 1-55860-664-5.
    • K. Hwang and Z. Xu, Scalable Parallel Computing: Technology, Architecture, Programming, McGraw-Hill, 1998, ISBN 0070317984.
    • A.E. Koniges (ed), Industrial Strength Parallel Computing, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000, ISBN 1-55860-540-1.
    • G.R. Andrews, Multithreaded, Parallel, and Distributed Programming,Addison-Wesley, Reading, Mass., 2000, ISBN 0-201-35752-6.
    • G.F. Pfister, In Search of Clusters, 2nd Edition, PTR Prentice-Hall, Upper Saddle River, NJ, 1998, ISBN 0-13-899709-8.
    • Kai Hwang, Advanced Computer Architecture - Parallelism, Scalability, Programmability, McGraw-Hill, New York, NY, 1993, ISBN 0-07-031622-8.

• Grading Policy: Exam 1: 20/100 (Saturday, November 7, 2009), Exam 2: 20/100 (Monday, December 28, 2009), Course project: 20/100,  Homework: 10/100, and Final Exam: 30/100 (scheduled by the registrar).
• Attendance: attendance is required by all students. Excuse for official authorized must be presented to the instructor no later than one week following the absence. Unexcused absences lead to a ``DEN'' grade.

Course Description: Introduction to parallel processing architectures, sequential, parallel, pipelined, and dataflow architectures. Vectorization methods, optimization, and performance. Interconnection networks, routing, complexity, and performance. Small-scale, medium-scale, and large-scale multiprocessors. Data-parallel paradigm and techniques. Multithreaded architectures and programming. The students are expected to carry out research projects in related field of studies. (Pre-requisite: COE 308 or equivalent).

Course Outline:

1. The Need and Feasibility of Parallel Computing, Technology Trends, Microprocessor Performance Attributes, Goal of Parallel Computing. Computing Elements, Programming Models, Flynn's Classification, Multiprocessors Vs. Multicomputers. Current Trends In Parallel Architectures, Communication Architecture. (PCA Chapter 1.1, 1.2)
2. Parallel Architectures Convergence: Communication Architecture, Communication Abstraction. Naming, Operations, Ordering, Replication. Communication Cost Model.(PCA Chapter 1.2, 1.3)
3. Parallel Programs: Conditions of Parallelism. Asymptotic Notations for Algorithm Analysis, PRAM. Levels of Parallelism, Hardware Vs. Software Concurrency. Data Vs. Functional Parallelism. Amdahl’s Law, DOP, Concurrency Profile. Steps in Creating Parallel Programs: Decomposition, Assignment, Orchestration, Mapping. (PCA Chapter 2.1, 2.2)
4. Parallelization of An Example Program: Ocean simulation Iterative equation solver (2D Grid). (PCA Chapter 2.3)
5. Cluster Computing: Origins, Broad Issues in Heterogeneous Computing (HC). Message-Passing Programming. Overview of Message Passing Interface (MPI 1.2). (PP Chapter 2, Appendix A, and MPI)
6. Considerations in Parallel Program Creation Steps for Performance. (PCA Chapter 3)
7. Basic Parallel Programming Techniques and Examples. Massively Parallel Computations: Pixel-based Image Processing. Divide-and-conquer Problem Partitioning: Parallel Bucket Sort, Numerical Integration, Gravitational N-Body Problem. Pipelined Computations: Addition, Insertion Sort, Solving Upper-triangular System of Linear Equations. Synchronous Iteration: Barriers, Iterative Solution of Linear Equations. Dynamic Load Balancing: Centralized, Distributed, Moore's Shortest Path Algorithm. (PP Chapters 3-7, 12)
8. Network Properties and Requirements For Parallel Processing. Static Point-to-point Connection Network Topologies. Network Embeddings. Dynamic Connection Networks. (PP Chapter 1.3, PCA Chapter 10)
9. Parallel System Performance: Evaluation & Scalability. Workload Selection. Parallel Performance Metrics Revisited. Application/Workload Scaling Models of Parallel Computers. Parallel System Scalability.
   (PP Chapter 1, PCA Chapter 4)
10. The Cache Coherence Problem in Shared Memory Multiprocessors. Cache Coherence Approaches. Snoopy Bus-Snooping Cache Coherence Protocols: Write-invalidate: MSI, MESI, Write-Update: Dragon.(PCA Chapter 5)
11. Cache Coherence in Scalable Distributed Memory Machines: Hierarchical Snooping, Directory-based cache coherence. (PCA Chapter 8)

Note: PCA stands for the book on Parallel Computer Architecture and PP stands for the book on Parallel Programming.