Method and computer program for determining a placement of at least one circuit for a reconfigurable logic device

• US 10,460,062 B2
• Filed: 12/11/2017
• Issued: 10/29/2019
• Est. Priority Date: 12/12/2016
• Status: Active Grant

• Current Assignee: Fraunhofer Gesellschaft Zur Foerderung Der Angewandten Forsching E.V.
• Original Assignee: Fraunhofer Gesellschaft Zur Foerderung Der Angewandten Forsching E.V.
• Inventors: Feld, Dustin, Soddemann, Thomas
• Primary Examiner(s): Alam, Mohammed
• Application Number:
  US15/837,124
• Publication Number:
  US 20180165400A1
• Time in Patent Office: 687 Days
• Field of Search: 716121
• CPC Class Codes: G06F 2111/04 Constraint-based CAD
• CPC Class Codes: G06F 2111/20 Configuration CAD, e.g. designing by assembling or positioning modules selected from libraries of predesigned modules
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18
• CPC Class Codes: G06F 30/34 for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]
• CPC Class Codes: G06F 30/347 Physical level, e.g. placement or routing
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

Embodiments relate to a method and computer program for determining a placement of at least one circuit for a reconfigurable logic device. The method comprises obtaining (110) information related to the at least one circuit. The at least one circuit comprises a plurality of blocks and a plurality of connections between the plurality of blocks. The plurality of blocks comprise a plurality of logic blocks. The method further comprises calculating (120) a circuit graph based on the information related to the at least one circuit. The circuit graph comprises a plurality of nodes and a plurality of edges. The plurality of nodes represent at least a subset of the plurality of blocks of the at least one circuit and wherein the plurality of edges represent at least a subset of the plurality of connections between the plurality of blocks of the at least one circuit. The method further comprises determining (130) a force-directed layout of the circuit graph. The force-directed layout is based on attractive forces based on the plurality of connections between the plurality of blocks and based on repulsive forces between the plurality of blocks. The method further comprises determining (140) a placement of the plurality of logic blocks onto a plurality of available logic cells of the reconfigurable logic device based on the force-directed layout of the circuit graph.

Claims

1. A method for determining a placement of at least one circuit for a reconfigurable logic device, the method comprising:

obtaining information related to the at least one circuit, wherein the at least one circuit comprises a plurality of blocks and a plurality of connections between the plurality of blocks, and wherein the plurality of blocks comprise a plurality of logic blocks and a plurality of input/output blocks;

calculating a circuit graph based on the information related to the at least one circuit, wherein the circuit graph comprises a plurality of nodes and a plurality of edges, wherein the plurality of nodes represent at least a subset of the plurality of blocks of the at least one circuit and wherein the plurality of edges represent at least a subset of the plurality of connections between the plurality of blocks of the at least one circuit;

determining a force-directed layout of the circuit graph, wherein the force-directed layout is based on attractive forces based on the plurality of connections between the plurality of blocks and based on repulsive forces between the plurality of blocks; and

determining a placement of the plurality of logic blocks onto a plurality of available logic cells of the reconfigurable logic device based on the force-directed layout of the circuit graph

determining a placement of the plurality of input/output blocks onto a plurality of available input/output cells, wherein the determining of the placement of the plurality of input/output blocks is based on the force-directed layout of the circuit graph and based on the placement of the plurality of logic blocks.

2. The method according to claim 1, wherein the determining of the placement of the plurality of logic blocks is based on an arrangement of nodes of the plurality of nodes defined by the force-directed layout of the circuit graph.

3. The method according to claim 1, wherein the determining of the force-directed layout of the circuit graph is based on determining an energy-minimal state of a plurality of spring functions between the plurality of nodes, wherein the plurality of spring functions are based on a counteracting between the attractive forces and the repulsive forces.

4. The method according to claim 1, wherein the determining of the force-directed layout is based on a Manhattan-distance between nodes of the plurality of nodes,

and/or wherein a repulsive force of a block of the plurality of blocks increases with a number of connections of the block of the plurality of blocks,

and/or wherein the plurality of available logic cells is arranged in a three-dimensional grid,

and wherein the force-directed layout of the circuit graph corresponds to a three-dimensional force-directed layout of the circuit graph based on attractive and repulsive forces.

5. The method according to claim 1, wherein the determining of the placement of the plurality of logic blocks comprises:

partitioning the placement of the plurality of logic blocks into a plurality of partitions, and

