Αρχιτεκτονική παράλληλων υπολογιστών

Topic outline

• General

  Collapse all Expand all
  • 

    General Information Page
  • 

    Course Information Page
  • 

    Assignments Page
  • Keywords: parallel computer architectures, shared memory, message passing, network interfaces, performance evaluation.

• Administration

  1. Course topics and logistics

  2. Assignment 1

  3. Lecture: Technology trends (Chapters: 1)

• Introduction & Background

  1. Assignment 1 intro

  • What are threads?

  • User vs. kernel threads

  2. Lecture: Convergence of parallel architectures (Chapters: 1)

  • 

    Assignment 1 Page

• Understanding Concurrency

  1. Assignment 1 data structures, ADTs, and mechanisms

  2. Paper discussion:

  • Why threads are a bad idea (for most purposes).  Invited talk. In USENIX 1996 Annual Technical Conference.
  • Why events are a bad idea. Rob von Behren, Jeremy Condit, and Eric Brewer. 9th Workshop on Hot Topics in Operating Systems (HotOS IX).

  • 

    Why Events Are A Bad Idea File
  • 

    Why threads are a bad idea File

• Convergence of Parallel Architectures Part 1

  1. Assignment 1 questions

  2. Lecture: Convergence of parallel architectures (Chapters: 1)

• Convergence of Parallel Architectures Part 2

  1. Lecture:  Parallel Programming Examples (Chapters: 2,3)

• Parallel Programming Part 1

  1. Paper discussion: J. B. Dennis and D. P. Misunas, "A Preliminary Architecture for a Basic Data-Flow Processor" Proc. 2nd Annual Symposium on Computer Architecture, Computer Architecture News, 3, 4 (December 1974), 126-132, ACM.

• Parallel Programming Part 2

  1. Lecture: Parallel Programming Examples (Chapters: 2,3)

• Workload-driven Performance Evaluation
  1. Assignment 1 due
  2. Assignment 2 intro
  3. Paper discussion: The SPLASH2 Programs: Characterization and Methodological Considerations. Steven Woo, Moriyoshi Ohara, Evan Torrie, Jaswinder Pal Singh and Anoop Gupta. In Proceedings of the 21st International Symposium on Computer Architecture, June 1995.

  • 

    The SPLASH2 Programs: Characterization and Methodological Considerations File
  • 

    Assignment 2 Page

• Parallel Programming, Workload-driven Performance Evaluation

  1. Lecture:  Workloadr-driven performance evaluation: Parameter space, metrics, interactions between application and architecture (Chapters: 4)

• Time, Ordering, and Memory Consistency Part 1

  1. Paper discussion (cont'd): The SPLASH2 Programs: Characterization and Methodological Considerations. Steven Woo, Moriyoshi Ohara, Evan Torrie, Jaswinder Pal Singh and Anoop Gupta. In Proceedings of the 21st International Symposium on Computer Architecture, June 1995.

  2. Lecture: Ordering issues, program order, sequential order, coherency vs. consistency, memory consistency models, ensuring coherency, ensuring consistency. (Chapters: 5,9)

• Time, Ordering, and Memory Consistency Part 2
  1. Assignment 2 due
  2. Assignment 3 intro

  3. Paper discussion: Time, Clocks, and the Ordering of Events in a Distributed System. Leslie Lamport. Communications of the ACM, 21(7), pp. 558-565, July 1978.

  • 

    Assignment 3 Page

• Memory consistency models Part 1

  1. Lecture: Memory consistency models: sequential consistency, weak consistency, release consistency, entry consistency. (Chapters: 5,9)

• Memory consistency models Part 2

  1. Paper discussion: Memory Consistency Models. D. Mosberger. ACM Operating Systems Review, 27(1), pp. 18-26, January 1993.

  • 

    Memory Consistency Models File

• Snoop-Based Shared Memory Multiprocessors

  1. Lecture: Providing consistency in bus-based shared memory multiprocessors. Cache coherency/memory consistency protocols, cache misses categorization. (Chapters: 6)

• Distributed Shared Memory Multiprocessors Part 1
  1. Paper discussion: Correct Memory Operation of Cache-Based Multiprocessors. C. Scheurich and M. Dubois. Proceedings of the 14th International Symposium on Computer Architecture, June 1987, pp. 234:243.

• Distributed Shared Memory Multiprocessors Part 2
  1. Lecture: Scalable shared memory machines, distributed shared memory, directory protocols, CC-NUMA, COMA, synchronization issues. (Chapters: 7, 8, 9)

• Distributed Shared Memory Multiprocessors Part 3

  1. Project proposals due. After ack from instructor, start working on your projects.

  2. Paper Discussion: An Evaluation of Directory Schemes for Cache Coherence. A. Agarwal, R. Simoni, J. Hennessy, M. Horowitz. ISCA'88.

  • 

    An Evaluation of Directory Schemes for Cache Coherence File

• Software Distributed Shared Memory
  1. Lecture: Software shared memory. Shared Virtual Memory, Instrumentation-based software DSM, Implementation issues. (Chapters: 9)
  2. Paper discussion: Fine-grain Access Control for Distributed Shared Memory, Ioannis Schoinas, Babak Falsafi, Alvin R. Lebeck, Steven K. Reinhardt, James R. Larus, David A. Wood (The Sixth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS VI), Oct. 1994).

  • 

    Fine-grain Access Control for Distributed Shared Memory File

