Recently, publications by Fettweis, et al. (1991) have divulged a new technique for simulating systems of partial differential equations (PDEs) in discrete space-time. This technique, based upon multi-dimensional wave digital structures, holds much promise for the stable simulation of systems of PDEs that model critical physical phenomena. To date, however, little has been published concerning handling other than the simplest types of boundary conditions for such systems. Here, in the one-dimensional transmission line case, is presented a straight-forward method for accommodating general, lumped, linear boundary terminations that appears to be extendable to higher dimensions.

Multi-dimensi onal (MD) systems are widely used in scienti c applications such as image processing, geophysical signal processing and uid dynamics.Earlier scheduling methods in synthesizing MD systems do not explore loop pipelinin g across dierent dimensions.This paper explores the basic properties of MD loop pipelini ng and presents an algorithm, called multi-dimensional r otation scheduling, to nd an ecient s c hedule based on the multi-dimensional retiming technique we developed.The description and the correctness of our algorithm are presented in the paper.The experiments show that our algorithm can achieve optimal results ecien tly.

The use of massive parallelism in solving Partial Differential Equations (PDEs) has been studied for a long time. Fettweis and Nitache (1991) introduced a new method of transforming a PDE problem in a set of computational nodes represented by wave digital filters working in a multidimensional environment. Those computational nodes may not be mapped one-to-one to processor elements. After the nodes are partitioned into blocks, this paper introduces the concept of transforming such blocks to multidimensional data flow graphs, and an algorithm to obtain a final execution schedule with an optimal performance by using multidimensional retiming. The method is applicable to any uniformly represented data dependence graph and the Fettweis and Nitache method was chosen as an interesting example of its application.>

When designing a pipelined digital system, delay buffers (often implemented as shift registers) are usually introduced into the system in order to synchronize the various signals impinging on each and every processing element. By thus insuring that all related inputs to each processing element arrive at precisely the same time, additional memory for this purpose need not be included within the processing elements themselves. The design of these elements may therefore be carried out independently of the topologies of the systems within which they will ultimately appear. Clearly, any solution to this synchronization problem is not likely to be unique; that is, there will usually exist many combinations of buffer locations and lengths that can produce overall input data synchronization in a typical pipelined network. When selecting one solution from many available solutions, it is natural to observe that it would be beneficial to implement a solution that makes use of the minimum number of total delay buffer stages necessary to produce synchronization in order that the system hardware cost and complexity may be reduced. In this paper, we present a technique to solve this delay buffer problem in polynomial time. Unlike other polynomial-time methods, this approach solves both the pipeline synchronization and buffer minimization problems within a single formulation. Furthermore, this technique is readily extended to handle pipelined systems containing feedback loops as well as processing elements whose fanout loads are greater than one. It has been used in a synthesis design environment.>

When designing a pipelined digital system, dekay buffers (often implemented as shifr registers) are usually introduced into the system in order to synchronize the various signals impinging on each processing element. That is, to insure that all inputs to a processing block arrive at precisely the same time. Automatic techniques for finding the lengths of such buffers, and their proper points of insertion in the system, have been proposed. They are usually bared on graph-theoretic approaches. [l-31. However, the solution to this synchronization problem is not Imique. so there exist many combinations of buffer locatim and length that can produce overall synchronization in a typical pipelined network. Obviously. it would be beneficial to determine the minimum number of total delay buffer stages necessary to s)mchronize a pipelined system, so that the system hardware cost and complexity can be reduced. In this paper. we present an algorithm to solve this buffer minimization problem. We will show that it can be recast in term of the clarsical minimum cost network flow problem. Hence, the time complexity of our algorithm is polynomial rather than exponential as for the algorithm reported in 141. Our technique is qplicable to system con%aining feedback Imps, but in the interest 4 brevity in this article we will treat only the most common case in which our wderlying system graphs are acyclic. The algorithm has been used in a silicon compiler design environment described in [SI.

The design of a block floating-point hardware CORDIC unit intended for use in large single-chip systems of CORDIC processors is described. More than 100 of these processors should be able to fit onto a single chip in today's CMOS technology. This processor is fully programmable in function. That is, by modifying a few programming bits, one may evaluate any of the operations native to the CORDIC algorithm plus others such as square root, exponential, and logarithm. Connections between these CORDIC units in a single-chip system would also be programmable. From this basic operations set, small networks of CORDIC processors may be constructed to implement a wide range of mathematical functions including roots and powers, as well as the inverse trigonometrics and hyperbolics.>

The limitations on the numerical values of the functional arguments that are passed to the CORDIC computational units are discussed, with a special emphasis on the binary, fixed-point hardware implementation. Research in the area of expanding the allowed ranges of the input variables for which accurate output values can be obtained is presented. The methods proposed to expand the range of convergence for the CORDIC algorithm do not necessitate any unwidely overhead calculation, thus making this work amenable to a hardware implementation. The number of extra iterations introduced in the modified CORDIC algorithms is significantly less than the number of extra iterations discussed elsewhere. This reduction in the number of extra iterations will lead to a faster hardware implementation. Examples demonstrate the usefulness of the methods in realistic situations.>

C.S.G. Lee and P.R. Chang (1986) have shown how the mathematical and nonlinear function evaluation operations involved in the inverse kinematic solution for a six-joint manipulator could be re-expressed and reordered so as to allow their evaluation by an interconnection of CORDIC processors. The present authors describe the use of specialized, dedicated CORDIC processors, implemented in bit-serial form, to construct an inverse kinematics computational unit on a single VLSI chip.>

A useful class of digital filters is the rank order filter, of which the median filter is the most popular. This paper details the NMOS IC design of a 6-bit rank order filter based upon the approach of Fitch, Coyle, and Gallagher. The chip provides for programmable window lengths of 3, 5, 7, and 9; the selection of any element in the rank order; operation in the nonrecursive or recursive modes; and the ability to function in a "ganged" mode so that two or more identical chips can accommodate samples of length seven or eight bits.

A spatial domain image coding method which is computationally straightforward and requires only one pass through the incoming data is presented. The technique is based on approximating a near-optimal three-level uniform quantizer over a spatially local region of the image. This method can maintain single pixel resolution and is therefore applicable to wide bandwidth data. Results of applying this procedure to a variety of images are given, along with comparisons to some other image coding techniques. A variablelength code word version providing increased compression is also developed.