Daedalus is a system-level design flow for the design of multiprocessor system-on-chip (MP-SoC) based embedded multimedia systems. It offers a fully integrated tool-flow in which design space exploration (DSE), system-level synthesis, application mapping, and system prototyping of MP-SoCs are highly automated. In this paper, we describe our first industrial deployment experiences with the Daedalus framework. Daedalus is currently being deployed in the early stages of the design of an image compression system for very high resolution cameras targeting medical appliances. In this context, we performed a DSE study with a JPEG encoder application, which exploits both task and data parallelism. This application was mapped onto a range of different MP-SoC architectures. We achieved a performance speed-up of up to 20x compared to a single processor system. In addition, the results show that the Daedalus high-level MP-SoC models accurately predict the overall system performance, i.e., the performance error is around 5%.

For modern embedded systems in the realm of high-throughput multimedia, imaging, and signal processing, the complexity of embedded applications has reached a point where the performance requirements of these applications can no longer be supported by embedded system architectures based on a single processor. Thus, the emerging embedded system-on-chip platforms are increasingly becoming multiprocessor architectures. As a consequence, two major problems emerge, namely how to design and how to program such multiprocessor platforms in a systematic and automated way in order to reduce the design time and to satisfy the performance needs of applications executed on such platforms. As an efficient solution to these two problems, in this paper, we present the methodology and techniques implemented in a tool called Embedded System-level Platform synthesis and Application Mapping (ESPAM) for automated multiprocessor system design, programming, and implementation. ESPAM moves the design specification and programming from the Register Transfer Level and low-level C to a higher system level of abstraction. We explain how, starting from system-level platform, application, and mapping specifications, a multiprocessor platform is synthesized, programmed, and implemented in a systematic and automated way. The class of multiprocessor platforms we consider is introduced as well. To validate and evaluate our methodology, we used ESPAM to automatically generate and program several multiprocessor systems that execute three image processing applications, namely Sobel edge detection, Discrete Wavelet Transform, and Motion JPEG encoder. The performance of the systems that execute these applications is also presented in this paper.

The complexity of today's embedded applications requires modern high-performance embedded System-on-Chip (SoC) platforms to be multiprocessor architectures. Advances in FPGA technology make the implementation of such architectures in a single chip (MP-SoC) feasible and very appealing. In recent years, the FPGA vendors integrated enormous amount of hardware resources in their FPGAs allowing larger and more complex MPSoCs to be built in their FPGA fabric. The main limitation on the size of an MPSoC that can be built in a single FPGA appears to be the amount of on-chip memory. To relax this limitation, the usage of external (off-chip) memory has to be considered. The state-of-the-art development tools support off-chip memory for (multi-master) shared bus architectures with arbitration of the memory accesses. Such architectures might be efficient for single processor systems however for multiprocessor systems the shared bus concept significantly limits the systems performance even if a DMA mechanism is used. In this paper we present our approach and interface when using an external memory for inter-processor data communication in multiprocessor platforms. We propose a hierarchical memory system with a programmable controller to transfer data between external and on-chip memories using a DMA mechanism. Our approach does not require arbitration which results in better overall performance. Results demonstrating the effectiveness of the proposed hierarchical memory system are presented as well.

New embedded signal-processing architectures are emerging that are composed of loosely coupled heterogeneous components like CPUs or DSPs, specialized IP cores, reconfigurable units, or memories. We believe that these architectures should be programmed using the process network model of computation. To ease the mapping of applications, we are developing the Compaan compiler that automatically derives a process network (PN) description from an application written in Matlab or C. In this paper, we investigate a particular problem in nested loop programs, which is about classifying the interprocess communication in the PN representation of the nested loop program. The global memory arrays present in the code have to be replaced by a distributed communication structure used for communicating data between the network processes. We show that four types of communication exist, each exhibiting different requirements when realizing them in hardware or software. We first present two compile time tests that are based on integer linear programming to decide the type of the communication. In the second part of this paper, we present alternative classification techniques that have polynomial complexity. However, in some cases, those techniques do not give a definitive answer and the ILP tests have to be applied. All present tests are combined in a hybrid classification scheme that correctly classifies the interprocess communication. In only 5% of the cases to classify, we have to rely on integer linear programming while, in the remaining 95%, the alternative techniques presented in this paper are able to correctly classify each case. The hybrid classification scheme has become an important part of our Compaan compiler.

