Similar articles

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.

[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).