Automated system for designing and developing field programmable gate arrays

US 20040060032A1
Filed: 05/19/2003
Published: 03/25/2004
Est. Priority Date: 05/17/2002
Status: Active Grant

First Claim

Patent Images

1. An automated system for programming field programmable gate arrays (FPGAs) to implement a desired user-defined algorithm specified in a high level language for processing data vectors with one, two or more dimensions, the system comprising:

means for analyzing the user-defined algorithm to determine what logic components are required and their interrelationships, including means for determining how many of such components are required, the relative timing between the required components, and means for determining partial products and the presence of signal delays between selected components;

means for mapping the required logic components onto a target FPGA, including means for evaluating alternative interconnection routes between logic components within the target FPGA, and means for producing an optimized placement and routing of the logic components and interconnections on the target FPGA, and means for generating a low level command listing in a file operable to serve as an input file to a low-level conventional FPGA programming tool, whereby the FPGA programming tool from the input file is able to generate a hardware gate programming bitstream to be directed to the target FPGA, thereby programming the FPGA with the desired user-defined algorithm.

View all claims

5 Assignments

Timeline View

Assignment View

0 Petitions

Accused Products

Abstract

An automated system and method for programming field programmable gate arrays (FPGAs) is disclosed for implementing user-defined algorithms specified in a high level language. The system is particularly suited for use with image processing algorithms and can speed up the process of implementing and testing a fully written high-level user-defined algorithm to a matter of a few minutes, rather than the days, weeks or even months presently required using conventional software tools. The automated system includes an analyzer module and a mapper module. The analyzer determines what logic components are required and their interrelationships, and observes the relative timing between the required components and their partial products. It also ascertains when signal delays are required between selected components. The mapper module utilizes the output from the analyzer module and determines where the required logic components must be placed on a given target FPGA in order to reliably route, without interference, the required interconnections between various components and I/O. The mapper includes means for evaluating alternative interconnection routes between logic components within the target FPGA, and means for producing an optimized placement and routing of the logic components and interconnections on the target FPGA. The mapper also generates a low level command listing as a source file that serves as an input file for a conventional low-level FPGA programming tool. From that input file, the tool is able to generate a hardware gate-programming bitstream to be directed to the target FPGA, thereby programming the FPGA with the user-defined algorithm.

89 Citations

View as Search Results

20 Claims

1. An automated system for programming field programmable gate arrays (FPGAs) to implement a desired user-defined algorithm specified in a high level language for processing data vectors with one, two or more dimensions, the system comprising:
- means for analyzing the user-defined algorithm to determine what logic components are required and their interrelationships, including means for determining how many of such components are required, the relative timing between the required components, and means for determining partial products and the presence of signal delays between selected components;
  
  means for mapping the required logic components onto a target FPGA, including means for evaluating alternative interconnection routes between logic components within the target FPGA, and means for producing an optimized placement and routing of the logic components and interconnections on the target FPGA, and means for generating a low level command listing in a file operable to serve as an input file to a low-level conventional FPGA programming tool, whereby the FPGA programming tool from the input file is able to generate a hardware gate programming bitstream to be directed to the target FPGA, thereby programming the FPGA with the desired user-defined algorithm.
- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
- - 2. An automated system for programming FPGAs as set forth in claim 1, wherein:
    - the high level language that the user-defined algorithm is specified in is C++;
      
      the target FPGA is a Xilinx FPGA product; and
      
      the low-level conventional FPGA programming tool is part of an ISE FPGA program development platform.
  - 3. An automated system for programming FPGAs as set forth in claim 1 wherein:
    - the high level language in which the user-defined algorithm is specified is user-readable source code, and that such language is operable to specify parallelism at the source code level through object types; and
      
      the means for analyzing includes means for parsing the language of the source code using standard compiler techniques.
  - 4. An automated system for programming FPGAs as set forth in claim 3, wherein:
    - the means for analyzing includes;
      
      means for identifying vector elements within the source code; and
      
      means for providing a to provide a an operation dataflow graph that indicates the overall vector processing flow within the source code.
  - 5. An automated system for programming FPGAs as set forth in claim 4, wherein the means for analyzing includes:
    - means for identifying all operators and vector operands within the user-readable source code containing the user-defined algorithm; and
      
      means for determining from the identified operators and vector operands orders and dependencies of the procedures and operations specified by the source code.
  - 6. An automated system for programming FPGAs as set forth in claim 5, wherein the means for mapping includes:
    - means for automatically generating a mapping of necessary gates, logic components and connections needed on the target FPGA to accomplish the functions specified by the source code.
  - 7. An automated system for programming FPGAs as set forth in claim 1, further comprising:
    - means for specifying a selected overall vector processing architecture for the target FPGA, the architecture being selected from the group of digital image processing architectures including a parallel array processor, a raster sub-array processor, a pipeline raster sub-array processor and a multi-pipeline raster sub-array processor.
  - 8. An automated system for programming FPGAs as set forth in claim 7, the system further comprising:
    - a library of known functions, including first group of digital image processing functions, a second group of known arithmetic functions, and third group of Boolean functions, the library being operable to be callable by the means for analyzing and by the means for mapping, and wherein;
      
      the means for analyzing includes at least a first set of pre-determined rules representing known constraints associated with the target FPGA and with at least some of the known functions in the library, and first means for accessing the first set of rules with respect to the analysis of the user-defined algorithm such that design choices are made automatically within the means for analyzing based at least in part on a plurality of the rules from the first set of pre-determined rules; and
      
      the means for mapping includes at least a second set of pre-determined rules representing known constraints associated with the target FPGA and with at least some of the known functions in the library, and second means for accessing the second set of rules with respect to the mapping of the user-defined algorithm in order to develop and arrange logic components for the target FPGA based at least in part upon at least a plurality of the rules from the second set of pre-determined rules.
  - 9. An automated system for programming FPGAs as set forth in claim 1, the system further comprising:
    - a target FPGA which includes a plurality of configurable logic blocks, RAM memory portions, and multiplier portions.
  - 10. An automated system for programming FPGAs as set forth in claim 9, wherein the target FPGA is a Xilinx brand FPGA programmable with standard tools provided as part of the Virtex II platform from Xilinx.

