TY - JOUR AU - Královič, Rastislav AU - Rovan, Branislav AU - Ružička, Peter AU - Štefankovič, Daniel PY - 2012/02/21 Y2 - 2024/03/28 TI - Efficient deadlock-free multidimensional interval routing in hypercube-like networks JF - COMPUTING AND INFORMATICS JA - Comput. Inform. VL - 21 IS - 3 SE - Articles DO - UR - https://www.cai.sk/ojs/index.php/cai/article/view/498 SP - 265-287 AB - We present deadlock-free packet/wormhole routing algorithms ba\-sed on multidimensional interval schemes for certain hypercube related multiprocessor interconnection networks and give their analysis in terms of the compactness (i.e.~the maximum number of intervals per link) and the buffer-size (i.e.~the ma\-xi\-mum number of buffers per node/link). The issue of a simultaneous reduction of the compactness and the buffer-size is fundamental, worth to investigate and of practical importance, since the interval routing and wormhole routing have been industrially realized in INMOS Transputer C104 Router chips. <br />In this paper we give an evidence that for some well-known interconnection networks there are efficient deadlock-free multidimensional interval routing schemes (DFMIRS) despite of a provable non-existence of efficient deterministic shortest path interval routing schemes (IRS). For $d$-dimensional hypercubes (tori) we present a $d$-dimensional DFMIRS of compactness $1$ and size $2$ (of compactness $1$ and size $4$), while for shortest path IRS we can achieve the reduction to $2$ (to at most $5$) buffers per node with compactness $2^{d-1}$ (with compactness $O(n^{d-1})$). For $d$-dimensional generalized butterflies we give a $d$-dimensional DFMIRS with compactness $2$ and size $3$, while each shortest path IRS is of the compactness at least superpolynomial in $d$. For $d$-dimensional cube-connected cycles we show a $d$-dimensional DFMIRS with compactness and size polynomial in $d$, while each shortest path IRS needs compactness at least $2^{d/2}$. <br />We also present a nonconstant lower bound (in the form $\sqrt{d}$) on the size of deadlock-free packet routing (based on acyclic orientation covering) for a set of monotone routing paths on $d$-dimensional hypercubes. ER -