Communication overhead is the time or resource cost of exchanging data between processors or concurrent tasks. Like workers coordinating while shoveling snow, tasks can lose performance while waiting for information. section 13.6
Reduce communication overhead by changing how work is organized:
- Increase locality by combining tasks that exchange data, making their communication part of one task. section 13.6
- Group tasks that send data and tasks that receive data, reducing waiting even when transmission time stays the same. section 13.6
- Balance simplicity against performance: fewer, larger tasks can communicate less but may complicate the design. section 13.6
Partitioned matrix multiplication
A fine-grained matrix multiplication assigns one task to each output element, requiring each subtask to receive a row of matrix A and a column of matrix B. Sharing matrices between threads can make this arrangement effective on SIMD computers, but its communication pattern affects performance. section 13.6
