DieRouter+: Enhancing Die-Level Routing with SOCP and Scheduler-Driven DP

Verifying functional correctness is a key challenge in VLSI design. FPGA prototyping balances runtime and cost in logic verification and is widely used for large-scale circuit verification. To accommodate the increasing complexity of circuits, it extends from a single FPGA to a Multi-Fpga System (MFS), a network of interconnected FPGA dies. Die-Level routing, which determines a routing topology and its corresponding Time-Division Multiplexing (TDM) assignment scheme, is crucial for maximizing the operating frequency of MFS. This paper presents DieRouter+, an improved die-level router built upon DieRouter, the first published solution to this problem. DieRouter+ introduces three key innovations: (1) a simpler yet more effective initial routing method based on shortest path trees, (2) a Second-Order Cone Programming formulation of an extended relaxed TDM assignment problem to compute optimal continuous TDM ratios, thereby improving the optimality of the legalized TDM assignment derived from these ratios, and (3) a scheduler-driven Dynamic Programming (DP)-based legalization technique that adaptively schedules state evaluations, reducing the number of state evaluations by about 50% compared to the original DP in DieRouter. We evaluate DieRouter+ on 10 benchmark test cases from the 2023 EDA Elite Design Challenge. It outperforms both the competition’s 1st-place method and DieRouter, reducing the maximum net delay by 10.12% and 5.71% on average for 5 challenging cases with up to millions of nets, while maintaining comparable performance on easier cases with at most a few thousand nets. Additionally, for large-scale instances, DieRouter+ achieves a 40% speedup over DieRouter. These results confirm the effectiveness of DieRouter+ in optimizing die-level routing.