Mapping and scheduling of concurrent communication traffic in multicomputer networks.
Bing-Rung Tsai · Deep Blue (University of Michigan) · 1994
In a multicomputer network, each task is decomposed into modules which are then executed by a number of processing nodes. During the execution, bursty concurrent communication traffic among processor nodes can lead to network congestion and become a bottleneck. Our goal is to improve the system communication performance in such a situation using on-line traffic flow-control mechanisms, and develop task mapping strategies with sufficient task behavior information prior to the execution. Flow-control mechanisms include message routing algorithms, message scheduling policies, and in the case of virtual channel networks, time-division multiplexing methods. For on-line applications, we propose low-complexity distributed mechanisms to be implemented on each node. Using simulations, we show that effective mechanisms can improve network performance significantly. Without proper flow-control mechanisms, adding communication resources such as links and buffers can actually degrade the network performance. Also, under heavy concurrent traffic, a low-complexity routing algorithm, when combined with a good message scheduling policy, can outperform a much more complex routing algorithm and achieve near-optimal performance. Before their execution, if the task communication behavior can be predicted (with a certain degree of accuracy), task modules can be mapped to processor nodes strategically to exploit their communication locality and thus improve the run-time performance. However, due to the complex interactions among these modules, the performance objective can be very difficult to formulate, making direct optimization impossible. Thus, we propose simple cost functions so that when mappings are optimized with respect to these functions, the actual performance objectives are also optimized. For this purpose, various heuristic algorithms are developed and tested through analytical modeling and simulations. Several cost functions are studied and a few of them found to be very effective when used with appropriate algorithms. For binary hypercubes, we also extend our study to the problem of mapping concurrently communicating subcubes. We show that the optimization process can be simplified and existing algorithms can be easily adapted for this application.