To embed a ring in a hypercube is to find a Hamiltonian cycle through every node of the hypercube. It is obvious that no 2/sup n/-node Hamiltonian cycle exists in an n-dimensional faulty hypercube which has at least one faulty node. However, if a hypercube has faulty links only and the number of faulty links is at most n-2, at least one 2/sup n/-node Hamiltonian cycle can be found. In this paper, we propose a distributed ring-embedding algorithm that can find a Hamiltonian cycle in a fault-free or faulty n-dimensional hypercube (Q,), and the complexity is O(n) parallel steps. The algorithm is based on the recursion property of the hypercube and the free-link dimension concept. In some cases, even when the number of faulty links is larger than n-2, Hamiltonian cycles may still exist. We show that the largest possible number of faulty links that can be tolerated is 2/sup n-1/-1. The performance and the constraints of the fault-tolerant algorithm is also analyzed in detail in this paper. Furthermore, a dynamic reconfiguration algorithm for an embedded ring is proposed and discussed. Due to the distributed nature of the algorithms, they are useful for the simulation of ring-based multiprocessors on MIMD hypercube multiprocessors.

The Mobile IP protocol allows transparent routing of IP datagrams on the Internet. Each mobile node is identified by its home address disregarding its current location in the Internet. While away from home, a mobile node is associated with a care-of address which gives information about its current location. Mobile IP specifies how a mobile node registers with its home agent and how the home agent routes datagrams to the mobile node through a tunnel. The authors first outline the Mobile IP protocol and its extension mechanism defined for carrying information. They then present the architecture of their working implementation which is based on objected-oriented methodology. Finally some implementation considerations and challenges for Mobile IP are investigated.

The tree communication scheme was shown to be very efficient for global operations on data residing in the processors of a hypercube with time complexity of O(log/sub 2/N), where N is the number of processors. This communication scheme is very useful for many parallel algorithms on hypercube multiprocessors. If a problem can be divided into independent subproblems, each subproblem can first be solved by one of the processors. Then, the tree communication scheme is invoked to merge the subresults into the final results. All the algorithms for problems with this property can benefit from the tree communication scheme. We propose a more general and efficient tree communication scheme in this paper. In addition, we also propose fault-tolerant algorithms for the tree communication scheme, by exploiting the unique properties of the tree communication scheme. The computation and communication slowdown is small (<2) under the effect of multiple link and/or node failures.

Several new algorithms for matrix-matrix multiplications on hypercube multiprocessors are presented and evaluated based on the number of multiplications, additions, and transfers. The matrices to be multiplied are uniformly distributed to all processors of a hypercube system. Each processor owns some submatrices which are derived by dividing the source matrices. Each submatrix multiplication can now be performed independently within a processor. All the partial results are then summed up and transferred to a single processor. An orthogonal tree is used for efficient communication. The time complexity is O(log/sub 2/p) if p /spl times/ p processors are used. In addition, the UDD (Uniform Data Distribution) approach is employed when some processors do not work properly and the faulty effects have been detected. Two classes of fault patterns are considered and evaluated.>