Time and work optimal simulation of basic reconfigurable meshes on hypercubes

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 <f>O(log B)</f> time algorithm for the segmented scan problem on a <f>(2n−1)</f>-node toroidal X-tree, where <f>B</f> 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. [Copyright &y& Elsevier]