The spined cube: A new hypercube variant with smaller diameter

Bijective connection graphs (in brief, BC graphs) are a family of hypercube variants, which contains hypercubes, twisted cubes, crossed cubes, Möbius cubes, locally twisted cubes, etc. It was proved that the smallest diameter of all the known n-dimensional bijective connection graphs (BC graphs) is , given a fixed dimension n. An important question about the smallest diameter among all the BC graphs is: Does there exist a BC graph whose diameter is less than the known BC graphs such as crossed cubes, twisted cubes, Möbius cubes, etc., with the same dimension? This paper answers this question. In this paper, we find that there exists a kind of BC graphs called spined cubes and we prove that the n-dimensional spined cube has the diameter ⌈n/3⌉+3 for any integer n with n?14. It is the first time in literature that a hypercube variant with such a small diameter is presented.     

Embedding hierarchical hypercube networks into the hypercube

The embedding of one interconnection network into another is a very important issue in the design and analysis of parallel algorithms. Through such embeddings, the algorithms originally developed for one architecture can be directly mapped to another architecture. This paper describes a new embedding method, based on matrix transformations, for optimally embedding hierarchical hypercube networks (HHNs) into the hypercube (binary n-cube). Thus, this embedding method has practical importance in enhancing the capabilities and extending the usefulness of the hypercube, since hierarchical hypercube networks have proven to be very cost-effective for a wide range of applications     

Scheduling on a hypercube

We present a Θ(n²) worst-case-time algorithm to determine the minimum finishing time for a preemptive schedule of n independent jobs on a hypercube of fixed dimension.     

Parallel simulation on the hypercube multiprocessor

Summary This paper focuses upon a particular conservative algorithm for parallel simulation, the Time of Next Event (TNE) suite of algorithms [13]. TNE relies upon a shortest path algorithm which is independently executed on each processor in order to unblock LPs in the processor and to increase the parallelism of the simulation. TNE differs fundamentally from other conservative approaches in that it takes advantage of having several LPs assigned to each processor, and does not rely upon message passing to provide lookahead. Instead, it relies upon a shortest path algorithm executed independently in each processor. A deadlock resolution algorithm is employed for interprocessor deadlocks. We describe an empirical investigation of the performance of TNE on the iPSC/i860 hypercube multiprocessor. Several factors which play an important role in TNE's behavior are identified, and the speedup relative to a fast uniprocessor-based event list algorithm is reported. Our results indicate that TNE yields good speedups and out-performs an optimized version of the Chandy&Misra-null message (CMB) algorithm. TNE was 2–5 times as fast as the CM approach for less than 10 processors (and 1.5–3 times as fast when more than 10 processors were used for the same population of processes.) Azzedine Boukerche received the State Engineer degree in Software Engineering from Oran University, Oran, Algeria, and the M.Sc. degree in Computer Science from McGill University, Montreal, Canada. He is a Ph.D. candidate at the School of Computer Science, McGill University. During 1991–1992, he was a visiting doctoral student at the California Institute of Technology. He is employed as a Faculty Lecturer of computer Science at McGill University since 1993. His research interests include parallel simulation, distributed algorithms, and system performance analysis. He is a student member of the IEEE and ACM. Carl Tropper is an Associate Professor of Computer Science at McGill University. His primary area of research is parallel discrete event simulation. His general area of interest is in parallel computing and distributed algorithms in particular. Previously, he has done research in the performance modeling of computer networks, having written a book,Local Computer Network Technologies, while active in the area. Before coming to university life, he worked for the BBN Corporation and the Mitre Corporation, both located in the Boston area. He spent the 1991–92 academic year on a sabbatical leave at the Jet Propulsion Laboratories of the California Institute of Technology where he contributed to a project centered about the verification of flight control software. As part of this project he developed algorithms for the parallel simulation of communicating finite state machines. During winters he may be found hurtling down mountains on skis.This work has been completed while the author was a visiting doctoral student at the California Institute of TechnologyWas on sabbatical leave at the Jet Propulsion laboratories, California Institute of Technology     

Routing algorithms on the bus-based hypercube network

In this paper, we study the properties of the bus-based hypercube, denoted as U(n,b), which is a kind of multiple-bus networks (MBN). U(n,b) consists of 2/sup n/ processors and 2/sup b/ buses, where 0 /spl les/ b /spl les/ n - 1, and each processor is connected to either /spl lceil/(b+2)/2/spl rceil/ or /spl lceil/(b+1)/2/spl rceil/ buses. We show that the diameter of U(n,b) is /spl lceil/(b-1)/2/spl rceil/ if b /spl ges/ 2. We also present an algorithm to select the best neighbor processor via which we can obtain one shortest routing path. In U(n,b), we show that if there exist some faults, the fault diameter DF(n,b,f) /spl les/ b+1, where f is the sum of bus faults and processor faults and 0 /spl les/ f /spl les/ /spl lceil/(b+3)/2/spl rceil/. Furthermore, we also show that the bus fault diameter DB(n,b,f) /spl les/ b/-2/spl rfloor/ - 3, where 0 /spl les/ f /spl les/ /spl lceil/(b-1)/2/spl rceil/ and f is the number of bus faults. These results improve significantly the previous result that DB(n,b,f) /spl les/ b - 2f + 1, where f is the number of bus faults.     

