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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.