GeCoS is an open source framework that provide a highly productive environment for hardware design. GeCoS primarily targets custom hardware design using High Level Synthesis, distinguishing itself from classical compiler infrastructures. Compiling for custom hardware makes use of domain specific semantics that are not considered by general purpose compilers. Finding the right balance between various performance criteria, such as area, speed, and accuracy, is the goal, contrary to the typical goal in high performance context to maximize speed. The GeCoS infrastructure facilitates the prototyping of hardware design flows, going beyond compiler analyses and transformations. Hardware designers must interact with the compiler for design space exploration, and it is important to be able to give instant feedback to the users.

In this article, we present a constraint programming approach for solving hard design problems present when automatically designing specialized processor extensions. Specifically, we discuss our approach for automatic selection and synthesis of processor extensions as well as efficient application compilation for these newly generated extensions. The discussed approach is implemented in our integrated design framework, IFPEC , built using Constraint Programming (CP). In our framework, custom instructions, implemented as processor extensions, are defined as computational patterns and represented as graphs. This, along with the graph representation of an application, provides a way to use our CP framework equipped with subgraph isomorphism and connected component constraints for identification of processor extensions as well as their selection, application scheduling, binding, and routing. All design steps assume architectures composed of runtime reconfigurable cells, implementing selected extensions, tightly connected to a processor. An advantage of our approach is the possibility of combining different heterogeneous constraints to represent and solve all our design problems. Moreover, the flexibility and expressiveness of the CP framework makes it possible to solve simultaneously extension selection, application scheduling, and binding and improve the quality of the generated results. The article is largely illustrated with experimental results.

This paper presents a new method, based on constraint programming, for modeling and solving scheduling and instruction selection for processors extended with a functionally reconfigurable cell fabric. Our method models parallel reconfigurable architectures, the selection of application specific computational patterns and application scheduling. It takes also into account architectural constraints. The method provides efficient design space exploration that selects existing processor instructions and new instructions implementing computational patterns on a reconfigurable cell fabric. All instructions are scheduled enabling parallel instruction execution. Our method can be used directly for VLIW architectures by relaxing constraints concerning cell-processor data transfers. MediaBench and MiBench benchmarks have been used for evaluation and we obtained optimal results in many cases.

The new Digital Video Broadcasting Satellite (DVB-S2) standard is able to provide capacity gains of about 30% over the previous standard by using a powerfull Forward Error Correction (FEC) scheme based on very large LDPC code words and BCH codes. The implementation of the DVBS2FEC decoder is a big challenge. The designer must deal with the overall design complexity and the decoding throughput in order to obtain a high decoding performance in terms of bit error rate (BER). We present in detail a complete design flow allowing a better understanding of the algorithm in terms of complexity, performance and its hardware implementation. We focus on complexity-performance trade-offs due to message quantizations and we compare its effects on several algorithm corrections used to check nodes for DVB-S2 decoding. The simulation results show that the best compromise between complexity and performance is obtained for the FOMS algorithm approximation.

In this paper, we discuss a low power embedded sensor node architecture we are developing for distributed sensor network systems deployed in a natural environment. In particular, we examine the sensor node for energy efficient processing-at-the-sensor. We analyze the following modes of operation; event detection, data acquisition, and data processing using low power, high performance embedded technology such as specialized embedded DSP processors and low power FPGAs at the sensing node. We use compute intensive sensor node applications: an acoustic vehicle classifier (frequency domain analysis) and a video license plate identification application (learning algorithm). We report performance and energy for these applications and discuss the system architecture design trade offs.

This paper presents a new constraint-driven method for computational pattern selection, mapping and application scheduling using reconfigurable processor extensions. The presented method is a part of DURASE system (Generic Environment for Design and Utilization of Reconfigurable Application-Specific Processors Extensions). The selected processor extensions are implemented as specialized processor instructions. They correspond to computational patterns identified as most frequently occurring or other interesting patterns in the application graph. Our methods can handle both time-constrained and resource-constrained scheduling. Experimental results obtained for the Media-Bench and Mi-Bench benchmarks show that the presented method ensures high speed-ups in application execution.

