Detailed Description

• Study the description of the unit-size placement problem as presented in the book (pages 54-55).
• Study the description of simulated annealing as presented in the book (pages 71-73).
• Study also the following article:

  Sechen, C. and A. Sangiovanni-Vincentelli, "The TimberWolf Placement and Routing Package", IEEE Journal of Solid-State Circuits, Vol. SC-20(2), pp 510-522, (April 1985).

• The problem definition is taken from a file that obeys the following syntax:
  • The first line gives the length L of the area available for placement.
  • The second line gives the area's width W.
  • The third line gives the number of cells m (m is less than or equal to LW).
  • The fourth line gives the number of nets n.
  • The fifth line is empty.
  • The next n lines describe the netlist: the first line lists all the cells that are connected to Net 1, the second the cels connected to Net 2, etc.
  Example of a file for a problem instance with 8 cells and 9 nets in a 3-by-5 area (Net 1 connects the cells 1, 4 and 5):

  3 
  5
  8
  9
  
  1 4 5 
  1 3 6
  2 3 5 7 8
  2 4
  3 5 6
  3 8
  4 5 6 7
  6 8
  7 8
  

• Write a program that tries to find the optimal placement. Optimality means here the "minimal estimated total wire length" (use the "half perimeter" wire length metric by preference).
• Test your program with problems invented by yourself or provided to you by your supervisor.
• Choose your data structures carefully and motivate your choice. They should be chosen such that the program can handle large problem instances without major problems.