Stream oriented processing is an important methodology used in FPGA-based parallel processing. Characteristics of stream-oriented computing include high-data-rate flow of one or more data sources; fixed size, small stream payload (one byte to one word); compute-intensive operations, usually low precision fixed point, on the data stream; access to small local memories holding coefficients and other constants; and occasional synchronization between computational phases. We describe language constructs, compiler technology, and hardware/software libraries embodying the Streams-C system which has been developed to support stream-oriented computation on FPGA-based parallel computers. The language is implemented as a small set of library functions callable from a C language program. The Streams-C compiler synthesizes hardware circuits for multiple FPGAs as well as a multi-threaded software program for the control processor. Our system includes a functional simulation environment based on POSIX threads, allowing the programmer to simulate the collection of parallel processes and their communication at the functional level. Finally we present an application written both in Streams-C and hand-coded in VHDL. Compared to the hand-crafted design, the Streams-C-generated circuit takes 3x the area and runs at 1/2 the clock rate. In terms of time to market, the hand-done design took a month to develop by an experienced hardware developer. The Streams-C design rook a couple of days, for a productivity increase of 10x.

FPGA-based processors, like many conventional DSP systems, often associate small high performance memories with each processing chip. These memories may be on-board embedded SRAMs or discrete parts. In the process of mapping a computation onto an FPGA processor, it is necessary to map the applications' data to memories. In this work, we present an algorithm that has been implemented in our NAPA C compiler to assign data automatically to memories to produce minimum overall execution time of the loops in the program. With the addition of this algorithm to our compiler, the programmer need not explicitly annotate array declarations with location information. Rather, the compiler analyzes the usage patterns of variables and selects the optimal location for each variable. The algorithm uses a search technique known as implicit enumeration to reduce the otherwise exponential search space. In practice, the use of this memory allocation compiler phase in our SUIF-based NAPA C compiler has negligible effect on compiler run time.

Hybrid architectures combining conventional processors with configurable logic resources enable efficient coordination of control with datapath computation. With integration of the two components on a single device, loop control and data-dependent branching can be handled by the conventional processor. While regular datapath computation occurs on the configurable hardware. This paper describes a novel pragma-based approach to programming such hybrid devices. The NAPA C language provides pragma directives so that the programmer (or an automatic partitioner) can specify where data is to reside and where computation is to occur with statement-level granularity. The NAPA C compiler, targeting National Semiconductor's NAPA1000 chip, performs semantic analysis of the pragma-annotated program and co-synthesizes a conventional program executable combined with a configuration bit stream for the adaptive logic. Compiler optimizations include synthesis of hardware pipelines from pipelineable loops.

A compare-and-swap shared-queue algorithm is presented that permits concurrent access. This algorithm is nondelaying in that no processor need wait for an action by another processor. A verification method that analyzes the states of the shared data structure is given. By drawing a graph that incorporates in a simple way the effects of multiprocessor interleaving, one can quickly find errors in an algorithm or produce a proof of correctness. Since enqueue and dequeue operations may begin at any time, concurrent queue operations are represented by providing, in each state of the shared data structure, one transition that initiates an enqueue operation and another transition for a dequeue operation. The method is a practical one that is applicable to a variety of algorithms that use shared data structures.>

We present a case study that illustrates a method of debugging concurrent processes in a parallel programming environment. It uses a new approach called speculative replay to reconstruct the behavior of a program from the histories of its individual processes. Known time dependencies between events in different processes are used to divide the histories into dependence blocks. A graphical representation called a concurrency map displays possibilities for concurrency among processes. The replay technique preserves the known dependencies and compares the process histories generated during replay with those that were logged during the original program execution. If a process generates a replay history that does not match its original history, replay backs up. An alternative ordering of events is created and tested to see if it produces process histories that match the original histories. Successively more controlled replay sequences are generated, by introducing additional dependencies. We describe ongoing work on tools that will control replay without reconstructing the entire space of possible event orderings.