Skip to main content
SpringerLink
Log in

Rate-optimal schedule for multi-rate DSP computations

  • Published:
Journal of VLSI signal processing systems for signal, image and video technology Aims and scope Submit manuscript

Abstract

In this paper we present a novel framework ofmulti-rate scheduling of signal processing programs represented by regular stream flow graphs (RSFGs). The main contribution of this paper is translating the scheduling problem of RSFGs into an equivalent problem in the domain of Karp-Miller computation graphs. A distinct feature of our scheduling framework—called themulti-rate software pipelining—is to allow maximum overlapping of operations from successive iterations, subject only to precedence constraints caused by data dependences. p ]We demonstrate that the scheduling of regular stream flow graphs can be formulated as a mathematical problem by capturing data dependences between two actors as a precedence relation between the firing of these actors. Using linear schedules, the problem is further translated into a linear program formulation. An efficient solution for the linear programming problem is obtained by first constructing what is called theprecedence graph. A polynomial-time solution is obtained by observing that the optimal computation rate is theminimum cost-to-time ratio cycle (MCTRC) in the precedence graph and using the well-established solution methods for the MCTRC problem. Finally, to minimize the buffer requirement for the obtained rate-optimal schedule, a graph coloring method based on thecyclic interval graph representation has been proposed.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. E.A. Lee and D.A. Messerschmitt, “Static scheduling of synchronous data flow programs for digital signal processing,”IEEE Transactions on Computers, Vol. C36, pp. 24–35, 1987.

    Article  Google Scholar 

  2. H. Printz, “Automatic mapping of large signal processing systems to a parallel machine,” Memorandum CMU-CS-91-101 (Ph.D. Dissertation), Computer Science Department, Carnegie-Mellon University, 1991.

  3. L.-G. Jeng and L.-G. Chen, “Rate-optimal dsp synthesis by pipeline and minimum unfolding,”IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 2, pp. 81–88, 1994.

    Article  Google Scholar 

  4. K.K. Parhi and D.G. Messerschmitt, “Static rate-optimal scheduling of iterative data-flow programs via optimum unfolding,”IEEE Transactions on Computers, Vol. C-40, pp. 178–195, 1991.

    Article  Google Scholar 

  5. V. Zivojnovic and S. Ritz, “Multirate retiming: A powerful tool for hardware/software codesign,” Internal Report, ISS 802/94-1, Aachen University of Technology, Aachen, Germany, 1994.

    Google Scholar 

  6. G.R. Gao, R. Govindarajan, and P. Panangaden, “Construction rules for well-behaved stream programs,” ACAPS Technical Memo 26, School of Computer Science, McGill University, Montreal, Que., April 1992.

    Google Scholar 

  7. G.R. Gao, R. Govindarajan, and P. Panangaden, “Well-behaved dataflow programs for DSP computation,”Proc. of the 1992 Intl. Conf. on Acoustics, Speech, and Signal Processing, San Francisco, CA, pp. 561–564, 1992.

  8. E.A. Lee, “Consistency in dataflow graphs,”IEEE Transactions on Parallel and Distributed Systems, Vol. 2, pp. 223–235, 1991.

    Article  Google Scholar 

  9. J.B. Dennis, “First version of a data-flow procedure language,”Proc. of the Colloque sur la Programmation, number 19 in Lec. Notes in Comp. Sci., Springer-Verlag, pp. 362–376, 1975.

  10. A. Aiken and A. Nicolau, “Optimal loop parallelization,”Proc. of the SIGPLAN'88 Conf. on Programming Language Design and Implementation. SIGPLAN Notices, Vol. 23, 1988.

  11. M. Lam, “Software pipelining: An effective scheduling technique for VLIW machines,”Proc. of the SIGPLAN '88 Conf. on Programming Language Design and Implementation, SIGPLAN Notices, Vol. 23, pp. 318–328, Jul. 1988.

    Google Scholar 

  12. L.-F. Chao and E.H.-M. Sha, “Rate-optimal static scheduling for dsp dataflow programs,”Proc. of the 1993 Great Lakes Symposium on VLSI, pp. 80–84, 1993.

  13. A. Aiken,Compaction-Based Parallelization. Ph.D. Thesis, Cornell U., 1988. Also publ. as Tech. Rep. TR 88-922, Dept. of Computer Science.

  14. K. Ebcioğlu, “A compilation technique for software pipelining of loops with conditional jumps,”Proc. of the 20th Ann. Work. on Microprogramming, Dec. 1987.

  15. K. Ebcioğlu and A. Nicolau, “A global resource-constrained parallelization technique,”Conf. Proc., 1989 Intl. Conf. on Supercomputing, Crete, Greece, pp. 154–163, 1989.

  16. G.R. Gao, Y.-B. Wong, and Q. Ning, “A timed Petri-Net model for fine-grain loop scheduling,”Proc. of the SIGPLAN '91 Conf. on Programming Language Design and Implementation, pp. 204–218, Toronto, Ontario, Jun. 26–28, 1991, ACM SIGPLAN.SIGPLAN Notices, Vol. 26, 1991.

  17. A. Nicolau, K. Pingali, and A. Aiken, “Fine-grain compilation for pipelined machines,” Tech. Rep. TR 88-934, Dept. of Comp. Sci., Cornell U., Ithaca, N.Y., 1988.

    Google Scholar 

  18. B.R. Rau and C.D. Glaeser, “Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing,”Proc. of the 14th Ann. Microprogramming Work., Chatham, Mass., pp. 183–198, Oct. 12–15, 1981.

  19. R.F. Touzeau, “A FORTRAN compiler for the FPS-164 scientific computer,”Proc. of the SIGPLAN'84 Symp. on Compiler Construction, pp. 48–57, Montréal, Qué., Jun. 17–22, 1984.

  20. V. Van Dongen, G.R. Gao, and Q. Ning, “A polynomial time method for optimal software pipelining,”Proc. of the Conf. on Vector and Parallel Processing, CONPAR-92, pp. 613–624, Lyon, France, Sept. 1992. Also in LNCS-634.

  21. E.L. Lawler,Combinatorial Optimization: Networks and Matroids, Ft Worth, TX: Saunders College Publishing, 1976.

    MATH  Google Scholar 

  22. G.C. Sih, “Multiprocessor scheduling to account for interprocessor communication,” Memorandum, UCB/ERL M91/29 (Ph.D. Dissertation), EECS Department, University of California, Berkeley, 1991.

    Google Scholar 

  23. Q. Ning and G. Gao, “Minimizing loop storage allocation for an argument-fetching dataflow architecture model,” D. Etiemble and J.-C. Syre, editors,Proc. of PARLE '92—Parallel Architectures and Languages Europe, pp. 585–600, Paris, France, Jun. 15–18, 1992. Springer-Verlag, Lec. Notes in Comp. Sci. 605.

  24. C.V. Ramamoorthy and Gary S. Ho, “Performance evaluation of asynchronous concurrent systems using Petri nets,”IEEE Trans. on Software Eng., Vol. 6, pp. 440–449, 1980.

    Article  MathSciNet  MATH  Google Scholar 

  25. R. Reiter, “Scheduling parallel computations,”J. of the ACM, Vol. 15, pp. 590–599, 1968.

    Article  MATH  Google Scholar 

  26. G.R. Gao, Q. Ning, and V. Van Dongen, “Multi-statement multi-dimensional loop scheduling: A new-approach,” ACAPS Technical Memo 53, School of Computer Science, McGill University, Montreal, Que., Dec. 1992.

    Google Scholar 

  27. R.M. Karp, “A characterization of the minimum cycle mean in a digraph,”Discrete Mathematics, Vol. 23, pp. 309–311, 1978.

    Article  MathSciNet  MATH  Google Scholar 

  28. G.J. Chaitin, M. Auslander, A. Chandra, J. Cocke, M. Hopkins, and P. Markstein, “Register allocation via coloring,”Computer Languages, Vol. 6, pp. 47–57, 1981.

    Article  Google Scholar 

  29. G.J. Chaitin, “Register allocation and spilling via graph coloring,”Proc. of the ACM SIGPLAN Symp. on Compiler Construction, pp. 98–105, 1982.

  30. L.J. Hendren, G.R. Gao, E.R. Altman, and C. Mukerji, “A register allocation framework based on hierarchical cyclic interval graphs.” U. Kastens and P. Pfahler, editors,Proc. of the Intl. Conf. on Compiler Construction, number 641 in Lec. Notes in Comp. Sci., Springer-Verlag, pp. 176–191, Oct. 1992.

  31. Q. Ning and G.R. Gao, “Optimal memory allocation for argument fetching dataflow machines,” ACAPS Tech. Memo 32, Sch. of Comp. Sci., McGill U., Montréal, Qué., Jan. 1992.

    Google Scholar 

  32. Q. Ning and G. R. Gao, “A novel framework of register allocation for software pipelining,”Conf. Rec. of the Twentieth Ann. ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, Charleston, pp. 29–42, South Carolina, Jan. 10–13, 1993.

  33. P.N. Hilfinger, “Silage reference manual, DRAFT release 2.0,” Technical report, EECS Dept., University of California, Berkeley, July 1989.

    Google Scholar 

  34. E.A. Lee, W.-H. Ho, E. Geoi, J. Bier, and Bhattacharyya, “Gabriel: A design environment for DSP,”IEEE Transactions on Acoustics, Speech, Signal Processing, Nov. 1989.

  35. S. Ha and E.A. Lee, “Compile-time scheduling and assignment of data-flow program graphs with data-dependent iteration,”IEEE Transactions on Computers, Vol. C40, pp. 1225–1238, 1991.

    Article  Google Scholar 

  36. M. Cubric and P. Panangaden, “Minimal memory schedules for data flow networks,” E. Best, editor,Proc. of the 4th Intl. Conf. on Concurrency Theory, August 1993. Lecture Notes in Computer Science 715.

  37. C.E. Leiserson, F. Rose, and J. Saxe, “Optimizing synchronous circuitry by retiming,”Proc. of the Third Caltech Conference on VLSI, Pasadena, C.A., pp. 87–116, March 1983.

  38. L.E. Lucke and K.K. Parhi, “Generalized ILP scheduling and allocation for high-level DSP synthesis,”Proc. of the 1993 IEEE Custom Integrated Circuits Conf., 1993.

  39. L. Thiele, “Resource constrained scheduling of uniform algorithms,”Proc. of the Intl. Conf. on Application Specific Array Processors, Venice, Italy, pp. 29–40, Oct. 1993.

  40. P.D. Hoang, “Compiling real-time digital signal processing applications onto multiprocessor systems,” Memorandum UCB/ERL M92/68 (Ph.D. Dissertation), College of Engineering, University of California, Berkeley, 1992.

    Google Scholar 

  41. D.B. Powell, E.A. Lee, and W.C. Newmann, “Direct synthesis of optimized DSP assembly code from signal flow block diagrams,”Proc. of the 1992 Conf. on Acoustics, Speech, and Signal Processing, San Francisco, 1992.

  42. S. Ritz, M. Pankert, and H. Meyr, “High level software synthesis for signal processing systems”Proc. of the 1992 Conf. on Application Specific Array Processors, San Francisco, 1992.

  43. R.B. Jones and V.H. Allan, “Software pipelining: An evaluation of enhanced pipelining,”Proc. of the 24th Intl. Workshop on Microprogramming and Microarchitectures, pp. 82–92, 1991.

Download references

Author information

Author notes

  1. R. Govindarajan

    Present address: Department of Computer Science, Memorial University of Newfoundland, A1B 3X5, St. John's, Canada

Authors and Affiliations

  1. Department of Electrical Engineering, McGill University, H3A 2A7, Montreal, Canada

    R. Govindarajan

  2. School of Computer Science, McGill University, H3A 2A7, Montreal, Canada

    Guang R. Gao

Authors
  1. R. Govindarajan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Guang R. Gao
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Govindarajan, R., Gao, G.R. Rate-optimal schedule for multi-rate DSP computations. Journal of VLSI Signal Processing 9, 211–232 (1995). https://doi.org/10.1007/BF02407086

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02407086

Keywords

Search

Navigation