The model we present assumes that processors pass messages to each other via a communications network. In this model, a processor sending a message incurs overhead costs for startup such as preparing a message for transmission, alerting the destination processor that it will receive this message, and handling the destination's acknowledgment. We call this time .

The sending processor partitions the outgoing message into sections of length bits, determined by hardware constraints. Each packet, with routing information prepended and an integrity check field using a cyclic redundancy code appended, is sent through the data network. The destination processor then reassembles the complete message from the received packets.

The communications time to send a message with this model is

where is the message length, and is the transmission rate of the source into the network measured in seconds per packet.

Fortunately, all the algorithms described in this paper use regular
communication patterns whose complexities can be easily estimated on
the two architectures of the CM-2 and of the CM-5. Each such
communication pattern can be expressed as a constant number of *
block permutations*, where given blocks of contiguous data, , residing in processors , and a permutation , block has to be sent from processor
to , where each block is of the same size, say
. As we illustrate next, on both the CM-2 and
the CM-5, the communication complexity of a regular block permutation
can be expressed as follows:

where is the start-up cost and is the packet transmission rate. We next address how to estimate the communication complexity for operations on images and their relationship to block permutations.

David A. Bader

dbader@umiacs.umd.edu