High-quality, deterministic parallel placement for FPGAs on commodity hardware

ABSTRACT

In this paper, we describe the application of two parallelization strategies to the Quartus II FPGA placer. The first uses a pipelining approach and achieves speedups of 1.3x on two processing cores. The second uses a parallel moves approach and achieves speedups of 2.2x on four cores. Unlike all previous parallel moves algorithms, ours is deterministic and always gives the same answer as the serial version of the algorithm, without any significant reduction in performance.

We also describe a process to quantify multi-core performance effects, such as memory subsystem limitations and explicit synchronization overhead, and fully describe these effects on a CAD tool for the first time. Memory limitations alone are found to cost up to 35% of total runtime. Unlike previous algorithms, our algorithms have negligible explicit synchronization overhead. These results are relevant to both CAD designers and to any developers seeking to parallelize existing software.

REFERENCES

• 1: H. Sutter, "A fundamental turn toward concurrency in software," Dr. Dobb's J. Mar. 2005.
• 2: Altera Corp., "Quartus II Incremental Compilation for Hierarchical & Team-Based Design," in The Quartus II Handbook, Version 7.1, Vol. 1, Ch. 2 2007.
• 3: J. Chandy, S. Kim, B. Ramkumar, S. Parkes, and P. Banerjee, "An evaluation of parallel simulated annealing strategies with application to standard cell placement," TCAD vol. 16, pp.398--410, Apr. 1997.
• 4: M. Sarrafzadeh, M. Wang, and X. Yang, Modern Placement Techniques Boston: Kluwer Academic Publishers, 2003.
• 5: C. Alpert, L. Hagen, and A. Kahng, "A hybrid multilevel/genetic approach for circuit partitioning," tech. rep., CS Dept., UCLA, Los Angeles, CA, USA, 1996.
• 6: J.M. Kleinhans, G. Sigl, F. Johannes, and K. Antreich, "GORDIAN: VLSI placement by quadratic programming and slicing optimization," TCAD vol. 10, pp.356--365, Mar. 1991.
• 7: S.N.R. Borra, A. Muthukaruppan, S. Suresh, and V. Kamakoti, "A parallel genetic approach to the placement problem for field programmable gate arrays," in IPDPS (Nice, France), p.184, 2003.
• 8: S. Kirkpatrick, C. Gelatt Jr., and M. Vecchi, "Optimization by simulated annealing," Science pp.671--680, May 1983.
• 9: C. Sechen and A. Sangiovanni-Vincentelli, "The TimberWolf placement and routing package," JSSC pp.510--522, Apr. 1985.
• 10: 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
• 11: M. Hutton and V. Betz, "FPGA synthesis and physical design," in Electronic Design Automation for Integrated Circuits Handbook (L. Scheffer,L. Lavagno, and G. Martin, eds.), vol. 1, ch. 13, pp.13.1--13.32, Taylor and Francis CRC Press, 2006.
• 12: Pak K. Chan , Martine D. F. Schlag, Parallel placement for field-programmable gate arrays, Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays, February 23-25, 2003, Monterey, California, USA [doi>10.1145/611817.611825]
• 13: S. Kravitz and R. Rutenbar, "Placement by simulated annealing on a multiprocessor," TCAD pp.534--549, Jul. 1987.
• 14: Malay Haldar , Anshuman Nayak , Alok Choudhary , Prith Banerjee, Parallel algorithms for FPGA placement, Proceedings of the 10th Great Lakes symposium on VLSI, p.86-94, March 02-04, 2000, Chicago, Illinois, United States [doi>10.1145/330855.330988]
• 15: P. Banerjee , M. H. Jones , J. S. Sargent, Parallel Simulated Annealing Algorithms for Cell Placement on Hypercube Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.91-106, January 1990 [doi>10.1109/71.80128]
• 16: Wern-Jieh Sun , Carl Sechen, A loosely coupled parallel algorithm for standard cell placement, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.137-144, November 06-10, 1994, San Jose, California, United States
• 17: Sungho Kim , Prithviraj Banerjee , Balkrishna Ramkumar , Steven Parkes , John A. Chandy, ProperPLACE: A Portable Parallel Algorithm for Standard Cell Placement, Proceedings of the 8th International Symposium on Parallel Processing, p.932-941, April 01, 1994
• 18: J. A. Chandy , P. Banerjee, Parallel simulated annealing strategies for VLSI cell placement, Proceedings of the 9th International Conference on VLSI Design: VLSI in Mobile Communication, p.37, January 03-06, 1996
• 19: E. E. Witte , R. D. Chamberlain , M. A. Franklin, Parallel Simulated Annealing using Speculative Computation, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.483-494, October 1991 [doi>10.1109/71.97904]
• 20: E H L Aarts , F M J de Bont , E H A Habers , P J M van Laarhoven, Parallel implementations of the statistical cooling algorithm, Integration, the VLSI Journal, v.4 n.3, p.209-238, Sept. 1986 [doi>10.1016/0167-9260(86)90002-7]
• 21: Michael G. Wrighton , André M. DeHon, Hardware-assisted simulated annealing with application for fast FPGA placement, Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays, February 23-25, 2003, Monterey, California, USA [doi>10.1145/611817.611824]
• 22: S. Vadlamani and S. Jenks, "Architectural considerations for efficient software execution on parallel microprocessors," in IPDPS (Long Beach, CA, USA), 2007.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

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

  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Algorithms, Design, Performance

Keywords:
FPGAs, parallel placement, timing-driven placement