Formation of hypercube representation of relational database

In the paper, a technology of constructing hypercube data representation from an original relational database is considered. The construction is based on formal definitions of the intermediate and target data models. Using an example of a particular relational database scheme, a mechanism of automated application generation is discussed.     

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     

Orthogonal-column Latin hypercube designs with small samples

Latin hypercube designs with zero pair-wise column correlations are examined for their space-filling properties. Such designs, known as orthogonal-column Latin hypercube designs, are often used in computer experiments and in screening experiments, since all coefficients in a first-order model are estimated independently of each other. This makes interpretation of the factor effects particularly simple. Complete or partial enumeration searches are carried out to investigate the space-filling properties of all orthogonal-column Latin hypercube designs, with from 5 to 9 runs, and, from 2 to 5 factors. In cases where there are several designs with similar properties, the designs with minimum mean squared distance are determined. The maximum number of factors that can be accommodated in orthogonal-column Latin hypercube designs is determined for each design size, and designs found by various algorithmic methods proposed in the literature are identified.     

Executing algorithms with hypercube topology on torusmulticomputers

Many parallel algorithms use hypercubes as the communication topology among their processes. When such algorithms are executed on hypercube multicomputers the communication cost is kept minimum since processes can be allocated to processors in such a way that only communication between neighbor processors is required. However, the scalability of hypercube multicomputers is constrained by the fact that the interconnection cost-per-node increases with the total number of nodes. From scalability point of view, meshes and toruses are more interesting classes of interconnection topologies. This paper focuses on the execution of algorithms with hypercube communication topology on multicomputers with mesh or torus interconnection topologies. The proposed approach is based on looking at different embeddings of hypercube graphs onto mesh or torus graphs. The paper concentrates on toruses since an already known embedding, which is called standard embedding, is optimal for meshes. In this paper, an embedding of hypercubes onto toruses of any given dimension is proposed. This novel embedding is called xor embedding. The paper presents a set of performance figures for both the standard and the xor embeddings and shows that the latter outperforms the former for any torus. In addition, it is proven that for a one-dimensional torus (a ring) the xor embedding is optimal in the sense that it minimizes the execution time of a class of parallel algorithms with hypercube topology. This class of algorithms is frequently found in real applications, such as FFT and some class of sorting algorithms     

The exchanged hypercube

This paper presents the exchanged hypercube, a new interconnection network obtained by systematically removing links from a binary hypercube. It maintains several desirable properties of the binary hypercube yet with reduced interconnection complexity. We also introduce the extended binomial tree, a spanning tree of the exchanged hypercube that preserves many desirable properties of the original binomial tree. A fault-tolerant routing strategy is also proposed for the exchanged hypercube.     

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.     

Programming a hypercube multicomputer

The issues encountered by programmers are explored. A brief overview of parallel architectures is followed by an example problem of image-template matching. The programming consideration for this problem are discussed     

A versatile ring-connected hypercube

Our work in deriving and comparing the reliability formulas for three leading hypercubic models-the original hypercube, Shih's cube, and the ring-connected hypercube-demonstrates the superiority of the ring-connected hypercube (RCH) approach. Though it needs twice the links of the original hypercube network, which is the best result to date, the RCH can recover from node failures. The higher resultant reliability of this fault-tolerant architecture makes the RCH an attractive candidate for many critical parallel-computation applications     

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.     

Nested maximin Latin hypercube designs

In the field of design of computer experiments (DoCE), Latin hypercube designs are frequently used for the approximation and optimization of black-boxes. In certain situations, we need a special type of designs consisting of two separate designs, one being a subset of the other. These nested designs can be used to deal with training and test sets, models with different levels of accuracy, linking parameters, and sequential evaluations. In this paper, we construct nested maximin Latin hypercube designs for up to ten dimensions. We show that different types of grids should be considered when constructing nested designs and discuss how to determine which grid to use for a specific application. To determine nested maximin designs for dimensions higher than two, four variants of the ESE algorithm of Jin et al. (J Stat Plan Inference 134(1):268–287, 2005) are introduced and compared. Our main focus is on GROUPRAND, the most successful of these four variants. In the numerical comparison, we consider the calculation times, space-fillingness of the obtained designs and the performance of different grids. Maximin distances for different numbers of points are provided; the corresponding nested maximin designs can be found on the website .     

Processor allocation in hypercube multiprocessors

The processor allocation problem requires recognizing and locating a free subcube that can accommodate a request for a subcube of a specified size for an incoming task. Methods reported in the literature fall into two strategies: bottom-up or bit mapped technique (BMT) and top-downer available cube technique (ACT). Our algorithm that solves the allocation problem in faulty hypercubes falls into the category of ACT's which offer the advantage over BMT's of quickly recognizing whether or not a requested subcube is available in the list of fault-free subcubes. We introduce new algebraic functions and the concept of separation factor to select a subcube for allocation. The notion of overlap-syndrome, defined in the text, quantifies the overlap among free subcubes. Our technique has full subcube recognition ability and thus recognizes more subcubes as compared to bit mapped techniques: Buddy, Gray code and its variants. The advantages of our approach over some of the existing ACT's in terms of fragmentation and overall completion time are described in the text and in simulation results     

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.     

On the maximal connected component of hypercube with faulty vertices

In evaluating an interconnection network, it is indispensable to estimate the size of the maximal connected components of the underlying graph when the network begins to lose processors. Hypercube is one of the most popular interconnection networks. This article addresses the maximal connected components of an n-dimensional cube with faulty processors. We first prove that an n-cube with a set F of at most 2n???3 failing processors has a component of size ≥2 ⁿ ???|F|???1. We then prove that an n-cube with a set F of at most 3n???6 missing processors has a component of size ≥2 ⁿ ???|F|???2.     

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.     

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.     

On the area of hypercube layouts

This paper precisely analyzes the wire density and required area in standard layout styles for the hypercube. It shows that the most natural, regular layout of a hypercube of N² nodes in the plane, in an N×N grid arrangement, uses ⌊2N/3⌋+1 horizontal wiring tracks for each row of nodes. (In the process, we see that the number of tracks per row can be reduced by 1 with a less regular design, as can also be seen from an independent argument of Bezrukov et al.) This paper also gives a simple formula for the wire density at any cut position and a full characterization of all places where the wire density is maximized (which does not occur at the bisection).     

Finding cycles in hierarchical hypercube networks

The hierarchical hypercube network, which was proposed as an alternative to the hypercube, is suitable for building a large-scale multiprocessor system. A bipartite graph G=(V,E) is bipancyclic if it contains cycles of all even lengths ranging from 4 to |V|. In this paper, we show that the hierarchical hypercube network is bipancyclic.     

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