FDPrior: A force-directed based parallel partitioning algorithm for three dimensional integrated circuits on GPGPU

Wan Jing Chen; Hsien Kai Kuo; Tsou Han Chiu; Bo-Cheng Lai

doi:10.1109/VDAT.2011.5783580

FDPrior: A force-directed based parallel partitioning algorithm for three dimensional integrated circuits on GPGPU

Wan Jing Chen^*, Hsien Kai Kuo, Tsou Han Chiu, Bo-Cheng Lai

^*Corresponding author for this work

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

1 Scopus citations

Abstract

This paper proposes an innovative force-directed parallel algorithm, FDPrior, to solve the multilayer partitioning problem of 3DICs. The growing scale and multi-layered structure of the 3DIC technology make it computational expensive for EDA tools to achieve optimization goals. Exploiting the algorithmic parallelism on multi-core architectures becomes the key to attain scalable runtime. By adopting the N-body simulation scheme and novel techniques to reduce synchronization overhead, FDPrior successfully exposes the massive parallelism on the multi-core GPGPU architecture. The objective is to minimize the total number of Through Silicon Vias (TSVs) while meeting the area constraint for each layer. The experimental results on ISPD98 benchmark show that FDPrior outperforms the conventional FM algorithm by achieving in average 5.0X better TSVs and up to 247.3X runtime speedup. Compared with PP3D, a parallel 3DIC partitioning algorithm, FDPrior achieves 6.7X better TSVS with 3.3 X runtime enhancement.

Original language	English
Title of host publication	Proceedings of 2011 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2011
Pages	70-73
Number of pages	4
DOIs	https://doi.org/10.1109/VDAT.2011.5783580
State	Published - 28 Jun 2011
Event	2011 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2011 - Hsinchu, Taiwan Duration: 25 Apr 2011 → 28 Apr 2011

Publication series

Name	Proceedings of 2011 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2011

Conference

Conference	2011 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2011
Country/Territory	Taiwan
City	Hsinchu
Period	25/04/11 → 28/04/11

Access to Document

10.1109/VDAT.2011.5783580

Cite this

Chen, W. J., Kuo, H. K., Chiu, T. H., & Lai, B-C. (2011). FDPrior: A force-directed based parallel partitioning algorithm for three dimensional integrated circuits on GPGPU. In Proceedings of 2011 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2011 (pp. 70-73). [5783580] (Proceedings of 2011 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2011). https://doi.org/10.1109/VDAT.2011.5783580

Chen, Wan Jing ; Kuo, Hsien Kai ; Chiu, Tsou Han et al. / FDPrior : A force-directed based parallel partitioning algorithm for three dimensional integrated circuits on GPGPU. Proceedings of 2011 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2011. 2011. pp. 70-73 (Proceedings of 2011 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2011).

@inproceedings{77869f945bf947ed855dcafddef7a156,

title = "FDPrior: A force-directed based parallel partitioning algorithm for three dimensional integrated circuits on GPGPU",

abstract = "This paper proposes an innovative force-directed parallel algorithm, FDPrior, to solve the multilayer partitioning problem of 3DICs. The growing scale and multi-layered structure of the 3DIC technology make it computational expensive for EDA tools to achieve optimization goals. Exploiting the algorithmic parallelism on multi-core architectures becomes the key to attain scalable runtime. By adopting the N-body simulation scheme and novel techniques to reduce synchronization overhead, FDPrior successfully exposes the massive parallelism on the multi-core GPGPU architecture. The objective is to minimize the total number of Through Silicon Vias (TSVs) while meeting the area constraint for each layer. The experimental results on ISPD98 benchmark show that FDPrior outperforms the conventional FM algorithm by achieving in average 5.0X better TSVs and up to 247.3X runtime speedup. Compared with PP3D, a parallel 3DIC partitioning algorithm, FDPrior achieves 6.7X better TSVS with 3.3 X runtime enhancement.",

author = "Chen, {Wan Jing} and Kuo, {Hsien Kai} and Chiu, {Tsou Han} and Bo-Cheng Lai",

year = "2011",

month = jun,

day = "28",

doi = "10.1109/VDAT.2011.5783580",

language = "English",

isbn = "9781424484997",

series = "Proceedings of 2011 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2011",

pages = "70--73",

booktitle = "Proceedings of 2011 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2011",

note = "null ; Conference date: 25-04-2011 Through 28-04-2011",

}