Parameterized static affine nested loop programs can be automatically converted to input-output equivalent Kahn Process Network specifications. These networks turn out to be close relatives of parameterized cyclo-static dataflow graphs. Token production and consumption can be cyclic with a finite number of cycles or finite non-cyclic. Moreover the token production and consumption sequences are binary.

Emerging embedded System-on-Chip (SoC) platforms are increasingly becoming multiprocessor architectures. The advances in the FPGA chip technology make the implementation of such architectures in a single chip feasible and very appealing. Although the FPGA chip technology is well developed by companies such as Xilinx and Altera, the concepts and the necessary tool support for building multiprocessor systems on a single FPGA chip are still not mature enough. As a consequence, system designers experience significant difficulties in 1) designing multiprocessor systems on FPGAs in a short amount of time and 2) programming such systems in order to satisfy the performance needs of applications executed on them. In this paper we present our concept for multiprocessor system design, programing, and implementation that addresses and solves the above two problems in a particular way. We have implemented the concept in a tool called ESPAM which is briefly introduced as well. Also, we present some results obtained by applying our concept and ESPAM tool to automatically generate multiprocessor systems that execute a real-life application, namely a Motion-JPEG encoder.

Data-driven applications that are mapped onto large-scale systems need to be controlled for (re-)configuration, test and monitoring. Such systems consist of distributed and heterogeneous components. We specify the behavior of a control network independent of the system architecture and independent of the data-driven application. We address particularly the key problem of the interfacing between the control model and the data-driven application model.

The COMPAAN/LAURA (Stefanov et al., 2004) tool chain maps nested loop applications written in Matlab onto reconfigurable platforms, such as FPGAs. COMPAAN rewrites the original Matlab application as a process network in which the control is parameterized and distributed. This control is given as parameterized polytopes that are expressed in terms of pseudo-linear expressions. These expressions cannot always be mapped efficiently onto hardware as they contain multiplication and integer division operations. This obstructs the data flow through the processes. Therefore, we present in this paper the expression compiler that efficiently maps pseudo-linear expressions onto a dedicated hardware data-path in such a way that the distributed and parameterized control never obstructs the data flow through processors. This compiler employs techniques like number theory axioms, method of difference, and predicated static single assignment code.

Today's applications in the domains of multimedia, signal processing, etc. consist of a number of interacting components. If the way of interaction is determined at run time, we say that an application is non-static. In general, complex real-world applications are non-static. In this paper, we summarize a method for modeling and FPGA implementation of applications that have a specific type of non-static behavior. This method is based on program decomposition resulting in the generation of truly parameterized Kahn process networks and their mapping onto FPGAs. We automated the method by integrating it in our tools Compaan/Laura. The efficiency of our method is demonstrated by an implementation of a real-world application taken from the automotive domain.

At Leiden University, we are developing a design methodology that allows for fast mapping of nested-loop applications (e.g. DSP, imaging, or multimedia) written in a subset of Matlab onto reconfigurable devices. This design methodology is implemented into a tool chain that we call COM-PAAN/LAURA (Stefanov et al., 2004). This methodology generates a process network in which the inter-process communication takes place in a point-to-point fashion. Four types of point-to-point inter-processor communication exist in the PN. Two of them use a FIFO like communication and the other two use a cache like memory to exchange data. In this paper, we investigate the realizations for the four communication types and show that point-to-point communication at the level of scalars can be realized automatically and very efficiently in today's FPGAs.

