Lecture 4: Principles of Parallel Algorithm Design
Lecture 4: Principles of Parallel Algorithm Design
1
Constructing a Parallel Algorithm
? identify portions of work that can be performed concurrently
? map concurrent portions of work onto multiple processes running in parallel
? distribute a program's input, output, and intermediate data
? manage accesses to shared data: avoid conflicts ? synchronize the processes at stages of the
parallel program execution
2
Task Decomposition and Dependency Graphs
Decomposition: divide a computation into smaller parts, which can be executed concurrently Task: programmer-defined units of computation.
Task-dependency graph: Node represent s task. Directed edge represents control dependence.
3
Example 1: Dense Matrix-Vector Multiplication
? Computing y[i] only use ith row of A and b ? treat computing y[i] as a task.
? Remark:
? Task size is uniform ? No dependence between tasks ? All tasks need b
4
Example 2: Database Query Processing
? Executing the query: Model ="civic" AND Year = "2001" AND (Color = "green" OR Color = "white") on the following database:
5
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- task scheduling in parallel processing analysis
- lecture 4 principles of parallel algorithm design
- parallelism in c
- concurrency and parallelism with c 17 and c 20 23
- suck it dry tuning parallel execution
- parallel computing
- parallel algorithm development for a specific
- d functions of individual elements are
- definition of parallel computer a collection of
- computer parallel
Related searches
- principles of management lecture notes
- principles of marketing lecture notes
- 4 principles of ethics
- principles of accounting lecture notes
- impedance of parallel rlc
- voltage of parallel circuit
- 4 principles of healthcare ethics
- 4 principles of medical ethics
- calculate ampacity of parallel conductors
- 4 principles of orm
- equations of parallel planes
- verilog synthesis of parallel if statements