Guodong Li

Document Type

Thesis - University Access Only

Award Date

1995

Degree Name

Master of Science (MS)

Department / School

Computer Science

First Advisor

Bin Cong

Abstract

Hypercube topology is one of the most important interconnection networks. It has gained widespread acceptance in parallel computing due to its many attractive properties. Also, it has been shown that many interconnection networks can be simulated by the hypercube with a minimum overhead. A new alternative version of the hypercube is the X-hypercube. It preserves many of the attractive properties of the hypercube and its diameter is reduced by half. The complete binary tree is another important interconnection network, because it captures the essence of the divide and conquer algorithm. The pointer jumping technique is a widely used paradigm in parallel processing, particularly in the PRAM algorithm design. How to implement the pointer jumping technique in parallel systems is a very important issue. Meshes are also popular interconnection networks used to build massively parallel computer systems. How to efficiently simulate multidimensional meshes by small hypercubes is another important issue in parallel processing. In this thesis, we first show that complete binary trees up to height 7 (with 127 nodes) can be embedded into their optimum X-hypercubes with unit expansion and unit dilation, and then we show that any complete binary tree can be embedded into its optimum X-hypercube with unit expansion and with only about 1.3% of the tree edges being mapped to the paths of length two in the X-hypercube. Then we propose and investigate several computer networks involved with the pointer jumping techniques, namely, pointer jumping cubes (PJC), linear pointer jumping arrays (LPJA), multidimensional pointer jumping arrays (MPJA), and cross pointer jumping cubes (CPJC). We show that (a) PJC and CPJC are incomplete hypercube networks (i.e. they are subgraphs of some hypercubes); (b) a hypercube can be embedded into its optimum pointer jumping cube with dilation 2n -1, where n is the dimension of the hypercube; (c) a complete binary tree can be embedded into its optimum PJC with dilation two; ( d) a complete binary tree can be embedded into its half size PJC with dilation one and some load factors. These new topologies provide a new platform for implementing parallel algorithms based on the PRAM models. Finally, we describe how to embed an arbitrary 3-dimensional mesh (3-D mesh) into its 1/2-size hypercube. We obtained the following results: (a) a 3-D mesh with the form of [3x3xp], can be embedded into its 1/2-size hypercube with dilation two and load factor two by the uniform braiding technique; (b) a 3-D mesh M with the form of [3x5xp] can be embedded into its 1/2-size hypercube with dilation one and load factor two, if M's 1/2 density≤ 1.5; (c) all other 3-D meshes can be embedded into their 1/2-size hypercubes with dilation one and load factor two, if their 1/2-densities≤1.828.

Library of Congress Subject Headings

Computer networks -- Design
Hypercube networks (Computer networks)

Format

application/pdf

Publisher

South Dakota State University

Download

Share

COinS
 

Rights Statement

In Copyright