Optimal algorithms for the channel-assignment problem on a reconfigurable array of processors with wider bus networks

The computation model on which the algorithms are developed is the reconfigurable array of processors with wider bus networks (abbreviated to RAPWBN). The main difference between the RAPWBN model and other existing reconfigurable parallel processing systems is that the bus width of each network is bounded within the range [2,[/spl radic/(N)]]. Such a strategy not only saves the silicon area of the chip as well as increases the computational power enormously, but the strategy also allows the execution speed of the proposed algorithms to be tuned by the bus bandwidth. To demonstrate the computational power of the RAPWBN, the channel-assignment problem is derived in this paper. For the channel-assignment problem with N pairs of components, we first design an O(T + [N//spl omega/]) time parallel algorithm using 2N processors with a 2N-row by 2N-column bus network, where the bus width of each bus network is /spl omega/-bit for 2 /spl les/ /spl omega/ /spl les/ [/spl radic/N] and T = [log/sub /spl omega//N] + 1. By tuning the bus bandwidth to the natural log N-bit and the extended N/sup 1/c/-bit (N/sup 1/c/ > log N) for any constant c and c /spl ges/ 1, two more results which run in O(log N/log log N) and O(1) time, respectively, are also derived. When compared to the algorithms proposed by Olariu et al. [17] and Lin [14], it is shown that our algorithm runs in the equivalent time complexity while significantly reducing the number of processors to O(N).     

Hypercube computations on partitioned optical passive stars networks

This paper shows that an n=2/sup k/ processor partitioned optical passive stars (POPS) network with g groups and d processors per group can simulate every bidirectional move of an n processor hypercube using one slot when dg. Moreover, the same POPS network can simulate every monodirectional move of a processor hypercube using one slot when d=g. All these results are shown to be optimal. Our simulations improve on the literature whenever d/spl ne/g and directly yield several important consequences. For example, as a direct consequence of our simulations, a POPS network, n=dg and d相似文献   

Crossover frequency limitations in MIMO nonminimum phase feedback systems

This paper investigates limitations and design tradeoffs of the closed-loop sensitivity/performance of linear-time-invariant nonminimum-phase uncertain multiple-input-multiple-output plants, with I inputs and m outputs, where m /spl les/ l. It is shown that if rows i/sub 1/...,i/sub k/ of the plant transfer function form a k /spl times/ l nonminimum phase transfer matrix, and if the design is such that the sensitivity gain of k - 1 rows among the rows i/sub 1/,...,i/sub k/ of the closed-loop transfer function is low, then by necessity the sensitivity gain of the remaining row is high. This sensitivity constraint is quantified with the help of the crossover frequency restriction of a specially constructed single-input-single-output transfer function that includes the right half plane zeros and poles of the k /spl times/ l transfer matrix.     

A residue number system on reconfigurable mesh with applications to prefix sums and approximate string matching

Several new number representations based on a residue number system are presented which use the smallest prime numbers as moduli and are suited for parallel computations on a reconfigurable mesh architecture. The bit model of linear reconfigurable mesh with exclusive write and unit-time delay for broadcasting on a subbus is assumed. It is shown how to convert in O(1) time any integer, ranging between 0 and n-1, from any commonly used representation to any new representation proposed in this paper (and vice versa) using an n/spl times/O(log/sup 2/ n/log log n) reconfigurable mesh. In particular, some of the previously known conversion techniques are improved. Moreover, as a byproduct, it is shown how to compute in O(1) time the Prefix Sums of n bits by a reconfigurable mesh having the above mentioned size, thus improving previously known results. Applications to the Prefix Sums of n h-bit integers and to Approximate String Matching with /spl alpha/ mismatches are also considered. The Summation and the Prefix Sums can be computed in O(1) time using O(h log N+log/sup 2/ N/log log N)/spl times/Nh and O(h/sup 2/+log/sup 2/ N/log(h+log N))/spl times/O(N(h+log N)) reconfigurable meshes, respectively. Moreover, it is shown for the first time how to find in O(1) time all the occurrences of a pattern of length m in a text of length n, allowing less than /spl alpha/ mismatches, using a reconfigurable mesh of size O(m log|/spl Sigma/|)/spl times/O (n(log|/spl Sigma/|+log/sup 2/ /spl alpha//log log /spl alpha/)), where the pattern and the text are strings over a finite alphabet /spl Sigma/ and /spl alpha/相似文献   

Scalable hardware-algorithms for binary prefix sums

We address the problem of designing efficient and scalable hardware-algorithms for computing the sum and prefix sums of a w^k -bit, (k⩾2), sequence using as basic building blocks linear arrays of at most w² shift switches, where w is a small power of 2. An immediate consequence of this feature is that in our designs broadcasts are limited to buses of length at most w². We adopt a VLSI delay model where the “length” of a bus is proportional with the number of devices on the bus. We begin by discussing a hardware-algorithm that computes the sum of a w^k-bit binary sequence in the time of 2k-2 broadcasts, while the corresponding prefix sums can be computed in the time of 3k-4 broadcasts. Quite remarkably, in spite of the fact that our hardware-algorithm uses only linear arrays of size at most w², the total number of broadcasts involved is less than three times the number required by an “ideal” design. We then go on to propose a second hardware-algorithm, operating in pipelined fashion, that computes the sum of a kw²-bit binary sequence in the time of 3k+[log_w k]=3 broadcasts. Using this design, the corresponding prefix sums can be computed in the time of 4k+[log_w k]-5 broadcasts     

Optimal quantization of periodic task requests on multiple identical processors

We simplify the periodic tasks scheduling problem by making a trade off between processor load and computational complexity. A set N of periodic tasks, each characterized by its density /spl rho//sub i/, contains n possibly unique values of /spl rho//sub i/. We transform N through a process called quantization, in which each /spl rho/i /spl isin/ N is mapped onto a service level s/sub j/ /spl isin/ L, where |L| = l /spl Lt/ n and /spl rho//sub i/ /spl les/ s/sub j/, (this second condition differentiates this problem from the p-median problem on the real line). We define the periodic task quantization problem with deterministic input (PTQ-D) and present an optimal polynomial time dynamic programming solution. We also introduce the problem PTQ-S (with stochastic input) and present an optimal solution. We examine, in a simulation study, the trade off penalty of excess processor load needed to service the set of quantized tasks over the original set, and find that, through quantization onto as few as 15 or 20 service levels, no more than 5 percent processor load is required above the amount requested. Finally, we demonstrate that the scheduling of a set of periodic tasks is greatly simplified through quantization and we present a fast online algorithm that schedules quantized periodic tasks.     

Designing asymmetric Hopfield-type associative memory with higher order hamming stability

The problem of optimal asymmetric Hopfield-type associative memory (HAM) design based on perceptron-type learning algorithms is considered. It is found that most of the existing methods considered the design problem as either 1) finding optimal hyperplanes according to normal distance from the prototype vectors to the hyperplane surface or 2) obtaining weight matrix W=[w/sub ij/] by solving a constraint optimization problem. In this paper, we show that since the state space of the HAM consists of only bipolar patterns, i.e., V=(v/sub 1/,v/sub 2/,...,v/sub N/)/sup T//spl isin/{-1,+1}/sup N/, the basins of attraction around each prototype (training) vector should be expanded by using Hamming distance measure. For this reason, in this paper, the design problem is considered from a different point of view. Our idea is to systematically increase the size of the training set according to the desired basin of attraction around each prototype vector. We name this concept the higher order Hamming stability and show that conventional minimum-overlap algorithm can be modified to incorporate this concept. Experimental results show that the recall capability as well as the number of spurious memories are all improved by using the proposed method. Moreover, it is well known that setting all self-connections w/sub ii//spl forall/i to zero has the effect of reducing the number of spurious memories in state space. From the experimental results, we find that the basin width around each prototype vector can be enlarged by allowing nonzero diagonal elements on learning of the weight matrix W. If the magnitude of w/sub ii/ is small for all i, then the condition w/sub ii/=0/spl forall/i can be relaxed without seriously affecting the number of spurious memories in the state space. Therefore, the method proposed in this paper can be used to increase the basin width around each prototype vector with the cost of slightly increasing the number of spurious memories in the state space.     

Many-to-many disjoint path covers in hypercube-like interconnection networks with faulty elements

A many-to-many k-disjoint path cover (k-DPC) of a graph G is a set of k disjoint paths joining k distinct source-sink pairs in which each vertex of G is covered by a path. We deal with the graph G/sub 0/ /spl oplus/ G/sub 1/ obtained from connecting two graphs G/sub 0/ and G/sub 1/ with n vertices each by n pairwise nonadjacent edges joining vertices in G/sub 0/ and vertices in G/sub 1/. Many interconnection networks such as hypercube-like interconnection networks can be represented in the form of G/sub 0/ /spl oplus/ G/sub 1/ connecting two lower dimensional networks G/sub 0/ and G/sub 1/. In the presence of faulty vertices and/or edges, we investigate many-to-many disjoint path coverability of G/sub 0/ /spl oplus/ G/sub 1/ and (G/sub 0/ /spl oplus/ G/sub 1/) /spl oplus/ (G/sub 2/ /spl oplus/ G/sub 3/ ), provided some conditions on the Hamiltonicity and disjoint path coverability of each graph G/sub i/ are satisfied, 0 /spl les/ i /spl les/ 3. We apply our main results to recursive circulant G(2/sup m/, 4) and a subclass of hypercube-like interconnection networks, called restricted HL-graphs. The subclasses includes twisted cubes, crossed cubes, multiply twisted cubes, Mobius cubes, Mcubes, and generalized twisted cubes. We show that all these networks of degree m with f or less faulty elements have a many-to-many k-DPC joining any k distinct source-sink pairs for any k /spl ges/ 1 and f /spl ges/ 0 such that f+2k /spl les/ m - 1.     

Channel assignment with separation for interference avoidance in wireless networks

Given an integer /spl sigma/>1, a vector (/spl delta//sub 1/, /spl delta//sub 2/,..., /spl delta//sub /spl sigma/-1/), of nonnegative integers, and an undirected graph G=(V, E), an L(/spl delta//sub 1/, /spl delta//sub 2/,..., /spl delta//sub /spl sigma/-1/)-coloring of G is a function f from the vertex set V to a set of nonnegative integers, such that |f(u)-f(v)|/spl ges//spl delta//sub i/, if d(u,v)=i, for 1相似文献   

Should model-based inverse inputs be used as feedforward under plant uncertainty?

Bounds on the size of the plant uncertainties are found such that the use of the inversion-based feedforward input improves the output-tracking performance when compared to the use of feedback alone. The output-tracking error is normalized by the size of the desired output and used as a measure of the output tracking performance. The worst-case performance is compared for two cases: (1) with the use of feedback alone and (2) with the addition of the feedforward input. It is shown that inversion-based feedforward controllers can lead to performance improvements at frequencies w where the uncertainty /spl Delta/ (jw) in the nominal plant is smaller than the size of the nominal plant G/sub 0/(jw) divided by its condition number K/sub G0/ (jw), i.e., /spl par//spl Delta/(jw)/spl par//sub 2/ < /spl par/G/sub 0/(jw) /spl par//sub 2//k/sub G0/ (jw). A modified feedforward input is proposed that only uses the model information in frequency regions where plant uncertainty is sufficiently small. The use of this modified inverse with (any) feedback results in improvement of the output tracking performance, when compared to the use of the feedback alone.     

Remarks on the L/sup p/-input converging-state property

Let X /spl sub/ /spl Ropf//sup N/ and consider a system x/spl dot/ = f(x,u), f : X /spl times/ /spl Ropf//sup M/ /spl rarr/ /spl Ropf//sup N/, with the property that the associated autonomous system x/spl dot/ = f (x,0) has an asymptotically stable compactum C with region of attraction A. Assume that x is a solution of the former, defined on [0,/spl infin/), corresponding to an input function u. Assume further that, for each compact K /spl sub/ X, there exists k > 0 such that |f(z,v) - f(z,0)| /spl les/ k|v| for all (z,v) /spl isin/ /spl times/ /spl Ropf//sup M/. A simple proof is given of the following L/sup p/-input converging-state property: if u /spl isin/ L/sup p/ for some p /spl isin/ [1,/spl infin/) and x has an /spl omega/-limit point in A, then x approaches C.     

Robust H/sub /spl infin// control for uncertain discrete-time-delay fuzzy systems via output feedback controllers

This work investigates the problem of robust output feedback H/sub /spl infin// control for a class of uncertain discrete-time fuzzy systems with time delays. The state-space Takagi-Sugeno fuzzy model with time delays and norm-bounded parameter uncertainties is adopted. The purpose is the design of a full-order fuzzy dynamic output feedback controller which ensures the robust asymptotic stability of the closed-loop system and guarantees an H/sub /spl infin// norm bound constraint on disturbance attenuation for all admissible uncertainties. In terms of linear matrix inequalities (LMIs), a sufficient condition for the solvability of this problem is presented. Explicit expressions of a desired output feedback controller are proposed when the given LMIs are feasible. The effectiveness and the applicability of the proposed design approach are demonstrated by applying this to the problem of robust H/sub /spl infin// control for a class of uncertain nonlinear discrete delay systems.     

H/sub /spl infin// control for discrete-time nonlinear stochastic systems

In this note, we develop an H/sub /spl infin//-type theory for a large class of discrete-time nonlinear stochastic systems. In particular, we establish a bounded real lemma (BRL) for this case. We introduce the notion of stochastic dissipative systems, analogously to the familiar notion of dissipation associated with deterministic systems, and utilize it in the derivation of the BRL. In particular, this BRL establishes a necessary and sufficient condition, in terms of a certain Hamilton Jacobi inequality (HJI), for a discrete-time nonlinear stochastic system to have l/sub 2/-gain/spl les//spl gamma/. The time-invariant case is also considered as a special case. In this case, the BRL guarantees necessary and sufficient conditions for the system to have l/sub 2/-gain/spl les//spl gamma/, by means of a solution to a certain algebraic HJI. An application of this theory to a special class of systems which is a characteristic of numerous physical systems, yields a more tractable HJI which serves as a sufficient condition for the underlying system to possess l/sub 2/-gain/spl les//spl gamma/. Stability in both the mean square sense and in probability, is also discussed. Systems that possess a special structure (norm-bounded) of uncertainties in their model are considered. Application of the BRL to this class of systems yields a linear state-feedback stabilizing controller which achieves l/sub 2/-gain/spl les//spl gamma/, by means of certain linear matrix inequalities (LMIs).     

Designing and learning of adjustable quasi-triangular norms with applications to neuro-fuzzy systems

We introduce a new class of operators called quasi-triangular norms. They are denoted by H and parameterized by a parameter /spl nu/:H(a/sub 1/,a/sub 2/,...,a/sub n/;/spl nu/). From the construction of function H, it follows that it becomes a t-norm for /spl nu/=0 and a dual t-conorm for /spl nu/=1. For /spl nu/ close to 0, function H resembles a t-norm and for /spl nu/ close to 1, it resembles a t-conorm. In the paper, we also propose adjustable quasi-implications and a new class of neuro-fuzzy systems. Most neuro-fuzzy systems proposed in the past decade employ "engineering implications" defined by a t-norm as the minimum or product. In our proposition, a quasi-implication I(a,b;/spl nu/) varies from an "engineering implication" T{a,b} to corresponding S-implication as /spl nu/ goes from 0 to 1. Consequently, the structure of neuro-fuzzy systems presented in This work is determined in the process of learning. Learning procedures are derived and simulation examples are presented.     

Constructing edge-disjoint spanning trees in product networks

A Cartesian product network is obtained by applying the cross operation on two graphs. We study the problem of constructing the maximum number of edge-disjoint spanning trees (abbreviated to EDSTs) in Cartesian product networks. Let G=(V/sub G/, E/sub G/) be a graph having n/sub 1/ EDSTs and F=(V/sub F/, E/sub F/) be a graph having n/sub 2/ EDSTs. Two methods are proposed for constructing EDSTs in the Cartesian product of G and F, denoted by G/spl times/F. The graph G has t/sub 1/=|E/sub G/|/spl middot/n/sub 1/(|V/sub G/|-1) more edges than that are necessary for constructing n/sub 1/ EDSTs in it, and the graph F has t2=|E/sub F/'-n/sub 2/(|V/sub F/|-1) more edges than that are necessary for constructing n/sub 2/ EDSTs in it. By assuming that t/sub 1//spl ges/n/sub 1/ and t/sub 2//spl ges/n/sub 2/, our first construction shows that n/sub 1/+n/sub 2/ EDSTS can be constructed in G/spl times/F. Our second construction does not need any assumption and it constructs n/sub 1/+n/sub 2/-1 EDSTs in G/spl times/F. By applying the proposed methods, it is easy to construct the maximum numbers of EDSTs in many important Cartesian product networks, such as hypercubes, tori, generalized hypercubes, mesh connected trees, and hyper Petersen networks.     

A condition number for point matching with application to registration and postregistration error estimation

Selecting salient points from two or more images for computing correspondence is a well-studied problem in image analysis. This paper describes a new and effective technique for selecting these tiepoints using condition numbers, with application to image registration and mosaicking. Condition numbers are derived for point-matching methods based on minimizing windowed objective functions for 1) translation, 2) rotation-scaling-translation (RST), and 3) affine transformations. Our principal result is that the condition numbers satisfy K/sub Trans/ /spl les/ K/sub RST/ /spl les/ K/sub Affine/. That is, if a point is ill-conditioned with respect to point-matching via translation, then it is also unsuited for matching with respect to RST and affine transforms. This is fortunate since K/sub Trans/ is easily computed whereas K/sub RST/ and K/sub Affine/ are not. The second half of the paper applies the condition estimation results to the problem of identifying tiepoints in pairs of images for the purpose of registration. Once these points have been matched (after culling outliers using a RANSAC-like procedure), the registration parameters are computed. The postregistration error between the reference image and the stabilized image is then estimated by evaluating the translation between these images at points exhibiting good conditioning with respect to translation. The proposed method of tiepoint selection and matching using condition number provides a reliable basis for registration. The method has been tested on a large number of diverse collection of images - multidate Landsat images, aerial images, aerial videos, and infrared images. A Web site where the users can try our registration software is available and is being actively used by researchers around the world.     

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.     

