next up previous
Next: Layout of Local Process Up: Mapping Logical Memory to Previous: Mapping Logical Memory to

Assignment of Processes to Processors

  Consider, first, the assignment of processes, (p,q), to physical processors. In general, more than one process may be assigned to a processor, so the problem may be overdecomposed. To avoid load imbalance the same number of processes should be assigned to each processor as nearly as possible. If this condition is satisfied, the assignment of processes to processors can still affect performance by influencing the communication overhead. On recent distributed memory machines, such as the Intel Delta and CM-5, the time to send a single message between two processors is largely independent of their physical location [27, 42, 43], and hence the assignment of processes to processors does not have much direct effect on performance. However, when a collective communication task, such as a broadcast, is being done, contention for physical resources can degrade performance. Thus, the way in which processes are assigned to processors can affect performance if some assignments result in differing amounts of contention. Logarithmic contention-free broadcast algorithms have been developed for processors connected as a two-dimensional mesh [6, 45], so on such machines process (p,q) is usually mapped to the processor at position (p,q) in the mesh of processors. Such an assignment also ensures that the multiple one-dimensional broadcasts of tex2html_wrap_inline2001 and tex2html_wrap_inline2419 along the rows and columns of the template, respectively, do not give rise to contention.

Jack Dongarra
Sun Feb 9 10:05:05 EST 1997