The current lookahead in the FPGA interchange implementation is disabled by default because it is slow to compute and requires significant memory, both when being computed and when using it. This issue covers topics around how the lookahead might be improved and goals in that directly.

Current status

The current lookahead is data-driven, and in theory should be robust to various architectures, and work both on timing and non-timing driven situations. It is derived from the extended map lookahead (https://github.com/verilog-to-routing/vtr-verilog-to-routing/blob/master/vpr/src/route/router_lookahead_extended_map.h) developed as part of the VPR flow for https://github.com/symbiflow/symbiflow-arch-defs/ .

Current problems

• The time to compute the lookahead is fairly high for the A35T (6 min on a 56 core machine). In theory, computation time should not increase with larger fabrics, but this has not been verified.
• Memory consumption during the computation of the lookahead is fairly high (~15 GiB) and when the lookahead is being used (~6 GiB).

Potential solutions

• To lower the computation time when computing the lookahead, consider shrinking small search space, either geometrically or via limiting the depth of the expansion. Doing so will need to be traded with router performance
• Profile lookahead computation and see if there are further optimizations that are possible
• Explore ways to shring number of and size of CostMap (which consume the majority of the disk and RAM)
• Currently the lookahead has no duplicate detection for wire pairs with similiar cost map's. Potentially detect (or supply in the chipdb) wire similarity information. There is a trade off to requiring arch's to supply this information, so prefer solutions that are driven based on the routing graph alone, rather than architecture specific input.
• Explore parameteric equations to represent CostMap's. It is likely that many/all of the cost maps could be reduced to a set of parameteric equations and/or table lookups with less resolution. See if level of detail techiniques can be applied.