DESIGNING PARALLEL PROGRAMS (2)

PARTITIONING@ DECOMPOSITION

• breaking the problem into discrete 'chunks' that can be distributed to multiple tasks

• two types: 

• DOMAIN DECOMPOSITION
• data is decomposed
• each parallel tasks then works on their portion of data

• FUNCTIONAL DECOMPOSITION

• - focuses on the computation that is to be performed
• the problem is decomposed according to the work that must be done
• each task performs a portion of the overall work

COMMUNICATION

• cost of communication
• inter-task communication always implies overhead
• communication between task typically requires synchronization between tasks, which results in time spent 'waiting' rather than doing work
• latency vs. bandwidth
• latency : time taken to send minimal message (0 bytes) across two points. Expressed in microseconds.
• bandwidth: the amount of data transferred over time (Mbps or Gbps)
• concept : package small messages into large message to increase the effective communication of bandwidth
• scope of communication
• point to point
• collective

LOAD BALANCING

• distributing work evenly among all tasks so that all tasks are kept busy ALL THE TIME
• minimization of task idle time
• Achieving LOAD BALANCE
• equally partitioning the work each task receives
• for array/matrix operations (each task performs similar work) : evenly distribute data set among tasks
• for loop iterations (similar work is done in each iteration) : evenly distribute iteration across tasks
• dynamic work assignment
• certain classes of problems result in load imbalances even if data is evenly distributed
• sparse array: some tasks have actual data to work on while others mostly have 'zero's
• adaptive grid method: some tasks may need to refine their mesh while others don't
• when the amount of work each task does is intentionally variable, it is better to use scheduler-class-pool
• scheduler task pool: after each task finishes its work, it is lined up for another task 

BY LUA XIN LIN B031210345