Jack Volder’s original motivation for the COordinate DIgital Computer (CORDIC) was the real-time digital solution of spherical triangle equations employed in airborne navigation, for which he presented a solution flow diagram without detailing its construction. In fact, without a strong guidance, it is not easy to express the solutions of linear algebraic problems such as those involved when solving spherical triangles as cascades of CORDIC operations—called by Volder CORDIC solution-flow diagrams—and thus to devise a system solution on CORDIC processing units. As it gives a bird’s eye view of the system design problem, a signal flow graph representation of the underlying system of linear equations provides such guidance; the operations leading to the problem solution are uncovered by performing a sequence of partial flow reversals on the graph. The approach is illustrated by the problem where two sides and the included angle of a spherical triangle are given, called SAS problem, that is encountered in applications as diverse as air navigation, lattice filters for adaptive processing, and dexterous robotic hands. The solutions thus obtained are at least as efficient as existing ones, whenever available.

The search of a mapping of a Synchronous Data Flow Graph (SDFG) on a distributed architecture that achieves a given throughput while satisfying memory constraints is a difficult challenge. Solving this problem calls for evaluating throughput and buffer capacities associated to a mapping. Since the available mapping evaluation methods are not polynomial with respect to the SDFG description, mapping techniques using them are not scalable. This paper develops a polynomial method for the evaluation of any given SDFG mapping on a distributed architecture. The method is based on a simple transformation of the SDFG to model communications through a Network on Chip. The key result is that the size of the memory required in order to guarantee the liveness or a given throughput of an application may be evaluated in polynomial time. Experimentally, computing the memory size guaranteeing liveness of a mapping of a 670-node H264 graph on a 4-cluster architecture takes 70 ms on an Intel Core i5-660 processor and grows linearly with graph size.

Weighted Petri nets provide convenient models of many man-made systems. Real applications are often required to possess the fundamental Petri net properties of liveness and reversibility, as liveness preserves all the functionalities (fireability of all transitions) of the system and reversibility lets the system return to its initial state (marking) using only internal operations. Characterizations of both behavioral properties, liveness and reversibility, are known for well-formed weighted Choice-Free and ordinary Free-Choice Petri nets, which are special cases of Equal-Conflict Petri nets. However, reversibility is not well understood for this larger class, where choices must share equivalent preconditions, although characterizations of liveness are known. In this paper, we provide the first characterization of reversibility for all live Equal-Conflict Petri nets by extending, in a weaker form, a known condition that applies to the Choice-Free and Free-Choice subclasses. We deduce the monotonicity of reversibility in the live Equal-Conflict class. We also give counter-examples for other classes where the characterization does not hold. Finally, we focus on well-formed Equal-Conflict Petri nets, for which we offer the first polynomial sufficient conditions for liveness and reversibility, contrasting with the previous exponential time conditions.

Dataflow modeling is a highly regarded method for the design of embedded systems. Measuring the performance of the associated analysis and compilation tools requires an efficient dataflow graph generator. This paper presents a new graph generator for Phased Computation Graphs (PCG), which augment Cyclo-Static Dataflow Graphs with both initial phases and thresholds.

Join-Free Petri nets, whose transitions have at most one input place, model systems without synchronizations, while Choice-Free Petri nets, whose places have at most one output transition, model systems without conflicts. These classes respectively encompass the state machines (S-systems) and the marked graphs (T-systems). Whereas a structurally bounded and structurally live Petri net is said to be “well-formed”, a bounded and live Petri net is said to be “well-behaved”. Necessary and sufficient conditions for the well-formedness of Join-Free and Choice-Free nets have been known for some time, yet the behavioral properties of these classes are still not well understood. In particular polynomial sufficient conditions for liveness, that is, polynomial in time and with a polynomial initial number of tokens, have not been found until now. Besides, home markings , which can be reached from every reachable marking thus allowing for the construction of systems that can return to their initial data distribution, are not well apprehended either for these subclasses. We extend results on weighted T-systems to the class of weighted Petri nets and present transformations which preserve the language of the system and reduce the initial marking. We introduce a notion of balancing that makes possible the transformation of conservative systems into so-called “token-conservative” systems, whose number of tokens is invariant, while retaining the feasible transition sequences. This transformation is pertinent for all well-formed Petri nets and leads to polynomial sufficient conditions of liveness for well-formed Join-Free and Choice-Free nets. Finally, we also provide polynomial live and home markings for Fork-Attribution systems.

