The systematic synthesis of a systolic array of orthogonal and hyperbolic Householder processor elements for solving large (dense) systems of linear equations is described. The design procedure allows the design of an array which is independent of the size of the problem. The design stage for full problem size arrays was executed with the CAD tool SYSTARS. A special partitioning strategy is used to handle (virtually) infinitely large problems on a fixed-size array. Moreover, the partitioning maintains a high degree of pipelining of the data. A relatively simple architecture for the processor elements of the array is also presented. As a result of the systematic approach, a complete specification of the array is obtained in terms of its interconnections, processor elements, and controller.>

Most algorithms for high,quality modeling and coding of stochastic sequences (speech or images) make extensive use of matrix operations. Because of the high computational complexity of these operations, the use of conventional implementation techniques and architecture designs would almost certainly rule out such algorithms as candidates for real-time signal processing. In this paper, we present an algorithm and its mapping on a VLSI architecture for the solution ofN (n +1)by(n +1)systems of linear equations, which arise from a speech coding algorithm. The systems of equations form an ordered set of equations and they mutually exhibit rank 1 differences. This property is exploited to obtain concurrently the solution of all equations. Via an analysis of the algebraic structure of the systems of equations, we succeed in reducing the complexity to a single matrix inversion, while enhancing the regularity of the algorithm, e.g., by including the back substitution in the main factorization loop. Next, we proceed to map the algorithm on VLS1 hardware, using a very systematic hierarchical temporal/structural decomposition/ partitioning approach. To achieve high throughput, we make extensive use of pipelining and show how a pipelined CORDIC processor element supports the desired operations. The complete equation solver is build around two pipelined CORDIC processor elements and two FIFO-type memories. The solver fits on three VLSI chips of size 6.5*6.5 mm2in a standard-slow-NMOS technology. The chips are of medium complexity and the resulting floorplan is shown. The resulting architecture achieves a very high throughput with minimal dataflow-oriented hardware.

In this paper we report on the design of a high-speed VLSI system-solver for solving a set of systems of linear equations in fixed point arithmetic, concurrently and in real-time. The systems originate from a speech coding least-squares fitting problem. They are strongly coupled and can be jointly solved, when properly nested, by a recursive algorithm. This algorithm has a computational complexity not greater than in case of a single system with multiple inhomogeneous terms. The algorithm exhibits sufficient structure and concurrency, which are exploited for its mapping on a fast VLSI system-solver. The mapping is carried out systematically by a strict-hierarchical temporal and local decomposition of the algorithm. Estimates show that the solver fits on 3 VLSI chips, each of size 6.5 × 6.5 mm2. Two of these are pipelined CORDICs, the third is a FIFO-type memory chip. The expected robust behavior of the design has been confirmed through simulations at the register level.