Placement processing for programmable logic devices
First Claim
1. A method of mapping a plurality of circuit elements onto a plurality of configurable logic blocks (CLBs) in a programmable logic device (PLD), comprising:
- generating a mapping of the circuit elements to the GLBs in the PLD;
selecting a critical path in the PLD corresponding to the mapping, wherein;
the critical path comprises a first node in a first GLB in the PLD; and
the first CLB further comprises one or more other nodes; and
changing node assignment of the first node from a current location to a different location without changing node assignment of at least one other node in the first CLB, wherein;
the change in node assignment results in a change of circuit performance;
the different location falls within an area adjacent to the current location;
the first node is a terminal node; and
the area is a circle centered at a connecting node having a radius corresponding to a distance measure between the terminal and connecting nodes.
4 Assignments
0 Petitions
Accused Products
Abstract
A method for placing configurable logic blocks (CLBs) in a PLD, such as an FPGA. In one embodiment, after packing gates/clusters into blocks and then assigning those blocks to CLBs to generate an initial placement, the packing and/or placement of CLBs is changed prior to performing CLB routing. For each node of the most critical of the K most critical paths in the initial placement, moving the node to a different CLB is considered in order to reduce the criticality of that path. A move is applied if certain acceptability conditions are met. After the most critical path is improved, the criticality of the K paths is updated, and the procedure is repeated for the new most critical of the K updated paths. The method, which can be automated to reduce human intervention in the design process, improves circuit performance, e.g., by enabling higher circuit operation frequencies.
-
Citations
26 Claims
-
1. A method of mapping a plurality of circuit elements onto a plurality of configurable logic blocks (CLBs) in a programmable logic device (PLD), comprising:
-
generating a mapping of the circuit elements to the GLBs in the PLD;
selecting a critical path in the PLD corresponding to the mapping, wherein;
the critical path comprises a first node in a first GLB in the PLD; and
the first CLB further comprises one or more other nodes; and
changing node assignment of the first node from a current location to a different location without changing node assignment of at least one other node in the first CLB, wherein;
the change in node assignment results in a change of circuit performance;
the different location falls within an area adjacent to the current location;
the first node is a terminal node; and
the area is a circle centered at a connecting node having a radius corresponding to a distance measure between the terminal and connecting nodes. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
packing circuit elements of a circuit design into blocks, each block corresponding to a CLB; and
generating the mapping by assigning the blocks to the CLBs in the PLD.
-
-
6. The invention of claim 5, wherein the mapping is generated using simulated annealing.
-
7. The invention of claim 1, wherein, for changing node assignment, the first node comprises a plurality of circuit elements.
-
8. The invention of claim 1, wherein:
-
selecting the critical path comprises;
identifying K critical paths in the PLD, where K>
1; and
selecting a most critical path of the K critical paths; and
the method further comprises;
selecting a new most critical path from K updated critical paths corresponding to the change in node assignment; and
changing node assignment for the new most critical path.
-
-
9. The invention of claim 1, wherein the distance measure is the Manhattan distance between the terminal and connecting nodes.
-
10. The invention of claim 1, wherein the change of circuit performance includes at least one of:
-
(i) change of one or more delays corresponding to one or more different paths having the reassigned node; and
(ii) size change of a bounding box for at least one net having the reassigned node.
-
-
11. The invention of claim 1, wherein changing node assignment includes at least one of:
-
(1) swapping two similar nodes between two locations;
(2) moving a node into an unassigned area of a new location; and
(3) swapping two dissimilar nodes between two locations.
-
-
12. The invention of claim 1, wherein:
-
the first CLB comprises a plurality of primitive elements; and
the first node comprises a subset of the plurality of primitive elements in the first GLB.
-
-
13. The invention of claim 1, wherein the critical path is a signal path having a longest signal propagation delay in the mapping.
-
14. A circuit mapping generated by implementing a method of mapping a plurality of circuit elements onto a plurality of configurable logic blocks (CLBs) in a programmable logic device (PLD), the method comprising:
-
generating an initial mapping of the circuit elements to the CLBs in the PLD;
selecting a critical path in the PLD corresponding to the initial mapping, wherein;
the critical path comprises a first node in a first CLB in the PLD; and
the first CLB further comprises one or more other nodes; and
changing node assignment of the first node from a current location to a different location without changing node assignment of at least one other node in the first CLB, wherein;
the change in node assignment results in a change of circuit performance;
the different location falls within an area adjacent to the current location;
the first node is a terminal node; and
the area is a circle centered at a connecting node and having a radius corresponding to a distance measure between the terminal and connecting nodes.
-
-
15. A programmed PLD having a plurality of circuit elements mapped onto a plurality of CLBs, the PLD generated by implementing a method comprising:
-
generating a mapping of the circuit elements to the CLBs in the PLD;
selecting a critical path in the PLD corresponding to the mapping, wherein;
the critical path comprises a first node in a first CLB in the PLD; and
the first CLB further comprises one or more other nodes; and
changing node assignment of the first node from a current location to a different location without changing node assignment of at least one other node in the first CLB, wherein;
the change in node assignment results in a change of circuit performance;
the different location falls within an area adjacent to the current location;
the first node is a terminal node; and
the area is a circle centered at a connecting node and having a radius corresponding to a distance measure between the terminal and connecting nodes.
-
-
16. A machine-readable medium, having encoded thereon program code, wherein, when the program code is executed by a machine, the machine implements a method of mapping a plurality of circuit elements onto a plurality of configurable logic blocks (CLBs) in a programmable logic device (PLD), the method comprising:
-
generating a mapping of the circuit elements to the CLBs in the PLD;
selecting a critical path in the PLD corresponding to the mapping, wherein;
the critical path comprises a first node in a first CLE in the PLD; and
the first CLB further comprises one or more other nodes; and
changing node assignment of the first node from a current location to a different location without changing node assignment of at least one other node in the first CLB, wherein;
the change in node assignment results in a change of circuit performances;
the different location falls within an area adjacent to the current location;
the first node is a terminal node; and
the area is a circle centered at a connecting node and having a radius corresponding to a distance measure between the terminal and connecting nodes. - View Dependent Claims (17, 18, 19)
packing circuit elements of a circuit design into blocks, each block corresponding to a CLB; and
generating the mapping by assigning the blocks to the CLBs in the PLD.
-
-
18. The invention of claim 16, wherein:
-
selecting the critical path comprises;
identifying K critical paths in the PLD, where K>
1; and
selecting a most critical path of the K critical paths; and
the method further comprises;
selecting a new most critical path from K updated critical paths corresponding to the change in node assignment; and
changing node assignment for the new most critical path.
-
-
19. The invention of claim 16, wherein the change of circuit performance includes at least one of:
-
(i) change of one or more delays corresponding to one or more different paths having the reassigned node; and
(ii) size change of a bounding box for at least one net having the reassigned node.
-
-
20. A method of mapping a plurality of circuit elements onto a plurality of configurable logic blocks (GLBs) in a programmable logic device (PLD), comprising:
-
generating a mapping of the circuit elements to the CLBs in the PLD;
selecting a critical path in the PLD corresponding to the mapping; and
for at least one node of the critical path, changing node assignment from a current location to a different location, wherein;
the change in node assignment results in a change of circuit performance;
the different location falls within an area adjacent to the current location;
the node is a terminal node; and
the area is a circle centered at a connecting node and having a radius corresponding to a distance measure between the terminal and connecting nodes. - View Dependent Claims (21)
-
-
22. A method of mapping a plurality of circuit elements onto a plurality of configurable logic blocks (CLBs) in a programmable logic device (PLD), comprising:
-
generating a mapping of the circuit elements to the CLBs in the PLD;
selecting a critical path in the PLD corresponding to the mapping; and
for at least one node of the critical path, changing node assignment from a current location to a different location, wherein;
the change in node assignment results in a change of circuit performance;
the different location falls within an area adjacent to the current location;
the node is an intermediate node; and
the area is an ellipse having the foci at two connecting nodes.
-
-
23. A machine-readable medium, having encoded thereon program code, wherein, when the program code is executed by a machine, the machine implements a method of mapping a plurality of circuit elements onto a plurality of configurable logic blocks (CLBs) in a programmable logic device (PLD), the method comprising:
-
generating a mapping of the circuit elements to the CLBs in the PLD;
selecting a critical path in the PLD corresponding to the mapping; and
for at least one node of the critical path, changing node assignment from a current location to a different location, wherein;
the change in node assignment results in a change of circuit performance;
the different location falls within an area adjacent to the current location;
the node is a terminal node; and
the area is a circle centered at a connecting node and having a radius corresponding to a distance measure between the terminal and connecting nodes.
-
-
24. A machine-readable medium, having encoded thereon program code, wherein, when the program code is executed by a machine, the machine implements a method of mapping a plurality of circuit elements onto a plurality of configurable logic blocks (CLBs) in a programmable logic device (PLD), the method comprising:
-
generating a mapping of the circuit elements to the CLBs in the PLD;
selecting a critical path in the PLD corresponding to the mapping; and
for at least one node of the critical path, changing node assignment from a current location to a different location, wherein;
the change in node assignment results in a change of circuit performance;
the different location falls within an area adjacent to the current location;
the node is an intermediate node; and
the area is an ellipse having the foci at two connecting nodes.
-
-
25. A method of mapping a plurality of circuit elements onto a plurality of configurable logic blocks (CLBs) in a programmable logic device (PLD), comprising:
-
generating a mapping of the circuit elements to the CLBs in the PLD;
selecting a critical path in the PLD corresponding to the mapping, wherein;
the critical path comprises a first node in a first CLB in the PLD; and
the first CLB further comprises one or more other nodes; and
changing node assignment of the first node from a current location to a different location without changing node assignment of at least one other node in the first CLB, wherein;
the change in node assignment results in a change of circuit performance;
the different location falls within an area adjacent to the current location;
the first node is an intermediate node; and
the area is an ellipse having the foci at two connecting nodes.
-
-
26. A machine-readable medium, having encoded thereon program code, wherein, when the program code is executed by a machine, the machine implements a method of mapping a plurality of circuit elements onto a plurality of configurable logic blocks (CLBs) in a programmable logic device (PLD), the method comprising:
-
generating a mapping of the circuit elements to the CLBs in the PLD;
selecting a critical path in the PLD corresponding to the mapping, wherein;
the critical path comprises a first node in a first CLB in the PLD; and
the first CLB further comprises one or more other nodes; and
changing node assignment of the first node from a current location to a different location without changing node assignment of at least one other node in the first GLB, wherein;
the change in node assignment results in a change of circuit performance;
the different location falls within an area adjacent to the current location;
the first node is an intermediate node; and
the area is an ellipse having the foci at two connecting nodes.
-
Specification