Back to Search Start Over

Optimum simulation of meshes by small hypercubes

Authors :
Ivan Hal Sudborough
Bin Cong
Zevi Miller
Source :
Aspects and Prospects of Theoretical Computer Science ISBN: 9783540534143, IMYCS
Publication Year :
1990
Publisher :
Springer Berlin Heidelberg, 1990.

Abstract

We consider optimum simulations of large mesh networks by hypercubes. For any arbitrary mesh M, let "M's optimum hypercube" be the smallest hypercube that has at least as many processors as M and, for any k>0, let Q(M/2k) be "M's 1/2k-size hypercube", which has 1/2k as many processors as M's optimum hypercube. The ratio MI/Q(M/2k) is called M's 1/2 k - density. We show that (a) for every 2-D mesh M, if M's 1/2-density≤1.828, then M can be embedded into its 1/2-size hypercube with dilation 1 and load factor 2, (b) for every 2-D mesh M, if M's 1/4-density≤3.809, then M can be embedded into its 1/4-size hypercube with dilation 1 and load factor 4, and if M's 1/4-density≤2.8125, then M can be embedded into its 1/4-size hypercube with dilation 1 and load factor 3, (c) If every 2-D mesh M with 1/2k1-density≤a can be embedded into its 1/2k1-size hypercube with dilation 1 and load factor l1, and every 2-D mesh M with 1/2k2-density ≤b can be embedded into its 1/2k2-size hypercube with dilation 1 and load factor l2, then we can obtain the densities for load factor l1+l2 and load factor l1×l2 based on a, b.

Details

ISBN :
978-3-540-53414-3
ISBNs :
9783540534143
Database :
OpenAIRE
Journal :
Aspects and Prospects of Theoretical Computer Science ISBN: 9783540534143, IMYCS
Accession number :
edsair.doi...........2073b205870662f6b1490cfaf641ee0f
Full Text :
https://doi.org/10.1007/3-540-53414-8_28