This paper presents a constant slow-down, optimal and locally normal simulation for basic reconfigurable meshes on hypercubes, if the log-time delay model for broadcasting is assumed. Such a simulation algorithm is based on: (i) an O(log B) time algorithm for the segmented scan problem on a (2n-1)-node toroidal X-tree, where B is the size of the longest segment; this algorithm is time optimal; (ii) a constant slow-down optimal and locally normal simulation algorithm for basic reconfigurable meshes on the mesh of toroidal X-trees; and (iii) a constant slow-down optimal simulation of locally normal algorithms for meshes of toroidal X-trees on the hypercube.

Time and work optimal simulation of reconfigurable meshes on hypercubes / BERTOSSI A.; A. MEI. - In: JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING. - ISSN 0743-7315. - STAMPA. - 64:(2004), pp. 173-180. [10.1016/S0743-7315(03)0118-7]

Time and work optimal simulation of reconfigurable meshes on hypercubes

BERTOSSI, ALAN ALBERT;
2004

Abstract

This paper presents a constant slow-down, optimal and locally normal simulation for basic reconfigurable meshes on hypercubes, if the log-time delay model for broadcasting is assumed. Such a simulation algorithm is based on: (i) an O(log B) time algorithm for the segmented scan problem on a (2n-1)-node toroidal X-tree, where B is the size of the longest segment; this algorithm is time optimal; (ii) a constant slow-down optimal and locally normal simulation algorithm for basic reconfigurable meshes on the mesh of toroidal X-trees; and (iii) a constant slow-down optimal simulation of locally normal algorithms for meshes of toroidal X-trees on the hypercube.
2004
Time and work optimal simulation of reconfigurable meshes on hypercubes / BERTOSSI A.; A. MEI. - In: JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING. - ISSN 0743-7315. - STAMPA. - 64:(2004), pp. 173-180. [10.1016/S0743-7315(03)0118-7]
BERTOSSI A.; A. MEI
File in questo prodotto:
Eventuali allegati, non sono esposti

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/11585/854
 Attenzione

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

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact