Full Text:   <1297>

CLC number: TP391.7

On-line Access: 

Received: 2006-05-16

Revision Accepted: 2006-08-09

Crosschecked: 0000-00-00

Cited: 0

Clicked: 3454

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE A 2007 Vol.8 No.1 P.119~126

http://doi.org/10.1631/jzus.2007.A0119


Fast combination of scheduling chains under resource and time constraints


Author(s):  WANG Ji-min, PAN Xue-zeng, WANG Jie-bing, SUN Kang

Affiliation(s):  School of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China

Corresponding email(s):   bigjim@zju.edu.cn

Key Words:  Fast combination algorithm, Chain-based scheduling algorithm, High-level synthesis (HLS), Minimum length prediction


WANG Ji-min, PAN Xue-zeng, WANG Jie-bing, SUN Kang. Fast combination of scheduling chains under resource and time constraints[J]. Journal of Zhejiang University Science A, 2007, 8(1): 119~126.

@article{title="Fast combination of scheduling chains under resource and time constraints",
author="WANG Ji-min, PAN Xue-zeng, WANG Jie-bing, SUN Kang",
journal="Journal of Zhejiang University Science A",
volume="8",
number="1",
pages="119~126",
year="2007",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.2007.A0119"
}

%0 Journal Article
%T Fast combination of scheduling chains under resource and time constraints
%A WANG Ji-min
%A PAN Xue-zeng
%A WANG Jie-bing
%A SUN Kang
%J Journal of Zhejiang University SCIENCE A
%V 8
%N 1
%P 119~126
%@ 1673-565X
%D 2007
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.2007.A0119

TY - JOUR
T1 - Fast combination of scheduling chains under resource and time constraints
A1 - WANG Ji-min
A1 - PAN Xue-zeng
A1 - WANG Jie-bing
A1 - SUN Kang
J0 - Journal of Zhejiang University Science A
VL - 8
IS - 1
SP - 119
EP - 126
%@ 1673-565X
Y1 - 2007
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.2007.A0119


Abstract: 
Scheduling chain combination is the core of chain-based scheduling algorithms, the speed of which determines the overall performance of corresponding scheduling algorithm. However, backtracking is used in general combination algorithms to traverse the whole search space which may introduce redundant operations, so performance of the combination algorithm is generally poor. A fast scheduling chain combination algorithm which avoids redundant operations by skipping “incompatible” steps of scheduling chains and using a stack to remember the scheduling state is presented in this paper to overcome the problem. Experimental results showed that it can improve the performance of scheduling algorithms by up to 15 times. By further omitting unnecessary operations, a fast algorithm of minimum combination length prediction is developed, which can improve the speed by up to 10 times.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[1] Chantana, C., Wanlop, S., Edwin, S., 2004. Efficient Scheduling for Design Exploration with Imprecise Latency and Register Constraints. Proc. EUC. Aizu-Wakamatsu City, Japan, p.259-270.

[2] Gajski, D., Dutt, N., Pangrle, B., 1986. Silicon Compilation (Tutorial). Proceedings of the IEEE Custom Integrated Circuits Conference. IEEE Computer Society Press, Los Alamitos, California, p.102-110.

[3] Hwang, C.T., Lee, J.H., Hsu, Y.C., 1991. A formal approach to the scheduling problem in high level synthesis. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 10(4):464-475.

[4] Kumar, A., Bayoumi, M., Elgamel, M., 2004. A methodology for low power scheduling with resource operating at multiple voltages. Integration, the VLSI Journal, 37(1):29-62.

[5] Lin, Y.L., 1997. Recent development in high level synthesis. ACM Transactions on Design Automation of Electronic Systems, 2(1):2-21.

[6] Memik, S.O., Fallah, F., 2002. Accelerated SAT-based Scheduling of Control/Data Flow Graphs. Proceedings of the 2002 IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD’02). Washington DC, USA, p.395-400.

[7] Memik, S.O., Kastner, R., Bozorgzadeh, E., Sarrafzadeh, M., 2005. A scheduling algorithm for optimization and early planning in high-level synthesis. ACM Transactions on Design Automation of Electronic Systems, 10(1):33-57.

[8] Mohanty, S.P., Ranganathan, N., 2005. Energy-efficient datapath scheduling using multiple boltages and dynamic clocking. ACM Transactions on Design Automation of Electronic Systems, 10(2):330-353.

[9] Mohanty, S.P., Ranganathan, N., Chappidi, S.K., 2006. ILP models for simultaneous energy and transient power minimization during behavioral synthesis. ACM Transactions on Design Automation of Electronic Systems, 11(1):186-212.

[10] Narasimhan, M., Ramanujam, J., 2001. A fast approach to computing exact solutions to the resource-constrained scheduling problem. ACM Transactions on Design Automation of Electronic Systems, 6(4):490-500.

[11] Parker, A.C., Pizarro, J., Mlinar, M., 1986. Maha: A Program for Datapath Synthesis. Proc. DAC. Las Vegas, USA, p.461-466.

[12] Paulin, P.G., Knight, J.P., 1989. Force-directed scheduling for the behavioral synthesis of ASICs. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 8(6):661-679.

[13] Sllame, A.M., Drabek, V., 2002. An Efficient List-based Scheduling Algorithm for High-level Synthesis. Proc. DSD’02. Dortmund, Germany, p.316-323.

[14] Ullman, J., 1975. NP-complete scheduling problems. Journal of Computer System Science, 10(3):384-393.

[15] Yuan, X.L., Shen, X.B., 1998. A path-based scheduling algorithm. Computer Research and Development, 35(3):279-282 (in Chinese).

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE