Embedding Large Complete Binary Trees in Hypercubes with Load Balancing

✍ Scribed by Kemal Efe

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 211 KB
• Volume: 35
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1996.0073

✦ Synopsis

In the next section we present basic definitions and notations where the criterion of optimality is defined and related to the concept of ''normal'' algorithms. In Section 3 we present an optimal embedding method that balances the processor loads. In Section 4 we present a nonoptimal embedding method which has the advantage of simplicity.

In Section 5 we present our concluding remarks.

2. DEFINITIONS AND MOTIVATIONS

Emulation of a ''guest'' graph G by a ''host'' graph H means performance of the steps of an algorithm developed for the guest on the processors of the host. The major cost measure in emulating one graph by another is the ''slowdown.'' This is the ratio of the emulation time on the host to the running time on the guest. The slowdown of emulation depends on the following cost parameters:

Load. The maximum number of nodes of G mapped to any node of H.

Dilation. The length of the longest path in H to which any edge of G is mapped.

Congestion. The maximum number of paths (images of the edges of G) which share an edge of H.