research-article

Analyzing System-Level Information’s Correlation to FPGA Placement

Authors:

Farnaz Gharibian,

Lesley Shannon,

Peter Jamieson,

Kevin ChungAuthors Info & Claims

ACM Transactions on Reconfigurable Technology and Systems (TRETS), Volume 6, Issue 3

Article No.: 15, Pages 1 - 21

https://doi.org/10.1145/2501985

Published: 01 October 2013 Publication History

Abstract

One popular placement algorithms for Field-Programmable Gate Arrays (FPGAs) is called Simulated Annealing (SA). This algorithm tries to create a good quality placement from a flattened design that no longer contains any high-level information related to the original design hierarchy. Placement is an NP-hard problem, and as the size and complexity of designs implemented on FPGAs increases, SA does not scale well to find good solutions in a timely fashion. In this article, we investigate if system-level information can be reconstructed from a flattened netlist and evaluate how that information is realized in terms of its locality in the final placement. If there is a strong relationship between good quality placements and system-level information, then it may be possible to divide a large design into smaller components and improve the time needed to create a good quality placement. Our preliminary results suggest that the locality property of the information embedded in the system-level HDL structure (i.e. “module”, “always”, and “if” statements) is greatly affected by designer HDL coding style. Therefore, a reconstructive algorithm, called Affinity Propagation, is also considered as a possible method of generating a meaningful coarse-grain picture of the design.

References

[1]

Behrens, D., Harbich, K., and Barke, E. 1996. Circuit partitioning using high-level design information. In Proceedings of the Conference on Integrated Design and Process Technology. 259--266.

[2]

Betz, V., Rose, J., and Marquardt, A. 1999. Architecture and CAD for Deep-Submicron FPGAs. Kluwer Academic Publishers, Norwell, MA.

Digital Library

[3]

Bian, H., Ling, A. C., Choong, A., and Zhu, J. 2010. Towards scalable placement for FPGAs. In Proceedings of the 18th Annual ACM/SIGDA International Symposium on FPGAs. 147--156.

Digital Library

[4]

Caldwell, A. E., Kahng, A. B., and Markov, I. L. 1999. Optimal partitioners and end-case placers for standard-cell layout. In Proceedings of the International Symposium on Physical Design. 90--96.

Digital Library

[5]

Chan, T. F., Cong, J., Kong, T., and Shinnerl, J. R. 2000. Multilevel optimization for large-scale circuit placement. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. 171--176.

Digital Library

[6]

Chandy, J. and Banerjee, P. 1996. Parallel simulated annealing strategies for vlsi cell placement. In Proceedings of the 9th International Conference on VLSI Design. 37--42.

Digital Library

[7]

Cong, J. 2002. Timing closure based on physical hierarchy. In Proceedings of the International Symposium on Physical Design. 170--174.

Digital Library

[8]

Cong, J., Peck, J., and Ding, Y. 1996. RASP: A general logic synthesis system for SRAM-based FPGAs. In Proceedings of the ACM/SIGDA International Symposium on FPGAs. 137--143.

Digital Library

[9]

Donath, W. E. 1980. Complexity theory and design automation. In Proceedings of the 17th Design Automation Conference. 412--419.

Digital Library

[10]

Emmert, J. M. and Bhatia, D. 1999. A methodology for fast FPGA floorplanning. In Proceedings of the 7th International ACM/SIGDA Symposium on FPGAs. 47--56.

Digital Library

[11]

Frey, B. J. and Dueck, D. 2007. Clustering by passing messages between data points. Science, 315, 5814, 972--976.

[12]

Gharibian, F., Shannon, L., and Jamieson, P. 2010. Finding system-level information and analyzing its correlation to FPGA placement. In Proceedings of the 20th International Conference on Field-Programmable Logic and Applications (FPL’10).

Digital Library

[13]

Grover, L. K. 1987. Standard cell placement using simulated sintering. In Proceedings of the 24th ACM/IEEE Design Automation Conference. 56--59.

Digital Library

[14]

Haldar, M., Nayak, A., Choudhary, A., and Banerjee, P. 2000. Parallel algorithms for FPGA placement. In Proceedings of the 10th Great Lakes Symposium on VLSI. 86--94.

Digital Library

[15]

Jamieson, P. A., Kent, K. B., Gharibian, F., and Shannon, L. 2010. Odin II - An open-source Verilog HDL synthesis tool for academic CAD flows. In Proceedings of the Annual IEEE Symposium on Field-Programmable Custom Computing Machines.

Digital Library

[16]

Jones, J. 2003. Abstract syntax tree implementation idioms. In Proceedings of the 10th Conference on Pattern Languages of Programs (PLoP2003).

[17]

Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. 1983. Optimization by simulated annealing. Science 220, 4598, 671--680.

[18]

Ludwin, A., Betz, V., and Padalia, K. 2008. High-quality, deterministic parallel placement for FPGAs on commodity hardware. In Proceedings of the 16th International ACM/SIGDA Symposium on FPGAs. 14--23.

Digital Library

[19]

Luu, J., Kuon, I., Jamieson, P., Campbell, T., Ye, A., Fang, W. M., and Rose, J. 2009. VPR 5.0: FPGA CAD and architecture exploration tools with single-driver routing, heterogeneity and process scaling. In Proceedings of the ACM/SIGDA International Symposium on FPGAs.

