Task-Level Parallelism: Creating TasksPartition a single problem into multiple related tasks(threads)-Explicitly:Parallelprogramming·EasywhentasksarenaturalintheproblemWeb/databasequeries. Difficult when natural task boundaries are unclear-Transparently/implicitly: Thread level speculation. Partition a single thread speculatively: Run many independent tasks (processes) together- Easy when there are many processes·Batch simulations, different users,cloud computing workloads- Does not improve the performance of a single taskComputerArchitecture
Computer Architecture Task-Level Parallelism: Creating Tasks • Partition a single problem into multiple related tasks (threads) – Explicitly: Parallel programming • Easy when tasks are natural in the problem – Web/database queries • Difficult when natural task boundaries are unclear – Transparently/implicitly: Thread level speculation • Partition a single thread speculatively • Run many independent tasks (processes) together – Easy when there are many processes • Batch simulations, different users, cloud computing workloads – Does not improve the performance of a single task 6
Multiprocessing FundamentalsComputerArchitecture
Computer Architecture Multiprocessing Fundamentals 7
Multiprocessor Types. Loosely coupled multiprocessors- No shared global memory address space-Multicomputernetwork:Network-basedmultiprocessors-Usuallyprogrammedviamessagepassing. Explicit calls (send, receive) for communicationTightly coupled multiprocessors- Shared global memory address space- Traditional multiprocessing: symmetric multiprocessing (SMP):Existingmulti-coreprocessors,multithreadedprocessors- Programming model similar to uniprocessors (i.e.,multitasking uniprocessor)exceptOperations on shared data require synchronizationComputerArchitecture
Computer Architecture Multiprocessor Types • Loosely coupled multiprocessors – No shared global memory address space – Multicomputer network • Network-based multiprocessors – Usually programmed via message passing • Explicit calls (send, receive) for communication • Tightly coupled multiprocessors – Shared global memory address space – Traditional multiprocessing: symmetric multiprocessing (SMP) • Existing multi-core processors, multithreaded processors – Programming model similar to uniprocessors (i.e., multitasking uniprocessor) except • Operations on shared data require synchronization 8
Main Issues in Tightly-Coupled MP. Shared memory synchronization- Locks,atomic operationsCacheconsistency-MorecommonlycalledcachecoherenceOrdering of memory operations- What should the programmer expect the hardware to provide?Resource sharing, contention, partitioning Communication: Interconnection networksLoad imbalanceComputerArchitecture
Computer Architecture Main Issues in Tightly-Coupled MP • Shared memory synchronization – Locks, atomic operations • Cache consistency – More commonly called cache coherence • Ordering of memory operations – What should the programmer expect the hardware to provide? • Resource sharing, contention, partitioning • Communication: Interconnection networks • Load imbalance 9
Aside: Hardware-based Multithreading· Coarse grained-Quantumbased- Event based (switch-on-event multithreading)· Fine grained- Cycleby cycle- Thornton, "CDC 6600: Design of a Computer," 1970.- Burton Smith, “A pipelined, shared resource MIMD computer," ICPP1978..Simultaneous Can dispatch instructions from multiple threads at the same time-Goodfor improving execution unit utilizationComputerArchitecture10
Computer Architecture Aside: Hardware-based Multithreading • Coarse grained – Quantum based – Event based (switch-on-event multithreading) • Fine grained – Cycle by cycle – Thornton, “CDC 6600: Design of a Computer, ” 1970. – Burton Smith, “A pipelined, shared resource MIMD computer, ” ICPP 1978. • Simultaneous – Can dispatch instructions from multiple threads at the same time – Good for improving execution unit utilization 10