Abstract:
Efficient routing of messages is critical to the performance of multicomputers.
Many adaptive routing algorithms have been proposed to improve the network
efficiency; however, they can make only short-sighted decisions to choose a channel
for message routing because of limited information about network condition. The
short-sighted decisions may cause unnecessary waits at the next clock cycle if the
adaptive routing algorithm chooses a channel which has high probability of message
block at the next clock cycle.
In this thesis, look-ahead routing scheme is introduced to provide better
performance for conventional adaptive routing algorithms. The look-ahead scheme
as an adaptive routing algorithm makes longer-sighted decision to avoid possible
blocks at the next clock cycle.
This thesis also simulates the XY, the West-First, and the Double-Y channel
routing algorithms, which are deterministic, partially-adaptive and fully-adaptive,
respectively, in a 16 x 16 mesh network. Their performances are compared and
analyzed. The simulation includes the examination of look-ahead effect for the
West-First and the Double-Y channel routing algorithms.
