Incremental generation of an FPGA implementation with a graph-based similarity search

Patent metadata

Field	Value
Publication number	US-10706196-B2
Application number	US-201816207457-A
Country	US
Kind code	B2
Filing date	Dec 3, 2018
Priority date	Jan 10, 2018
Publication date	Jul 7, 2020
Grant date	Jul 7, 2020

Abstract

A method for generating an FPGA implementation based on an FPGA design serving as an FPGA model and/or a hardware description, including the steps of synthesizing a net list from the FPGA design and generating the FPGA implementation from the net list. The method includes searching for a similar FPGA implementation, the step of generating the FPGA implementation from the net list takes place using the similar FPGA implementation, the method includes a step of generating a graph-based representation based on the FPGA design, and the step of searching for a similar FPGA implementation comprises comparing the graph-based representation of the FPGA design with a graph-based representation of the at least one similar FPGA implementation. A method for generating a bit stream based on an FPGA design is also provided, serving as an FPGA model and/or a hardware description.

First claim

What is claimed is:

1. A method for generating an FPGA implementation based on an FPGA design as an FPGA model and/or a hardware description, the method comprising:
synthesizing a net list from the FPGA design;
generating a graph-based representation based on the FGPA design;
searching for a similar FGPA implementation; and
generating the FPGA implementation from the net list using the similar FPGA implementation,
wherein said searching for a similar FPGA implementation comprises comparing the graph-based representation of the FPGA design with a graph-based representation of the similar FPGA implementation.

2. The method according to claim 1 , wherein the FPGA design comprises a partial implementation,
wherein said searching for the similar FPGA implementation includes searching for a similar partial implementation, and
wherein said generating the FPGA implementation is performed using the similar partial implementation.

3. The method according to claim 1 , wherein said searching for the similar FPGA implementation comprises searching for a similar FPGA implementation in a database of prior FPGA implementations.

4. The method according to claim 1 , further comprising identifying a modified sub-region of the FPGA design,
wherein said synthesizing the net list comprises the synthesis of the net list for the modified sub-region of the FPGA design, and
wherein said generating the FPGA implementation comprises generating the FPGA implementation for the net list of the modified sub-region of the FPGA design.

5. The method according to claim 1 , further comprising:
determining a measure of similarity between the graph-based representation of the FPGA design and the graph-based representation of the at least one similar FPGA implementation; and
generating the FPGA implementation from the net list without using a similar FPGA implementation if a measure of similarity is below a threshold value.

6. The method according to claim 1 , wherein said comparing the graph-based representation of the FPGA design with the graph-based representation of the similar FPGA implementation comprises solving a linear optimization problem in which for each node in a graph, and
wherein the most similar node is identified in another graph without duplicate assignment of a node.

7. The method according to claim 1 , further comprising determining the similarity between a node of the graph-based representation of the FPGA design and a node of the graph-based representation of the at least one similar FPGA implementation, including determining a match of differentiation points.

8. The method according to claim 7 , wherein said determining a match of the differentiation points comprises a weighting of the differentiation points.

9. The method according to claim 1 , further comprising:
performing a similarity analysis of a plurality of graphs contained in the database; and
storing the computed similarities in a similarity diagram or matrix.

10. The method according to claim 9 , further comprising calculating similarities of relationships between the graphs contained in the database.

11. The method according to claim 1 , further comprising performing a prior determination of expected high similarities of relationships not yet determined using already determined similarities.

12. The method according to claim 1 , wherein said comparing the graph-based representation of the FPGA design with a graph-based representation of the similar FPGA implementation comprises neighbor matching to account for neighborhood relationships.

13. The method according to claim 1 , wherein said generating a graph-based representation based on the FPGA design comprises a de-hierarchization of the FPGA design while accounting for virtual connections and the application of a transformation function based on the de-hierarchization of the FPGA design.

14. The method of claim 1 , wherein said synthesizing the net list from the FPGA design and said generating the graph-based representation based on the FPGA design are performed in parallel.

15. The method of claim 1 , wherein said comparing the graph-based representation of the FPGA design with a graph-based representation of the at least one similar FPGA implementation is performed based on an algorithm for the similarity analysis of graphs.

16. A method of generating a bit stream based on an FPGA design serving as an FPGA model and/or a hardware description, the method comprising:
generating an FPGA implementation based on an FPGA design serving as an FPGA model and/or a hardware description according to claim 1 ; and
generating the bit stream from the generated FPGA implementation.

Assignees

• Dspace Gmbh

Inventors

• Lubeley Dominik
• Kalte Heiko

Classifications

• G06F30/34 Primary

  for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD] · CPC title

• G06F2117/06

  Spare resources, e.g. for permanent fault suppression · CPC title

• G06F30/327

  Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist · CPC title

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/90335

  Query processing · CPC title