Architecture, Performance and Applications of a Hierarchial Network of Hypercubes

Abstract

This thesis, presents a multiprocessor topology, the hierarchical network of hyper-cubes, which has a low diameter, low degree of connectivity and yet exhibits hypercube like versatile characteristics. The hierarchical network of hyper-cubes consists of k-cubes interconnected in two or more hierarchical levels. The network has a hierarchical, expansive, recursive structure with a constant pre-defined building block. The basic building block of the hierarchical network of hyper-cubes comprises of a k-cube of processor elements and a network controller. The hierarchical network of hyper-cubes retains the positive features of the k-cube at different levels of hierarchy and has been found to perform better than the binary hypercube in executing a variety of application problems. The ASCEND/DESCEND class of algorithms can be executed in O(log2 N) parallel steps (N is the number of data elements) on a hierarchical network of hypercubes with N processor elements. A description of the topology of the hierarchical network of hypercubes is presented and its architectural potential in terms of fault-tolerant message routing, executing a class of highly parallel algorithms, and in simulating artificial neural networks is analyzed. Further, the proposed topology is found to be very efficient in executing multinode broadcast and total exchange algorithms. We subsequently, propose an improvisation of the network to counter faults, and explore implementation of artificial neural networks to demonstrate efficient implementation of application problems on the network. The fault-tolerant capabilities of the hierarchical network of hypercubes with two network controllers per k-cube of processor elements are comparable to those of the hypercube and the folded hypercube. We also discuss various issues related to the suitability of multiprocessor architectures for simulating neural networks. Performance analysis of ring, hypercube, mesh and hierarchical network of hypercubes for simulating artificial neural networks is presented. Our studies reveal that the performance of the hierarchical network of hypercubes is better than those of ring, mesh, hypernet and hypercube topologies in implementing artificial neural networks. Design and implementation aspects of hierarchical network of hypercubes based on two schemes, viz., dual-ported RAM communication, and transputers are also presented. Results of simulation studies for robotic applications using neural network paradigms on the transputer-based hierarchical network of hypercubes reveal that the proposed network can produce fast response times of the order of hundred microseconds.