Chair: Robert M. Owens, Pennsylvania State University (USA)
Nelson Luiz Passos, University of Notre Dame (USA)
Edwin Hsing-Mean Sha, University of Notre Dame (USA)
Two- dimensional filters are commonly used in digital image processing applications. These filters have the characteristic of processing recursive sets of instructions requiring high computational speed. In this paper, these sets are modeled as cyclic two-dimensional data flow graphs, which are also used to represent the equivalent circuit design. In this new method, such graphs are submitted to a multi- dimensional retiming in order to reduce their cycle time. Such a reduction can achieve a cycle equal to the longest atomic operation in the filter, by inserting a fixed number of registers, independent of the size of the problem, into the circuit paths. Examples, description and the correctness of our algorithm are presented in the paper.
Kin H. Yu, University of Wisconsin-Madison (USA)
In this paper we present an approach for performing dynamic context-dependent transformations (DCDT) to improve code generation for programmable digital signal processors. Unlike static optimizations, DCDT can guarantee to improve the quality of the generated code, at the expense of longer computational time. For many embedded DSP applications, hand coding in assembly is still the only effective approach. We show that our code generation approach, when combined with DCDT, can yield code of quality comparable to that of hand- written codes by DSP experts and many times superior to that generated by a conventional optimizing compiler.
Liang-Fang Chao, Iowa State University
Edwin Hsing-Mean Sha, University of Notre Dame (USA)
In order to realize DSP applications on multi-processor systems with optimal throughput, properties and efficient techniques need to be derived. Rate-optimal scheduling with minimum unfolding has been studied in the past for static schedules only. The scheduling models called cyclo- static and periodic schedules allow more flexibility on processor assignment. This paper derives the minimum unfolding factors to achieve rate-optimal schedules for cyclo-static and periodic schedules. The necessary and sufficient conditions for the existence of these schedules are also derived. >From these results, it is shown that unfolding is necessary under these two models for certain data-flow graphs to achieve rate-optimality. Furthermore, all the theorems are proved in a constructive way, in which an efficient shortest-path algorithm is used for scheduling.
Thomas M. Parks, University of California (USA)
Edward A. Lee, University of California (USA)
Real-time signal processing applications can be described naturally with dataflow graphs. The systems we consider have a mix of real-time and non-real-time processing, where independent dataflow graphs represent tasks and individual dataflow actors are subtasks. Rate-monotonic scheduling is optimal for fixed-priority, preemptive scheduling of periodic tasks. Priority inheritance protocols extend rate-monotonic scheduling theory to include tasks that contend for exclusive access to shared resources. We show that non-preemptive rate-monotonic scheduling can be viewed as preemptive scheduling where the processor is explicitly considered a shared resource. We propose a dynamic, real-time execution model inspired by multithreaded dataflow architectures.
Mark Kahrs, Rutgers University (USA)
MHDL is a new language created for the behavioral description of state-of-the-art microwave hardware. A microwave communication system includes both continuous time and discrete time processing subsystems. MHDL includes a number of novel features; some of these features are of direct use in the specification of both continuous time and discrete time signal processing. MHDL includes data types complex and z that find direct use in signal processing applications. This report describes the use of MHDL in the description of signal processing algorithms.
Thorsten Grotker, Aachen University of Technology (GERMANY)
Peter Zepter, Aachen University of Technology (GERMANY)
Heinrich Meyr, Aachen University of Technology (GERMANY)
Different levels of abstraction are suited for algorithm design and hardware architecture development. This paper presents a tool (ADEN) that provides a link from system design to VLSI implementation. It generates synchronous timed descriptions of digital hardware from dynamic data-flow system level configurations. It allows to make use of optimized architectures available for a broad range of communication system components. These components are kept in the extensible ComBox library which provides means to characterize their data-flow and timing properties. The design methodology together with the tool operation and the library concept will be explained. An actual design example is presented to demonstrate effectiveness of this approach.
Marc Moonen, Katholieke Universitet Leuven (BELGUIM)
Ed Deprettere, Delft University of T echnology (THE NETHERLANDS)
Ian K. Proudler, Defense Research Agency (UK)
John G. McWhirter, Defense Research Agency (UK)
A graphical derivation is presented for a recently developed 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 an earlierly presented arrray.
Mohammad Shajaan, Technical University of Denmark (DENMARK)
Karsten Nielsen, Technical University of Denmark (DENMARK)
John Aasted Sorenson, Technical University of Denmark (DENMARK)
Simultaneous design of multiplier-free filters and their hardware implementation in Xilinx Field Programmable Gate Array (XC4000) is presented. The filter synthesis method is a new approach based on cascade coupling of loworder sections. The complexity of the design algorithm is O(filter order). The hardware design methodology leads to high performance filters with sampling frequencies in the interval 20-50 MHz. Time-area efficiency and performance of the architectures are considerably above any known approach.
Greet Bilsen, Katholieke Universiteit Leuven (BELGIUM)
Marc Engels, Katholieke Universiteit Leuven (BELGIUM)
Rudy Lauwereins, Katholieke Universiteit Leuven (BELGIUM)
J.A. Peperstraete, Katholieke Universiteit Leuven (BELGIUM)
The high sample-rates involved in many DSP-applications, require the use of static schedulers wherever possible. The construction of static schedules however is classically limited to applications that fit in the synchronous data flow model. In this paper we present cyclo-static data flow as a model to describe applications with a cyclically changing behaviour. We give both a necessary and sufficient condition for the existence of a static schedule for a cyclo-static data flow graph and show how such a schedule can be constructed. The example of a video encoder is used to illustrate the importance of cyclo-static data flow for real-life DSP-systems.
Karim P. Khiar, Thomson-CSF and University of California (USA)
Edward A. Lee, Thomson-CSF and University of California (USA)
The synchronous dataflow model is used in a variety of visual programming environments to describe and design digital signal processing systems. In this paper, we present two main improvements over existing methodologies. Both are concerned with convenient manipulations of multidimensional data. The first describes a systematic method for transposing multidimensional data structures embedded within a one dimensional stream. This enables the use of scalar stream operators for processing multidimensional data. The second shows how higher-order functions combined with visual hierarchy can be used to build intuitive, maintainable, and scalable applications that operate on multidimensional data. These techniques are combined to design a beamforming radar simulation using the Ptolemy simulation environment.
Kurt Baudendistel, AT&T Bell Laboratories (USA)
Linkable simulators for Programmable Digital Signal Processors allow the development of heterogeneous executables that mix object code executing directly on a host workstation with object code executing indirectly on a target device via a software simulator or hardware emulator running on the host. However, these linkable simulators typically require extensive development of interface code to create such heterogeneous executables. This new tool allows interface code to be generated automatically, allowing the creation of heterogeneous executables with only minor modifications to original C language source code. Since the required modifications to the original source code are minor and independent of the execution domain, a new methodology of porting DSP applications from host workstations to PDSPs can be considered, where functions are moved one at a time from the host to the target execution domain.