An optimal lower-bound algorithm for the high-level synthesis scheduling problem

Geguang Pu; Jifeng He; Zongyan Qiu

doi:10.1109/DDECS.2006.1649599

An optimal lower-bound algorithm for the high-level synthesis scheduling problem

Geguang Pu^*
, Jifeng He
, Zongyan Qiu

^*Corresponding author for this work

Software Engineering Institute

Peking University

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

1 Scopus citations

Abstract

An optimal scheduling algorithm in High-Level Synthesis is described, which searches for the minimum time scheduling under given resource constraints. The algorithm can substantially reduce the computational effort required to obtain the exact solution using a branch-and-bound search method and some novel bounding techniques to prune the unfruitful search space. Some time properties are explored to enlighten these bounding techniques. Experimental results on several benchmarks with varying resource constraints show our algorithm is both efficient and effective.

Original language	English
Title of host publication	2006 IEEE Design and Diagnostics of Electronic Circuits and systems
Pages	149-150
Number of pages	2
DOIs	https://doi.org/10.1109/DDECS.2006.1649599
State	Published - 2006
Event	2006 IEEE Design and Diagnostics of Electronic Circuits and systems - Praque, Czech Republic Duration: 18 Apr 2006 → 21 Apr 2006

Publication series

Name	2006 IEEE Design and Diagnostics of Electronic Circuits and systems
Volume	2006

Conference

Conference	2006 IEEE Design and Diagnostics of Electronic Circuits and systems
Country/Territory	Czech Republic
City	Praque
Period	18/04/06 → 21/04/06

Access to Document

10.1109/DDECS.2006.1649599

Cite this

@inproceedings{090d5e4b96be4bf281ae008831562e87,

title = "An optimal lower-bound algorithm for the high-level synthesis scheduling problem",

abstract = "An optimal scheduling algorithm in High-Level Synthesis is described, which searches for the minimum time scheduling under given resource constraints. The algorithm can substantially reduce the computational effort required to obtain the exact solution using a branch-and-bound search method and some novel bounding techniques to prune the unfruitful search space. Some time properties are explored to enlighten these bounding techniques. Experimental results on several benchmarks with varying resource constraints show our algorithm is both efficient and effective.",

author = "Geguang Pu and Jifeng He and Zongyan Qiu",

year = "2006",

doi = "10.1109/DDECS.2006.1649599",

language = "英语",

isbn = "1424401852",

series = "2006 IEEE Design and Diagnostics of Electronic Circuits and systems",

pages = "149--150",

booktitle = "2006 IEEE Design and Diagnostics of Electronic Circuits and systems",

note = "2006 IEEE Design and Diagnostics of Electronic Circuits and systems ; Conference date: 18-04-2006 Through 21-04-2006",

}

Pu, G , He, J & Qiu, Z 2006, An optimal lower-bound algorithm for the high-level synthesis scheduling problem. in 2006 IEEE Design and Diagnostics of Electronic Circuits and systems., 1649599, 2006 IEEE Design and Diagnostics of Electronic Circuits and systems, vol. 2006, pp. 149-150, 2006 IEEE Design and Diagnostics of Electronic Circuits and systems, Praque, Czech Republic, 18/04/06. https://doi.org/10.1109/DDECS.2006.1649599

An optimal lower-bound algorithm for the high-level synthesis scheduling problem. / Pu, Geguang ; He, Jifeng; Qiu, Zongyan.
2006 IEEE Design and Diagnostics of Electronic Circuits and systems. 2006. p. 149-150 1649599 (2006 IEEE Design and Diagnostics of Electronic Circuits and systems; Vol. 2006).

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

TY - GEN

T1 - An optimal lower-bound algorithm for the high-level synthesis scheduling problem

AU - Pu, Geguang

AU - He, Jifeng

AU - Qiu, Zongyan

PY - 2006

Y1 - 2006

N2 - An optimal scheduling algorithm in High-Level Synthesis is described, which searches for the minimum time scheduling under given resource constraints. The algorithm can substantially reduce the computational effort required to obtain the exact solution using a branch-and-bound search method and some novel bounding techniques to prune the unfruitful search space. Some time properties are explored to enlighten these bounding techniques. Experimental results on several benchmarks with varying resource constraints show our algorithm is both efficient and effective.

AB - An optimal scheduling algorithm in High-Level Synthesis is described, which searches for the minimum time scheduling under given resource constraints. The algorithm can substantially reduce the computational effort required to obtain the exact solution using a branch-and-bound search method and some novel bounding techniques to prune the unfruitful search space. Some time properties are explored to enlighten these bounding techniques. Experimental results on several benchmarks with varying resource constraints show our algorithm is both efficient and effective.

UR - https://www.scopus.com/pages/publications/33847110682

U2 - 10.1109/DDECS.2006.1649599

DO - 10.1109/DDECS.2006.1649599

M3 - 会议稿件

AN - SCOPUS:33847110682

SN - 1424401852

SN - 9781424401857

T3 - 2006 IEEE Design and Diagnostics of Electronic Circuits and systems

SP - 149

EP - 150

BT - 2006 IEEE Design and Diagnostics of Electronic Circuits and systems

T2 - 2006 IEEE Design and Diagnostics of Electronic Circuits and systems

Y2 - 18 April 2006 through 21 April 2006

ER -

An optimal lower-bound algorithm for the high-level synthesis scheduling problem

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this