Low Density Parity Check (LDPC) codes have recently been chosen in the CCSDS standard for uses in near-earth applications. The specified code belongs to the class of Quasi-Cyclic LDPC codes which provide very high data rates and high reliability. Even if these codes are suited to high data rate, the complexity of LDPC decoding is a real challenge for hardware engineers. This paper presents a generic architecture for a CCSDS LDPC decoder. This architecture uses the regularity and the parallelism of the code and a genericity based on an optimized storage of the data. Two FPGA implementations are proposed: the first one is low-cost oriented and the second one targets high-speed decoder.

In this paper, we present a novel method for merging sets of computational patterns into a reconfigurable cell respecting design constraints and optimizing specific design aspects. Each cell can then be used in a run-time reconfigurable processor extension. Our method uses constraint programming to define the pattern merging problem and therefore can easily include design constraints and optimize different design aspects. Experiments carried out on Media-Bench test suite indicate 50% average reduction of cell area without increasing critical path.

This article presents a new tool for automatic design of application-specific reconfigurable processor extensions based on UPaK (Abstract U nified Pa tterns Based Synthesis K ernel for Hardware and Software Systems). We introduce a complete design flow that identifies new instructions, selects specific instructions and schedules a considered application on the newly created reconfigurable architecture. The identified extensions are implemented as specialized sequential or parallel instructions. These instructions are executed on a reconfigurable unit implementing all merged patterns. Our method uses specially developed algorithms for subgraph isomorphism that are implemented as graph matching constraints. These constraints together with separate algorithms are able to efficiently identify computational patterns and carry out application mapping and scheduling. Our methods can handle both time-constrained and resource-constrained scheduling. Experimental results show that the presented method provides high coverage of application graphs with small number of patterns and ensures high application execution speedup both for sequential and parallel application execution with reconfigurable processor extensions implementing selected patterns.

This paper presents a new method for automatic selection of application-specific processor extensions and shows how applications are scheduled on these new reconfigurable architectures. The extensions are implemented as specialized sequential or parallel instructions. They correspond to identified most frequently occurring computational patterns or other interesting patterns and are finally selected during mapping and scheduling. Our methods can handle both time-constrained and resource-constrained scheduling. Experimental results show that the presented method provides high coverage of application graphs with small number of patterns and ensures high application execution speed-up both for sequential and parallel application execution with processor extensions implementing selected patterns.

We propose a parallel and modular architecture well suited to 802.16e WiMax LDPC code decoding. The proposed design is fully compliant with all the code classes defined by the WiMax standard. It has been validated through an implementation on a Xilinx Virtex5 FPGA component. A four or six-module FPGA design yields a throughput ranging from 10 to 30 Mbit/s by means of 20 iterations at a clock frequency of 160 MHz which mostly satisfies communication throughput in the case of the WiMax mobile communication.

In this paper, we introduce a constraint programming-based approach for optimization of routing and reconfiguration overhead for a class of reconfigurable processor array architectures called weakly programmable. For a given set of different algorithms the execution of which is supposed to be switched upon request at run-time, we provide static solutions for optimal routing of data between processors as well as for minimization of the routing area and the reconfiguration overhead when switching between the execution of these algorithms. In fact, applying the switching can be accomplished in just a few clock cycles. Our experiments confirm that our method can minimize routing overhead and reduce reconfiguration time significantly.

We propose a new powerful scalable generic parallel and modular architecture well suited to LDPC code decoding. This architecture template has been instantiated in the case of the 802.16e WiMax standard. The proposed design is fully compliant with all the code classes defined by the standard. It has been validated through an implementation on a Xilinx Virtex5 FPGA component. A four or six-module FPGA design yields a throughput ranging from 10 to 30 Mbit/s by means of 20 iterations at a clock frequency of 160 MHz which mostly satisfies communication throughput in the case of the WiMax mobile communication.

In this paper, we present a constraint programming-based approach for optimization of routing and reconfiguration overhead for a class of reconfigurable processor array architectures called weakly programmable. For a given set of different algorithms the execution of which is supposed to be switched upon request at run-time, we provide static solutions for optimal routing of data between processor elements as well as for minimization of the routing area and the reconfiguration overhead when switching between the execution of these algorithms. Our experiments confirm that our method can minimize routing overhead and reduce reconfiguration time significantly.

