Routing and sorting on circular arrays
Jop F. Sibeyn · Max Planck Digital Library · 1993
We analyze routing and sorting problems on circular processor arrays with bidirectional connections. We assume that initially and finally each PU holds k 1 packets. On linear processor arrays the routing and sorting problem can easily be solved for any k, but for the circular array it is not obvious how to exploit the wrap-around connection. We show that on an array with n PUs k-k routing, k 4, can be performed optimally in k \\Delta n=4+ p n steps by a deterministical algorithm. For k = 1, the routing problem is trivial. For k = 2 and k = 3, we prove lower-bounds and show that these (almost) can be matched. A very simple algorithm has good performance for dynamic routing problems. For the k-k sorting problem we use a powerful algorithm which also can be used for sorting on higher-dimensional tori and meshes. For the ring the routing time is maxfn; k \\Delta n=4g +O((k \\Delta n) 2=3 ) steps. For large k we take the computation time into account and show that for n = o(log...