Deterministic parallel routing approach for accelerating pathfinder-based algorithms
View Patent ↗A field-programmable gate array (FPGA) routing tool within a computer-aided design system. The tool includes an input device for receiving a netlist containing nets with source nodes, sink nodes, and intermediate nodes at fixed positions. The tool further includes a processing circuitry configured with a design router responsible for constructing non-overlapping routing trees for all nets, ensuring connections from source nodes to sink nodes without exceeding fixed routing resource capacity of the FPGA. The design router utilizes incremental routing, which applies deterministic parallel routing to a window of initial iterations with high routing workload and sequential routing to subsequent iterations. Additionally, a display device is provided to continuously exhibit interconnections and routing utilization during the determination of routing trees.
1. A field programmable gate array (FPGA) routing tool in a computer-aided design system, comprising:
an input device for receiving a netlist having nets with source nodes, sink nodes, and a plurality of intermediate nodes at fixed positions; and
processing circuitry configured with
a design router for building non-overlapping routing trees for all nets, including finding a routing tree for each net that connects the source nodes to the sink nodes without exceeding a capacity of fixed routing resources available on the FPGA;
the design router with incremental routing that:
applies deterministic parallel routing to a window of initial iterations having a high routing workload, where the window of initial iterations covers a range from a first iteration to an i-th iteration, and
applies sequential routing to all iterations after the i-th iteration; and
a display device to continuously display interconnections and a routing utilization while the routing trees are being determined.
2. The routing tool of claim 1 , wherein the window of initial iterations is a window of first K iterations, where K is a positive integer smaller than a predefined threshold.
3. The routing tool of claim 1 , wherein the design router applies parallel routing that includes
divide the nets (N) into N P blocks of substantially equal sizes; and
sequentially route all nets belonging to the block assigned to it.
4. The routing tool of claim 3 , wherein the design router applies parallel routing that further includes
divide the nets into two sets: C HF , and C LF , where C HF contains the nets having high fanout and C LF contains the nets having small fanout, wherein the high fanout nets are those nets whose fanout is more than or equal to a fanout threshold value.
5. The routing tool of claim 4 , wherein the design router applies the sequential routing that includes
partition the nets in C LF into three sets: C U , C L , and C LU , where C U and C L contain non-overlapping nets, and C LU contains nets that lie in both partitions C U and C L , and
perform sequential routing of nets in a union of {C HF and C LU } using a connection router C 0 .
6. The routing tool of claim 5 , wherein the design router applies net partitioning that includes
find a cutline that separates the nets into upper and lower halves based on their bounding boxes while ensuring that each partition has nearly equal number of branches to route.
7. The routing tool of claim 6 , wherein the design router applies net partitioning that includes
find the cutline's vertical axis, denoted by I, which is equal to an index where one-to-one difference between elements of an array “Workload-after” and an array “Workload-before” is minima.
8. The routing tool of claim 7 , wherein the design router applies net partitioning that includes
insert all nets whose bounding boxes lie completely on an upper side of the cutline into C U , and the nets whose bounding boxes lie on a lower side of the cutline into C L , and the nets whose bounding boxes crosses the cutline are inserted in C LU .
9. A non-transitory computer-readable storage medium including computer executable instructions, wherein the instructions, when executed by a computer, cause the computer to perform a method for routing a field programmable gate array (FPGA) by a routing tool in a computer-aided design system, the method comprising:
receiving, by an input device, a netlist having nets with source nodes, sink nodes, and a plurality of intermediate nodes at fixed positions; and
building, by processing circuitry, non-overlapping routing trees for all nets, including determining a routing tree for each net that connects the source nodes to the sink nodes without exceeding a capacity of fixed routing resources available on the FPGA;
applying, by the processing circuitry, deterministic parallel routing to a window of initial iterations having a high routing workload, where the window of initial iterations covers a range from a first iteration to an i-th iteration, and applying sequential routing to all iterations after the i-th iteration;
and
continuously displaying, by a display device, a interconnections and a routing utilization while the routing trees are being determined.
10. The non-transitory computer-readable storage medium of claim 9 , wherein the window of initial iterations is a window of first K iterations, where K is a positive integer smaller than a predefined threshold.
11. The non-transitory computer-readable storage medium of claim 9 , wherein the applying parallel routing that includes
dividing the nets (N) into N P blocks of substantially equal sizes; and
sequentially routing all nets belonging to the block assigned to it.
12. The non-transitory computer-readable storage medium of claim 11 , wherein the applying parallel routing that further includes
dividing the nets into two sets: C HF , and C LF , where CH F contains the nets having high fanout and C LF contains the nets having small fanout, wherein the high fanout nets are those nets whose fanout is more than or equal to a fanout threshold value.
13. The non-transitory computer-readable storage medium of claim 12 , wherein the applying the sequential routing that includes
partitioning the nets in C LF into three sets: C U , C L , and C LU , where C U and C L contain non-overlapping nets, and C LU contains nets that lie in both partitions C U and C L ; and
performing sequential routing of nets in a union of {C HF and C LU } using a connection router C 0 .
14. The non-transitory computer-readable storage medium of claim 13 , wherein the applying net partitioning that includes
finding a cutline that separates the nets into upper and lower halves based on their bounding boxes while ensuring that each partition has nearly equal number of branches to route.
15. The non-transitory computer-readable storage medium of claim 14 , wherein the applying net partitioning that includes
finding the cutline's vertical axis, denoted by I, which is equal to an index where one-to-one difference between elements of an array “Workload-after” and an array “Workload-before” is minima.
16. The non-transitory computer-readable storage medium of claim 15 , wherein the applying net partitioning that includes
inserting all nets whose bounding boxes lie completely on an upper side of the cutline into C U , and the nets whose bounding boxes lie on a lower side of the cutline into C L , and the nets whose bounding boxes crosses the cutline are inserted in C LU .