By incorporating reconfigurable hardware in embedded system architectures it has become easier to satisfy the performance constraints of demanding applications while lowering system cost. In order to evaluate the performance of a candidate architecture, the nodes (tasks) of the data flow graphs that describe an application must be assigned to the computing resources of the architecture: programmable processors and reconfigurable FPGA, whose run-time reconfiguration capabilities must be exploited. In this paper we present a novel design exploration tool - based on a local search algorithm with global convergence properties - which simultaneously explores choices for computing resources, assignments of nodes to these resources, task schedules on the programmable processors and context definitions for the reconfigurable circuits. The tool finds a solution that minimizes system cost while meeting the performance constraints; more precisely it lets the designer select the quality of the optimization (hence its computing time) and finds accordingly a solution with close-to-minimal cost.

In current embedded system design practice, only few architectural solutions and mappings of the functionalities of a system on the architecture's components are examined. This paper presents an optimization-based method and the associated tool developed to help designers take architectural decisions. The principle of this approach is to efficiently explore the design space and to dynamically provide the user with the capabilities to visualize the evolution of selected criteria. The first objective is solved by developing an enhanced version of the adaptive simulated annealing algorithm. Since the method is iterative, multiple solutions may be examined and the tool lets the user stop exploration at any time, tune parameters and select solutions. Moreover we present an approach for systems whose functionalities are specified by means of multiple models of computation, in order to handle descriptions of digital signal applications at several levels of detail. The tool has been applied to a motion detection application in order to determine architectural parameters

Matrix computations are often expressed in terms of plane rotations, which may be implemented using COordinate Rotation Digital Computer (CORDIC) arithmetic. As matrix sizes increase multiprocessor systems employing traditional CORDIC arithmetic, which operates on two-dimensional (2D) vectors, become unable to achieve sufficient speed. Speed may be increased by expressing the matrix computations in terms of higher dimensional rotations and implementing these rotations using novel CORDIC algorithms-called Householder CORDIC-that extend CORDIC arithmetic to arbitrary dimensions. The method employed to prove the convergence of these multidimensional algorithms differs from the one used in the 2D case. After a discussion of scaling factor decomposition, range extension and numerical errors, VLSI implementations of Householder CORDIC processors are presented and their speed and area are estimated. Finally, some applications of the Householder CORDIC algorithms are listed.>

Many statistical signal processing algorithms operating on real data are based on rotations on two-dimensional (2-D) real vectors. The original, 2-D CORDIC algorithms are well suited to parallel implementations of these algorithms. However they are not as well suited to the operations on 2-D complex vectors that arise when dealing with complex data. We briefly describe extensions of the 2-D CORDIC algorithms to 4-D space and show how to use them to speed up parallel computations when solving overdetermined complex linear systems and Hermitian systems.>

