More Web Proxy on the site http://driver.im/

research-article

Parallel multi-level analytical global placement on graphics processing units

Authors:

Yi ZouAuthors Info & Claims

ICCAD '09: Proceedings of the 2009 International Conference on Computer-Aided Design

Pages 681 - 688

https://doi.org/10.1145/1687399.1687525

Published: 02 November 2009 Publication History

Abstract

GPU platforms are becoming increasingly attractive for implementing accelerators because they feature a larger number of cores with improved programmability. In this paper, we describe our implementation of a state-of-the-art academic multi-level analytical placer mPL [8] on Nvidia's massively parallel GT200 series platforms. We detail our efforts on performance tuning and optimizations. When compared to software implementation on Intel's recent generation Xeon CPU, the speed of the global placement part of mPL is 15X faster on average using a Tesla C1060 card, with comparable WL. (less than 1% WL degradation on average)

References

[1]

ICCAD04 mixed-size placement benchmarks. URL http://vlsicad.eecs.umich.edu/BK/ICCAD04bench/.

[2]

ISPD'06 placement contest benchmark. URL http://www.sigda.org/ispd2006/contest.html.

[3]

Peko suite, placement example with known optimal wirelength. URL http://cadlab.cs.ucla.edu/~pubbench/placement/.

[4]

Peku suite, placement example with known upperbound of wirelength. URL http://cadlab.cs.ucla.edu/~pubbench/peku.htm.

[5]

S. N. Adya, S. Chaturvedi, J. A. Roy, D. A. Papa, and I. L. Markov. Unification of partitioning, placement and floorplanning. In ICCAD '04: Proc. International Conference on Computer-Aided Design, pages 550--557, 2004.

Digital Library

[6]

A. E. Caldwell, A. B. Kahng, and I. L. Markov. Can recursive bisection alone produce routable placements? In DAC '00: Proc. Design Automation Conference, pages 477--482, 2000.

Digital Library

[7]

B. Catanzaro, K. Keutzer, and B.-Y. Su. Parallelizing CAD: a timely research agenda for EDA. In DAC '08: Proc. Design Automation Conference, pages 12--17, 2008.

Digital Library

[8]

T. Chan, J. Cong, and K. Sze. Multilevel generalized force-directed method for circuit placement. In ISPD '05: Proc. International Symposium on Physical Design, pages 185--192, 2005.

Digital Library

[9]

J. A. Chandy and P. Banerjee. A parallel circuit-partitioned algorithm for timing-driven standard cell placement. J. Parallel Distrib. Comput., 57(1):64--90, 1999.

Digital Library

[10]

J. Cong. Timing closure based on physical hierarchy. In ISPD '02: Proc. International Symposium on Physical Design, pages 170--174, 2002.

Digital Library

[11]

J. Cong, G. Luo, and E. Radke. Highly efficient gradient computation for density-constrained analytical placement. IEEE Trans. on CAD of Integrated Circuits and Systems, 27(12):2133--2144, 2008.

Digital Library

[12]

P. J. Davis and P. Rabinowitz. Methods of Numerical Integration: Second Edition. Dover Publications, November 2007.

[13]

H. Eisenmann and F. M. Johannes. Generic global placement and floorplanning. In DAC '98: Proc. Design Automation Conference, pages 269--274, 1998.

Digital Library

[14]

G. Flach, M. Johann, R. Hentschke, and R. Reis. Cell placement on graphics processing units. In SBCCI '07: Proc. Annual Conference on Integrated Circuits and Systems Design, pages 87--92, 2007.

Digital Library

[15]

M. Harris. Optimizing parallel reduction in CUDA. URL http://developer.download.nvidia.com/compute/cuda/1_1/Website/projects/reduction/doc/reduction.pdf.

[16]

A. B. Kahng, S. Reda, and Q. Wang. Aplace: a general analytic placement framework. In ISPD '05: Proc. International Symposium on Physical Design, pages 233--235, 2005.

Digital Library

[17]

A. Ludwin, V. Betz, and K. Padalia. High-quality, deterministic parallel placement for FPGAs on commodity hardware. In FPGA '08: Proc. International Symposium on Field Programmable Gate Arrays, pages 14--23, 2008.

Digital Library

[18]

J. Markoul. A fast cosine transform in one and two dimensions. IEEE Trans. Acoust., Speech Signal Process, 28(1):27--34, 1980.

[19]

G.-J. Nam and J. Cong. Modern Circuit Placement, Best Practices and Results. Springer, New York, 2007.

Digital Library

[20]

C. Sechen and A. Sangiovanni-Vincentelli. TimberWolf3.2: a new standard cell placement and global routing package. In DAC '86: Proc. Design Automation Conference, pages 432--439, 1986.

Digital Library

[21]

N. Viswanathan and C. C.-N. Chu. FastPlace: efficient analytical placement using cell shifting, iterative local refinement and a hybrid net model. In ISPD '04: Proc. International Symposium on Physical Design, pages 26--33, 2004.

Digital Library

[22]

M. Wang, X. Yang, and M. Sarrafzadeh. Dragon2000: standard-cell placement tool for large industry circuits. In ICCAD '00: Proc. International Conference on Computer-Aided Design, pages 260--263, 2000.

Digital Library

Cited By

