The paper presents an algorithm to determine the close-to-smallestpossible data buffer sizes for arbitrary synchronous dataflow (SDF) applications, such that we can guarantee the existenceof a deadlock free schedule. The presented algorithm fits inthe design flow of GRAPE, an environment for the emulation andimplementation of digital signal processing (DSP) systems onarbitrary target architectures, consisting of programmable DSPprocessors and FPGAs. Reducing the size of data buffers is ofhigh importance when the application will be mapped on FieldProgrammable Gate Arrays (FPGA), since register resources arerather scarce.

The paper presents an algorithm to determine the smallest possible data buffer sizes for arbitrary synchronous data flow (SDF) applications, such that we can guarantee the existence of a deadlock free schedule. The presented algorithm fits in the design flow of GRAPE, an environment for the emulation and implementation of digital signal processing (DSP) systems on arbitrary target architectures, consisting of programmable DSP processors and FPGAs. Reducing the size of data buffers is of high importance when the application will be mapped on Field Programmable Gate Arrays (FPGA), since register resources are rather scarce.

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.

GRAPE-II (Graphical Rapid Prototyping Environment-II) is a hardware-software codesign environment for the real-time functional emulation of synchronous DSP systems. It allows one to specify the application's data dependency graph in a target-machine-independent way. After specifying the heterogeneous target machine's architecture, it estimates the resources needed by each application subtask. Based on these requirements, it assigns the subtasks to specific target devices at compile-time, be they processors or FPGAs, establishes routing paths and determines a static schedule. It generates a main shell for each target device and generates intra-device and inter-device communication code. After downloading the executable images on to the target machine, it allows the designer to modify end-user controls and application settings at run-time. This paper situates the tool in the application design cycle, explains GRAPE-II's design flow and shows the advantages of hardware-software codesign by evaluating the achievable sampling frequency for a small example application.

Studies synchronous multi-rate data flow graphs to determine the minimal required buffer sizes that still guarantee the construction of a deadlock-free static schedule. We develop a rule to quickly analyze a graph's consistency. A graph is split up into single and parallel paths. Single paths are analysed, as well as the most frequent parallel paths. The results are used in the rapid prototyping environment GRAPE-II in the case where the emulation hardware contains FPGAs, or when memory is critical.>

Describes two novel features that are supported in GRAPE-II (Graphical RApid Prototyping Environment): geometric parallelism and cyclo-static data flow. GRAPE-II is intended as a system level tool for the rapid prototyping of digital signal processing (DSP) applications on multiprocessors. GRAPE-II fully supports code generation for multi-rate and asynchronous DSP applications on heterogeneous target multiprocessors. The first feature detailed in the paper, geometric parallelism, allows the programmer to efficiently specify data parallel operations, where multiple identical functions operate on different data sets. The second feature, cyclo-static data flow, enables the specification of cyclicly changing data dependencies, while still leading to static schedules.>

In the graphical programming environment GRAPE-II intended for rapid prototyping of DSP ASICs on a multi-processor, a load balancing tool is required to map the different jobs of the DSP application on the multi-processor. Since most of the existing load balancing algorithms perform less well when they have to handle large or complex applications, the authors develop a tool that is better suited for such problems. This tool is based on three main techniques. (1) By exploiting the hierarchy that exists in the application graph, the complexity for each of the tools can be reduced. (2) Splitting the load balancing in sub tasks leads to three smaller search spaces instead of one big space. (3) Each of the smaller search spaces on its turn is reduced by using appropriate heuristic rules. As an example of this approach the scheduling tool and the basics of the assignment tool are presented.>

The authors describe the process-level debugger of GRAPE, an environment for the rapid prototyping of digital signal processing systems on parallel computers. This debugger allows one to debug concurrent programs that are based on communicating sequential processes. Its unique feature is that it clearly separates the identification of erroneous processes from the exact localisation of the bug on the source-level. This divide-and-conquer approach is absolutely necessary for debugging complex parallel programs in a fast and systematic way, which is a key issue for rapid prototyping. The process-level debugging approach is based on an animation of program behaviour on its hierarchical graphical representation. Graphical views are used that reflect the programmer's mental picture of the application. Hierarchy allows one to employ a top-down debugging approach in which one successively refines the search-space by zooming in on suspect processes first-time-right. They consider both hierarchy that hides algorithmic details, and hierarchy that hides implementation issues. During animation a debugging kernel implementing a record-replay mechanism guarantees reproducible program behaviour even for programs containing asynchronisities.>

The second version of the graphical programming environment (GRAPE) is described. It is intended as a tool for the rapid prototyping of digital signal processing (DSP) application-specific integrated circuits (ASICs) on a multiprocessor. GRAPE-II fully supports multirate and asynchronous DSP applications and heterogeneous target multiprocessors. The extensions that are required to the programming model and the intermediate specification language to support multirate and asynchronous operation are described. The programming model is clarified by an example. The global structure of GRAPE-II is presented. The status of the project is indicated.>

The CASE tool GRAPE (GRAphical Programming Environment) is presented which allows for easy programming, compiling, debugging and evaluating high frequency real-time DSP algorithms. Its main distinctive feature is that the tool spans the whole design process, ranging from analysis over simulation and emulation up to implementation on general purpose DSP multiprocessors or integration on an Application Specific Integrated Circuit (ASIC). The DSP multiprocessor can be the target hardware or can be used for real-time emulation or accelerated simulation of an ASIC. The paper mainly focuses on the CASE tool and on the design of a flexible multiprocessor board for the real-time emulation of DSP ASIC's.>

In several data flow architectures, “streams” are proposed as special data structures able to improve parallel execution in functional programs by providing a pipelining effect between different program parts.

During the last ten years, data flow has become an exciting research area and several architectures have been proposed and built. They differ mostly in the way they handle data structures and how they provide mechanisms for token labeling or colouring in order to make data flow graphs reentrant. The paper presents a data flow architecture with a paged memory system to hold both data flow programs and data structures. The token labeling mechanism is coupled with the memory management system in order to provide for each token a unique memory location. The instruction format allows instructions with multiple operands and multiple destinations for each result. Data structures are held in memory while pointers to the structures are circulating as tokens. The proposed architecture is able to execute data flow programs at the level of single instructions or at a higher level.