๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Topological properties and algorithms for two-level hypernet networks

โœ Scribed by Huang, Hui-Ling; Chen, Gen-Huey


Publisher
John Wiley and Sons
Year
1998
Tongue
English
Weight
261 KB
Volume
31
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

โœฆ Synopsis


Although many networks have been proposed as the topology of a large-scale parallel and distributed system, most of them are neither expansible nor of equal degree. A network with these two properties will gain the advantages of easy implementation and low cost when it is manufactured. The hypernet, which was proposed by Hwang and Ghosh, represents a family of recursively scalable networks that are both expansible and of equal degree. In addition to the two merits, the hypernet has proven efficient for communication and computation. But, unfortunately, most topological properties and the problem of shortest-path routing for the hypernet are still unsolved. The reason is that the structure of the hypernet is complex and asymmetric, and, especially, no mathematical description was given before. In this paper, considering current hardware restrictions, we concentrate our effort on the hypernet of moderate size. We first give a concise mathematical definition for the hypernet and then solve the following problems for the hypernet of two levels: (1) shortest-path routing, (2) diameter, (3) connectivity, (4) minimum-height spanning trees, and (5) embedding of rings, tori, and hypercubes.


๐Ÿ“œ SIMILAR VOLUMES


Handbook of Applied Algorithms || Locali
โœ Nayak, Amiya; Stojmenovi, Ivan ๐Ÿ“‚ Article ๐Ÿ“… 2008 ๐Ÿ› John Wiley & Sons, Inc. ๐ŸŒ English โš– 225 KB ๐Ÿ‘ 2 views

discover The Benefits Of Applying Algorithms To Solve Scientific, Engineering, And Practical Problems Providing A Combination Of Theory, Algorithms, And Simulations, Handbook Of Applied Algorithms Presents An All-encompassing Treatment Of Applying Algorithms And Discrete Mathematics To Practi

Performance evaluation of Two-level Sche
โœ Yukio Ohishi; Keizo Saisho; Akira Fukuda ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 210 KB

In this article, we simulate and evaluate various Twolevel Scheduling algorithms for cluster-based NUMA (Non-Uniform Memory Access) multiprocessors. Twolevel Scheduling is a kind of space partitioning scheduling. We evaluate the following variations: (1) Cluster-free Algorithm and (2) Cluster-limite