Incremental generation of an FPGA implementation with a graph-based similarity search
View Patent ↗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.
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.