• Message Passing Multiprocessors Part 1
  1. Lecture: Node-to-network interfaces in message passing systems, programming considerations. Increasing message throughput. (Chapters: 10, 7.7)

• Message Passing Multiprocessors Part 2
  1. Paper Discussion: Introduction to the Cell multiprocessor. J. A. Kahle, M. N. Day, H. P. Hofstee, C. R. Johns, T. R. Maeurer, and D. Shippy. IBM Journal of Research and Development. Volume 49, Number 4/5, 2005.

• Message Passing Multiprocessors Part 3

  1. Lecture: Node-to-network interfaces in message passing systems, programming considerations. Reducing CPU overhead. (Chapters: 10, 7.7)

• Message Passing Multiprocessors Part 4

  1. Paper discussion: Software Overhead in Message Passing Layers: Where Does the Time Go? Vijay Karamcheti and Andrew Chien. International Conference on Architectural Support for Programming Languages and Operating Systems. October 1994.

  • 

    Software Overhead in Messaging Layers: Where Does the Time Go? File

• Message Passing Multiprocessors Part 5

  1. Lecture: Node-to-network interfaces in message passing systems, programming considerations. Reducing message latency. (Chapters: 10, 7.7)

• Communication in Anton
  1. Paper discussion: Dror, R.O.; Grossman, J. P.; Mackenzie, K.M.; Towles, B.; Chow, E.; Salmon, J.K.; Young, C.; Bank, J.A.; Batson, B.; Deneroff, M.M.; Kuskin, J.S.; Larson, R.H.; Moraes, M.A.; Shaw, D.E. Overcoming Communication Latency Barriers in Massively Parallel Scientific Computation. Micro, IEEE , vol.31, no.3, pp.8,19, May-June 2011.

• Parallel I/O (in Anton)
  1. Lecture: Why is parallel I/O important - main problems.
  2. Paper Discussion: Accelerating parallel analysis of scientific simulation data via Zazen. Tiankai Tu, Charles A. Rendleman, Patrick J. Miller, Federico Sacerdoti, Ron O. Dror, and David E. Shaw. Usenix FAST'10.

• Project Presentations
  1. Projects due: Presentations, 15-20 mins/project.
  2. End of HY527

• Further reading
  1. How to Make a Multiprocessor That Correctly Executes Multiprocess Programs. Leslie Lamport. IEEE Trans. on Computers, Vol. C-28, Number 9, pp. 690-691, September 1979.

  2. J. E. THORNTON "Parallel Operation in the Control Data 6600," Fall Joint Computers Conference, vol. 26, pp. 33-40, 1961.

  3. G. MOORE, "Cramming More Components onto Integrated Circuits", Electronics, p114-117, April 1965.

  4. G. M. AMDAHL, "Validity of the Single-Processor Approach to Achieving Large Scale Computing Capabilities", AFIPS Conference Proceedings, (April 1967), 483-485.