并行计算(4):并行算法模型
目录

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

支持牛逼冉 于 2012-06-02 16:33 时评论:
支持牛逼冉

发表评论