Scheduling a system of nonsingular affine recurrence equations onto a processor array

Most work on the problem of scheduling computations onto a systolic array is restricted to systems of uniform recurrence equations. In this paper, this restriction is relaxed to include systems of affine recurrence equations. In this broader class, a sufficient condition is given for the system to be computable. Necessary and sufficient conditions are given for the existence of an affine schedule, along with a procedure that constructs the schedule vector, when one exists. This material is based upon work supported by the Office of Naval Research under contract nos. N00014-84-K-0664 and N00014-85-K-0553.     

The mapping of linear recurrence equations on regular arrays

The parallelization of many algorithms can be obtained using space-time transformations which are applied on nested do-loops or on recurrence equations. In this paper, we analyze systems of linear recurrence equations, a generalization of uniform recurrence equations. The first part of the paper describes a method for finding automatically whether such a system can be scheduled by an affine timing function, independent of the size parameter of the algorithm. In the second part, we describe a powerful method that makes it possible to transform linear recurrences into uniform recurrence equations. Both parts rely on results on integral convex polyhedra. Our results are illustrated on the Gauss elimination algorithm and on the Gauss-Jordan diagonalization algorithm. This work was partially funded by the French Coordinated Research ProgramC ³ and by a Grant from the SOREP company     

Finding Quadratic Schedules for Affine Recurrence Equations Via Nonsmooth Optimization

Frequently, affine recurrence equations can be scheduled more efficiently by quadratic scheduling functions than by linear scheduling functions. In this paper, the problem of finding optimal quadratic schedules for affine recurrence equations is formulated as a convex nonsmooth programming problem. In particular, sufficient constraints for causality are used generalizing Lamport's condition. In this way, the presented problem formulation becomes independent of the problem size. The research tool AQUAD is described implementing this problem formulation. Several nontrivial examples demonstrate that AQUAD can be effectively used to calculate quadratic schedules for affine recurrence equations. Finally, it is shown how array processors can be synthesized from affine recurrence equations which are scheduled by quadratic functions with a singular Hessian matrix.     

A parallel algorithm for evaluating general linear recurrence equations

A block parallel partitioning method for evaluating general linearmth order recurrence equations is presented and applied to solve the eigenvalues of symmetric tridiagonal matrices. The algorithm is based on partitioning, in a way that ensures load balance during computation. This method is applicable to both shared memory and distributed memory MIMD systems. The algorithm achieves a speedup ofO(p) on a parallel computer withp-fold parallelism, which is linear and is greater than the existing results, and the data communication between processors is less than that required for other methods. For solving symmetric tridiagonal eigenvalue problems, our method is faster than the best previous results. The results were tested and evaluated on an MIMD machine, and were within 79% to 96% of the predicted performance for the second order linear recurrence problem.Supported by the Texas Advanced Technology Program under Grant No. 999903-165 and the National Science Foundation under Grant No. MIP8809328.     

Linear mappings ofn-dimensional uniform recurrences ontok-dimensional systolic arrays

We propose two methods for the synthesis of systolic arrays from uniform recurrence equations. First, we discuss a synthesis method for mappingn-dimensional uniform recurrence equations ontok-dimensional systolic arrays with a two-dimensional system clock. In this method we are led by the idea that all space-time conflicts caused by a scalar valued causal timing function and an allocation function can be rule out by a second scalar valued timing function. Stacking both timing functions yields a two-dimensional clock. Second, we develop a method to synthesizek-dimensional arrays with a scalar valued clock from a large subclass ofn-dimensional uniform recurrence equations containing important algorithms from signal and image processing. This method is based on a decomposition of the domain of the uniform recurrence equations into subdomains according to a given procesor allocation which allows the construction of a timing function for the whole domain from timing functions for the subdomains. In this way, the problem of finding optimal timing functions is reduced to finding optimal functions for the subdomains which are usually easier to establish. This synthesis method exhibits simplicity but its drawback lies in its limited applicability.     

Linear mappings ofn-dimensional uniform recurrences ontok-dimensional systolic arrays

We propose two methods for the synthesis of systolic arrays from uniform recurrence equations. First, we discuss a synthesis method for mappingn-dimensional uniform recurrence equations ontok-dimensional systolic arrays with a two-dimensional system clock. In this method we are led by the idea that all space-time conflicts caused by a scalar valued causal timing function and an allocation function can be rule out by a second scalar valued timing function. Stacking both timing functions yields a two-dimensional clock. Second, we develop a method to synthesizek-dimensional arrays with a scalar valued clock from a large subclass ofn-dimensional uniform recurrence equations containing important algorithms from signal and image processing. This method is based on a decomposition of the domain of the uniform recurrence equations into subdomains according to a given procesor allocation which allows the construction of a timing function for the whole domain from timing functions for the subdomains. In this way, the problem of finding optimal timing functions is reduced to finding optimal functions for the subdomains which are usually easier to establish. This synthesis method exhibits simplicity but its drawback lies in its limited applicability.     

