A force directed partitioning algorithm for 3D floorplanning

Linquan Lyu; Takeshi Yoshimura

doi:10.1109/ASICON.2017.8252576

A force directed partitioning algorithm for 3D floorplanning

Linquan Lyu, Takeshi Yoshimura

Graduate School of Information, Production and Systems

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

6 Citations (Scopus)

Abstract

Partitioning is very important to 3D IC physical design. Currently, hMetis (most famous partitioning software package) is widely used for partitioning. However, hMetis is for partitioning of hyper graphs. When the method is used for layer assignment of 3D floorplan/placement, some net might be too long. This paper develops a partitioning algorithm for 3D floorplan. The proposed combines a cost-based heuristic and force directed algorithm, which places the nodes considering attractive force and repulsive force, in order to solve the long net problem. We consider both the wire length and the number of TSVs in this work. The second part of the algorithm has two kinds according to the different emphasis. The experimental results demonstrated our algorithms can effectively reduce the wire length and the number of TSV. By comparing the experimental results of two focuses, we can get the differences and strengths of the two algorithms separately.

Original language	English
Title of host publication	Proceedings - 2017 IEEE 12th International Conference on ASIC, ASICON 2017
Publisher	IEEE Computer Society
Pages	718-721
Number of pages	4
Volume	2017-October
ISBN (Electronic)	9781509066247
DOIs	https://doi.org/10.1109/ASICON.2017.8252576
Publication status	Published - 2018 Jan 8
Event	12th IEEE International Conference on Advanced Semiconductor Integrated Circuits, ASICON 2017 - Guiyang, China Duration: 2017 Oct 25 → 2017 Oct 28

Other

Other	12th IEEE International Conference on Advanced Semiconductor Integrated Circuits, ASICON 2017
Country/Territory	China
City	Guiyang
Period	17/10/25 → 17/10/28

Keywords

3D IC
Force-directed algorithm
IC partitioning
TSV
Wire length

ASJC Scopus subject areas

Hardware and Architecture
Electrical and Electronic Engineering

Access to Document

10.1109/ASICON.2017.8252576

Cite this

Lyu, L & Yoshimura, T 2018, A force directed partitioning algorithm for 3D floorplanning. in Proceedings - 2017 IEEE 12th International Conference on ASIC, ASICON 2017. vol. 2017-October, IEEE Computer Society, pp. 718-721, 12th IEEE International Conference on Advanced Semiconductor Integrated Circuits, ASICON 2017, Guiyang, China, 17/10/25. https://doi.org/10.1109/ASICON.2017.8252576

@inproceedings{430999f0146f4cd2a31c771dd34d8ee7,

title = "A force directed partitioning algorithm for 3D floorplanning",

abstract = "Partitioning is very important to 3D IC physical design. Currently, hMetis (most famous partitioning software package) is widely used for partitioning. However, hMetis is for partitioning of hyper graphs. When the method is used for layer assignment of 3D floorplan/placement, some net might be too long. This paper develops a partitioning algorithm for 3D floorplan. The proposed combines a cost-based heuristic and force directed algorithm, which places the nodes considering attractive force and repulsive force, in order to solve the long net problem. We consider both the wire length and the number of TSVs in this work. The second part of the algorithm has two kinds according to the different emphasis. The experimental results demonstrated our algorithms can effectively reduce the wire length and the number of TSV. By comparing the experimental results of two focuses, we can get the differences and strengths of the two algorithms separately.",

keywords = "3D IC, Force-directed algorithm, IC partitioning, TSV, Wire length",

author = "Linquan Lyu and Takeshi Yoshimura",

year = "2018",

month = jan,

day = "8",

doi = "10.1109/ASICON.2017.8252576",

language = "English",

volume = "2017-October",

pages = "718--721",

booktitle = "Proceedings - 2017 IEEE 12th International Conference on ASIC, ASICON 2017",

publisher = "IEEE Computer Society",

note = "12th IEEE International Conference on Advanced Semiconductor Integrated Circuits, ASICON 2017 ; Conference date: 25-10-2017 Through 28-10-2017",

}

TY - GEN

T1 - A force directed partitioning algorithm for 3D floorplanning

AU - Lyu, Linquan

AU - Yoshimura, Takeshi

PY - 2018/1/8

Y1 - 2018/1/8

N2 - Partitioning is very important to 3D IC physical design. Currently, hMetis (most famous partitioning software package) is widely used for partitioning. However, hMetis is for partitioning of hyper graphs. When the method is used for layer assignment of 3D floorplan/placement, some net might be too long. This paper develops a partitioning algorithm for 3D floorplan. The proposed combines a cost-based heuristic and force directed algorithm, which places the nodes considering attractive force and repulsive force, in order to solve the long net problem. We consider both the wire length and the number of TSVs in this work. The second part of the algorithm has two kinds according to the different emphasis. The experimental results demonstrated our algorithms can effectively reduce the wire length and the number of TSV. By comparing the experimental results of two focuses, we can get the differences and strengths of the two algorithms separately.

AB - Partitioning is very important to 3D IC physical design. Currently, hMetis (most famous partitioning software package) is widely used for partitioning. However, hMetis is for partitioning of hyper graphs. When the method is used for layer assignment of 3D floorplan/placement, some net might be too long. This paper develops a partitioning algorithm for 3D floorplan. The proposed combines a cost-based heuristic and force directed algorithm, which places the nodes considering attractive force and repulsive force, in order to solve the long net problem. We consider both the wire length and the number of TSVs in this work. The second part of the algorithm has two kinds according to the different emphasis. The experimental results demonstrated our algorithms can effectively reduce the wire length and the number of TSV. By comparing the experimental results of two focuses, we can get the differences and strengths of the two algorithms separately.

KW - 3D IC

KW - Force-directed algorithm

KW - IC partitioning

KW - TSV

KW - Wire length

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

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

U2 - 10.1109/ASICON.2017.8252576

DO - 10.1109/ASICON.2017.8252576

M3 - Conference contribution

AN - SCOPUS:85044783024

VL - 2017-October

SP - 718

EP - 721

BT - Proceedings - 2017 IEEE 12th International Conference on ASIC, ASICON 2017

PB - IEEE Computer Society

T2 - 12th IEEE International Conference on Advanced Semiconductor Integrated Circuits, ASICON 2017

Y2 - 25 October 2017 through 28 October 2017

ER -

A force directed partitioning algorithm for 3D floorplanning

Abstract

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this