A new placement algorithm for custom chip design

Zhi-Ming Lin, Hung C. Lin

Research output: Contribution to journal › Conference article

Abstract

A placement algorithm which consists of three subalgorithms--an O(kn2) circle model relative placement algorithm, an O(n2 log n triangulation algorithm, and an O(n2 log n2) optimal slicing algorithm for custom chip design--is presented. This relative placement algorithm addresses size effect and net connectivity effect simultaneously, while attaining a low polynomial time complexity O(kn2) without loss of global perspective, where k is a constant and depends on the accuracy that the placement required. The triangulation algorithm has O(n2 log n) time complexity. The triangulated planar graph can be used to do the floorplan by either the nonslicing RDG (rectangular dual graph) or slicing embedding methods. The optimum slicing algorithm has O(n2 log n2) time complexity. As expected, the wire length of the placement algorithm is shorter than that of a point model. However, since the optimal values of l0 and DEF (deformation ratio) are unknown, different values for l0 and DEF should be used in different circuits to obtain better placement results.

Original languageEnglish
Pages (from-to)1672-1675
Number of pages4
JournalProceedings - IEEE International Symposium on Circuits and Systems
Volume3
Publication statusPublished - 1990 Dec 1
Event1990 IEEE International Symposium on Circuits and Systems Part 3 (of 4) - New Orleans, LA, USA
Duration: 1990 May 1 → 1990 May 3

Fingerprint

Triangulation
Polynomials
Wire
Networks (circuits)

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering

Cite this

Lin, Zhi-Ming ; Lin, Hung C. / A new placement algorithm for custom chip design. In: Proceedings - IEEE International Symposium on Circuits and Systems. 1990 ; Vol. 3. pp. 1672-1675.
@article{9ac18d7bb73e435aa342db64042c249c,
title = "A new placement algorithm for custom chip design",
abstract = "A placement algorithm which consists of three subalgorithms--an O(kn2) circle model relative placement algorithm, an O(n2 log n triangulation algorithm, and an O(n2 log n2) optimal slicing algorithm for custom chip design--is presented. This relative placement algorithm addresses size effect and net connectivity effect simultaneously, while attaining a low polynomial time complexity O(kn2) without loss of global perspective, where k is a constant and depends on the accuracy that the placement required. The triangulation algorithm has O(n2 log n) time complexity. The triangulated planar graph can be used to do the floorplan by either the nonslicing RDG (rectangular dual graph) or slicing embedding methods. The optimum slicing algorithm has O(n2 log n2) time complexity. As expected, the wire length of the placement algorithm is shorter than that of a point model. However, since the optimal values of l0 and DEF (deformation ratio) are unknown, different values for l0 and DEF should be used in different circuits to obtain better placement results.",
author = "Zhi-Ming Lin and Lin, {Hung C.}",
year = "1990",
month = "12",
day = "1",
language = "English",
volume = "3",
pages = "1672--1675",
journal = "Proceedings - IEEE International Symposium on Circuits and Systems",
issn = "0271-4310",
publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

Lin, Z-M & Lin, HC 1990, 'A new placement algorithm for custom chip design', Proceedings - IEEE International Symposium on Circuits and Systems, vol. 3, pp. 1672-1675.

A new placement algorithm for custom chip design. / Lin, Zhi-Ming; Lin, Hung C.

In: Proceedings - IEEE International Symposium on Circuits and Systems, Vol. 3, 01.12.1990, p. 1672-1675.

Research output: Contribution to journal › Conference article

TY - JOUR

T1 - A new placement algorithm for custom chip design

AU - Lin, Zhi-Ming

AU - Lin, Hung C.

PY - 1990/12/1

Y1 - 1990/12/1

N2 - A placement algorithm which consists of three subalgorithms--an O(kn2) circle model relative placement algorithm, an O(n2 log n triangulation algorithm, and an O(n2 log n2) optimal slicing algorithm for custom chip design--is presented. This relative placement algorithm addresses size effect and net connectivity effect simultaneously, while attaining a low polynomial time complexity O(kn2) without loss of global perspective, where k is a constant and depends on the accuracy that the placement required. The triangulation algorithm has O(n2 log n) time complexity. The triangulated planar graph can be used to do the floorplan by either the nonslicing RDG (rectangular dual graph) or slicing embedding methods. The optimum slicing algorithm has O(n2 log n2) time complexity. As expected, the wire length of the placement algorithm is shorter than that of a point model. However, since the optimal values of l0 and DEF (deformation ratio) are unknown, different values for l0 and DEF should be used in different circuits to obtain better placement results.

AB - A placement algorithm which consists of three subalgorithms--an O(kn2) circle model relative placement algorithm, an O(n2 log n triangulation algorithm, and an O(n2 log n2) optimal slicing algorithm for custom chip design--is presented. This relative placement algorithm addresses size effect and net connectivity effect simultaneously, while attaining a low polynomial time complexity O(kn2) without loss of global perspective, where k is a constant and depends on the accuracy that the placement required. The triangulation algorithm has O(n2 log n) time complexity. The triangulated planar graph can be used to do the floorplan by either the nonslicing RDG (rectangular dual graph) or slicing embedding methods. The optimum slicing algorithm has O(n2 log n2) time complexity. As expected, the wire length of the placement algorithm is shorter than that of a point model. However, since the optimal values of l0 and DEF (deformation ratio) are unknown, different values for l0 and DEF should be used in different circuits to obtain better placement results.

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

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

M3 - Conference article

AN - SCOPUS:0025692944

VL - 3

SP - 1672

EP - 1675

JO - Proceedings - IEEE International Symposium on Circuits and Systems

JF - Proceedings - IEEE International Symposium on Circuits and Systems

SN - 0271-4310

ER -

Lin Z-M, Lin HC. A new placement algorithm for custom chip design. Proceedings - IEEE International Symposium on Circuits and Systems. 1990 Dec 1;3:1672-1675.

Access to Document