Automatic temperature controller for multielement array hyperthermia systems

This paper concerns the optimization and performance analysis of an automatic control algorithm for managing power output of large multielement array hyperthermia applicators. Simulation and corresponding measurement of controller performance in a solid tissue equivalent phantom model is utilized for analysis of controller response to dynamically varying thermal load conditions that simulate clinical treatments. The analysis leads to an optimum controller which demonstrates the ability to achieve a uniform and stable temperature profile over a large surface area regardless of surrounding thermal load. This paper presents several advancements to the performance of a previously published control routine, including: 1) simplified simulation techniques for thorough characterization of controller performance; 2) an optimization procedure leading to an improved hybrid control algorithm for maintaining optimal performance during periods of both "rising" and "steady-state" temperature; 3) performance analysis of a control algorithm tailored for large area hyperthermia treatments with a mulitelement array applicator. The optimized hybrid controller is applied to the conformal microwave array (CMA) hyperthermia system previously developed for heating large area surface disease such as diffuse chestwall recurrence of breast carcinoma, and shown to produce stable, uniform temperatures under the multielement array applicator for all thermal load conditions.     

Initial conditions and initialization of linear fractional differential equations

Mastery of the initial conditions of fractional order systems remains an open problem, in spite of a great number of contributions. This paper proposes a solution dedicated to linear fractional differential equations (FDEs), which is based on an equivalence principle between the original system and an exactly equivalent infinite dimensional ordinary differential equation (ODE). This equivalence principle is derived from the fractional integration operator concept and the frequency distributed state space model of this operator. Thanks to this principle, the FDE initial conditions problem is converted into a conventional ODE initialization problem, however with an infinite dimensional state vector. Practical FDE initialization is performed using an observer based technique applied to the equivalent ODE; a numerical example demonstrates the efficiency of this approach.     

Synthesis of linear antenna arrays using Z transforms

It is well known that a linear antenna array with equally spaced elements can be represented by a polynomial whose roots correspond to the nulls of its antenna pattern. Since the linear array has equally spaced elements, its polynomial has only integral powers of the variable, so that the array can be represented by aZtransform. Therefore, the effect of moving roots of the polynomial can be represented as a linear sampled-data system problem, which is solved by using a table ofZtransforms or by discrete numerical convolution. In this paper, the quantitative effects on the array and its antenna pattern caused by moving roots of the polynomial are determined, and these effects are utilized for array synthesis to produce desired antenna patterns. Examples illustrating the use of this new synthesis technique include modification of a uniform array to obtain low sidelobes in the antenna pattern and synthesis of an array to produce nulls in its antenna pattern in the directions of discrete and spatially distributed interference sources.     

Synthesis of ASIC regular arrays for real-time image processing systems

In this paper the problems involved with high-level synthesis of ASIC regular arrays for real-time signal processing systems will be outlined. It will be shown that novel nonlinear, behavior preserving, transformations and extended affine mapping techniques are of key importance in mapping nonuniform recurrence equations on regular arrays with realistic constraints on area, throughput and I/O bandwidth.     

A Versatile Iterative Framework for the Reconstruction of Bandlimited Signals from Their Nonuniform Samples

In this paper, we study a versatile iterative framework for the reconstruction of uniform samples from nonuniform samples of bandlimited signals. Assuming the input signal is slightly oversampled, we first show that its uniform and nonuniform samples in the frequency band of interest can be expressed as a system of linear equations using fractional delay digital filters. Then we develop an iterative framework, which enables the development and convergence analysis of efficient iterative reconstruction algorithms. In particular, we study the Richardson iteration in detail to illustrate how the reconstruction problem can be solved iteratively, and show that the iterative method can be efficiently implemented using Farrow-based variable digital filters with few general-purpose multipliers. Under the proposed framework, we also present a completed and systematic convergence analysis to determine the convergence conditions. Simulation results show that the iterative method converges more rapidly and closer to the true solution (i.e. the uniform samples) than conventional iterative methods using truncation of sinc series.     

The injectivity of the canonical signal module for multidimensional linear systems of difference equations with variable coefficients

We consider discrete behaviors with varying coefficients. Our results are new also for one-dimensional systems over the time-axis of natural numbers and for varying coefficients in a field, we derive the results, however, in much greater generality: Instead of the natural numbers we use an arbitrary submonoid N of an abelian group, for instance the standard multidimensional lattice of r-dimensional vectors of natural numbers or integers. We replace the base field by any commutative self-injective ring F, for instance a direct product of fields or a quasi-Frobenius ring or a finite factor ring of the integers. The F-module W of functions from N to F is the canonical discrete signal module and is a left module over the natural associated noncommutative ring A of difference operators with variable coefficients. Our main result states that this module is injective and therefore satisfies the fundamental principle: An inhomogeneous system of linear difference equations with variable coefficients has a solution if and only if the right side satisfies the canonical compatibility conditions. We also show that for the typical cases of partial difference equations and in contrast to the case of constant coefficients the A-module W is not a cogenerator. We also generalize the standard one-dimensional theory for periodic coefficients to the multidimensional situation by invoking Morita equivalence.     

