Efficient two-phase approaches for branch-and-bound style resource constrained scheduling

Mingsong Chen; Fan Gu; Lei Zhou; Geguang Pu; Xiao Liu

doi:10.1109/VLSID.2014.35

Efficient two-phase approaches for branch-and-bound style resource constrained scheduling

Mingsong Chen
, Fan Gu
, Lei Zhou
, Geguang Pu^*
, Xiao Liu

^*Corresponding author for this work

Software Engineering Institute

East China Normal University

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

2 Scopus citations

Abstract

In high-level synthesis (HLS), the resource constrained scheduling (RCS) tries to explore a time-minimum schedule for low-level hardware implementations under specific resource constraints. To achieve such an optimal schedule quickly, branch-and-bound (B&B) approaches are widely investigated to prune the fruitless search space. However, due to the lack of approaches that can obtain a tight initial feasible schedule, RCS generally starts with an incompact search space, which is not time-efficient. This paper proposes an efficient two-phase approach, which can quickly shrink the search space using a smaller upper-bound for efficient B&B RCS search. The experimental results demonstrate that our approach can drastically reduce the overall RCS time.

Original language	English
Title of host publication	Proceedings - 27th International Conference on VLSI Design, VLSID 2014; Held Concurrently with 13th International Conference on Embedded Systems Design
Pages	162-167
Number of pages	6
DOIs	https://doi.org/10.1109/VLSID.2014.35
State	Published - 2014
Event	27th International Conference on VLSI Design, VLSID 2014 - Held Concurrently with 13th International Conference on Embedded Systems Design - Mumbai, India Duration: 5 Jan 2014 → 9 Jan 2014

Publication series

Name	Proceedings of the IEEE International Conference on VLSI Design
ISSN (Print)	1063-9667

Conference

Conference	27th International Conference on VLSI Design, VLSID 2014 - Held Concurrently with 13th International Conference on Embedded Systems Design
Country/Territory	India
City	Mumbai
Period	5/01/14 → 9/01/14

Keywords

Branch-and-Bound
High-Level Synthesis
Resource Constrained Scheduling

Access to Document

10.1109/VLSID.2014.35

Cite this

Chen, M., Gu, F., Zhou, L., Pu, G., & Liu, X. (2014). Efficient two-phase approaches for branch-and-bound style resource constrained scheduling. In Proceedings - 27th International Conference on VLSI Design, VLSID 2014; Held Concurrently with 13th International Conference on Embedded Systems Design (pp. 162-167). Article 6733124 (Proceedings of the IEEE International Conference on VLSI Design). https://doi.org/10.1109/VLSID.2014.35

Chen, Mingsong ; Gu, Fan ; Zhou, Lei et al. / Efficient two-phase approaches for branch-and-bound style resource constrained scheduling. Proceedings - 27th International Conference on VLSI Design, VLSID 2014; Held Concurrently with 13th International Conference on Embedded Systems Design. 2014. pp. 162-167 (Proceedings of the IEEE International Conference on VLSI Design).

@inproceedings{66c0d4d0b2214ac69bb11d2b6137d349,

title = "Efficient two-phase approaches for branch-and-bound style resource constrained scheduling",

abstract = "In high-level synthesis (HLS), the resource constrained scheduling (RCS) tries to explore a time-minimum schedule for low-level hardware implementations under specific resource constraints. To achieve such an optimal schedule quickly, branch-and-bound (B\&B) approaches are widely investigated to prune the fruitless search space. However, due to the lack of approaches that can obtain a tight initial feasible schedule, RCS generally starts with an incompact search space, which is not time-efficient. This paper proposes an efficient two-phase approach, which can quickly shrink the search space using a smaller upper-bound for efficient B\&B RCS search. The experimental results demonstrate that our approach can drastically reduce the overall RCS time.",

keywords = "Branch-and-Bound, High-Level Synthesis, Resource Constrained Scheduling",

author = "Mingsong Chen and Fan Gu and Lei Zhou and Geguang Pu and Xiao Liu",

year = "2014",

doi = "10.1109/VLSID.2014.35",

language = "英语",

isbn = "9781479925124",

series = "Proceedings of the IEEE International Conference on VLSI Design",

pages = "162--167",

booktitle = "Proceedings - 27th International Conference on VLSI Design, VLSID 2014; Held Concurrently with 13th International Conference on Embedded Systems Design",

note = "27th International Conference on VLSI Design, VLSID 2014 - Held Concurrently with 13th International Conference on Embedded Systems Design ; Conference date: 05-01-2014 Through 09-01-2014",

}