This work deals with the general case of processors with multiple, possibly pipelined, functional units that operate concurrently and presents a method for the minimization of the actual computation time n/sub sys/*t/sub sys/. The selection of a linear scheduling function, which minimizes n/sub sys/*t/sub sys /is formulated as a combinatorial optimization problem, which is shown to have a bounded search space. An efficient branch-and-bound method for the solution of that problem is proposed and applied to several examples.>

A novel n-dimensional (n-D) CORDIC algorithm for Euclidean and pseudo-Euclidean rotations is proposed. This algorithm is closely related to Householder transformations. It is shown to converge faster than CORDIC algorithms developed earlier for n=3 and 4. Processor architectures for the algorithm are presented. The area and time performance of n-D CORDIC processors are evaluated. For a comparable time performance, the processors require significantly less area than parallel Householder processors. Furthermore, arrays of n-D Euclidean CORDIC processors are shown to speed up the QR decomposition of rectangular matrices by a factor of n-1 in comparison with a 2-D CORDIC processor array.>

An arithmetic algorithm is presented which speeds up the parallel Jacobi method for the eigen-decomposition of real symmetric matrices. After analyzing the elementary mathematical operations in the Jacobi method (i.e. the evaluation and application of Jacobi rotations), the author devises arithmetic algorithms that effect these mathematical operations with few primitive operations (i.e. few shifts and adds) and enable the most efficient use of the parallel hardware. The matrices to which the plane Jacobi rotations are applied are decomposed into even and odd parts, enabling the application of the rotations from a single side and thus removing some sequentiality from the original method. The rotations are evaluated and applied in a fully concurrent fashion with the help of an implicit CORDIC algorithm. In addition, the CORDIC algorithm can perform rotations with variable resolution, which lead to a significant reduction in the total computation time.>

It is shown that simulated annealing, with a properly designed annealing schedule and move-generation strategy, achieves significant speedups for high-quality solutions when compared with tailored heuristics on two well-studied problems: the traveling-salesman problem and the graph-partition problem. Efficient heuristics can be applied to power and ground routing for the traveling-salesman problem and to min-cut placement and logic partitioning for the graph-partition problem.>

Digital feedback is at the heart of implementations of many functions and can be used for the evaluation and application of rotations in definite and indefinite metrics. The CORDIC algorithms exploit this concept to perform rotations in two dimensions. These algorithms are analyzed as a first step before extending them to higher dimensions. A side result of this analysis is the simultaneous reduction of the number of steps and the enlargement of the domain of convergence of the algorithms. A few guidelines for their extension and a worked out three-dimensional example are then presented.

Motivated by recent advances made in VLSI and VLSI-based systems, we describe the functional programming(FP) style as proposed by Backus [1]. Comparative studies are made by coding simple algorithms in a conventional language and in FP. We find that the methodologies involved in the two approaches are different; conventional languages require thinking at an object level while FP styles favour a more hierarchical formalization. The paper also discusses some limitations of FP styles that will have to be remedied.

On-line identification methods for dynamic systems traditionally assume given-order rational models. The class of finite shift-rank processes includes processes with rational models of arbitrary order and, if the observed process is approximated by a finite shift-rank process, the determination of the model order becomes a natural part of the identification procedure. The Fast Cholesky and Extended Levinson algorithms exploit the finite shift-rank structure in order to compute the time-varying coefficients of the growing-order modeling/whitening filters of finite shift-rank processes. The recursions performed by the algorithms suggest that the growing-order filters may also be implemented in a modular fashion where the modules have constant coefficients, thus displaying the structural invariants. Such a modular filtering structure is presented in this paper.

In this paper, the Fast Cholesky algorithms, both by columns and by rows, are reviewed. It is shown that the algorithms lead naturally to a prediction error feedback filter. In addition, if this filter is used as the whitening filter for a moving average process, it is of fixed order but has time-varying coefficients. Simulation results for the case when the data came from the output of a moving average process driven by white Gaussian noise confirms theoretical results on convergence and stability of the triangular factors. In addition, the bandedness of the process being identified is revealed. Finally, from a VLSI implementation standpoint, it is shown that an array of CORDIC processors may be configured and controlled to factor a covariance matrix. In particular, there exists a method of factorization where the partial correlations associated with the given matrix are stored within the processors.

A new framework is presented for the problem of estimating source location from a set of time difference of arrival (TDOA) measurements. First the conditions under which the source coordinates are identifiable are derived and geometrically interpreted. Then it is shown that the source location can be found, when it is identifiable, by estimating the coefficients of a set of linear relationships, with the number of equations being equal to the number of stations.