Hypersphere Mapper: A Nonlinear Programming Approach to the Hypercube Embedding Problem

✍ Scribed by J.K. Antonio; R.C. Metzger

• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 667 KB
• Volume: 19
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1993.1110

✦ Synopsis

A nonlinear programming approach is introduced for solving the hypercube embedding problem. The basic idea of the proposed approach is to approximate the discrete space of an (n)-dimensional hypercube, i.e., (\left{z: z \in{0,1}^{n}\right}), with the continuous space of an (n)-dimensional hypersphere, i.e., (\left{x: x \in \mathscr{R}^{n} &|x|^{2}=1\right}). The mapping problem is initially solved in the continuous domain by employing the gradient projection technique to a continuously differentiable objective function. The optimal process "locations" from the solution of the continuous hypersphere mapping problem are then discretized onto the (n)-dimensional hypercube. The proposed approach can solve, directly, the problem of mapping (P) processes onto (N) nodes for the general case where (P>N). In contrast, competing embedding heuristics from the literature can produce only one-to-one mappings and cannot, therefore, be directly applied when (P>N). O 1993 Academic Press, Inc.