Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Efficient Block Scheduling to Minimize Context Switching Time for Programmable Embedded Processors

  • Published:
Design Automation for Embedded Systems Aims and scope Submit manuscript

Abstract

Scheduling is one of the most often addressed optimization problems in DSP compilation, behavioral synthesis, and system-level synthesis research. With the rapid pace of changes in modern DSP applications requirements and implementation technologies, however, new types of scheduling challenges arise. This paper is concerned with the problem of scheduling blocks of computations in order to optimize the efficiency of their execution on programmable embedded systems under a realistic timing model of their processors. We describe an effective scheme for scheduling the blocks of any computation on a given system architecture and with a specified algorithm implementing each block. We also present algorithmic techniques for performing optimal block scheduling simultaneously with optimal architecture and algorithm selection. Our techniques address the block scheduling problem for both single- and multiple-processor system platforms and for a variety of optimization objectives including throughput, cost, and power dissipation. We demonstrate the practical effectiveness of our techniques on numerous designs and synthetic examples.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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. S. S. Bhattacharyya, P. K. Murthy, and E. A. Lee. Optimal parenthesization of lexical orderings for DSP block diagrams. VLSI Signal Processing Workshop, pp. 177-186, 1995.

  2. S. S. Bhattacharyya, J. T. Buck, S. Ha, and E. A. Lee. Generating compact code from dataflow specifications of multirate signal processing algorithms. IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications 42(3): 138-50, 1995.

    Google Scholar 

  3. S. S. Bhattacharyya, P. K. Murthy, and E. A. Lee. APGAN and RPMC: Complementary heuristics for translating DSP block diagrams into efficient software implementations. Design Automation for Embedded Systems 2(1): 33-60, 1997.

    Google Scholar 

  4. A. P. Chandrakasan, S. Sheng, and R. W. Broderson. Low power CMOS digital design. IEEE Journal of Solid-State Circuits 27(4): 473-484, 1992.

    Google Scholar 

  5. S. Chaudhuri and R. A. Walker. Computing lower bounds on functional units before scheduling. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 4(2): 273-9, 1996.

    Google Scholar 

  6. P. Chou and G. Borriello. Software scheduling in the co-synthesis of reactive real-time systems. Design Automation Conference, pp. 1-4, 1994.

  7. G. De Micheli. Synthesis and Optimization of Digital Circuits. McGraw-Hill, New York, NY, 1994.

    Google Scholar 

  8. M. Feuer and C. C. Koo. Method for rechaining shift register latches which contain more than one physical book. IBM Technical Disclosure Bulletin 25(9): 4818-4820, 1983.

    Google Scholar 

  9. M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., 1979.

  10. M. J. Gonzales. Deterministic processor scheduling. ACM Computing Surveys 9(3): 173-204, 1977.

    Google Scholar 

  11. R. Jain, A. Mujumdar, and A. Sharma. Empirical evaluation of some high-level synthesis scheduling heuristics. Design Automation Conference, pp. 686-689, 1991.

  12. D. S. Johnson. Local optimization and the traveling salesman problem. In Proceedings of the 17th Intl. Colloquium on Automata, Languages and Programming, pp. 446-460, 1990.

  13. R. Jonker and T. Volgenant. Transforming asymmetric into symmetric traveling salesman problems. Operations Research Letters 2(4), 1983.

  14. P.-C. Kanellakis and C. H. Papadimitriou. Local search for asymmetric traveling salesman problem. Operations Research 28: 1086-1099, 1980.

    Google Scholar 

  15. S. Kirkpatrick, C. Gelatt, and M. Vecchi. Optimization by simulated annealing. Science 220(4598): 671-680, 1983.

    Google Scholar 

  16. K. N. Lalgudi, M. C. Papaefthymiou, and M. Potkonjak. Optimizing systems for effective block-processing: The k-delay problem. Design Automation Conference, pp. 714-719, 1996.

  17. E. L. Lawler, J. K. Lenstra, A. Rinnooy-Kan, and D. Shmoys. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, Chichester, 1985.

    Google Scholar 

  18. E. A. Lee and T. M. Parks. Dataflow process networks. Proceedings of the IEEE 83(5): 773-801, 1995.

    Google Scholar 

  19. C. Lee, M. Potkonjak, and W. Wolf. System-level synthesis of application specific systems using A* search and generalized force-directed heuristics. International Symposium on System Synthesis, pp. 2-7, 1996.

  20. S. Lin and B.W. Kernighan. An effective heuristics algorithm for the traveling-salesman problem. Operations Research 31: 498-516, 1973.

    Google Scholar 

  21. C. L. Liu and J.W. Layland. Scheduling algorithms for multiprogramming in a hard real time environment. Journal of the ACM 20(1): 46-61, 1973.

    Google Scholar 

  22. O. Martin, S. W. Otto, and E. W. Felten. Large-step Markov chains for the TSP incorporating local search heuristics. Operations Research Letters 11(4): 219-224, 1992.

    Google Scholar 

  23. M. C. McFarland, A. C. Parker, and R. Camposano. The high-level synthesis of digital systems. Proceedings of the IEEE 78(2): 301-317, 1990.

    Google Scholar 

  24. D. L. Miller and J. K. Pekny. Exact solution of large asymmetric traveling salesman problems. Science 251: 754-761, 1991.

    Google Scholar 

  25. P. K. Murthy, S. S. Bhattacharyya, and E. A. Lee. Joint minimization of code and data for synchronous dataflow programs. Formal Methods in System Design 11(1): 41-70, 1997.

    Google Scholar 

  26. P. G. Paulin and J. P. Knight. Force-directed scheduling for the behavioral synthesis of ASICs. IEEE Transactions on CAD 8(6): 661-679, 1989.

    Google Scholar 

  27. M. Potkonjak and J. Rabaey. Algorithm selection: A quantitative computation-intensive optimization approach. International Conference on Computer-Aided Design, pp. 90-95, 1994.

  28. M. Potkonjak and J. Rabaey. Optimizing resource utilization using transformations. IEEE Transformations on CAD 13(3): 277-292, 1994

    Google Scholar 

  29. M. Potkonjak and W. Wolf. Cost optimization in ASIC implementation of periodic hard-real time systems using behavioral synthesis techniques. International Conference on Computer-Aided Design, pp. 446-451, 1995.

  30. K. Ramamritham and J. A. Stankovic. Scheduling algorithms and operating systems support for real-time systems. Proceedings of the IEEE 82(1): 55-67, 1994.

    Google Scholar 

  31. G. Reinelt. Fast heuristics for large geometric traveling salesman problems. ORSA Journal on Computing 4(2): 206-217, 1992.

    Google Scholar 

  32. A. Sharma and R. Jain. Estimating architectural resources and performance for high-level synthesis applications. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 1(2): 175-90, 1993.

    Google Scholar 

  33. W. F. J. Verhaegh, P. E. R. Lippens, E. H. L. Aarts, J. H. M. Korst, J. L. van Meergergen, and A. van der Werf. Improved force-directed scheduling in high-throughput digital signal processing. IEEE Transactions on CAD 14(8): 945-960, 1995.

    Google Scholar 

  34. V. Zivojnovic, S. Ritz, and H. Meyr. Retiming of DSP programs for optimum vectorization. International Conference on Acoustic, Speech, and Signal Processing 2: 465-468, 1994.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, University of California, Los Angeles

    Inki Hong & Miodrag Potkonjak

  2. EECS Department, University of Michigan, Ann Arbor

    Marios Papaefthymiou

Authors
  1. Inki Hong
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Miodrag Potkonjak
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Marios Papaefthymiou
    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

Hong, I., Potkonjak, M. & Papaefthymiou, M. Efficient Block Scheduling to Minimize Context Switching Time for Programmable Embedded Processors. Design Automation for Embedded Systems 4, 311–327 (1999). https://doi.org/10.1023/A:1008921705476

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1008921705476

Search

Navigation