New heterogeneous multiprocessor platforms are emerging that are typically composed of loosely coupled components that exchange data using programmable interconnections. The components can be CPUs or DSPs, specialized IP cores, reconfigurable units, or memories. To program such platform, we use the Process Network (PN) model of computation. The localized control and distributed memory are the two key ingredients of a PN allowing us to program the platforms. The localized control matches the loosely coupled components and the distributed memory matches the style of interaction between the components. To obtain applications in a PN format, we have built the Compaan compiler that translates affine nested-loop programs into functionally equivalent PNs. In this paper, we describe a novel analytical translation procedure we use in our compiler that is based on integer linear programming. The translation procedure consists of four main steps and we will present each step by describing the main idea involved, followed by a representative example.

New emerging embedded system platforms in the realm of high-throughput multimedia, imaging, and signal processing will consist of multiple microprocessors and reconfigurable components. One of the major problems is how to program these platforms in a systematic and automated way so as to satisfy the performance need of applications executed on these platforms. In this paper, we present our system design approach as an efficient solution to this programming problem. We show how for an application written in Matlab, a Kahn process network specification can automatically be derived and systematically mapped onto a target platform composed of a microprocessor and an FPGA. Furthermore, we illustrate how the mapping approach is applied on a real-life example, namely an M-JPEG encoder.

In industry, embedded systems for stream-based processing are often modelled and verified by using process networks, such as Kahn process networks. An advantage of Kahn networks is that they allow asynchronous operation of process components in a network. A problem in these networks, however, is that asynchronously interfering events cannot be handled properly because they are intrinsically indeterminate and therefore destroy the compositional properties of the network. We propose to extend the Kahn model of computations with a simple indeterminate construct. We call the resulting network a context-aware process network (CAPN). We show that these networks are capable of handling certain classes of events and can still be reduced to a class of parametrised Kahn networks.

The Compaan compiler framework automates the transformation of DSP applications written in Matlab into Kahn process networks (KPNs). These KPNs express the signal processing applications in a parallel distributed way, making them more suitable for mapping onto parallel architectures. A simple instance of a generated KPN by Compaan is a producer process that communicates with a consumer process via a FIFO buffer with the consumer reading data from the FIFO using a blocking read. When the sequence of producing data is different from the sequence of consuming data, a simple FIFO is not sufficient to implement the communication. For such a case, extra storage and control are needed at the consumer side. This paper presents a novel approach that determines at compile time whether a FIFO buffer is sufficient for every producer/consumer pair of a Compaan-generated KPN. For the case when the additional memory is required, we also provide an address generation mechanism at compile time. The presented approach is based on the Ehrhart theory.

Presents and evaluates the SPADE (System level Performance Analysis and Design space Exploration) methodology through an illustrative case study. SPADE is a method and tool for architecture exploration of heterogeneous signal processing systems. In this case study we start from an M-JPEG application and use SPADE to evaluate alternative multiprocessor architectures for implementing this application. SPADE follows the Y-chart paradigm for system level design; application and architecture are modeled separately and mapped onto each other in an explicit design step. SPADE permits architectures to be modeled at an abstract level using a library of generic building blocks, thereby reducing the cost of model construction and simulation. The case study shows that SPADE supports efficient exploration of candidate architectures; models can be easily constructed, modified and simulated in order to quickly evaluate alternative system implementations.

High level modeling and (quantitative) performance analysis of signal processing systems requires high level models for the applications (algorithms) and the implementations (architecture), a mapping of the former into the latter and a simulator for fast execution of the whole. Signal processing algorithms are very often nested-loop algorithms with a high degree of inherent parallelism. This paper presents-for such applications-suitable application and implementation models, a method to convert a given imperative executable specification to a specification in terms of the application model, a method to map this specification into an architecture specification in terms of the implementation model, and a method to analyze the performance through simulation. The methods and tools ore illustrated by means of an example.

High-resolution parameter estimation techniques have been applied to jointly estimate multiple signal parameters. We consider the problem of determining the directions and center frequencies of a number of narrow-band sources in a certain frequency band of interest. We present a joint angle-frequency estimation method, based on the multidimensional ESPRIT algorithm. A perturbation error analysis gives bounds on the parameter estimates, and provides optimal values for the temporal and spatial smoothing parameters. The analysis is shown to be consistent with simulation results.

