Simulated Annealing

[danielyang2055]

1. Initial fill insertion
2. Reduce fill to minimize cost in each bin
3. Metal fill again (probably using random fill with some random behavior)
4. Go back to step 2
   (loop forever)

[danielyang2055]

For Step 2:

• Determine critical net, non-critical net and metal fill, and ground net
• Cost of a fill is calculated by the overlap area with weight and capacitance parameters
• Density reduction is done in each bin
  • Sort metal fill by cost/metal_area = cp (get cp list)
  • Choose a metal fill with largest cp to reduce first
    • Rectangle Resize (return scaled rectangle) (up, dw, lt, rt)
    • Rectangle min width, max width check (DRC)
    • Use Rectangle Resize to do multiple tries and choose the best reduction
    • Delete the fill if necessary.
  • Reduced metal fill has new cp value
  • loop until bin density reach minimum requirement.