Data Structures:

• Three Separate Grid Cells:
  • Cost Cell: 4-bit cost is used to index an array of quantized cost values. Costs are quantized from all possible values at the beginning of each ripup and reroute pass into a 16 element array. However, one cost element in the array is reserved for pin cells, which have infinite cost.
  • Direction and Visited Cell: 3-bits designate the direction from which this cell was reached, used to trace back the best path to reach the target. 1-bit designates if the cell has been expanded on current wavefront expansion. These bits are reset before any net, or net segment, is mazerouted.
  • Occupancy Cell: A linked-list of all nets that route through this cell, accessed after each pass of ripup and reroute.
• Wavefront: Is implemented using an stl priority_queue. The queue is sorted using floating point path cost and total cost (path cost + estimated distance) values.

Optimizations:

• Grid cell size: The grid cell size is essentially 8-bits during wavefront expansion.
• Constant tuning: The constants (bend cost, via cost, wrong way cost, and the "fudge factor" used in depth first prediction) have been hand-tuned to quickly provide suitable routing solutions.
• Hand-Coded Optimizations: Within the main loop of the mazerouter, functions and critical control paths have been in-lined and shortened to provide optimum performance.

Tricks:

• List of wire segments: Originally this list stored the cells through which a net routed. It has since been shortened by storing only the maximally long wire segments that comprise the net. This optimization drastically reduces the memory footprint of larger examples.
• Splitting grid cell into separate cell types: Dividing the grid cell, by splitting the cost bits from the direction and visited bits, has allowed the fast memset operation to reset the latter variables, a task required at the start of each wavefront expansion.