In this paper, we introduce a constraint programming-based approach for the optimization of area and of reconfiguration time for communication networks for a class of regular 2D reconfigurable processor array architectures. For a given set of different algorithms the execution of which is supposed to be switched upon request at run-time, we provide static solutions for the optimal routing of data between processors. Here, we support also multi-casting data transfers for the first time. The routing found by our method minimizes the area or the reconfiguration time of the communication network, when switching between the execution of these algorithms. In fact, when switching, the communication network reconfiguration can be executed in just a few clock cycles. Moreover the communication network area can be minimized significantly (62% in average).

This paper presents a new method for computational patterns identification that forms basis for application specific instruction selection. The new algorithm is radically different from previous proposed methods. It is based on graph isomorphism constraint and constraint programming that makes it very flexible and provides opportunity to mix graph isomorphism constraints, other constraints and heuristic search for patterns in one formal environment. This algorithm takes into account graph structure and frequency of occurrence of patterns in application graphs. We have extensively evaluated our algorithm on MediaBench benchmarks. The experimental results indicate very good performance of our algorithm. It provides very high coverage for most graphs with a small number of identified computational patterns in a short amount of time.

We propose a run-time re-configurable parametric architecture (fabric) for local neighborhood image processing. The proposed architecture is composed of polymorphous cells where each cell accesses neighborhood data from a local cell memory, and executes a neighborhood function sequentially. The architecture is flexible since different neighborhood functions can be implemented by rewriting a cell's software micro-code. High throughput is achieved because many cells execute concurrently. We show that for a satellite image feature extraction application, our architecture, implemented on Stratix II and Virtex 2 field programmable gate arrays, achieves similar performance, hardware resource utilization, and throughput as a fully pipelined systolic array architecture, yet offers imp roved flexibility to the developer. We compare and contrast these two architectures for their usability to the image processing community

The authors propose a run-time re-configurable architecture for local neighborhood image processing. Discussion of how the new architecture can offer improved flexibility to the developer. The authors show that for a satellite image feature extraction application, our architecture, implemented on Stratix II and Virtex 2 field programmable gate arrays, achieves similar performance, hardware resource utilization, and throughput as fully pipelined systolic array architecture

This paper presents a novel method to generate optimized architecture of hardware processes implemented on "system on a programmable chip" (SoPC). The hardware processes are the applications tailored "cells" in the processor-coupled polymorphous fabric (Ch. Wolinski et al., 2003, Ch. Wolinski et al., 2002) implemented on the reconfigurable SoPC platform. In order to obtain optimized high performance pipelined architecture each process implementing repetitive conditional behavior with possible inter-iteration dependencies is scheduled under hardware resource constraints using "fabric cell synthesis tool" (FAST). The scheduling problem is defined and solved using constraints programming approach. This approach makes it possible to obtain optimal solutions in terms of execution time and number of registers for a number of real cases. Our method is illustrated using a simple example and a part of the "CORDIC" application (S.F. Hsiao et al., 1991). The final design is implemented on a reconfigurable platform that shows feasibility of our approach. Optimal schedules are achieved for both discussed applications.

This paper presents a method to obtain an optimized static schedule of CSP-like communications between a collection of concurrent hardware processes implemented on "system on a programmable chip" (SoPC). The hardware processes are the applications tailored "cells" in the processor-coupled polymorphous fabric (Wolinski et al., 2003 and Wolinski et al., 2002) implemented on the Altera Excalibur Arm SoPC platform. In our global approach, a static communications schedule is adopted to reduce hardware overhead due to inter-cells message transfer synchronization and to speed-up application execution. The scheduling problem is defined and solved using constraints programming approach. This approach makes it possible to obtain optimal communication schedules in a number of real cases. It makes also possible to easily generate pipelined schedules that improve significantly performance of the final implementation. Our method is illustrated with a fabric-based implementation of the K-means clustering algorithm. An optimal communication scheduled is achieved for this application.

