We propose and evaluate low-complexity, low-overhead schemes for distributed message scheduling and routing in binary hypercube multicomputers equipped with a hardware communication adapter at each node. The goal is to optimize the network performance not only for steady traffic flow, but also for concurrent bursty traffic. We comparatively evaluate the performance of different scheduling-coding combinations for several switching methods, such as message switching, circuit switching and virtual cut-through. The evaluation results have indicated that in case of heavy transient traffic, a partially-adaptive routing scheme, when combined with an appropriate message-scheduling policy, can outperform a fully-adaptive routing scheme.

It is difficult to define and evaluate a meaningful performance metric when many packets are generated and exchanged concurrently in mesh-connected multicomputers equipped with wormhole switching and virtual channels. Thus, an approximate metric/cost function must be chosen so that when, task modules are mapped by optimizing this function, the actual performance of the mapping is also optimized. Several low-complexity cost functions are evaluated using the simulated annealing optimization process. The mappings found by optimizing these cost functions are then fed into a flit-level simulator to evaluate their actual performance. One particular cost function is found to be very effective.

Under the fixed-path e-cube routing in mesh multicomputers, we evaluate the performance of several low-overhead packet sequencing and flit multiplexing methods. In the presence of concurrent inter-node communication traffic, we found that unless proper packet sequencing is employed, adding more communication resources, such as links and buffers, can actually degrade the network performance. A good packet-sequencing policy combined with proper flit multiplexing is shown to improve performance by more than 30%.

The problem of assigning task modules within a hypercube multicomputer with possible link failures is investigated. A concept of indirect optimization is introduced and a function, called communication traffic, is proposed as the objective of optimization. The assignments obtained from optimizing this function are shown to significantly improve the actual communication performance measure, called communication turnaround time, over random assignments.>

The problem of mapping a task that is composed of interacting modules onto a hypercube multicomputer is formulated and solved by minimizing an objective function called the communication traffic. The objective function allows module assignments to be found with the usual straightforward combinatorial optimization techniques. The problem of finding an assignment that minimizes the communication traffic is proved to be NP-hard, so a standard state-space search algorithm as well as other heuristic algorithms are used to find optimal/suboptimal solutions. The relative performances of various algorithms are evaluated using simulations. The assignments obtained from these algorithms are evaluated using an event-driven simulator to learn how they perform in real-world execution environments.>