Cheng XZhou JZhang ZYu W(2024)An Analytical GPU-Enabled Framework for the Stacked 3D IC LayoutsJournal of Circuits, Systems and Computers10.1142/S021812662450281533:16Online publication date: 10-Jun-2024
https://doi.org/10.1142/S0218126624502815
Liu LFu BLin SLiu JYoung EWong M(2024)Xplace: An Extremely Fast and Extensible Placement FrameworkIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.334629143:6(1872-1885)Online publication date: Jun-2024
https://doi.org/10.1109/TCAD.2023.3346291
Guo LMaidee PZhou YLavin CHung ELi WLau JQiao WChi YSong LXiao YKaviani AZhang ZCong J(2023)RapidStream 2.0: Automated Parallel Implementation of Latency–Insensitive FPGA Designs Through Partial ReconfigurationACM Transactions on Reconfigurable Technology and Systems10.1145/359302516:4(1-30)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1145/3593025
Show More Cited By

Index Terms

Parallel multi-level analytical global placement on graphics processing units
1. Hardware
  1. Very large scale integration design
    1. Application-specific VLSI designs
      1. Application specific processors

Recommendations

A survey of graph processing on graphics processing units

Graphics processing units (GPUs) have become popular high-performance computing platforms for a wide range of applications. The trend of processing graph structures on modern GPUs has also attracted an increasing interest in recent years. This article ...
Acceleration of grammatical evolution using graphics processing units: computational intelligence on consumer games and graphics hardware
GECCO '11: Proceedings of the 13th annual conference companion on Genetic and evolutionary computation

Several papers show that symbolic regression is suitable for data analysis and prediction in financial markets. Grammatical Evolution (GE), a grammar-based form of Genetic Programming (GP), has been successfully applied in solving various tasks ...
Algorithmic performance studies on graphics processing units

We report on our experience with integrating and using graphics processing units (GPUs) as fast parallel floating-point co-processors to accelerate two fundamental computational scientific kernels on the GPU: sparse direct factorization and nonlinear ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '09: Proceedings of the 2009 International Conference on Computer-Aided Design

November 2009

803 pages

ISBN:9781605588001

DOI:10.1145/1687399

General Chair:
Jaijeet Roychowdhury
Univ. of California, Berkeley, Berkeley, California

Copyright © 2009 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]

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE CAS
IEEE Council on Electronic Design Automation (CEDA)

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 November 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ICCAD '09

Sponsor:

SIGDA

ICCAD '09: The International Conference on Computer-Aided Design

November 2 - 5, 2009

California, San Jose

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

30
Total Citations
View Citations
237
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)1

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Cheng XZhou JZhang ZYu W(2024)An Analytical GPU-Enabled Framework for the Stacked 3D IC LayoutsJournal of Circuits, Systems and Computers10.1142/S021812662450281533:16Online publication date: 10-Jun-2024
https://doi.org/10.1142/S0218126624502815
Liu LFu BLin SLiu JYoung EWong M(2024)Xplace: An Extremely Fast and Extensible Placement FrameworkIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.334629143:6(1872-1885)Online publication date: Jun-2024
https://doi.org/10.1109/TCAD.2023.3346291
Guo LMaidee PZhou YLavin CHung ELi WLau JQiao WChi YSong LXiao YKaviani AZhang ZCong J(2023)RapidStream 2.0: Automated Parallel Implementation of Latency–Insensitive FPGA Designs Through Partial ReconfigurationACM Transactions on Reconfigurable Technology and Systems10.1145/359302516:4(1-30)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1145/3593025
Jiang XGuo ZChai ZZhao YLin YWang RHuang R(2023)Invited Paper: Accelerating Routability and Timing Optimization with Open-Source AI4EDA Dataset CircuitNet and Heterogeneous Platforms2023 IEEE/ACM International Conference on Computer Aided Design (ICCAD)10.1109/ICCAD57390.2023.10323938(1-9)Online publication date: 28-Oct-2023
https://doi.org/10.1109/ICCAD57390.2023.10323938
Yang HFung KZhao YLin YYu BBolchini CO'Connor IVerbauwhede IWille R(2022)Mixed-cell-height legalization on CPU-GPU heterogeneous systemsProceedings of the 2022 Conference & Exhibition on Design, Automation & Test in Europe10.5555/3539845.3540032(784-789)Online publication date: 14-Mar-2022
https://dl.acm.org/doi/10.5555/3539845.3540032
Guo LMaidee PZhou YLavin CWang JChi YQiao WKaviani AZhang ZCong JAdler MIenne P(2022)RapidStreamProceedings of the 2022 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays10.1145/3490422.3502361(1-12)Online publication date: 13-Feb-2022
https://dl.acm.org/doi/10.1145/3490422.3502361
Liu LFu BWong MYoung EOshana R(2022)XplaceProceedings of the 59th ACM/IEEE Design Automation Conference10.1145/3489517.3530485(1309-1314)Online publication date: 10-Jul-2022
https://dl.acm.org/doi/10.1145/3489517.3530485
Huang GHu JHe YLiu JMa MShen ZWu JXu YZhang HZhong KNing XMa YYang HYu BYang HWang Y(2021)Machine Learning for Electronic Design Automation: A SurveyACM Transactions on Design Automation of Electronic Systems10.1145/345117926:5(1-46)Online publication date: 5-Jun-2021
https://dl.acm.org/doi/10.1145/3451179
Lin YJiang ZGu JLi WDhar SRen HKhailany BPan D(2021)DREAMPlace: Deep Learning Toolkit-Enabled GPU Acceleration for Modern VLSI PlacementIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2020.300384340:4(748-761)Online publication date: Apr-2021
https://doi.org/10.1109/TCAD.2020.3003843
Yu WCheng XZhang ZGong J(2021)Deep Learning Based Placement Acceleration for 3D-ICsNeural Information Processing10.1007/978-3-030-92307-5_27(231-238)Online publication date: 2-Dec-2021
https://doi.org/10.1007/978-3-030-92307-5_27
Show More Cited By

View Options

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents