Accelerate analytical placement with GPU: A generic approach

Chun Xun Lin, Martin D F Wong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper presents a generic approach of exploiting GPU parallelism to speed up the essential computations in VLSI nonlinear analytical placement. We consider the computation of wirelength and density which are widely used as cost and constraint in nonlinear analytical placement. For wirelength gradient computing, we utilize the sparse characteristic of circuit graph to transform the compute-intensive portions into sparse matrix multiplications, which effectively optimizes the memory access pattern and mitigates the imbalance workload. For density, we introduce a computation flattening technique to achieve load balancing among threads and a High-Precision representation is integrated into our approach to guarantee the reproducibility. We have evaluated our method on a set of contest benchmarks from industry. The experimental results demonstrate our GPU method achieves a better performance over both the CPU methods and the straightforward GPU implementation.

Original languageEnglish (US)
Title of host publicationProceedings of the 2018 Design, Automation and Test in Europe Conference and Exhibition, DATE 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1345-1350
Number of pages6
ISBN (Electronic)9783981926316
DOIs
StatePublished - Apr 19 2018
Event2018 Design, Automation and Test in Europe Conference and Exhibition, DATE 2018 - Dresden, Germany
Duration: Mar 19 2018Mar 23 2018

Publication series

NameProceedings of the 2018 Design, Automation and Test in Europe Conference and Exhibition, DATE 2018
Volume2018-January

Other

Other2018 Design, Automation and Test in Europe Conference and Exhibition, DATE 2018
CountryGermany
CityDresden
Period3/19/183/23/18

Fingerprint

Resource allocation
Program processors
Data storage equipment
Networks (circuits)
Graphics processing unit
Placement
Costs
Industry
Graph
Imbalance
Gradient
Load balancing
Integrated
Benchmark
Thread
Guarantee
Workload
Contests

ASJC Scopus subject areas

  • Safety, Risk, Reliability and Quality
  • Hardware and Architecture
  • Software
  • Information Systems and Management

Cite this

Lin, C. X., & Wong, M. D. F. (2018). Accelerate analytical placement with GPU: A generic approach. In Proceedings of the 2018 Design, Automation and Test in Europe Conference and Exhibition, DATE 2018 (pp. 1345-1350). (Proceedings of the 2018 Design, Automation and Test in Europe Conference and Exhibition, DATE 2018; Vol. 2018-January). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.23919/DATE.2018.8342222

Accelerate analytical placement with GPU : A generic approach. / Lin, Chun Xun; Wong, Martin D F.

Proceedings of the 2018 Design, Automation and Test in Europe Conference and Exhibition, DATE 2018. Institute of Electrical and Electronics Engineers Inc., 2018. p. 1345-1350 (Proceedings of the 2018 Design, Automation and Test in Europe Conference and Exhibition, DATE 2018; Vol. 2018-January).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Lin, CX & Wong, MDF 2018, Accelerate analytical placement with GPU: A generic approach. in Proceedings of the 2018 Design, Automation and Test in Europe Conference and Exhibition, DATE 2018. Proceedings of the 2018 Design, Automation and Test in Europe Conference and Exhibition, DATE 2018, vol. 2018-January, Institute of Electrical and Electronics Engineers Inc., pp. 1345-1350, 2018 Design, Automation and Test in Europe Conference and Exhibition, DATE 2018, Dresden, Germany, 3/19/18. https://doi.org/10.23919/DATE.2018.8342222
Lin CX, Wong MDF. Accelerate analytical placement with GPU: A generic approach. In Proceedings of the 2018 Design, Automation and Test in Europe Conference and Exhibition, DATE 2018. Institute of Electrical and Electronics Engineers Inc. 2018. p. 1345-1350. (Proceedings of the 2018 Design, Automation and Test in Europe Conference and Exhibition, DATE 2018). https://doi.org/10.23919/DATE.2018.8342222
Lin, Chun Xun ; Wong, Martin D F. / Accelerate analytical placement with GPU : A generic approach. Proceedings of the 2018 Design, Automation and Test in Europe Conference and Exhibition, DATE 2018. Institute of Electrical and Electronics Engineers Inc., 2018. pp. 1345-1350 (Proceedings of the 2018 Design, Automation and Test in Europe Conference and Exhibition, DATE 2018).
@inproceedings{37c4d7b00ab64a868d98ba13ce2ec0e4,
title = "Accelerate analytical placement with GPU: A generic approach",
abstract = "This paper presents a generic approach of exploiting GPU parallelism to speed up the essential computations in VLSI nonlinear analytical placement. We consider the computation of wirelength and density which are widely used as cost and constraint in nonlinear analytical placement. For wirelength gradient computing, we utilize the sparse characteristic of circuit graph to transform the compute-intensive portions into sparse matrix multiplications, which effectively optimizes the memory access pattern and mitigates the imbalance workload. For density, we introduce a computation flattening technique to achieve load balancing among threads and a High-Precision representation is integrated into our approach to guarantee the reproducibility. We have evaluated our method on a set of contest benchmarks from industry. The experimental results demonstrate our GPU method achieves a better performance over both the CPU methods and the straightforward GPU implementation.",
author = "Lin, {Chun Xun} and Wong, {Martin D F}",
year = "2018",
month = "4",
day = "19",
doi = "10.23919/DATE.2018.8342222",
language = "English (US)",
series = "Proceedings of the 2018 Design, Automation and Test in Europe Conference and Exhibition, DATE 2018",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "1345--1350",
booktitle = "Proceedings of the 2018 Design, Automation and Test in Europe Conference and Exhibition, DATE 2018",
address = "United States",

}

TY - GEN

T1 - Accelerate analytical placement with GPU

T2 - A generic approach

AU - Lin, Chun Xun

AU - Wong, Martin D F

PY - 2018/4/19

Y1 - 2018/4/19

N2 - This paper presents a generic approach of exploiting GPU parallelism to speed up the essential computations in VLSI nonlinear analytical placement. We consider the computation of wirelength and density which are widely used as cost and constraint in nonlinear analytical placement. For wirelength gradient computing, we utilize the sparse characteristic of circuit graph to transform the compute-intensive portions into sparse matrix multiplications, which effectively optimizes the memory access pattern and mitigates the imbalance workload. For density, we introduce a computation flattening technique to achieve load balancing among threads and a High-Precision representation is integrated into our approach to guarantee the reproducibility. We have evaluated our method on a set of contest benchmarks from industry. The experimental results demonstrate our GPU method achieves a better performance over both the CPU methods and the straightforward GPU implementation.

AB - This paper presents a generic approach of exploiting GPU parallelism to speed up the essential computations in VLSI nonlinear analytical placement. We consider the computation of wirelength and density which are widely used as cost and constraint in nonlinear analytical placement. For wirelength gradient computing, we utilize the sparse characteristic of circuit graph to transform the compute-intensive portions into sparse matrix multiplications, which effectively optimizes the memory access pattern and mitigates the imbalance workload. For density, we introduce a computation flattening technique to achieve load balancing among threads and a High-Precision representation is integrated into our approach to guarantee the reproducibility. We have evaluated our method on a set of contest benchmarks from industry. The experimental results demonstrate our GPU method achieves a better performance over both the CPU methods and the straightforward GPU implementation.

UR - http://www.scopus.com/inward/record.url?scp=85048783823&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85048783823&partnerID=8YFLogxK

U2 - 10.23919/DATE.2018.8342222

DO - 10.23919/DATE.2018.8342222

M3 - Conference contribution

AN - SCOPUS:85048783823

T3 - Proceedings of the 2018 Design, Automation and Test in Europe Conference and Exhibition, DATE 2018

SP - 1345

EP - 1350

BT - Proceedings of the 2018 Design, Automation and Test in Europe Conference and Exhibition, DATE 2018

PB - Institute of Electrical and Electronics Engineers Inc.

ER -