A modified likelihood function approach to DOA estimation in thepresence of unknown spatially correlated Gaussian noise using a uniformlinear array

The problem of modified ML estimation of DOAs of multiple source signals incident on a uniform linear array (ULA) in the presence of unknown spatially correlated Gaussian noise is addressed here. Unlike previous work, the proposed method does not impose any structural constraints or parameterization of the signal and noise covariances. It is shown that the characterization suggested here provides a very convenient framework for obtaining an intuitively appealing estimate of the unknown noise covariance matrix via a suitable projection of the observed covariance matrix onto a subspace that is orthogonal complement of the so-called signal subspace. This leads to a formulation of an expression for a so-called modified likelihood function, which can be maximized to obtain the unknown DOAs. For the case of an arbitrary array geometry, this function has explicit dependence on the unknown noise covariance matrix. This explicit dependence can be avoided for the special case of a uniform linear array by using a simple polynomial characterization of the latter. A simple approximate version of this function is then developed that can be maximized via the-well-known IQML algorithm or its variants. An exact estimate based on the maximization of the modified likelihood function is obtained by using nonlinear optimization techniques where the approximate estimates are used for initialization. The proposed estimator is shown to outperform the MAP estimator of Reilly et al. (1992). Extensive simulations have been carried out to show the validity of the proposed algorithm and to compare it with some previous solutions     

A broadcast reference technique for self-calibrating of largeantenna phased arrays

A modified phase-multilateration technique is proposed for calibrating the element locations of a flexible phased array. The technique requires several auxiliary beacons. The calibrating system measures the phase, relative to a broadcast reference, of each beacon signal at each array element. Automatic calibration of the differential phase delay in each antenna element signal path is included in the self-survey process. Digital beamforming is used for array signal processing. The beacon locations can be accurately or loosely known. For the system with loosely known beacon locations, an additional baseline measurement is required, and the beacon locations are treated as unknown variables. It is shown that a simple variable transformation can transform the mathematical equations of this technique into a form identical to that of the corresponding equations of previous cabled reference systems. The mathematical properties of the algorithm and its associated tolerance analysis are therefore readily available. A combination of the versions of this technique with accurately known and loosely known beacon locations is shown to have better performance than the individual version     

A hybrid projection method for analysis of waveguide arrays with protruding dielectric elements: A 3D problem

The method proposed for solution of 2D problems is extended to solution of a 3D problem for an array of circular waveguides with protruding cylinder-conical dielectric rods. The transverse electromagnetic field in the domain containing the rods is expanded into a series of vector functions of a Floquet channel. The series contains variable coefficients whose values are determined from solution of a system of ordinary differential equations derived upon projection of the Maxwell equations onto the same vector functions. The differential equations are transformed into algebraic equations via application of a 1D finite-element method and matching of fields with waveguide and spatial harmonics on the boundaries of this domain. The results of numerical solution of the obtained algebraic system are used for calculation of the array characteristics, which are compared to the data published in the literature and the experimental results available for several particular cases.     

非周期扩频系统中基于均匀圆阵的角度和时延的联合估计

该文通过空域匹配滤波器,将阵元空间中的均匀圆阵转化为波束空间中的均匀线阵,并将时空匹配滤波器的输出转换到频域,利用 DOA Matrix方法解决了非周期扩频系统中均匀圆阵条件下多径信号的角度和时延的联合估计问题及常规空域处理方法中多径数不能大于阵元数的问题。理论分析和仿真实验结果表明,该方法是一种无偏估计,且其估计精度远远高于滑动相关方法。     

Direction of arrival estimation for more correlated sources than active sensors

In this paper, a new direction of arrival (DOA) estimation method for more correlated sources than active receiving antennas is proposed. The trick to solve this problem using only second-order statistics is to consider a periodic scanning of an underlying uniform array, where a single scanning period contains several time slots and in different time slots different sets of antennas are activated leading to a dynamic non-uniform array with possibly less active antennas than sources in each time slot. We collect the spatial correlation matrices of the active antenna arrays for all time slots and are able to present them as a linear function of the spatial correlation matrix of the underlying array. We provide a necessary and sufficient condition for this system of equations to be full column-rank, which allows for a least squares (LS) reconstruction of the spatial correlation matrix of the underlying array. Some practical greedy algorithms are presented to design dynamic arrays satisfying this condition. In a second step, we use the resulting spatial correlation matrix of the underlying array to estimate the DOAs of the possibly correlated sources by spatial smoothing and MUSIC. Alternatively, we can express this matrix as a linear function of the correlation matrix of the sources (incoming signals) at a grid of investigated angles, and solve this system of equations using either LS or sparsity-regularized LS (possibly assisted by additional constraints), depending on the grid resolution compared to the number of antennas of the underlying array.