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. (C) 2003 Elsevier Inc. All rights reserved.

Efficient algorithms for checking the equivalence of multistage interconnection networks / Calamoneri, Tiziana; Massini, Annalisa. - In: JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING. - ISSN 0743-7315. - STAMPA. - 64:1(2004), pp. 135-150. [10.1016/j.jpdc.2003.09.003]

Efficient algorithms for checking the equivalence of multistage interconnection networks

CALAMONERI, Tiziana;MASSINI, Annalisa
2004

Abstract

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. (C) 2003 Elsevier Inc. All rights reserved.
2004
layered cross product; layered graphs; multistage interconnection networks; topological equivalence
01 Pubblicazione su rivista::01a Articolo in rivista
Efficient algorithms for checking the equivalence of multistage interconnection networks / Calamoneri, Tiziana; Massini, Annalisa. - In: JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING. - ISSN 0743-7315. - STAMPA. - 64:1(2004), pp. 135-150. [10.1016/j.jpdc.2003.09.003]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/235145
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 4
social impact