Application of the theory of optimal experiments to adaptive electromagnetic-induction sensing of buried targets

A mobile electromagnetic-induction (EM I) sensor is considered for detection and characterization of buried conducting and/or ferrous targets. The sensor maybe placed on a robot and, here, we consider design of an optimal adaptive-search strategy. A frequency-dependent magnetic-dipole model is used to characterize the target at EMI frequencies. The goal of the search is accurate characterization of the dipole-model parameters, denoted by the vector /spl Theta/; the target position and orientation are a subset of /spl Theta/. The sensor position and operating frequency are denoted by the parameter vector p and a measurement is represented by the pair (p, O), where O denotes the observed data. The parameters p are fixed for a given measurement, but, in the context of a sequence of measurements p may be changed adaptively. In a locally optimal sequence of measurements, we desire the optimal sensor parameters, p/sub N+1/ for estimation of /spl Theta/, based on the previous measurements (p/sub n/, O/sub n/)/sub n=1,N/. The search strategy is based on the theory of optimal experiments, as discussed in detail and demonstrated via several numerical examples.     

Robust H/sub /spl infin// and mixed H/sub 2//H/sub /spl infin// filters for equalization designs of nonlinear communication systems: fuzzy interpolation approach

Generally, it is difficult to design equalizers for signal reconstruction of nonlinear communication channels with uncertain noises. In this paper, we propose the H/sub /spl infin// and mixed H/sub 2//H/sub /spl infin// filters for equalization/detection of nonlinear channels using fuzzy interpolation and linear matrix inequality (LMI) techniques. First, the signal transmission system is described as a state-space model and the input signal is embedded in the state vector such that the signal reconstruction (estimation) design becomes a nonlinear state estimation problem. Then, the Takagi-Sugeno fuzzy linear model is applied to interpolate the nonlinear channel at different operation points through membership functions. Since the statistics of noises are unknown, the fuzzy H/sub /spl infin// equalizer is proposed to treat the state estimation problem from the worst case (robust) point of view. When the statistics of noises are uncertain but with some nominal (or average) information available, the mixed H/sub 2//H/sub /spl infin// equalizer is employed to take the advantage of both H/sub 2/ optimal performance with nominal statistics of noises and the H/sub /spl infin// robustness performance against the statistical uncertainty of noises. Using the LMI approach, the fuzzy H/sub 2//H/sub /spl infin// equalizer/detector design problem is characterized as an eigenvalue problem (EVP). The EVP can be solved efficiently with convex optimization techniques.