COMPARISON OF THE PERFORMANCE OF MAZE ROUTING AND RIP-UP & REROUTE ALGORITHMS IN VLSI ROUTING

Tóm tắt

This paper compares the performance of two routing algorithms, Maze Routing and Rip-Up & Reroute, in VLSI design, focusing on their ability to meet processing speed and routing quality requirements. Data collection and statistical analysis were conducted over 100 simulation runs on grid-based circuit layouts with two sizes (20×20 and 40×40) and two obstacle density levels (5% and 10%). In each simulation, a set of nets was randomly generated on cells free of obstacles. The evaluation metrics included execution time, path length, number of bends, routing success rate, and number of rip-ups. The results indicate that on the 20×20 grid, the execution time of Maze Routing (0.0032 ± 0.0051 seconds) in the scenario with 5% obstacles and 3 nets was about 10% of that of Rip-Up & Reroute (0.0336 ± 0.0522 seconds), while Maze Routing maintained a high routing success rate (88.7% compared to Rip-Up & Reroute’s 78.0%). On the 40×40 grid, Maze Routing continued to demonstrate fast processing times (from 0.0047 to 0.0075 seconds) and a low number of rip-ups. Overall, the study shows that Maze Routing excels in processing time and routing success rate, whereas Rip-Up & Reroute can achieve shorter path lengths in some scenarios but is hindered by higher computational costs and an increased number of rip-ups. This evaluation underscores the importance of balancing computational efficiency and path quality when selecting routing algorithms for VLSI applications.