Performance-constrained hierarchical pipelining for behaviors, loops, and operations

ABSTRACT

Behavioral specifications of DSP systems generally contain a number of nested loops. In order to obtain high date rates for such systems, it is necessary to pipeline the system within the behavior, within the loop bodies, and also within the operations. In order to hierarchically pipeline a performance-constrained system, an important step consists of distributing the performance constraint among the loops in such a manner that the constraint is satisfied and design cost is minimized. This paper presents an algorithm for propagating constraints and hierarchically pipelining a given throughput-constrained system. Along with pipelining, the algorithm schedules the operations within the loop bodies and selects components for them, with the aim of minimizing cost while satisfying the constraint propagated to the loop body. Results demonstrate the necessity of pipelining across the three granularity levels in order to obtain high performance designs. They also demonstrate the feasibility and quality of our approach, the indicate that it may be efficiently used for synthesizing or estimating within system-level design.

REFERENCES

• 1: BAKSHI,S.AND GAJSKI, D. D. 1996. Hierarchical pipelining with hardware/software partitioning. Tech. Rep. 96-38. Dept. of ICS, University of California at Irvine, Irvine, CA.
• 2: S. Bakshi , D. Gajski , H. Juan, Component selection in resource shared and pipelined DSP applications, Proceedings of the conference on European design automation, p.370-375, September 1996, Geneva, Switzerland
• 3: Lars Svensson , Francky Catthoor, Application-Driven Architecture Synthesis, Kluwer Academic Publishers, Norwell, MA, 1993
• 4: CHU, C., POTKONJAK, M., THALER, M., AND RABAEY, J. 1989. HYPER: An interactive synthesis environment for high performance real time applications. In Proceedings of the IEEE International Conference on Computer Design (Cambridge, MA). IEEE Computer Society Press, Los Alamitos, CA, 432-436.
• 5: GAJSKI,D.D.,GONG, J., VAHID, F., AND NARAYAN, S. 1993. The SpecSyn design process and human interface. Tech. Rep. 93-3. Dept. of ICS, University of California at Irvine, Irvine, CA.
• 6: GAJSKI, D., GRUN, P., PAN, W., AND BAKSHI, S. 1996. Design exploration for pipelined IDCT. Tech. Rep. 96-41. Dept. of ICS, University of California at Irvine, Irvine, CA.
• 7: GOOSSENS, G., RABAEY, J., VANDEWALLE, J., AND DE MAN, H. 1990. An efficient microcode compiler for application specific DSP processors. IEEE Trans. Comput.-Aided Des. 9,9 (Sept.), 925-937.
• 8: G. Goossens , J. Vandewlle , H. De Man, Loop optimization in register-transfer scheduling for DSP-systems, Proceedings of the 26th ACM/IEEE conference on Design automation, p.826-831, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74384]
• 9: Rajiv Jain , Alice Parker , Nohbyung Park, Module selection for pipelined synthesis, Proceedings of the 25th ACM/IEEE conference on Design automation, p.542-547, June 12-15, 1988, Atlantic City, New Jersey, United States
• 10: JAIN, R., PARKER, A., AND PARK, N. 1990. MOSP: Module selection for pipelined designs with multi-cycle operations. In Proceedings of the IEEE International Conference on Computer-Aided Design (ICCAD'90, Nov.). IEEE Computer Society Press, Los Alamitos, CA, 212-215.
• 11: H. Juan , S. Bakshi , D. Gajski, Clock optimization for high-performance pipelined design, Proceedings of the conference on European design automation, p.330-335, September 1996, Geneva, Switzerland
• 12: David W. Knapp, Behavioral synthesis: digital system design using the synopsys behavioral compiler, Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 13: LEE, T.-F., WU, A.-H., LIN, Y.-L., AND GAJSKI, D. D. 1994. A transformation-based method for loop folding. IEEE Trans. Comput.-Aided Des. 13, 4 (Apr.), 439-450.
• 14: NOTE, S., CATTHOOR, F., GOOSSENS, G., AND DE MAN, H. J. 1992. Combined hardware selection and pipelining in high-performance data-path design. IEEE Trans. Comput.-Aided Des. 11, 4, 413-423.
• 15: PAULIN,P.G.AND KNIGHT, J. P. 1989. Force-directed scheduling for the behavioral synthesis of ASICs. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 8, 6 (June), 661-679.
• 16: RAMACHANDRAN,L.AND GAJSKI, D. D. 1991. An algorithm for component selection in performance optimized scheduling. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD '91, Santa Clara, CA, Nov. 11-14). IEEE Computer Society Press, Los Alamitos, CA, 92-95.
• 17: THORDARSON, A. B. 1995. Comparison of manual and automatic behavioral synthesis on MPEG-algorithm. Master's Thesis. University of California at Irvine, Irvine, CA.
• 18: TIMMER,A.H.,HEIJLIGERS,M.J.M.,STOK, L., AND JESS, J. A. G. 1993. Module selection and scheduling using unrestricted libraries. In Proceedings of the IEEE European Conference on Design Automation (EURO-DAC '93). IEEE Computer Society Press, Los Alamitos, CA, 547-551.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids
          Subjects: Automatic synthesis

General Terms:
Algorithms, Design, Performance

Keywords:
DSP (digital signal processing) systems, component selection, hierarchical pipelining, loop pipelining, pipelined systems, scheduling