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

^*此作品的通讯作者

软件工程学院

East China Normal University

科研成果: 书/报告/会议事项章节 › 会议稿件 › 同行评审

2 引用（Scopus）

摘要

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.

源语言	英语
主期刊名	Proceedings - 27th International Conference on VLSI Design, VLSID 2014; Held Concurrently with 13th International Conference on Embedded Systems Design
页	162-167
页数	6
DOI	https://doi.org/10.1109/VLSID.2014.35
出版状态	已出版 - 2014
活动	27th International Conference on VLSI Design, VLSID 2014 - Held Concurrently with 13th International Conference on Embedded Systems Design - Mumbai, 印度期限: 5 1月 2014 → 9 1月 2014

出版系列

姓名	Proceedings of the IEEE International Conference on VLSI Design
ISSN（印刷版）	1063-9667

会议

会议	27th International Conference on VLSI Design, VLSID 2014 - Held Concurrently with 13th International Conference on Embedded Systems Design
国家/地区	印度
市	Mumbai
时期	5/01/14 → 9/01/14

访问文件

10.1109/VLSID.2014.35

其它文件与链接

链接到 Scopus 的出版物

引用此

Chen, M., Gu, F., Zhou, L., Pu, G., & Liu, X. (2014). 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 (页码 162-167). 文章 6733124 (Proceedings of the IEEE International Conference on VLSI Design). https://doi.org/10.1109/VLSID.2014.35

Chen, Mingsong ; Gu, Fan ; Zhou, Lei 等. / 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. 页码 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. 在 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, 页码 162-167, 27th International Conference on VLSI Design, VLSID 2014 - Held Concurrently with 13th International Conference on Embedded Systems Design, Mumbai, 印度, 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 等.
Proceedings - 27th International Conference on VLSI Design, VLSID 2014; Held Concurrently with 13th International Conference on Embedded Systems Design. 2014. 页码 162-167 6733124 (Proceedings of the IEEE International Conference on VLSI Design).

科研成果: 书/报告/会议事项章节 › 会议稿件 › 同行评审

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. 在 Proceedings - 27th International Conference on VLSI Design, VLSID 2014; Held Concurrently with 13th International Conference on Embedded Systems Design. 2014. 页码 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

摘要

出版系列

会议

访问文件

其它文件与链接

指纹

引用此