11. A method for programming field programmable gate arrays (FPGAs) substantially automatically so as to render the FPGA operable to implement a user-selected algorithm involving the processing of data that is specified in a source code listing, the method comprising the steps of:
- considering constraints associated with the user-selected algorithm including data processing steps involved and throughput speed requirements;
  
  selecting a target FPGA to utilize;
  
  selecting a specific data processing architecture to use in connection with the low-level programming of the target FPGA;
  
  automatically analyzing the source code listing in order to identify order of functions and dependencies within the source code; and
  
  automatically generating a mapping for implementing the user-selected algorithm on the target FPGA, taking into account the identified functions and dependencies within the source code during the step of automatically analyzing.
- View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19)
- - 12. The method of programming FPGAs as forth in claim 11, further comprising:
    - providing the mapping from the step of automatically generating to a conventional FPGA programming tool so that the tool is now operable to generate a bitstream for hardware gate programming of the FPGA.
  - 13. The method of programming FPGAs as set forth in claim 12, further comprising the step of:
    - using the FPGA programming tool to generate a bitstream for hardware gate programming of the target FPGA.
  - 14. The method of programming FPGAs as set forth in claim 12, further comprising the step of:
    - providing the bitstream to the target FPGA, whereby the user-selected algorithm is actually programmed into the target FPGA.
  - 15. The method of programming FPGAs as set forth in claim 11, wherein:
    - the step of automatically generating a mapping produces a user-readable low-level source code to be provided to the FPGA programming tool.
  - 16. The method of programming FPGAs as set forth in claim 11, wherein the mapping from the step of automatically generating is provided to a low level programming tool which generates the bitstream for the hardware programming of the target FPGA and delivers the bitstream to the FPGA burn-in system, which substantially immediately uses the bitstream to program the target FPGA, whereby the user-specified algorithm can be thereafter tested for proper operation after no more than a few moments or minutes after having the algorithm programmed therein.
  - 17. The method of programming FPGAs as set forth in claim 11, wherein:
    - the step of automatically mapping includes automatically generating layout and routing information; and
      
      the step of specifically selecting an architecture results in a multi-pipeline raster sub-array processor architecture being selected.
  - 18. The method of programming FPGAs as set forth in claim 17 wherein:
    - providing, through FPGA programming system vendor, automatic programming software as part of a software package for designing, developing and testing FPGA programs, the software being arranged to handle at least a plurality of data processing architectures usable with at least a certain type of target FPGA;
      
      providing, as part of the automatic programming software, a library of known image processing functions, arithmetic functions and Boolean functions;
      
      providing, as part of the automatic programming software, at least a first predetermined input output structure to be utilized to connect at least a first pre-specified input and at least a first pre-specified output to the target FPGA; and
      
      the step of automatically mapping includes automatically generating partial layout and routing information which is operable to be connected to pre-specified input and output structures specified at least in part in conjunction with the target FPGA.
  - 19. The method of programming FPGAs as set forth in claim 11 wherein:
    - the step of automatically mapping is arranged to produce a generally serpentine flow path in the target FPGA, such that needed interconnections between various configurable logic blocks within the FPGA are simplified and reduced in length in comparison to do what they would be if a non-serpentine flow path were utilized to implement the user-selected algorithm in the target FPGA; and
      
      the step of automatically mapping, as part of the implementation of the user-selected algorithm, instantiates substantially only operations called out by the source code listing of user-selected algorithm.

20. A computer program product, to be used in a FPGA development and programming environment, the software product comprising:
- a storage medium readable by at least one processing circuit and storing instructions for execution for by the processing circuit for performing a method comprising the steps of considering constraints associated with the user-selected algorithm including data processing steps involved and throughput speed requirements;
  
  selecting a target FPGA to utilize;
  
  selecting a specific data processing architecture to use in connection with the low-level programming of the target FPGA;
  
  automatically analyzing the source code listing in order to identify order of functions and dependencies within the source code; and
  
  automatically generating a mapping for implementing the user-selected algorithm on the target FPGA, taking into account the identified functions and dependencies within the source code during the step of automatically analyzing.

Specification

Resources

Litigation Campaign Assessment

Current Assignee
Pixel Velocity Incorporated
Original Assignee
Pixel Velocity Incorporated
Inventors
McCubbrey, David L.

Granted Patent

US 7,073,158 B2
Time in Patent Office

Days
Field of Search
US Class Current

716/16
CPC Class Codes

G06F 2119/06   Power analysis or power opt...

G06F 30/34   for reconfigurable circuits...

G06F 8/456   Parallelism detection

H05K 1/144   Stacked arrangements of pla...

Automated system for designing and developing field programmable gate arrays

First Claim

5 Assignments

0 Petitions

Accused Products

Abstract

89 Citations

20 Claims

Specification

Solutions

Use Cases

Quick Links

Automated system for designing and developing field programmable gate arrays

First Claim

5 Assignments

Subscription Required

Subscription Required

0 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

89 Citations

20 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links