Multi-resolution ESPRIT is an extension of the ESPRIT direction finding algorithm to antenna arrays with multiple baselines. A short (half wavelength) baseline is necessary to avoid aliasing, a long baseline is preferred for accuracy. The MR-ESPRIT algorithm allows to combine both estimates. The same algorithm can be used for multi-resolution frequency estimation, by combining two different sampling frequencies. We show how this can be used to construct a joint angle-frequency estimator.

Cordic based QRD-MVDR adaptive beamforming algorithms possess desirable properties for VLSI implementation such as regularity and good finite-word length behavior. But this algorithm suffers from a speed limitation constraint due to the presence of recursive operations in the algorithm. In this paper, a fine-grain pipelined CORDIC based QRD-MVDR adaptive beamforming algorithm is developed using the matrix lookahead technique. The proposed architecture can operate at arbitrarily high sample rates, and consists of only Givens rotations which can be mapped onto a Jacobi specific dataflow processor. It requires a complexity of O(M(p/sup 2/+Kp)) Givens rotations per sample time, where p is the number of antenna elements, K is the number of look direction constrains, and M is the pipelining level.

We present a numerically robust method for modeling audio signals which is based on a exponential data model. This model is a generalization of the classical sinusoidal model in the sense that it allows the amplitude of the sinusoids to evolve exponentially. We show that, using this model, so called attacks can be represented very efficiently and we propose an algorithm for finding the exponentials in a robust way. Moreover, we show that by using a proper segmentation of the input data into variable length segments the signal-to-noise ratio can be drastically improved as compared to a fixed-length analysis.

Introduces a new type of arithmetic operations that we have called "fast rotations" or "orthonormal /spl mu/-rotations". These are methods for orthonormal rotation over a set of fixed angles, with a very low cost in implementation-basically a few shift and add operations, as opposed to lengthy CORDIC operations. We also present the underlying theory for the construction of such fast rotation methods. Furthermore, we give examples where fast rotations have been applied successfully in a wide variety of applications. These include the low-cost and robust implementation of an FIR filter bank for image coding, the generation of spherical sample rays in 3D graphics, and the computation of the eigenvalue decomposition (EVD) and singular value decomposition (SVD).

In this paper we present an approach for quantitative analysis of application-specific dataflow architectures. The approach allows the designer to rate design alternatives in a quantitative way and therefore supports him in the design process to find better performing architectures. The context of our work is video signal processing algorithms which are mapped onto weakly-programmable, coarse-grain dataflow architectures. The algorithms are represented as Kahn graphs with the functionality of the nodes being coarse-grain functions. We have implemented an architecture simulation environment that permits the definition of dataflow architectures as a composition of architecture elements, such as functional units, buffer elements and communication structures. The abstract, clock-cycle accurate simulator has been built using a multi-threading package and employs object oriented principles. This results in a configurable and efficient simulator. Algorithms can subsequently be executed on the architecture model producing quantitative information for selected performance metrics. Results are presented for the simulation of a realistic application on several dataflow architecture alternatives, showing that many different architectures can be simulated in modest time on a modern workstation.

In this paper we present a strategy for determining a dataflow processor which is intended for the execution of Jacobi algorithms which are found in the application domain of array processing and other real-lime adaptive signal processing applications. Our strategy to determine a processor for their execution is to exploit the quasi regularity property in their dependence graph representations in search for what we call the Jacobi processor. This processor emerges from an exploration iteration which takes off from a processor template and a set of Jacobi algorithms. Based on qualitative and quantitative performance analysis, both the algorithms and the processor template are restructured towards improved execution performance. To ensure the mapper is part of the emerging processor specification, the algorithm-to-processor mapping method is included in the iterative and hierarchical exploration method. Processor's hierarchy exploits properties related to regularity in the algorithm's structure, allows gentle transitions from regular to irregular levels in the algorithm hierarchy and offers different control models for the irregular structures that appear at deeper levels of the hierarchy. Transformations aiming at reducing critical paths, increasing throughput, improving mapping efficiency and minimizing control and flow overheads are essential. They include retiming, pipelining and lookahead techniques.