Clustering on a hypercube multicomputer

Squared error clustering algorithms for single-instruction multiple-data (SIMD) hypercubes are presented. The algorithms are shown to be asymptotically faster than previously known algorithms and require less memory per processing element (PE). For a clustering problem with N patterns, M features per pattern, and K clusters, the algorithms complete in O(k+log NM ) steps on NM processor hypercubes. This is optimal up to a constant factor. These results are extended to the case in which NMK processors are available. Experimental results from a multiple-instruction, multiple-data (MIMD) medium-grain hypercube are also presented     

Routing automorphisms of the hypercube

We present an online algorithm for routing the automorphisms (BPC permutations) of the queueless MIMD hypercube. The routing algorithm has the virtue of being executed by each node of the hypercube without knowing the state of the others nodes. The algorithm is also vertex and link-contention free. We show, using the proposed algorithm, that BPC permutations are arbitrarily routable in the considered communication model.     

The bipancycle-connectivity of the hypercube

Paths and cycles are popular interconnection networks due to their simplicity and low degrees, and therefore an efficient way of embedding them into an interconnection network is of particular importance. Many path-embedding aspects and cycle-embedding aspects, such as Hamiltonicity, Hamiltonian-connectivity, panconnectivity, bipanconnectivity, pancyclicity, vertex-pancyclicity and edge-pancyclicity, have been proposed and extensively studied. In fact, these discussions are meaningful for interconnection networks of resource-allocated systems or heterogeneous computing systems. In this paper, we propose a new cycle-embedding aspect called bipancycle-connectivity that combines the concepts of vertex-pancyclicity and bipanconnectivity. A bipartite graph is bipancycle-connected if an arbitrary pair of vertices x, y is contained by common cycles called bipanconnected cycles that include a cycle of every even length ranging from minc(x, y) to N; where minc(x, y) denotes the length of the minimum cycle that contains x and y, and N is the number of vertices. In this paper, we introduce a new graph called the cycle-of-ladders. We show that the hypercube is bipancycle-connected by presenting algorithms to embed the cycle-of-ladders into the hypercube.     

The nearest subclass classifier: a compromise between the nearest mean and nearest neighbor classifier

We present the Nearest Subclass Classifier (NSC), which is a classification algorithm that unifies the flexibility of the nearest neighbor classifier with the robustness of the nearest mean classifier. The algorithm is based on the Maximum Variance Cluster algorithm and, as such, it belongs to the class of prototype-based classifiers. The variance constraint parameter of the cluster algorithm serves to regularize the classifier, that is, to prevent overfitting. With a low variance constraint value, the classifier turns into the nearest neighbor classifier and, with a high variance parameter, it becomes the nearest mean classifier with the respective properties. In other words, the number of prototypes ranges from the whole training set to only one per class. In the experiments, we compared the NSC with regard to its performance and data set compression ratio to several other prototype-based methods. On several data sets, the NSC performed similarly to the k-nearest neighbor classifier, which is a well-established classifier in many domains. Also concerning storage requirements and classification speed, the NSC has favorable properties, so it gives a good compromise between classification performance and efficiency.     

Computing biconnected components on a hypercube

We describe two hypercube algorithms to find the biconnected components of a dense connected undirected graph. One is a modified version of the Tarjan-Vishkin algorithm and the other is an adaptation of Read's sequential algorithm. The two hypercube algorithms were experimentally evaluated on an NCUBE/7 MIMD hypercube computer. The two algorithms have comparable performance, and efficiencies as high as 0.7 were observed on dense graphs.This research was supported in part by the National Science Foundation under grants DCR84-20935 and MIP 86-17374.     

Hierarchical discrete-event simulation on hypercube architectures

The simulation of systems that include components at varying levels of abstraction is addressed. A performance model of a hierarchical discrete-event simulation algorithm running on a hypercube architecture is presented. The model allows the performance impact of decisions made in the design of the parallel processor as well as in the design of the simulation algorithm to be examined. Three static component partitioning strategies are considered: random partitioning, heuristic partitioning, and simulated annealing. The performance model is applied to digital system simulation     

Computing Hough transforms on hypercube multicomputers

Efficient algorithms to compute the Hough transform on MIMD and SIMD hypercube multicomputer are developed. Our algorithms can compute p angles of the Hough transform of an N × N image, p N, in 0(p + log N) time on both MIMD and SIMD hypercubes. These algorithms require 0(N ²) processors. We also consider the computation of the Hough transform on MIMD hypercubes with a fixed number of processors. Experimental results on an NCUBE/7 hypercube are presented.This research was supported by the National Science Foundation under grants DCR84-20935 and 86-17374. All correspondence should be mailed to Sanjay Ranka.     

