Routing with locality in partitioned-bus meshes
S. Cheung, Francis C. M. Lau · 2002
We show that adding partitioned-buses (as opposed to long buses that span an entire row or column) to ordinary meshes can reduce the routing time by approximately one-third for permutation routing with locality. A matching time lower bound is also proved. The result can be generalized to multi-packet routing.>