We estimated the perceptual entropy rate of the phonemes of American English and found that the upper limit of the perceptual entropy of voiced phonemes is approximately 1.4 bit/sample, whereas the perceptual entropy of unvoiced phonemes is approximately 0.9 bit/sample. Results indicate that a simple voiced/unvoiced classification is suboptimal when trying to minimize bit rate. We used two different methods for the entropy estimation, and the results of both methods show that short segments of unvoiced speech are approximately Gaussian.

Cordic based IIR digital filters possess desirable properties for VLSI implementation such as local connection, regularity, and good finite word-length behavior, but can't be pipelined to finer levels (such as bit or multi-bit levels) due to the presence of feedback loops. In this paper, a pipelining method for the cordic based IIR digital filters is proposed using the constrained filter design methods and the polyphase decomposition technique. Using this method, the filter sample rate can be increased to any desired level.

We present a processor and a compiler for prototyping array implementations of algorithms from the class of Jacobi algorithms. We use adaptive matrix QR decomposition as an illustrative example.

We present a schematic design methodology for multirate convolution systems, based on combined algorithmic development and architecture design. It allows us to map the algebraic specification of a long convolution algorithm directly onto efficient fast convolution hardware based on short FFT processor elements or dedicated VLSI processors. The design methodology exploits the known relationship between multirate filter banks and fast convolution schemes in an implicit manner, and allows the hardware designer to concentrate on typical application specific constraints such as processing speed, processor size and memory utilization. The methodology has proven its usefulness in the design of a convolution processor for real-time on-board synthetic aperture radar imaging.

Using state space representations of biorthogonal time-varying filter banks, it is possible to derive conditions under which the transition between two time-invariant filter banks can be so controlled that both the decomposition filters and the reconstruction functions gently embrace. The transition interval can be made arbitrarily short. If it is zero, then the special case of instantaneous transition is reached.

A graphical derivation is presented for a parallel filter structure (systolic array) for updating eigenvalue and singular value decompositions. The derivation of this array is non-trivial due to the presence of feedback loops and data contra-flow in the underlying signal flow graph (SFG). This would normally prohibit pipelined processing. However, it is shown that suitable delays may be introduced to the SFG by performing simple algorithmic transformations which compensate for the interference of crossing data flows and eliminate the critical feedback loops. The pipelined array is then obtained either by 2-slowing and retiming the SFG or by means of dependence graph scheduling and assignment, and turns out to be an improved version of the array presented in Moonen et al. (1993).

We present a parallel system for fast rendering of artificial scenes with photo realism. The underlying parallel algorithm is based on ray-tracing and radiosity shading. The system consists of a standard workstation, a medium-size mesh of cluster processors and a high-bandwidth interconnection between them. Each cluster processor consists of a programmable TMS320C40 core and three dedicated VLSI satellites. The rendering algorithm runs on both the workstation host and its rendering mate in a true shared/distributed manner. The system is the result of an exercise in combined algorithm and architecture design as well as software/hardware co-design.>

Implementing Jacobi algorithms in parallel processor arrays is a non-trivial task, in particular when the algorithms are parameterized with respect to size and the architectures are parameterized with respect to space-time trade-offs. The objective of this paper is to demonstrate that practical, time-adaptive singular value decomposition can be implemented on a parallel processor array using Cordic arithmetic and asynchronous communication, such that any degree of parallelism, from single-processor implementation up to full-size array implementation is supported by a 'universal' processing unit. This result is the product of judicious application of transformations in the combined algorithm and architecture space.>

The forumnists address the question of high density computations on a single chip. The surface of a chip offers an ideal medium not only to store information or to process data, but also to execute computations. The 1 Giga floating point operations per second per chip mark has been achieved, we are now moving towards the teraflop mark. How is this going to happen, what are the limitations, what are the opportunities-those are central questions.>

A full-precision floating-point Cordic algorithm, suitable for the implementation of a word-serial Cordic architecture, is presented. The extension to existing block floating-point Cordic algorithms is in a floating-point representation for the angle. The angle is represented as a combination of exponent, microrotation bits, and two bits to indicate prerotations over /spl pi/2 and /spl pi/ radians. Representing floating-point angles in this fashion maintains the accuracy that is present in the input data, which makes it ideally suited for implementing a floating-point Givens operator.>

