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.     

Security checking in relational database management systems augmented with inference engines

In this paper we will discuss the notion of multilevel security and the difficulties encountered in designing an implementation scheme for a security policy for a multilevel secure database management system (MLS/DBMS). We will then describe how these difficulties may be overcome in augmenting a database with an inference engine so that it functions like a knowledge based system.     

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     

Fixed hypercube embedding

The problem of embedding a graph into a fixed-size hypercube is shown to be NP-complete. This work complements recent work of the present authors showing that deciding whether a graph is embeddable into any size hypercube is NP-complete as well. The reduction is from 3-partition.     

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.     

The shared memory hypercube

We investigate the use of a hypercube packet switching network as a shared memory server for vector multiprocessors. Using the generalization of a high performance switch node introduced in an earlier paper, we develop a packet switched memory server capable of providing high bandwidth vector access to a shared memory. The network exhibits adaptive behavior, absorbing conflicts as a vector operation proceeds, and delivers full vector bandwidth to all processors simultaneously.In addition to its vector performance, the hypercube has another feature that makes it attractive as a shared memory server. The memory words are not equidistant from the processors. A hierarchy of distances occurs. By taking advantage of this one can provide segments of fast access memory within the global shared memory environment. This makes the shared memory hypercube very promising as a general purpose parallel computer.     

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     

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     

Abstracting timed preemption with engines

The need for a programming language abstraction for timed preemption is argued, and several possibilities for such an abstraction are presented. One, called engines, is adopted. Engines are an abstraction of bounded computation, not a process abstraction in the usual sense. However, in conjuction with first class continuations, engines allow a language to be extended with time-sharing implementations for a variety of process abstraction facilities. We present a direct implementation of hiaton streams. Engine nesting refers to the initiation of an engine computation by an already running engine. We consider the need for engine nesting and show how it may be accomplished in a manner that charges a parent engine for the computation of its offspring. We conclude by discussing the importance of simple and general abstractions such as engines.     

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 .     

Vision algorithms for hypercube machines

Several commercial hypercube parallel processors with the potential to deliver massive parallelism cost-effectively have been announced recently. They open the door to a wide variety of application areas that could benefit from parallelism. Computer vision is one of these application areas. This paper develops a general model for hypercube machines, and uses it to show how vision algorithms can be executed on hypercubes. In particular, the steps in the problem of thick-film inspection are used as a concrete example. The time needed to complete a typical inspection is used to demonstrate the performance of hypercube machines. Experimental results from a hypercube machine illustrate the potential use of such machines.     

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.     

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     

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     

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.     

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.