Expressions for communication complexity can range from very simple, e.g. all communication requires the same amount of time (a reasonable model in some cases for a shared memory system), to very complex, as would be required for an accurate model of a distributed memory system that communicates by message passing. In the former case, the number of accesses to memory times the average access time might suffice. In the latter case, a more complex analysis is necessary for an accurate model. For example, the time to send a message from processor i to processor j in a packet switched network is often modeled by an expression such as
where a is the overhead in setting up the message in the sending processor (and, if necessary, storing a message in the receiving processor), b is the distance from i to j, and is the length of the message in packets. Again, this simple formula hides many additional complexities that might or might not effect performance: the existence of a separate processor at each processing node to handle messages, contention at links or nodes, whether or the routing is fixed or dynamic, etc.
The overhead for synchronization can also involve a number of issues depending on the algorithm and the type of synchronization mechanism used. For example, an SIMD system automatically synchronizes parallel subtasks and no further modeling is required. For MIMD systems, in addition to the overhead associated with the actual synchronization process, there is also the idle time created when processors wait at a synchronization point. A thorough discussion of synchronization mechanisms may be found in Andrews and Schneider . The development of a complexity model involving all three of the above factors in great detail may be found in Reed and Patrick . A general discussion of many of the issues relative to linear algebra algorithms may be found in Ortega .