Architecture-adaptive range limit windowing for simulated annealing FPGA placement

ABSTRACT

Previous research has shown both theoretically and practically that simulated annealing can greatly benefit from the incorporation of an adaptive range limiting window to control the acceptance ratio of swaps during placement. However, the implementation of such a system is not necessarily obvious. Existing range limiting techniques have several fundamental shortcomings when dealing with both standard island-style FPGAs and more exotic architectures. In this paper we discuss the nature of these problems and present a new algorithm that attempts to deal with these issues.

REFERENCES

• 1: Vaughn Betz , Jonathan Rose, VPR: A new packing, placement and routing tool for FPGA research, Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications, p.213-222, September 01-03, 1997
• 2: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 3: André DeHon, Balancing interconnect and computation in a reconfigurable computing array (or, why you don't really want 100% LUT utilization), Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.69-78, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296431]
• 4: Eguro, K. and S. Hauck, "Issues of Wirelength Cost Models in Routing-Constrained FPGAs", University of Washington, Dept. of EE Technical Report UWEETR-2004-0006, 2004.
• 5: Jimmy Lam , Jean-Marc Delosme, Performance of a new annealing schedule, Proceedings of the 25th ACM/IEEE conference on Design automation, p.306-311, June 12-15, 1988, Atlantic City, New Jersey, United States
• 6: Akshay Sharma , Carl Ebeling , Scott Hauck, Architecture Adaptive Routability-Driven Placement for FPGAs (abstract only), Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays, February 20-22, 2005, Monterey, California, USA [doi>10.1145/1046192.1046235]
• 7: William Tsu , Kip Macy , Atul Joshi , Randy Huang , Norman Walker , Tony Tung , Omid Rowhani , Varghese George , John Wawrzynek , André DeHon, HSRA: high-speed, hierarchical synchronous reconfigurable array, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.125-134, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296442]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

General Terms:
Algorithms, Design

Keywords:
architecture-adaptive, placement, range limiting, reconfigurable logic, simulated annealing, windowing