- 海之寻趣
- Ranler
- 2012-06-02 16:43
- CC BY-NC-SA
Goals
The goals of parallel programming:
- Performance
- Productivity
- Generality
Parallelism is but one way to improve performance. Other well-known approaches include following, in roughly increasing order of difficulty:
- Run multiple instances of a sequential application
- Construct the application to make use of existing parallel software
- Apply performance optimization to the serial application
What makes parallel programming hard?
- Work Partitioning
- load balancing
- handle global errors and events
- communication between processes or threads
- control the number of concurrent threads
- extremely large state space, but nevertheless be easy to understand
-
embarrassingly parallel
-
Parallel Access Control
- whether the form of the access to a given resource depends on that resource's location
-
synchronization mechanisms when threads access to the resources, including message passing, locking,transactions,reference counting, explicit timing,shared atomic variables and data ownership.
-
Resource Partitioning and Replication
- partition write-intensive resources
-
replicate frequently accessed read-mostly resources
-
Interacting With Hardware
-
need to work directly with hardware
-
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.