Chen, M, Gu, F, Zhou, L, Pu, G & Liu, X 2014, Efficient two-phase approaches for branch-and-bound style resource constrained scheduling. in Proceedings - 27th International Conference on VLSI Design, VLSID 2014; Held Concurrently with 13th International Conference on Embedded Systems Design., 6733124, Proceedings of the IEEE International Conference on VLSI Design, pp. 162-167, 27th International Conference on VLSI Design, VLSID 2014 - Held Concurrently with 13th International Conference on Embedded Systems Design, Mumbai, India, 5/01/14. https://doi.org/10.1109/VLSID.2014.35

Efficient two-phase approaches for branch-and-bound style resource constrained scheduling. / Chen, Mingsong; Gu, Fan; Zhou, Lei et al.
Proceedings - 27th International Conference on VLSI Design, VLSID 2014; Held Concurrently with 13th International Conference on Embedded Systems Design. 2014. p. 162-167 6733124 (Proceedings of the IEEE International Conference on VLSI Design).

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

TY - GEN

T1 - Efficient two-phase approaches for branch-and-bound style resource constrained scheduling

AU - Chen, Mingsong

AU - Gu, Fan

AU - Zhou, Lei

AU - Pu, Geguang

AU - Liu, Xiao

PY - 2014

Y1 - 2014

N2 - In high-level synthesis (HLS), the resource constrained scheduling (RCS) tries to explore a time-minimum schedule for low-level hardware implementations under specific resource constraints. To achieve such an optimal schedule quickly, branch-and-bound (B&B) approaches are widely investigated to prune the fruitless search space. However, due to the lack of approaches that can obtain a tight initial feasible schedule, RCS generally starts with an incompact search space, which is not time-efficient. This paper proposes an efficient two-phase approach, which can quickly shrink the search space using a smaller upper-bound for efficient B&B RCS search. The experimental results demonstrate that our approach can drastically reduce the overall RCS time.

AB - In high-level synthesis (HLS), the resource constrained scheduling (RCS) tries to explore a time-minimum schedule for low-level hardware implementations under specific resource constraints. To achieve such an optimal schedule quickly, branch-and-bound (B&B) approaches are widely investigated to prune the fruitless search space. However, due to the lack of approaches that can obtain a tight initial feasible schedule, RCS generally starts with an incompact search space, which is not time-efficient. This paper proposes an efficient two-phase approach, which can quickly shrink the search space using a smaller upper-bound for efficient B&B RCS search. The experimental results demonstrate that our approach can drastically reduce the overall RCS time.

KW - Branch-and-Bound

KW - High-Level Synthesis

KW - Resource Constrained Scheduling

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

U2 - 10.1109/VLSID.2014.35

DO - 10.1109/VLSID.2014.35

M3 - 会议稿件

AN - SCOPUS:84894547874

SN - 9781479925124

T3 - Proceedings of the IEEE International Conference on VLSI Design

SP - 162

EP - 167

BT - Proceedings - 27th International Conference on VLSI Design, VLSID 2014; Held Concurrently with 13th International Conference on Embedded Systems Design

T2 - 27th International Conference on VLSI Design, VLSID 2014 - Held Concurrently with 13th International Conference on Embedded Systems Design

Y2 - 5 January 2014 through 9 January 2014

ER -

Chen M, Gu F, Zhou L, Pu G, Liu X. Efficient two-phase approaches for branch-and-bound style resource constrained scheduling. In Proceedings - 27th International Conference on VLSI Design, VLSID 2014; Held Concurrently with 13th International Conference on Embedded Systems Design. 2014. p. 162-167. 6733124. (Proceedings of the IEEE International Conference on VLSI Design). doi: 10.1109/VLSID.2014.35

Efficient two-phase approaches for branch-and-bound style resource constrained scheduling

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this