Port assignment for interconnect reduction in high-level synthesis

Hao Cong; Song Chen; Takeshi Yoshimura

doi:10.1109/VLSI-DAT.2012.6212613

Port assignment for interconnect reduction in high-level synthesis

Hao Cong^*, Song Chen, Takeshi Yoshimura

^*この研究の対応する著者

大学院情報生産システム研究科

研究成果: Conference contribution

4 被引用数 (Scopus)

抄録

This paper focuses on the Port Assignment Problem for Binary Commutative Operators (PAP-BCO) in high-level synthesis. Given a binding of operations and variables, the PAP-BCO pursues to build the connections of registers to functional units with an objective of minimizing the number of interconnections. In this paper, we formulate the PAP-BCO as a vertex partitioning problem on a graph, and propose an exact Integer Linear Programming (ILP) based method and a fast iterative method based on elementary transformations of spanning tree to solve it. Experimental results show that the fast iterative algorithm can get the optimum solutions in 97% runs. At the same time, the running time is only tens of milliseconds for the maximum test case with 64 registers and 140 operations, on which the ILP based method ran out of time.

本文言語	English
ホスト出版物のタイトル	2012 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2012 - Proceedings of Technical Papers
DOI	https://doi.org/10.1109/VLSI-DAT.2012.6212613
出版ステータス	Published - 2012
イベント	2012 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2012 - Hsinchu 継続期間: 2012 4月 23 → 2012 4月 25

Other

Other	2012 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2012
City	Hsinchu
Period	12/4/23 → 12/4/25

ASJC Scopus subject areas

ハードウェアとアーキテクチャ

文献へのアクセス

10.1109/VLSI-DAT.2012.6212613

他のファイルとリンク

引用スタイル

Cong, H, Chen, S & Yoshimura, T 2012, Port assignment for interconnect reduction in high-level synthesis. in 2012 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2012 - Proceedings of Technical Papers., 6212613, 2012 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2012, Hsinchu, 12/4/23. https://doi.org/10.1109/VLSI-DAT.2012.6212613

@inproceedings{fcabb178bd0f4692887a1645d4bd7db2,

title = "Port assignment for interconnect reduction in high-level synthesis",

abstract = "This paper focuses on the Port Assignment Problem for Binary Commutative Operators (PAP-BCO) in high-level synthesis. Given a binding of operations and variables, the PAP-BCO pursues to build the connections of registers to functional units with an objective of minimizing the number of interconnections. In this paper, we formulate the PAP-BCO as a vertex partitioning problem on a graph, and propose an exact Integer Linear Programming (ILP) based method and a fast iterative method based on elementary transformations of spanning tree to solve it. Experimental results show that the fast iterative algorithm can get the optimum solutions in 97% runs. At the same time, the running time is only tens of milliseconds for the maximum test case with 64 registers and 140 operations, on which the ILP based method ran out of time.",

author = "Hao Cong and Song Chen and Takeshi Yoshimura",

year = "2012",

doi = "10.1109/VLSI-DAT.2012.6212613",

language = "English",

isbn = "9781457720819",

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

note = "2012 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2012 ; Conference date: 23-04-2012 Through 25-04-2012",

}

TY - GEN

T1 - Port assignment for interconnect reduction in high-level synthesis

AU - Cong, Hao

AU - Chen, Song

AU - Yoshimura, Takeshi

PY - 2012

Y1 - 2012

N2 - This paper focuses on the Port Assignment Problem for Binary Commutative Operators (PAP-BCO) in high-level synthesis. Given a binding of operations and variables, the PAP-BCO pursues to build the connections of registers to functional units with an objective of minimizing the number of interconnections. In this paper, we formulate the PAP-BCO as a vertex partitioning problem on a graph, and propose an exact Integer Linear Programming (ILP) based method and a fast iterative method based on elementary transformations of spanning tree to solve it. Experimental results show that the fast iterative algorithm can get the optimum solutions in 97% runs. At the same time, the running time is only tens of milliseconds for the maximum test case with 64 registers and 140 operations, on which the ILP based method ran out of time.

AB - This paper focuses on the Port Assignment Problem for Binary Commutative Operators (PAP-BCO) in high-level synthesis. Given a binding of operations and variables, the PAP-BCO pursues to build the connections of registers to functional units with an objective of minimizing the number of interconnections. In this paper, we formulate the PAP-BCO as a vertex partitioning problem on a graph, and propose an exact Integer Linear Programming (ILP) based method and a fast iterative method based on elementary transformations of spanning tree to solve it. Experimental results show that the fast iterative algorithm can get the optimum solutions in 97% runs. At the same time, the running time is only tens of milliseconds for the maximum test case with 64 registers and 140 operations, on which the ILP based method ran out of time.

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

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

U2 - 10.1109/VLSI-DAT.2012.6212613

DO - 10.1109/VLSI-DAT.2012.6212613

M3 - Conference contribution

AN - SCOPUS:84864051717

SN - 9781457720819

BT - 2012 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2012 - Proceedings of Technical Papers

T2 - 2012 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2012

Y2 - 23 April 2012 through 25 April 2012

ER -

Port assignment for interconnect reduction in high-level synthesis

抄録

Other

ASJC Scopus subject areas

文献へのアクセス

他のファイルとリンク

フィンガープリント

引用スタイル