Mode grouping for more effective generalized scheduling of dynamic dataflow applications

ABSTRACT

For a number of years, dataflow concepts have provided designers of digital signal processing systems with environments capable of expressing high-level software architectures as well as low-level, performance-oriented kernels. To apply these proven techniques to new complex, dynamic applications, we identify repetitive sequences of atomic, repeatable actions ("modes") inside dynamic actors to expose more of the static nature of the application. In this work, we propose a mode grouping strategy that aids in the decomposition of a dynamic dataflow graph into a set of static dataflow graphs that interact dynamically. Mode grouping enables the discovery of larger static subgraphs improving scheduling results. We show that grouping modes results in improved schedules with lower memory requirements for implementations by up to 37% including a common imaging benchmark with dynamic behavior: 3D B-spline interpolation.

REFERENCES

• 1: S. S. Bhattacharyya, P. K. Murthy, and E. A. Lee. Software Synthesis from Dataflow Graphs. Kluwer Academic Publishers, 1996.
• 2: J. Eker, J. Janneck, E. A. Lee, J. Liu, X. Liu, J. Ludvig, S. Neuendorffer, S. R. Sachs, and Y. Xiong. Taming heterogeneity - the Ptolemy approach. Proceedings of the IEEE, Special Issue on Modeling and Design of Embedded Software, 91(1):127--144, January 2003.
• 3: C. Hsu, I. Corretjer, M. Ko., W. Plishker, and S. S. Bhattacharyya. Dataflow interchange format: Language reference for DIF language version 1.0, userŠs guide for DIF package version 1.0. Technical Report UMIACS-TR-2007-32, Institute for Advanced Computer Studies, University of Maryland at College Park, June 2007. Also Computer Science Technical Report CS-TR-4871.
• 4: B. Kienhuis and E. F. Deprettere. Modeling stream-based applications using the SBF model of computation. In Proceedings of the IEEE Workshop on Signal Processing Systems, pages 385--394, September 2001.
• 5: M. Ko, C. Zissulescu, S. Puthenpurayil, S. S. Bhattacharyya, B. Kienhuis, and E. Deprettere. Parameterized looped schedules for compact representation of execution sequences. In Proceedings of the International Conference on Application Specific Systems, Architectures, and Processors, pages 223--230, Steamboat Springs, Colorado, September 2006.
• 6: E. A. Lee and D. G. Messerschmitt. Static scheduling of synchronous dataflow programs for digital signal processing. IEEE Transactions on Computers, February 1987.
• 7: W. Plishker, N. Sane, and S. S. Bhattacharyya. A generalized scheduling approach for dynamic dataflow applications. In Proceedings of the Design, Automation and Test in Europe Conference and Exhibition, Nice, France, April 2009. 6 pages in electronic proceedings.
• 8: W. Plishker, N. Sane, M. Kiemb, K. Anand, and S. S. Bhattacharyya. Functional DIF for rapid prototyping. In Proceedings of the International Symposium on Rapid System Prototyping, pages 17--23, Monterey, California, June 2008.
• 9: S. Sriram and S. S. Bhattacharyya. Embedded Multiprocessors: Scheduling and Synchronization. Marcel Dekker, Inc., 2000.
• 10: M. H. Wiggers, M. J. G. Bekooij, and G. J. M. Smit. Computation of buffer capacities for throughput constrained and data dependent inter-task communication. In DATE '08: Proceedings of the conference on Design, automation and test in Europe, pages 640--645, New York, NY, USA, 2008. ACM.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management

General Terms:
Algorithms, Management

Keywords:
dataflow, mode grouping, scheduling