Task dependency graph:
DAG with nodes being tasks and edges being dependencies
Steps in the parallelization:
- Decomposition
- Assignment
- Orchestrating
- Mapping
Granularity of decomposition:
- Fine grain
- Coarse grain
Fine grain:
Each task computes a single element, lots of tasks
Possible decompositions into tasks:
- Independent or dependent
- Same code or different
- Same time or different
Coarse grain:
Each task computes multiple elements, little tasks
Decomposition techniques:
- Exploratory
- Speculative
Speculative decomposition approaches:
- Conservative
- Optimistic
Speculative decomposition optimistic approach:
Scheduling tasks even if thy might be dependent and just rolling back if there’s an error
Speculative decomposition conservative approach:
Identifying independent tasks only when they’re guaranteed to not have dependencies
Characteristics of tasks:
- Task generation
- Task size
- Data size
Task sizes:
- Uniform
- Non-uniform
Task size:
Amount of work and time a task takes
Data size examples with the input, output, and computation size:
- Puzzle: Input < Comp
- Min: Output < Input = Comp
- Sort: Input = Output < Comp
Characteristics of task interactions:
- Data and size
- Timing
- Pattern
- Known or unknown details
- Involvement
Orthogonal classification of tasks:
- Static vs dynamic
- Regular vs irregular
- Read-only vs read-write
- One-sided vs two-sided
Goal of mapping:
- Minimize overheads (cost of parallelization)
- Balance interactions and idling (serialization)
Factors that determine the mapping technique:
- Data size
- Interactions
- Programming models
Execution:
Alternating computation and interaction
Schemes for static mapping:
- Based on decomposition
- Based on partitioning
- Hybrid
Hypercube:
N-dimensional analogue of a square and a cube where adjacent nodes differ in 1 bit
Hierarchical mapping:
Task graph mapping at the top level and data partitioning in each level
Schemes for dynamic mapping:
- Centralized
- Distributed
Chunk scheduling:
A process picks up multiple tasks at once