Efficient histogramming on hypercube SIMD machines

This paper considers the histogramming problem on hypercube.N-PE hypercube is used to process anN ¹² × N¹²digitized image in which each pixel has a gray-level value between 0 andM − 1. In general,M, the range of gray-level values is much smaller thanN, the number of pixels being processed. Our algorithm generates the histogram of the image inO(logM * logN) time using radix sort and efficient data movement operations. This technique can be implemented on butterfly, shuffle-exchange and fat pyramid organizations.     

Balanced parallel sort on hypercube multiprocessors

A parallel sorting algorithm for sorting n elements evenly distributed over 2^d p nodes of a d-dimensional hypercube is presented. The average running time of the algorithm is O((n log n)/p+p log 2n). The algorithm maintains a perfect load balance in the nodes by determining the (kn/p)th elements (k1,. . ., (p-1)) of the final sorted list in advance. These p-1 keys are used to partition the sorted sublists in each node to redistribute data to the nodes to be merged in parallel. The nodes finish the sort with an equal number of elements (n/ p) regardless of the data distribution. A parallel selection algorithm for determining the balanced partition keys in O(p log2n) time is presented. The speed of the sorting algorithm is further enhanced by the distance-d communication capability of the iPSC/2 hypercube computer and a novel conflict-free routing algorithm. Experimental results on a 16-node hypercube computer show that the sorting algorithm is competitive with the previous algorithms and faster for skewed data distributions     

Maze routing on a hypercube multicomputer

The implementation of Lee's maze routing algorithm on an MIMD hypercube multiprocessor computer can follow several plausible mappings and synchronization strategies. These are evaluated experimentally on an NCUBE/7 hypercube computer with 64 processors. Different grid partitioning and mapping strategies result in a different balance between computation and communication time. The total routing time is significantly impacted by the synchronization and termination detection scheme used. Further, by rearranging the computation, it is possible to overlap much of the interprocessor communication with the computation and realize a significant reduction in the overall run time. By choosing the right partitioning and synchronization scheme and by overlapping computation and communication, a good speedup is obtained on large routing grids.     

Optimal visibility algorithms for binary images on the hypercube

Consider an×n binary image. Given a directionD, the parallel visibility problem consists of determining for each pixel of the image the portion that is visible (i.e., not obstructed by any other black pixel of the image) in directionD from infinity. A related problem, referred to as point visibility, is to compute for each pixel the portion that is visible from a given pointp. In this paper, we deriveO(logn) time SIMD algorithms for each of these two problems on the hypercube, where one processor is assigned to every pixel of the image. Since the worst case communication distance of two processors in an ²-processor hypercube is 2 logn, it follows that both of the above algorithms are asymptotically optimal.This paper summarizes a preliminary version [Ref. 1] and short note on a possible improvement [Ref. 2] presented at the 1988IFIP WG 10.3. Working Conference on Parallel Processing and 1988Allerton Conference on Communication, Control and Computing, respectively. The first and third authors' research are partially supported by the Natural Sciences and Engineering Research Council of Canada.     

Optimal algorithms on the pipelined hypercube and related networks

Parallel algorithms for several important combinatorial problems such as the all nearest smaller values problem, triangulating a monotone polygon, and line packing are presented. These algorithms achieve linear speedups on the pipelined hypercube, and provably optimal speedups on the shuffle-exchange and the cube-connected-cycles for any number p of processors satisfying 1⩽p⩽n/((log³n)(loglog n)²), where n is the input size. The lower bound results are established under no restriction on how the input is mapped into the local memories of the different processors     

Improved lower bounds on the reliability of hypercube architectures

The hypercube topology, also known as the Boolean n-cube, has recently been used for multiprocessing systems. The paper considers two structural-reliability models, namely, terminal reliability (TR) and network reliability (NR), for the hypercube. Terminal (network) reliability is defined as the probability that there exists a working path connecting two (all) nodes. There are no known polynomial time algorithms for exact computation of TR or NR for the hypercube. Thus, lower-bound computation is a better alternative, because it is more efficient computationally, and the system will be at least as reliable as the bound. The paper presents algorithms to compute lower bounds on TR and NR for the hypercube considering node and/or link failures. These algorithms provide tighter bounds for both TR and NR than known results and run in time polynomial in the cube dimension n, specifically, within time O(n²)     

Solving structural mechanics problems on the caltech hypercube machine

This paper reports our experience with the 32-node CalTech Hypercube multiprocessor for solving structural mechanics problems by the finite element method. We begin with an overview of the Hypercube that is pertinent to finite element computations, and the C-based system utilities used for message passing. We discuss the partitioning and mapping of the structure onto the Hypercube nodes. We illustrate the essential features of the employed concurrent algorithms and their implementation using a one-dimensional wave propagation problem and a two-dimensional stress analysis problem. Finally, we present some outstanding issues that need be addressed for the widespread use of parallel computers in engineering computations.