Efficient Algorithms for Checking the Equivalence of Multistage Interconnection Networks
In this paper we study the topological equivalence problem of
multistage interconnection networks (MINs).
We prove a new characterization of topologically equivalent MINs by
means of a novel approach.
Applying this characterization to log N stage MINs we completely
describe the
equivalence class which the Reverse Baseline belongs to.
Most important, we apply the characterization to (2 log N -1) stage
MINs obtained as concatenation of
two log N stage Reverse Baseline equivalent MINs: in this way, we deduce an
O(N log N) time algorithm testing the equivalence of two such MINs.
This result substantially improves the time complexity of the
previously known algorithms (O(N^{4} log N)).
Finally, we determine the number of different equivalence classes of (2
log N -1) stage MINs and we characterize each of them.
PDF Files
Journal
Version
Conference
Version