Permutation Routing on Reconfigurable Meshes

Permutation Routing on Reconfigurable Meshes

0.00 Avg rating0 Votes
Article ID: iaor20121051
Volume: 31
Issue: 1
Start Page Number: 44
End Page Number: 57
Publication Date: Sep 2001
Journal: Algorithmica
Authors: ,
Keywords: combinatorial optimization
Abstract:

In this paper we present efficient algorithms for packet routing on the reconfigurable linear array and the reconfigurable two‐dimensional mesh. We introduce algorithms that are efficient in the worst case and algorithms that are better on average. The time bounds presented are better than those achievable on the conventional mesh and previously known algorithms. We present two variants of the reconfigurable mesh. In the first model, M r , the processors are attached to a reconfigurable bus, the individual edge connections being bidirectional. In the second model, M mr , the processors are attached to two unidirectional buses. In this paper we present lower bounds and nearly matching upper bounds for packet routing on these two models. As a consequence, we solve two of the open problems mentioned in [9].

Reviews

Required fields are marked *. Your email address will not be published.