并行计算(2):计算模型
目录

Goals


The goals of parallel programming:

  1. Performance
  2. Productivity
  3. Generality

Parallelism is but one way to improve performance. Other well-known approaches include following, in roughly increasing order of difficulty:

  1. Run multiple instances of a sequential application
  2. Construct the application to make use of existing parallel software
  3. Apply performance optimization to the serial application

What makes parallel programming hard?


  1. Work Partitioning
  2. load balancing
  3. handle global errors and events
  4. communication between processes or threads
  5. control the number of concurrent threads
  6. extremely large state space, but nevertheless be easy to understand
  7. embarrassingly parallel

  8. Parallel Access Control

  9. whether the form of the access to a given resource depends on that resource's location
  10. synchronization mechanisms when threads access to the resources, including message passing, locking,transactions,reference counting, explicit timing,shared atomic variables and data ownership.

  11. Resource Partitioning and Replication

  12. partition write-intensive resources
  13. replicate frequently accessed read-mostly resources

  14. Interacting With Hardware

  15. need to work directly with hardware

  16. Composite Capabilities

Parallelism Challenges[Google]

  • Identifying work that can be done concurrently.
  • Mapping work to processing units.
  • Distributing the work
  • Managing access to shared data
  • Synchronizing various stages of execution.

Parallel Programming Pitfalls[Google]

  • Synchronization
  • Deadlock
  • Livelock
  • Fairness
  • Efficiency
  • Maximize parallelism
  • Reliability
  • Correctness
  • Debugging

Common Parallel Programming Models


1. Shared address space

  • Mostly used for programming SMP machines (multicore chips)
  • Key attributes
  • Shared address space
  • Threads
  • Shmget/shmat UNIX operations
  • Implicit parallelization
  • Process/Thread communication
  • Memory reads/stores
  • Shared Address Space
  • Communication
  • Read/write memory
  • Posix Thread API
  • Popular thread API
  • Operations
  • Creation/deletion of threads
  • Synchronization (mutexes, semaphores)
  • Thread management

2. Message passing

  • Most widely used for programming parallel computers (clusters of workstations)
  • Key attributes:
  • Partitioned address space
  • Explicit parallelization
  • Process interactions
  • Send and receive data
  • Communications
  • Sending and receiving messages
  • Primitives
  • send(buff, size, destination)
  • receive(buff, size, source)
  • Blocking vs non-blocking
  • Buffered vs non-buffered
  • Message Passing Interface (MPI)
  • Popular message passing library
  • ~125 functions

Popular parallel programming environments


  • C/C++, Locking Plus Threads: This includes POSIX Threads(pthreads), Windows Threads and so on, has an excellent performance on a single SMP.

  • Java: inherently multi-threaded environment, RPC,RMI

  • MPI, Message Passing Interface: used for largest scientific and technical computing clusters, multi-process based, distributed memory, (SMP,DSM,Cluster)

  • OpenMP: compiler directives , multi-thread based, shared memory, (SMP,DSM)

  • MapReduce: distributed memory, data-parallel, Automates data distribution & result aggregation (Cluster)

  • TBB: Threading Building Blocks

Some General Parallel Terminology


Massively Parallel: Refers to the hardware that comprises a given parallel system - having many processes. The meaning of "many" keep in increasing, but currently, the largest parallel computers can be comprised of processors in the hundreds of thousands.

Embarrassingly Parallel: Solving many similar, but independent task simultaneously; little to no need for coordination between the tasks.

参考

发表评论