Stream processing

ABSTRACT

Stream processing is a basic method of code optimization related to loop fusion that can improve the space and speed of iterative applicative expressions by a process of loop combination. It has been studied before in applications to program improvement and batch oriented database restructuring. Previous attempts at implementation have been either highly restrictive, have required manual intervention, or have involved naive strategies resulting in impractically slow running times. This paper defines a new model for a stream processing problem for handling a wide class of applicative expressions that can be evaluated by looping in an unordered way through a single set or tuple valued argument. This problem is formulated graph theoretically and shown to be NP-Hard, even in the presence of constraints. Two new efficient heuristic algorithms will be presented. The efficiency of these solutions allows stream processing to be applied dynamically as a database query optimization, and as an important component of a high level language optimizer. Our method of stream processing has been implemented and used effectively within the RAPTS transformational programming system.

REFERENCES

• 1: Allen. F. E., Cocke, John. A Catalogue of Optimizing Transformations. In Design and Optimization of Compilers, Randall Rustin, Ed.. Prentice Hall. 1971, pp. 1-30.
• 2: John Randal Allen, Dependence analysis for subscripted variables and its application to program transformations, 1983
• 3: Burge, William. An Optimizing Technique for High Level Programming Languages. Tech. Rept. Computer Science RC5834 #25271. IBM Research Center/Yorktown Heights, 1976.
• 4: R. M. Burstall , John Darlington, A Transformation System for Developing Recursive Programs, Journal of the ACM (JACM), v.24 n.1, p.44-67, Jan. 1977 [doi>10.1145/321992.321996]
• 5: Ronald Fagin , Jurg Nievergelt , Nicholas Pippenger , H. Raymond Strong, Extendible hashing—a fast access method for dynamic files, ACM Transactions on Database Systems (TODS), v.4 n.3, p.315-344, Sept. 1979 [doi>10.1145/320083.320092]
• 6: Feather, Martin S. A System for Developing Programs by Transformation. Ph.D. Th., U. of Edinburgh, Dept. of Artificial Intelligence, 1979.
• 7: Friedman, D., Wise, D. CONS should not evaluate its arguments. In Automata, Languages, and Programming. S. Michaelson and R. Milner, Ed..Edinburgh Univ. Press, Edinburgh, 1976. pp. 257-284.
• 8: Daniel P. Friedman , David S. Wise, Aspects of applicative programming for file systems (Preliminary Version), Proceedings of an ACM conference on Language design for reliable software, p.41-55, March 28-30, 1977, Raleigh, North Carolina
• 9: Garey, Michael R., Johnson, David S.. Computers and Intractability. Freeman. 1979.
• 10: Leo J. Guibas , Douglas K. Wyatt, Compilation and delayed evaluation in APL, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.1-8, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512761]
• 11: Halmos, P.R.. Naive Set Theory. Nan Nostrand, 1960.
• 12: Peter Henderson, Functional Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1980
• 13: Barron C. Housel, Pipelining: a technique for implementing data restructurers, ACM Transactions on Database Systems (TODS), v.4 n.4, p.470-492, Dec. 1979 [doi>10.1145/320107.320118]
• 14: Kennedy, K. A Survey of Compiler Optimization Techniques. In Program Flow Analysis. Muchnick, S. and Jones, N., Eds., Prentice Hall. 1981, pp. 5-54.
• 15: Kang-Sen Lu, Program optimization based on a non-procedural specification, 1981
• 16: Morgenstern. Matthew. Automated Design and Optimization of Management Information System Software. Ph.D. Th.. MIT. Laboratory for Computer Science, Sep 1976.
• 17: Mark H. Overmars, Design of Dynamic Data Structures, Springer-Verlag New York, Inc., Secaucus, NJ, 1987
• 18: Paige. R.. Formal Differentiation. UMI Research Press. Ann Arbor. Mich, 1981. Revision of Ph.D. thesis. NYU, June 1979
• 19: Robert Paige, Transformational programming: applications to algorithms and systems, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.73-87, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567076]
• 20: Paige, Robert. Applications of Finite Differencing to Database Integrity Control and Query/Transaction Optimization. In Advances In Database Theory, Volume 2. Gallaire, H.. Minker, J., and Nicolas. J.-M.. Ed.. Plenum Press, New York, 1984, pp. 171-210.
• 21: Robert Paige , Shaye Koenig, Finite Differencing of Computable Expressions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.402-454, July 1982 [doi>10.1145/357172.357177]
• 22: N. S. Prywes , Amir and S. Shastry, Use of a Nonprocedural Specification Language and Associated Program Generator in Software Development, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.2, p.196-217, Oct. 1979 [doi>10.1145/357073.357076]
• 23: Reif, J. and Scherlis, W. Deriving Efficient Graph Algorithms. Carnegie-Mellon U., 1982. Technical Report
• 24: Schwartz, J. T.. On Programming: An Interim Report on the SETL Project, Installments I and II. CIMS. New York Univ., New York. 1974.
• 25: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 26: Sharir, M. "Formal Integration - A Program Transformation Technique." Compout. Lang. 6, 1 (1982), 35-46.
• 27: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 28: Richard C. Waters, Expressional loops, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.1-10, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800511]
• 29: Weixalbaum, E. Formal Integration. unpublished manuscript

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.1 Expressions and Their Representation
          Subjects: Simplification of expressions
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Languages, Management