Notes from Lecture 5: Principles of Further Awareness Design (Part 2)

Introduction

• Focus on exploratory and speculative decomposition methods in problem-solving.
• Relation between decomposition techniques and problem-solving methods.

Exploratory Decomposition

• Involves exploring the state space of a solution.
• Problems often require generating various successors from the current state.
• It can change the amount of work done based on the problem context.
• Example: 15 puzzle problem involving a sequence of moves.

Speculative Decomposition

• Applicable in scenarios where tasks are known a priori and can be identified independently.
• This approach can be conservative (optimistic) or optimistic with a rollback mechanism for error handling.
• Used in discrete event simulations where events occur based on time order.
• Example: Behavior simulation of computer networks through packet assembly.

Hybrid Decomposition

• Combines multiple decomposition techniques for efficiency in handling tasks.
• Characteristics of tasks impact algorithm effectiveness and data handling.

Task Generation

Static Task Generation

• Tasks are predefined based on priority.
• Examples include max operations, matrix operations, and graph algorithms.

Dynamic Task Generation

• Tasks generated during computation, like in game playing or puzzle solving.
• The required size of state space can vary based on context.

Task Interaction

Static Interaction

• Tasks interact independently, e.g., pixel processing.

Dynamic Interaction

• More complex as interactions cannot be predetermined.
• Requires careful coding due to potential dependencies.

Overhead Minimization

• Primary overhead comes from communication and idling.
• Balancing load among processors is crucial to minimize overhead.

Dynamic Mapping Strategies

Centralized Mapping

• One process acts as the master to distribute tasks.
• Slave processes request more work from the master.

Distributed Mapping

• Processes can send and receive work from each other.
• Helps in load balancing and reduces idle time.

Data Partitioning and Task Graph Partitioning

• Techniques to divide computations efficiently across processors.
• Block distribution and block cyclic are strategies to handle data distribution.

Conclusion

• Understanding decomposition and mapping techniques is essential for parallel algorithm design.
• Exercises are assigned for practical application of concepts learned.