Digital Library

[20]

MacQueen, J. B. 1967. Some methods for classification and analysis of multivariate observations. In Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. Vol. 1, University of California Press, Berkeley, CA, 281--297.

[21]

Marquardt, A., Betz, V., and Rose, J. 1999. Using cluster-based logic blocks and timing-driven packing to improve FPGA speed and density. In Proceedings of the ACM/SIGDA International Symposium on FPGAs. 37--46.

Digital Library

[22]

Mishchenko, A., Chatterjee, S., and Brayton, R. K. 2007. Improvements to technology mapping for LUT-based FPGAs. IEEE Trans. Comput. Aid. Design Integr. Circuits Syst. 26, 2, 240--253.

Digital Library

[23]

Riess, B. M. and Ettelt, G. G. 1995. Speed: Fast and efficient timing driven placement. In Proceedings of the IEEE International Symposium on Circuits. 377--380.

[24]

Sankar, Y. and Rose, J. 1999. Trading quality for compile time: Ultra-fast placement for FPGAs. In Proceedings of the ACM/SIGDA International Symposium on FPGAs. 157--166.

Digital Library

[25]

Tanuj, J., Alpert, C. J., Hu, J., Li, Z., Nam, G.-J., and Winn, C. B. 2010. Detecting tangled logic structures in VLSI netlists. In Proceedings of the 47th Design Automation Conference. 603--608.

Digital Library

[26]

Tessier, R. 2002. Fast placement approaches for FPGAs. ACM Trans. Design Autom. Electron. Syst. 7, 2, 284--305.

Digital Library

[27]

Tsay, Y. W., Fang, W. J., Wu, A. C., and Lin, Y. L. 1997. Preserving HDL synthesis hierarchy for cell placement. In Proceedings of the International Symposium on Physical Design. 169--174.

Digital Library

[28]

Varanelli, J. M. and Cohoon, J. P. 1999. A fast method for generalized starting temperature determination in homogeneous two-stage simulated annealing systems. Comput. Oper. Res. 26, 5, 481--503.

Digital Library

[29]

Viswanathan, N. and Chu, C. 2004. Fastplace: Efficient analytical placement using cell shifting, iterative local refinement and a hybrid net model. In Proceedings of the International Symposium on Physical Design.

Digital Library

[30]

Vorwerk, K., Kennings, A., and Vannelli, A. 2004. Engineering details of a stable force-directed placer. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. 573--580.

Digital Library

Cited By

Jamieson PGharibian FShannon LWilton S(2022)Using data-mining techniques to improve combinatorial optimization algorithmsJournal of Algorithms & Computational Technology10.1177/1748302622113068016(174830262211306)Online publication date: 10-Oct-2022
https://doi.org/10.1177/17483026221130680
Gharibian FShannon LJamieson P(2014)Identifying and placing heterogeneously-sized cluster groupings based on FPGA placement data2014 24th International Conference on Field Programmable Logic and Applications (FPL)10.1109/FPL.2014.6927479(1-6)Online publication date: Sep-2014
https://doi.org/10.1109/FPL.2014.6927479

Index Terms

Analyzing System-Level Information’s Correlation to FPGA Placement
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing

Recommendations

Hardware accelerated FPGA placement

A key advantage of field-programmable gate arrays (FPGAs) over full-custom and semi-custom devices is that they provide relatively quick implementation from concept to physical realization. However, as modern FPGAs reach close to one million logic ...
Clock-Aware FPGA Placement Contest
ISPD '17: Proceedings of the 2017 ACM on International Symposium on Physical Design

Modern FPGA device contains complex clocking architecture on top of FPGA logic fabric. To best utilize FPGA clocking architecture, both FPGA designers and EDA tool developers need to understand the clocking architecture and design best methodology/...
A methodology for identifying and placing heterogeneous cluster groups based on placement proximity data (abstract only)
FPGA '14: Proceedings of the 2014 ACM/SIGDA international symposium on Field-programmable gate arrays

Due to the rapid growth in the size of designs and Field Programmable Gate Arrays (FPGAs), CAD run-time has increased dramatically. Reducing FPGA design compilation times without degrading circuit performance is crucial. In this work, we describe a ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Reconfigurable Technology and Systems

ACM Transactions on Reconfigurable Technology and Systems Volume 6, Issue 3

October 2013

85 pages

ISSN:1936-7406

EISSN:1936-7414

DOI:10.1145/2535556

Issue’s Table of Contents

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 2013

Accepted: 01 July 2013

Revised: 01 May 2013

Received: 01 September 2011

Published in TRETS Volume 6, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Natural Sciences and Engineering Research Council of Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
184
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jamieson PGharibian FShannon LWilton S(2022)Using data-mining techniques to improve combinatorial optimization algorithmsJournal of Algorithms & Computational Technology10.1177/1748302622113068016(174830262211306)Online publication date: 10-Oct-2022
https://doi.org/10.1177/17483026221130680
Gharibian FShannon LJamieson P(2014)Identifying and placing heterogeneously-sized cluster groupings based on FPGA placement data2014 24th International Conference on Field Programmable Logic and Applications (FPL)10.1109/FPL.2014.6927479(1-6)Online publication date: Sep-2014
https://doi.org/10.1109/FPL.2014.6927479

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents