Method of routing in a programmable logic device
A method is disclosed to efficiently route in a programmable logic device (PLD) such as a field-programmable gate array (FPGA). The method includes identifying a source and destination pair in a circuit design; determining multiple candidate paths to route a vector between the source and destination pair; and selecting one of the candidate paths for the vector route. Efficiency may be improved by using time-division multiplexing to route multiple connections through a PLD element.
1. A method of routing a programmable logic device, comprising:
reading a design containing connectivity information;
assigning priorities to vector connections identified in the design based on the connectivity information;
selecting a path for a vector connection using the assigned priorities; and
searching for alternate paths using one or more iterative processes, wherein the iterative processes including choosing an alternate path and adjusting a cost of one or more elements used in the path, wherein the choosing an alternate path comprises:
identifying one or more possible paths for an unsuccessful vector connection;
identifying path elements in one of the identified possible paths:
determining whether the path elements can be made available to a vector connection by searching for alternate paths for other vector connections that use the path elements; end
performing the following if the path elements can be made available:
selecting the possible path containing the available path elements;
adjusting the cost of all path elements in the selected path; and
selecting the alternate paths for the other vector connections that are using the required path elements.
2. The method of claim 1 , wherein the steps of claim 1 are stored as instructions on a computer-readable medium.
3. A method of configuring time-varying connections in a programmable logic device, comprising:
reading a design containing connectivity and timing information;
assigning priorities to the time-varying connections identified in the design based on the connectivity and timing information; and
selecting a path for a time-varying connection using the assigned priorities, wherein the assigning priorities comprises:
building a routing table containing the connectivity information, the connectivity information comprising source, destination, timing and cost estimate information for time-varying connections; and
using the cost estimate information to assign priorities.
4. The method of claim 3 , wherein the timing information includes state information.
5. The method of claim 3 , wherein the connections are vector connections.
6. The method of claim 3 , wherein the building a routing table comprises:
identifying source and destination information for a time-varying connection;
identifying state information for the time-varying connection;
calculating a cost estimate for the time-varying connection; and
including source, destination, and cost estimate information in the routing table.
7. The method of claim 3 , further comprising iteratively searching for alternate paths using one or more iterative processes.
8. The method of claim 3 , wherein the steps of claim 3 are stored as instructions on a computer-readable medium.
9. A method of configuring time-varying connections in a programmable logic device, comprising:
reading a design containing connectivity and timing information;
assigning priorities to time-varying connections identified in the design based on the connectivity and timing information; and
selecting a path for a time-varying connection using the assigned priorities;
wherein the selecting a path for a time-varying connection comprises:
generating one or more possible paths for a time-varying connection;
calculating an actual cost associated with a possible path;
selecting the path with the lowest actual cost; and
reserving the selected paths elements for the time-varying connection's states.
10. The method of claim 9 , wherein the timing information includes state information.
11. The method of claim 9 , wherein the connections are vector connections.
12. The method of claim 9 , further comprising iteratively searching for alternate paths using one or more iterative processes.
13. The method of claim 9 , wherein the steps of claim 9 are stored as instructions on a computer-readable medium.