The decomposition (analysis) of a finite-energy signal into a relatively small number of mutually independent signals which allows reconstruction (synthesis) of the original signal is called subband filtering. Subbands can be processed in parallel or recursively. In the latter case, one obtains a so-called quadrature mirror filter tree. The former case leads to cosine-modulated filter banks. The authors present a Cordic based cosine-modulated bank and a systolic algorithm for quadrature mirror tree filtering.>

A unified approach is presented to the related problems of recovering signal parameters from noisy observations and identifying linear system model parameters from observed input/output signals, both using singular value decomposition (SVD) techniques. Both known and new SVD-based identification methods are classified in a subspace-oriented scheme. The SVD of a matrix constructed from the observed signal data provides the key step in a robust discrimination between desired signals and disturbing signals in terms of signal and noise subspaces. The methods that are presented are distinguished by the way in which the subspaces are determined and how the signal or system model parameters are extracted from these subspaces. Typical examples, such as the direction-of-arrival problem and system identification from input/output measurements, are elaborated upon, and some extensions to time-varying systems are given.>

The paper presents a parallel architecture for a pel-recursive motion estimation algorithm. It is a linear array of processors, each consisting of an initialization part, a data-routing part and an updating part. The initializing part performs a prediction of the motion vector. The routing parts constitute a routing path along which previous-frame data is routed from processors that store to processors that request such data. A clocked version of the router is presented with some detail. The updating part calculates an update to the predicted motion vector. The architecture proposed is derived in a systematic way and is parameterized w.r.t. certain window sizes. It is thus completely different from the few existing pel-recursive motion estimation architectures.>

A parallel architecture for a pel-recursive motion estimation algorithm is presented. It is a linear array of processors, each consisting of an initialization part, a data-routing part, and an updating part. The initializing part performs a prediction of the motion vector. The routing parts constitute a routing path along which previous-frame data are routed from processors that store to processors that request such data. The router can be data driven or clocked. The latter approach is presented in more detail. The updating part calculates an update to the predicted motion vector. The architecture proposed is derived in a systematic way and is parameterized with respect to certain window sizes. It is thus completely different from the few existing pel-recursive motion estimation architectures.>

The authors describe the design and implementation of an algorithm and a processor which can be used to accelerate computations in which large amounts of rotations (circular as well as hyperbolic) are involved. The processor is a low-cost high-throughput VLSI implementation of the algorithm. With 10/sup 7/ rotations per second, many real-time and interaction-time applications in scientific computation become feasible. The required storage and/or silicon area is low and the execution time is independent of the particular operation performed. Another feature of this CORDIC design is its pipelined architecture and floating point extension. It is angle-pipelinable at the bit-level and has an execution time which is independent of any possible operation that can be executed.>

The authors have shown in their previous work that processor-clustering is a key operation in the design of problem-size independent systolic/wavefront arrays. Indeed, the processor clustering techniques (called passive-clustering and active-clustering) can not only be used to reduce the size of an array to a constant, but also to achieve the design objectives such as transforming inefficient arrays into efficient arrays, reducing the dimension of an array, and balancing local memory and external communication of processors in a systematic way, etc. They have shown that such an operation can be completely described in terms of a set of so-called clustering vectors. They derive explicit expressions for all possible clustering vectors. A simple and constructive procedure is given for the computation of these vectors. This makes processor clustering operations constructive and suitable for computer CAD software implementation. Moreover, they show that the concept and procedure described for the processor clustering can be used hierarchically at different levels of a design. This way, fixed-size arrays can be designed in a hierarchical and parameterized, semi-automatic way.>