Chen, WJ, Kuo, HK, Chiu, TH & Lai, B-C 2011, FDPrior: A force-directed based parallel partitioning algorithm for three dimensional integrated circuits on GPGPU. in Proceedings of 2011 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2011., 5783580, Proceedings of 2011 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2011, pp. 70-73, 2011 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2011, Hsinchu, Taiwan, 25/04/11. https://doi.org/10.1109/VDAT.2011.5783580

FDPrior : A force-directed based parallel partitioning algorithm for three dimensional integrated circuits on GPGPU. / Chen, Wan Jing; Kuo, Hsien Kai; Chiu, Tsou Han et al.

Proceedings of 2011 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2011. 2011. p. 70-73 5783580 (Proceedings of 2011 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2011).

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

TY - GEN

T1 - FDPrior

AU - Chen, Wan Jing

AU - Kuo, Hsien Kai

AU - Chiu, Tsou Han

AU - Lai, Bo-Cheng

PY - 2011/6/28

Y1 - 2011/6/28

N2 - This paper proposes an innovative force-directed parallel algorithm, FDPrior, to solve the multilayer partitioning problem of 3DICs. The growing scale and multi-layered structure of the 3DIC technology make it computational expensive for EDA tools to achieve optimization goals. Exploiting the algorithmic parallelism on multi-core architectures becomes the key to attain scalable runtime. By adopting the N-body simulation scheme and novel techniques to reduce synchronization overhead, FDPrior successfully exposes the massive parallelism on the multi-core GPGPU architecture. The objective is to minimize the total number of Through Silicon Vias (TSVs) while meeting the area constraint for each layer. The experimental results on ISPD98 benchmark show that FDPrior outperforms the conventional FM algorithm by achieving in average 5.0X better TSVs and up to 247.3X runtime speedup. Compared with PP3D, a parallel 3DIC partitioning algorithm, FDPrior achieves 6.7X better TSVS with 3.3 X runtime enhancement.

AB - This paper proposes an innovative force-directed parallel algorithm, FDPrior, to solve the multilayer partitioning problem of 3DICs. The growing scale and multi-layered structure of the 3DIC technology make it computational expensive for EDA tools to achieve optimization goals. Exploiting the algorithmic parallelism on multi-core architectures becomes the key to attain scalable runtime. By adopting the N-body simulation scheme and novel techniques to reduce synchronization overhead, FDPrior successfully exposes the massive parallelism on the multi-core GPGPU architecture. The objective is to minimize the total number of Through Silicon Vias (TSVs) while meeting the area constraint for each layer. The experimental results on ISPD98 benchmark show that FDPrior outperforms the conventional FM algorithm by achieving in average 5.0X better TSVs and up to 247.3X runtime speedup. Compared with PP3D, a parallel 3DIC partitioning algorithm, FDPrior achieves 6.7X better TSVS with 3.3 X runtime enhancement.

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

U2 - 10.1109/VDAT.2011.5783580

DO - 10.1109/VDAT.2011.5783580

M3 - Conference contribution

AN - SCOPUS:79959529191

SN - 9781424484997

T3 - Proceedings of 2011 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2011

SP - 70

EP - 73

BT - Proceedings of 2011 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2011

Y2 - 25 April 2011 through 28 April 2011

ER -

Chen WJ, Kuo HK, Chiu TH, Lai B-C. FDPrior: A force-directed based parallel partitioning algorithm for three dimensional integrated circuits on GPGPU. In Proceedings of 2011 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2011. 2011. p. 70-73. 5783580. (Proceedings of 2011 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2011). doi: 10.1109/VDAT.2011.5783580

FDPrior: A force-directed based parallel partitioning algorithm for three dimensional integrated circuits on GPGPU

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this