com.xilinx.rapidwright.rwroute

Class CUFR

Object

com.xilinx.rapidwright.rwroute.RWRoute

com.xilinx.rapidwright.rwroute.CUFR

public class CUFR
extends RWRoute

This is the implementation of the parallel structure Recursive Partitioning Ternary Tree (RPTT) in the solution of our team CUFR for the Runtime-First FPGA Interchange Routing Contest @ FPGA'24. More detailed descriptions of our methods are in the following paper: Xinshi Zang, Wenhao Lin, Shiju Lin, Jinwei Liu and Evangeline F.Y. Young. An Open-Source Fast Parallel Routing Approach for Commercial FPGAs. In Proceedings of the Great Lakes Symposium on VLSI 2024. Team CUFR improved the runtime performance of RWRoute through the following two aspects: 1. Implemented Recursive Partitioning Ternary Tree (RPTT), an enhanced tree-based parallel structure, enabling CUFR to perform multi-threaded routing compared to the single-threaded RWRoute, thereby improving the runtime. The traditional bi-partition tree algorithm uses a cutline to bisect a partition, with connections crossing the cutlines placed in the corresponding tree nodes, and then recursively building sub-trees for two sub-partitions. During routing, it first sequetially routes the connections within a tree node, and then parallelly routes the two sub-trees. It was observed that the traditional bi-partition tree has a small number of tree nodes in the layers closer to the tree root, with each node containing a large amount of connections to be sequentially routed. This makes it difficult to fully utilize the available threads during the early stage of the routing process. To address this issue, RPTT also builds a sub-tree for the connections crossing the cutline to achieve more parallelism, and this sub-tree is routed prior to the sub-trees of the two sub-partitions. 2. Proposed Hybrid Updating Strategy (HUS) targeting on larger and more difficult routing cases. (this strategy has been integrated into RWRoute)

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	CUFR.RouteNodeGraphCUFR
static class	CUFR.RouteNodeGraphCUFRTimingDriven

Field Summary

Fields inherited from class com.xilinx.rapidwright.rwroute.RWRoute

SUPPORTED_SERIES

Constructor Summary

Constructors

Constructor and Description
CUFR(Design design, RWRouteConfig config)

Method Summary

Modifier and Type	Method and Description
static void	main(String[] args) The main interface of CUFR that reads in a Design design (DCP or FPGA Interchange), and parses the arguments for the RWRouteConfig object of the router.
static Design	routeDesignFullNonTimingDriven(Design design) Routes a design in the full non-timing-driven routing mode using CUFR.
static Design	routeDesignFullTimingDriven(Design design) Routes a design in the full timing-driven routing mode using CUFR.
static Design	routeDesignWithUserDefinedArguments(Design design, String[] args) Routes a Design instance using CUFR.

Methods inherited from class com.xilinx.rapidwright.rwroute.RWRoute

addClkNet, createClkTimingData, getDesign, preprocess, printNodeTypeUsageAndWirelength, route, routeIndirectConnectionsIteratively

Methods inherited from class Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

CUFR

public CUFR(Design design,
            RWRouteConfig config)

Method Detail

routeDesignFullTimingDriven

public static Design routeDesignFullTimingDriven(Design design)

Routes a design in the full timing-driven routing mode using CUFR.

Parameters:

design - The Design instance to be routed.

routeDesignFullNonTimingDriven

public static Design routeDesignFullNonTimingDriven(Design design)

Routes a design in the full non-timing-driven routing mode using CUFR.

Parameters:

design - The Design instance to be routed.

routeDesignWithUserDefinedArguments

public static Design routeDesignWithUserDefinedArguments(Design design,
                                                         String[] args)

Routes a Design instance using CUFR.

Parameters:

design - The Design instance to be routed.

args - An array of string arguments, can be null. If null, the design will be routed in the full timing-driven routing mode with default a RWRouteConfig instance. For more options of the configuration, please refer to the RWRouteConfig class.

Returns:

Routed design.

main

public static void main(String[] args)

The main interface of CUFR that reads in a Design design (DCP or FPGA Interchange), and parses the arguments for the RWRouteConfig object of the router.

Parameters:

args - An array of strings that are used to create a RWRouteConfig object for the router.