Engineering Commons^™

Processor Allocation For Partitionable Multiprocessor Systems, Nicholaos C. Antoniou

Theses

The processor allocation problem in an n-dimensional hypercube multipro-cessor is similar to the conventional memory allocation problem. The main objective is to maximize the utilization of available resources as well as minimize the inherent system fragmentation. In this thesis, a new processor allocation strategy is proposed, and compared with the existing strategies, such as, the Buddy strategy, the Single Gray Code strategy (SGC), the Multiple Gray Code (MGC), and the Maximal Set of Subcubes (MSS). We will show that our proposed processor allocation strategy outperforms the existing strategies, by having the advantage of being able to allocate unused processors to …

Data Broadcasting And Reduction, Prefix Computation, And Sorting On Reduced Hypercube (Rh) Parallel Computers, Arup Mukherjee

Theses

The binary hypercube parallel computer has been very popular due to its rich interconnection structure and small average internode distance which allow the efficient embedding of frequently used topologies. Communication patterns of many parallel algorithms also match the hypercube topology. The hypercube has high VLSI complexity. however. due to the logarithmic increase in the number of connections to each node with the increase in the number of dimensions of the hypercube. The reduced hypercube (RH) interconnection network. which is obtained by a uniform reduction in the number of links for each hypercube node. yields lower-complexity interconnection networks when compared to …

Multilevel Embeddings For Massively-Parallel Hypercubes, Devenkuma P. Shah

Theses

Hierarchically structured arrays of processors have widely been used in the low and intermediate phases of image processing and computer vision. Since the pyramid structure efficiently supports local and global operations extensively required by these phases, it has been widely used for relevant algorithms. Multilevel systems keep all the advantages of the pyramid structure while providing a general hierarchical structure that is easier to be used for the development of several algorithms and may also provide higher performance.

Although the cost of pyramid machines may be tremendously high, they have limited applications. In contrast, the hypercube network is widely used …

Performance Analysis Of Pyramid Mapping Algorithms For The Hypercube, Jing-Chiou Liou

Theses

Comparative performance analysis of algorithms that map pyramids and multilevel structures onto the hypercube are presented. The pyramid structure is appropriate for low-level and intermediate-level computer vision algorithms. It is not only efficient for the support of both local and global operations but also capable of supporting the implementation of multilevel solvers. Nevertheless, pyramids lack the capability of efficient implementation of the majority of scientific algorithms and their cost may become unacceptably high. On a different horizon, hypercube machines have widely been used in the field of parallel computing due to their small diameter, high degree of fault tolerance, and …

Processor Allocation Strategies For Modified Hypercubes, Nagasimha G. Haravu

Theses

Parallel processing has been widely accepted to be the future in high speed computing. Among the various parallel architectures proposed/implemented, the hypercube has shown a lot of promise because of its poweful properties, like regular topology, fault tolerance, low diameter, simple routing, and ability to efficiently emulate other architectures. The major drawback of the hypercube network is that it can not be expanded in practice because the number of communication ports for each processor grows as the logarithm of the total number of processors in the system. Therefore, once a hypercube supercomputer of a certain dimensionality has been built, any …

Efficient Hypercube Communications, Shreyas R. Bhatt

Theses

Hypercube algorithms may be developed for a variety of communication-intensive tasks such as sending a message from one node to another, broadcasting a message from one node to all others, broadcasting a message from each node to all others, all-to-all personalized communication, one-to-all personalized communication, and exchanging messages between nodes via fixed permutations. All these communication patterns are special cases of many-to-many personalized communication. The problem of many-to-many personalized communication is investigated here.

Two routing algorithms for many-to-many personalized communication are presented here. The algorithms proposed yield very high performance with respect to the number of time steps and packet …