Partial indexing for nonuniform data distributions in relationalDBMS's

It is well known that the effectiveness of relational database systems is greatly dependent on the efficiency of the data access strategies. For this reason, much work has been devoted to the development of new access techniques, supported by adequate access structures such as the B⁺trees. The effectiveness of the B ⁺tree also depends on the data distribution characteristics; in particular, poor performance results when the data show strong key value distribution unbalancing. The aim of this paper is to present the partial index: a new access structure that is useful in such cases of unbalancing, as an alternative to the B⁺tree unclustered indexes. The access structures are built in the physical design phase, and at execution (or compilation) time, the optimizer chooses the most efficient access path. Thus, integration of the partial indexing technique in the design and in the optimization process are also described     

Evaluation of a parallel branch-and-bound algorithm on a class ofmultiprocessors

We propose and evaluate a parallel “decomposite best-first” search branch-and-bound algorithm (dbs) for MIN-based multiprocessor systems. We start with a new probabilistic model to estimate the number of evaluated nodes for a serial best-first search branch-and-bound algorithm. This analysis is used in predicting the parallel algorithm speed-up. The proposed algorithm initially decomposes a problem into N subproblems, where N is the number of processors available in a multiprocessor. Afterwards, each processor executes the serial best-first search to find a local feasible solution. Local solutions are broadcasted through the network to compute the final solution. A conflict-free mapping scheme, known as the step-by-step spread, is used for subproblem distribution on the MIN. A speedup expression for the parallel algorithm is then derived using the serial best-first search node evaluation model. Our analysis considers both computation and communication overheads for providing realistic speed-up. Communication modeling is also extended for the parallel global best-first search technique. All the analytical results are validated via simulation. For large systems, when communication overhead is taken into consideration, it is observed that the parallel decomposite best-first search algorithm provides better speed-up compared to other reported schemes     

Parallel architecture for fast transforms with trigonometric kernel

We present an unified parallel architecture for four of the most important fast orthogonal transforms with trigonometric kernel: Complex Valued Fourier (CFFT), Real Valued Fourier (RFFT), Hartley (FHT), and Cosine (FCT). Out of these, only the CFFT has a data flow coinciding with the one generated by the successive doubling method, which can be transformed on a constant geometry flow using perfect unshuffle or shuffle permutations. The other three require some type of hardware modification to guarantee the constant geometry of the successive doubling method. We have defined a generalized processing section (PS), based on a circular CORDIC rotator, for the four transforms. This PS section permits the evaluation of the CFFT and FCT transforms in n data recirculations and the RFFT and FHT transforms in n-1 data recirculations, with n being the number of stages of a transform of length N=rⁿ. Also, the efficiency of the partitioned parallel architecture is optimum because there is no cycle loss in the systolic computation of all the butterflies for each of the four transforms     

The classification, fusion, and parallelization of array languageprimitives

We present a classification scheme for array language primitives that quantifies the variation in parallelism and data locality that results from the fusion of any two primitives. We also present an algorithm based on this scheme that efficiently determines when it is beneficial to fuse any two primitives. Experimental results show that five LINPACK routines report 50% performance improvement from the fusion of array operators     

The fault-tolerant extension problem for complete multipartitenetworks

We develop a characterization for m-fault-tolerant extensions, and for optimal m-fault-tolerant extensions, of a complete multipartite graph. Our formulation shows that this problem is equivalent to an interesting combinatorial problem on the partitioning of integers. This characterization leads to a new procedure for constructing an optimal m-fault-tolerant extension of any complete multipartite graph, for any m⩾0. The proposed procedure is mainly useful when the size of the graph is relatively small, because the search time required is exponential. This exponential search, however, is not always necessary. We prove several necessary conditions that help us, in several cases, to identify some optimal m-fault-tolerant extensions without performing any search     

Neural network control of communications systems

Neural networks appear well suited to applications in the control of communications systems for two reasons: adaptivity and high speed. This paper describes application of neural networks to two problems, admission control and switch control, which exploit the adaptivity and speed property, respectively. The admission control problem is the selective admission of a set of calls from a number of inhomogeneous call classes, which may have widely differing characteristics as to their rate and variability of traffic, onto a network. It is usually unknown in advance which combinations of calls can be simultaneously accepted so as to ensure satisfactory performance. The approach adopted is that key network performance parameters are observed while carrying various combinations of calls, and their relationship is learned by a neural network structure. The network model chosen has the ability to interpolate or extrapolate from the past results and the ability to adapt to new and changing conditions. The switch control problem is the service policy used by a switch controller in transmitting packets. In a crossbar switch with input queueing, significant loss of throughput can occur when head-of-line service order is employed. A solution can be based on an algorithm which maximizes throughput. However since this solution is typically required in less than one microsecond, software implementation policy is infeasible. We will carry out an analysis of the benefits of such a policy, describe some existing proposed schemes for its implementation, and propose a further scheme that provides this submicrosecond optimization.     

Robust crossfeed design for hovering rotorcraft

Control law design for rotorcraft fly-by-wire systems normally attempts to decouple the angular responses using fixed-gain crossfeeds. This approach can lead to poor decoupling over the frequency range of pilot inputs and increase the load on the feedback loops. In order to improve the decoupling performance, dynamic crossfeeds should be adopted. Moreover, because of the large changes that occur in the aircraft dynamics due to small changes about the nominal design condition, especially for near-hovering flight, the crossfeed design must be ‘robust’. A new low-order matching method is presented here to design robust crossfeed compensators for multi-input, multi-output (MIMO) systems. The technique minimizes cross-coupling given an anticipated set of parameter variations for the range of flight conditions of concern. Results are presented in this paper of an analysis of the pitch/roll coupling of the UH-60 Black Hawk helicopter in near-hovering flight. A robust crossfeed is designed that shows significant improvement in decoupling perfomance and robustness over the fixed-gain or single point dynamic compensators. The design method and results are presented in an easily used graphical format that lends significant physical insight to the design procedure. This plant precompensation technique is an appropriate preliminary step to the design of robust feedback control laws for rotorcraft.     

An explicit finite difference method for finite-time observers

In this paper we present a numerical method for estimating the current state of a nonlinear control system. We use finite differences to discretize a modified version of the finite-time observer equations in James. The discretized equations are simple and easily programmed. The convergence and accuracy of the scheme is proved, and the scheme enjoys a number of important properties: availability of rate of convergence estimates, good robustness characteristics, and the ability to handle certain types of discontinuities in the observations. The major disadvantage is that the number of grid points required increases exponentially with the number of state dimensions.     

Low temperature wafer direct bonding

A pronounced increase of interface energy of room temperature bonded hydrophilic Si/Si, Si/SiO₂, and SiO₂/SiO ₂ wafers after storage in air at room temperature, 150°C for 10-400 h has been observed. The increased number of OH groups due to a reaction between water and the strained oxide and/or silicon at the interface at temperatures below 110°C and the formation of stronger siloxane bonds above 110°C appear to be the main mechanisms responsible for the increase in the interface energy. After prolonged storage, interface bubbles are detectable by an infrared camera at the Si/Si bonding seam. Desorbed hydrocarbons as well as hydrogen generated by a reaction of water with silicon appear to be the major contents in the bubbles. Design guidelines for low temperature wafer direct bonding technology are proposed