MODULE 3 Flashcards
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
