Arrival time aware scheduling to minimize clock cycle length

ABSTRACT

Conventional scheduling algorithms usually adjust the clock cycle duration to the execution time of the longest operations. This results in large slack times wasted in those cycles with faster operations. To reduce the wasted times multi-cycle and chaining techniques have been employed. The scheduling algorithm presented in this paper goes one step further. It breaks up some of the specification operations and schedule several data-dependent operation fragments in the same cycle. In consequence, some of the specification operations are executed during several cycles (non-necessarily consecutive ones), and in every execution cycle some result bits are calculated. Thus the execution of one operation may start even if its predecessors have not finished yet. In the experimental results carried out, the proposed algorithm improves circuit performance above 70% on average, with slight increments in the datapath area.

REFERENCES

• 1: N. Park, and A. Parker. "Sehwa: A Software Package for Synthesis of Pipelines from Behavioural Specifications". IEEE Trans. On Computer-Aided Design of Integrated Circuits and Systems, 1988.
• 2: K. S. Hwang, A. E. Casavant, C. T. Chang, and M. A. d'Abreu. "Scheduling and Hardware Sharing in Pipelined Data Paths". In Proc. ICCAD, 1989.
• 3: S. Park, and K. Choi. "Performance-Driven High-Level Synthesis with Bit-Level Chaining and Clock Selection". IEEE Trans. On Computer-Aided Design of Integrated Circuits and Systems, 2001.
• 4: Zhan Yu , Kei-Yong Khoo , Alan N. Willson, Jr., The use of carry-save representation in joint module selection and retiming, Proceedings of the 37th conference on Design automation, p.768-773, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337773]
• 5: V. Raghunathan, S. Ravi, and G. Lakshminarayana. "Integrating Variable-Latency Components into High-Level Synthesis". IEEE Trans. On Computer-Aided Design, October 2000.
• 6: Jianwen Zhu , Daniel D. Gajski, Soft scheduling in high level synthesis, Proceedings of the 36th ACM/IEEE conference on Design automation, p.219-224, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309917]
• 7: P. Marwedel, B. Landwehr, and R. Dömer. "Built-in Chaining: Introducing Complex Components into Architectural Synthesis". In proc. ASPDAC, 1997.
• 8: M. C. Molina , J. M. Mendías , R. Hermida, Bit-level scheduling of heterogeneous behavioural specifications, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.602-608, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774661]
• 9: P. G. Paulin, and J. P. Knight. "Force-directed scheduling for the behavioral synthesis of ASIC's". IEEE Trans. On Computer-Aided Design, June 1989.
• 10: M. Molina , J. Mendias , R. Hermida, Multiple-Precision Circuits Allocation Independent of Data-Objects Length, Proceedings of the conference on Design, automation and test in Europe, p.909, March 04-08, 2002
• 11: N. Dutt, "High-level Synthesis Workshop Benchmarks" Univ. California, Irvine, CA, Technical Report, 1992.