Back to Search
Start Over
Optimum simulation of meshes by small hypercubes
- 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