Nian-Feng Tzeng
Center for Advanced Computer Studies
University of Louisiana at Lafayette
Several interesting topics in this area have been pursued,
with a focus on hypercubes and meshes,
which are among popular message-passing architectures.
Parallel machines based on the hypercube and the mesh topologies have been
available commercially, and they exhibit a high potential for
the parallel execution of various algorithms.
The mesh system is suitable for the parallel execution of various algorithms. A few schemes for recognizing submeshes in a mesh-connected system have been considered, but they either lead to low processor utilization (because of large internal fragmentation) or cannot apply to general mesh systems. An efficient submesh allocation technique able to recognize submeshes with arbitrary sizes has been devised to assign a submesh of the precise size to an incoming task. It leads to significant improved performance over the previous submesh allocation scheme, while maintaining reasonably low time complexity.
Multiple copies of a certain resource (e.g., I/O processors, disks, compilers, etc.) often exist in the distributed memory machine to reduce access contention at any shared copy of the resource. Placing multiple copies of a resource in the hypercube has been considered such that every cube node without the resource is adjacent to a specified number of resource copies using as few resource copies as possible. This placement guarantees the resource to be accessible from every node in one hop even after some resource copies are lost. The placement is done systematically for any hypercube, following the multiple-adjacency codes devised, particularly useful for large-scale hypercubes to yield lowest potential access contention for a given number of resource copies (i.e., cost). The locations to place resource copies are specified by the codewords of an appropriate multiple-adjacency linear code constructed according to the degree of adjacency and the hypercube dimension.
A performance measure of interest in resource placement is
the resource diameter, which is defined as the maximum resource distance
among all the nodes, with the resource distance of a node being the minimum
number of hops from the node to a node equipped with a copy of the resource.
Placing copies of a certain resource to cube nodes under the situations
that the resource diameter is greater than 1 has been dealt with,
with approaches based on the covering radius results of known codes to
aid in constructing desired linear codes whose codewords address nodes
at which resource copies are placed.
They are applicable to any cube size systematically and
achieve placement results better than what are derived by previous methods.
Embedding trees and grids in incomplete hypercubes was pursued as well.
It is shown that better tree embedding results are often achievable in
incomplete hypercubes than in compatible complete hypercubes.
Likewise, superior embedding can be obtained in an incomplete hypercube
than in its complete counterpart for an absolute majority of cases.
Consequently, it is feasible and beneficial to reconfigure a faulty hypercube
into an incomplete cube so as to retain as many healthy nodes as possible.
The incomplete hypercube appears to be an attractive and practical topology.
A hypercube system often supports multi-tasking, by which several independent jobs can be executed simultaneously, one is assigned with one subcube. After repeated subcube allocation and deallocation in a hypercube, fragmentation tends to develop and cannot be eliminated without task migration, which is a process for relocating active tasks by migrating them to respective target subcubes so as to create a large free subcube. Speedy task migration in a hypercube system has been investigated by making use of two disjoint paths for delivering migration messages concurrently between every pair of corresponding nodes. All migration paths selected are pairwise disjoint and contain no link of active subcubes, so that task migration can be performed quickly and without interrupting the execution of other jobs. A highly fragmented hypercube may require compaction, which moves active tasks to a specified area such that all free nodes are at a contiguous region ready for upcoming jobs. An approach for compaction in a hypercube has been considered by using all disjoint paths from a subcube to its target subcube so as to achieve compaction at the fastest pace. This way accomplishes compaction in a fraction of the time needed with single paths.