A number of high-resolution methods used to determine the two-dimensional ( alpha /sub i/, beta /sub i/) directions of arrival (DOAs) of a number of plane waves, impinging on a sensor array are discussed. The array possesses an arbitrary geometry, but consists of triplets or quadruplets of sensors that are identical. The data from these sensors is first processed for each independent dimension using an ESPRIT-like subspace-based method. The correct ( alpha /sub i/, beta /sub i/) pairs are then determined by considering subspace properties that the proposed data would possess in the noise-free case. An algorithm is devised that potentially improves the parameter estimates and yields the correct parameter pairs while avoiding an extensive search over the two separate one-dimensional parameter sets. Resolution is improved by exploiting the spatial dependence of the measurements when sensor quadruplets are used.>

The authors present a methodology to design fixed-size systolic arrays. It allows a systematic and hierarchical mapping of full-size arrays to fixed-size arrays. Two processor-clustering techniques are described. They can be used to achieve the following design objectives: (1) transforming inefficient arrays into efficient arrays, (2) reducing the size of an array, (3) reducing the dimension of an array, and (4) balancing local memory and external communication of processors. A technique is described to cluster processors in such a way that the number of I/O pins of the resulting processor is independent of the number of processors that are clustered. The approach presented unifies and generalizes array reduction techniques.>

The authors consider a formal and systematic method to convert a class of nested loop programs to single assignment codes and, when possible, to regular algorithms (RAs) for systolic array implementation. The authors concentrate on the analysis of certain imperative nested loop programs in view of the ultimate objective, which is the (semi)-automatic design of systolic arrays from such initial behavioral specifications. The nested loop programs can be represented by a graph displaying the variable dependences between iterations. Characteristic properties of this dependence graph are given. In terms of this dependence graph, a procedure is described to transform the program into a single assignment program in which each variable takes on a unique value during the execution of the program. The method provides a systematic way to analyze data dependences in imperative nested loop programs. The approach is complementary to those used in parallelizing/vectorizing compilers. Instead of searching for independent iterations or statements (i.e. parallelism), iterations that are strictly dependent on each other are detected.>

A number of high-speed multiprocessor applications of a fast custom VLSI floating-point pipeline CORDIC processor are presented. The applications are concerned with speech processing, matrix arithmetic, antenna array processing, and computer graphics. The applications are designed using an interactive high-level functional design environment for multiprocessor systems and are implemented on a test bed for high-speed parallel processor arrays.>

