1. Data-parallel

1. Mapping of Work
2. static
3. Tasks -> Processes
4. Mapping of Data
5. Independent data items assigned to processes (Data Parallelism)
6. Computation
7. Tasks process data, synchronize to get new data or exchange results, continue until all data processed
8. Load Balancing
9. Uniform partitioning of data
10. Synchronizaion
11. Minimal or barrier needed at end of a phase

EX: Ray Tracing

2. Task graph

1. Mapping of Work
2. static
3. Tasks are mapped to nodes in a data dependency task dependency graph (Task parallelism)
4. Mapping of Data
5. Data moves throught graph
6. Computation
7. Each node processes input from previous node(s) and send output to next node(s) in the graph
8. Load Balancing
9. Assign more processes to a given task
10. Eliminate graph bottlenecks
11. Synchronizaion
12. Node data exchange

EX: Parallel Quicksort, Divide and Conquer approaches

3. Work pool

1. Mapping of Work/Data
2. No desired pre-mapping
3. Any task performed by any process
4. Computation
5. Processes work as data becomes available (or requests arrive)
6. Load Balancing
7. Dynamic mapping of tasks to processes
8. Synchronization
9. Adding/removing work from input queue

EX:Web Server

4. Master-slave

1. Modification to Worker Pool Model
2. One or more Master processes generate and assign work to worker processes
3. Load Balancing
4. A Master process can better distribute load to worker processes

5. Pipeline

1. Mapping of work
2. Processes are assigned tasks that correspond to stages in the pipeline
3. Static
4. Mapping of Data
5. Data processed in FIFO order
6. Stream parallelism
7. Computation
8. Data is passed through a succession of processes, each of which will perform some task on it
9. Load Balancing
10. Insure all stages of the pipeline are balanced (contain the same amount of work)
11. Synchronization
12. Producer/Consumer buffers between stages

Ex: Processor pipeline, graphics pipeline

6. Hybrid

Reference

• Google Code University - Distributed Systems

发表评论