We describe a unified approach to scheduling point-to-point uni-directional communications among concurrent FPGA-based hardware processes. In this model, processes have separate address spaces, and share data through communication. Once a channel is written, it may not be re-written until the receiving process reads the data. Thus if the writer process is ready before the reader has read the previous message, the writer must stall. We present an algorithm to automatically generate synchronized hardware schedules for the parallel processes that communicate, so that hardware stall management is not required. The algorithm requires that the parallel processes conform to certain constraints in program control structures and communications forms. If the processes do not conform to these requirements, hardware-supported stall mechanisms are used. We quantify the impact in area and clock speed between compiler-generated synchronization of process schedules and run-time, hardware-mediated synchronization.

This paper presents a novel approach to scheduling communications among concurrent hardware processes mapped onto a "System on a Programmable Chip." Point-to-point, broadcast and multi-cast ommunication types are supported. The algorithm has been prototyped on the Processor-Coupled Polymorphous Fabric for the Altera Excalibur Arm architecture. The communication schedule problem has been specified using Constraints Programming. The advantages of our method are the following: Application of a general constraint solver makes it possible to express many different sorts of constraints in a uniform manner. All imposed constraints are handled by the solver concurrently which increases the chances of obtaining optimal results. The scheduler guarantees that loops periods are the same for each iteration so the smaller controllers can be generated. The method has been illustrated with a Fabric-based implementation of the K-means clustering algorithm for which an optimal communication schedule has been achieved.

A Fabric-Based System (FBS) is a parameterized cellular architecture in which an array of computing cells communicates with an embedded processor through a global memory. This architecture is customizable to different classes of applications by functional unit, interconnect, and memory parameters, and can be instantiated efficiently on platform FPGAs (field programmable gate array). In previous work (Bellows et al., 2002), we have demonstrated the advantage of reconfigurable fabrics for image and signal processing applications. Recently, we have built a Fabric Generator (FG), a Java-based toolset that greatly accelerates construction of the fabrics. A module-generation library is used to define, instantiate, and interconnect cells' datapaths. FG also generates customized sequencers for individual cells or collections of cells. We describe the Fabric-Based System model, the FG toolset, and concrete realizations of fabric architectures generated by FG on the Altera Excalibur ARM that can deliver 4.5 GigaMACs/s (8/16 bit data, multiply-accumulate).

As hardware designs get increasingly complex and time-to-market constraints get tighter there is strong motivation for high-level synthesis (HLS). HLS must efficiently handle both dataflow-dominated and controlflow-dominated designs as well as designs of a mixed nature. In the past efficient tools for the former type have been developed but so far HLS of conditional behaviors lags behind. To bridge this gap an efficient scheduling heuristic for conditional behaviors is presented. Our heuristic and the techniques it utilizes are based on a unifying design representation appropriate for both types of behavioral descriptions, enabling the proposed heuristic to exploit under the same framework several well-established techniques (chaining, multicycling) as well as conditional resource sharing and speculative execution which are essential in efficiently scheduling conditional behaviors. Preliminary experiments confirm the effectiveness of our approach and prompted the development of the CODESIS HLS tool for further experimentation.

This paper presents a new high-level synthesis (HLS) approach which addresses the problem of synthesis of conditional behaviors. In proposed methodology, the conditional behaviors are represented by Hierarchical Conditional Dependence Graphs (HCDG) and synthesized using derived Constraints Logic Programming (CLP) models. Our synthesis methods exploit multicycle operations and chaining as well as conditional resource sharing and speculative execution at the same time. These techniques are essential in HLS and the experiments carried out using the developed prototype system showed good performance of the synthesized designs and proved the feasibility of the presented approach.

Scheduling conditional behaviors necessitates the use of a variety of scheduling optimization techniques like conditional resource sharing and speculative execution. Previous research work has clearly shown their effectiveness. The developed heuristics have several drawbacks relating to the effects of syntactic variance on the results. In this paper a list-based scheduling heuristic that exploits conditional resource sharing and speculative execution possibilities, is presented. Its results are quite insensitive to syntactic variance and conditional behavior is effectively accounted for by a probabilistic priority function.