Efficient Deadlock-Free Multi-dimensional Interval Routing in Interconnection Networks

摘要

We present deadlock-free packet (wormhole) routing algorithms based on multi-dimensional interval schemes for certain multiprocessor interconnection networks and give their analysis in terms of the compactness and the size (the maximum number of buffers per node (per link)). The issue of a simultaneous reduction of the compactness and the size is fundamental, worth to investigate and of practical importance, as interval routing and wormhole routing have been realized in INMOS Transputer C104 Router chips.