Ripup & Reroute: Optimization Goals

<< Back [Home] Next >>

The two optimizations are aimed at providing fast solutions that fit easily in memory.

  • Small Memory Footprint - Small grid size: The data structures used to represent the grid limit each grid to essentially 8-bit during wavefront expansion. Grid cells should be as small as possible while still storing all necessary information for mazerouting.
  • Quick Solutions - Small wave front expansion: A majority of the HORE running time is spent in wavefront expansion. Thus, the speed with which HORE generates solutions is very sensitive to the number of grids cells expanded during mazeroute. Several techniques were used to minimize wavefront expansion: minimum spanning tree-esque multipoint nets and depth first prediction.

<< Back [Home] Next >>