determining a refinement of the placement of the plurality of logic blocks onto the plurality of available logic cells based on a local refinement of partitions of the plurality of partitions based on an optimization criterion.

6. The method according to claim 1, wherein the determining of the force-directed layout of the circuit graph further comprises rotating an intermediate force-directed layout of the circuit graph;

and/or wherein the determining of the force-directed layout of the circuit graph further comprises rotating an intermediate force-directed layout of the circuit graph based on an evaluation of predicted routing distances for a plurality of rotation angles;

and/or wherein the determining of the force-directed layout of the circuit graph comprises at least determining a first force-directed layout of the circuit graph and determining a second force-directed layout of the circuit graph to obtain the force-directed layout of the circuit graph, wherein the attractive forces used for the second force-directed layout of the circuit graph are based on the criticality of paths defined by the plurality of logic blocks and influenced by the length of the edges of the first force-directed layout of the circuit graph.

7. The method according to claim 1, wherein the determining of the placement of the plurality of logic blocks onto a plurality of available logic cells comprises:

splitting the plurality of logic blocks into a plurality of slices based on a first direction based on the force-directed layout of the circuit graph, and

distributing logic blocks of a slice of the plurality of slices based on a second direction based on the force-directed layout of the circuit graph.

8. The method according to claim 1, further comprising:

determining a further force-directed layout of the circuit graph based on the placement of the plurality of input/output blocks and based on the attractive forces indicated by the plurality of connections between the plurality of cells; and

determining a refinement of the placement of the plurality of logic blocks onto the plurality of available logic cells based on the further force-directed layout of the circuit graph.

9. The method according to claim 8, wherein the force-directed layout of the circuit graph is based on a first distance metric and wherein the further force-directed layout of the circuit graph is based on a second distance metric being different from the first distance metric, and/or wherein the determining of the placement of the plurality of input/output blocks is based on a barycenter of logic blocks of the placement of the plurality of logic blocks connected to the plurality of input/output blocks.

10. The method according to claim 1, further comprising:

determining a routing of the plurality of connections between the plurality of blocks based on the placement of the plurality of logic blocks and based on the placement of the plurality of input/output-blocks.

11. The method according to claim 10, wherein the determining of the routing of the plurality of connections is based on a preferred routing of at least one critical path of the at least one circuit and/or on a predicted signal slack based on at least one critical path of the at least one circuit.

12. The method according to claim 1, wherein the plurality of blocks further comprises a plurality of memory blocks, wherein the method further comprises determining a placement of the plurality of memory blocks onto a plurality of available memory cells based on the force-directed layout of the circuit graph and based on the placement of the plurality of logic blocks,

and/or wherein the plurality of blocks further comprises a plurality of special function blocks, wherein the method further comprises determining a placement of the plurality of special function blocks onto a plurality of available special function cells based on the force-directed layout of the circuit graph and based on the placement of the plurality of logic blocks.

13. The method according to claim 1, further comprising determining a simulated shortest-path routing without capacity constraints on a routing architecture of the reconfigurable logic device to estimate a routability of a placement, and wherein at least one of the determining of the placement of the plurality of logic blocks, determining a placement of a plurality of input/input blocks, determining a placement of a plurality of memory blocks and determining a placement of a plurality of special function blocks is further based on the estimated routability of the placement.

14. A computer program having a program code for performing a method comprising:

obtaining information related to the at least one circuit, wherein the at least one circuit comprises a plurality of blocks and a plurality of connections between the plurality of blocks, and wherein the plurality of blocks comprise a plurality of logic blocks and a plurality of input/output blocks;

calculating a circuit graph based on the information related to the at least one circuit, wherein the circuit graph comprises a plurality of nodes and a plurality of edges, wherein the plurality of nodes represent at least a subset of the plurality of blocks of the at least one circuit and wherein the plurality of edges represent at least a subset of the plurality of connections between the plurality of blocks of the at least one circuit;

determining a force-directed layout of the circuit graph, wherein the force-directed layout is based on attractive forces based on the plurality of connections between the plurality of blocks and based on repulsive forces between the plurality of blocks; and

determining a placement of the plurality of logic blocks onto a plurality of available logic cells of the reconfigurable logic device based on the force-directed layout of the circuit graph

determining a placement of the plurality of input/output blocks onto a plurality of available input/output cells, wherein the determining of the placement of the plurality of input/output blocks is based on the force-directed layout of the circuit graph and based on the placement of the plurality of logic blocks.