A new applicative model is presented for the description and analysis of both synchronous and asynchronous VLSI networks at the top levels of abstraction.The model is based on two powerful paradigms, the Applicative State Transition concept of Backus [l] for the descriptive aspects and the theory of single token time(d) Petri Nets [2, 3, 41 for the communicative aspects

The authors describe a procedure to transform a class of sequential iterative algorithms to systems of (uniform) recurrent equations (REs) from which systolic arrays can automatically be derived. They derive an equivalent class of systems of recurrent equations for a class of sequential iterative algorithms. First, they construct two formal models: A for the class of sequential algorithms they consider and R for the REs. Then they construct a procedure which maps an algorithm in A on a corresponding one in R. The essence of the method is to find the trace of the variables in the former algorithm. The method described is general and can be implemented in a design system for systolic arrays.>

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.>

The general structure of this class of coders is reviewed, and the particulars of its members are discussed. The different analysis procedures are described, and the contributions of the various coder parameters to the performance of the coder are examined. Quantization procedures for each transmitted parameter are given along with examples of bit allocations. The speech quality produced by these coders is high at 16 kb/s and good at 8 kb/s, but only fair at 4.8 kb/s. The use of postprocessing techniques changes the performance at lower rates, but more research is needed to further improve the coders.>

In this paper we present a VLSI system architecture for high-speed synthesis of 3D images composed of diffusely reflective surfaces. The system consists of two loosely coupled sub-systems. The first sub-system computes the form-factor matrix F. The form-factor computation is based on the hemi-cube approximation technique, where the patch-to-hemi-cube projections are computed by an efficient ray-tracing algorithm. The second sub-system, a multiprocessor Gauss-Seidel iterative system solver, solves the sparse system of radiosity equations (I-AF)b=e. The described system is suitable for VLSI implementation. Pipelined CORDIC processors are used in the first sub-system, and pipelined multiplier/accumulator processors are used in the second sub-system.

Images can be effectively and efficiently modeled as a random output field of a non-constant spectral shaping filter input with a certain low bit rate excitation field. The shaping filter is taken to be the inverse of a field-adaptive linear prediction filter. The excitation field is taken to be a closed-loop weighted approximation of the LP residual. In this paper, we focus on approximations that are field extensions of 1D so-called Multi-Pulse and Regular-Pulse excitations that have been successfully applied in weighted analysis-by-synthesis speech coding algorithms.

An attractive algorithm for the encoding of toll-quality speech below 16 kb/s is based on the so-called regular.pulse encoding (RPE) modeling scheme [1]. Basically. the RPE speech coder models the speech signal as the output of a linear predictive spectral envelope filter whose input is a short-time base-band approximation of the prediction residual. Although the complexity of the conceptual RPE algorithm is only moderate, we will demonsrate in this paper that under certain simplifying, albeit realistic, assumptions it turns out to be possible to come up with a scheme that combines the computational simplicity of a well designed base-band coder [2], with the subjective optimality of the uncompromisod RPE concept. Moreover, we shall also show that it is possible to overcome the problem of large encoding delay, wMch is of major concern in certain real-time applications.

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.

This paper describes an effective and efficient time domain speech encoding technique that has an appealingly low complexity, and produces (near) toll quality speech at rates below 16 kbit/s. The proposed coder uses linear predictive techniques to remove the short-time correlation in the speech signal. The remaining (residual) information is then modeled by a regular (in time) excitation signal that, when inputted to the time-varying model filter, produces a signal that is "close" to the reference speech signal. The procedure for finding the appropriate excitation model parameters incorporates the solution of a few sets of linear equations and is of moderate complexity compared to competing coding systems such as Adaptive Transform Coding and Multi-Pulse Excitation Coding.

The paper presents a revised functional description of Volder's Coordinate Rotation Digital Computer algorithm (CORDIC), as well as allied VLSI implementable processor architectures. Both pipelined and sequential structures are considered. In the general purpose or multi-function case, pipeline length (number of cycles), function evaluation time and accuracy are all independent of the various executable functions. High regularity and minimality of data-paths, simplicity of control circuits and enhancement of function evaluation speed are ensured, partly by mapping a unified set of micro-operations, and partly by invoking a natural encoding of the angle parameters. The approach benefits the execution speed in array configurations, since it will allow pipelining at the bit level, thereby providing fast VLSI implementations of certain algorithms exhibiting substantial structural pipelining or parallelism.

We report on the results obtained from simulations of the Multi-Pulse Excitation Coder as proposed by Atal and Remde [4]. We investigated the effects of the different analysis parameters on the resulting synthetic speech signals, using objective and subjective tests. We compared the in [4] proposed sub-optimal solutions with another sub-optimal solution based on an orthogonalization of the solution space and found that the original proposed solutions are reasonable choices. We demonstrate that the inclusion of a pitch detector significantly improves the perceived quality of the synthetic speech. We also describe a modification of the original algorithm, resulting in a lower complexity, and a speech quality close to the results obtained with the original algorithm.

The paper gives a quick and concise introduction to orthogonal filter synthesis. Orthogonal filters are special well structured and well behaved modular algorithms that perform conventional digital filtering, making use of but 1 functional unit :the (Givens) plane rotation cell. Synthesis of such filters is a routine to determine-from some form of transfer function specification- type, number and order of (multi-cell) modules as well as values of constants (angles) in such modules. Number and type of modules is prescribed by the zeros of the transfer function. The order can be chosen at will. Angles of rotor cells are parameters in a generalized Schur parametrization recursion.

A class of least squares time-variant lattice recursions is presented, in which the lattice coefficients are sequences that are generated in a recursive test for matrix positivity. The computations of these sequences go partly along the lines of the test recursion and partly via recursive update procedures reflecting a low index of non Toeplitzness of the underlying matrix. In applications, these mixed form algorithms allow for a substantially reduction of the computational complexity, by performing stepwize tracking, in an exact manner, of estimation parameters.