Towards an automated tupling strategy

ABSTRACT

The tupling transformation strategy can be used to merge loops together by combining recursive calls and also to eliminate redundant calls for a class of programs. The clever (and difficult) step of this transformation strategy is to find an appropriate tuple of calls, called the eureka tuple, which would allow each set of calls to be computed recursively from its previous set. In many cases, this transformation can produce super-linear speedup. In this paper, we present an analysis method which could find eureka tuples for a wide range of functional programs. Our work extends that of a number of past techniques which have used dependency graphs of function calls for analysing redundancy patterns. Our main contribution is the use of appropriate call orderings based on recursion parameters to systematically search for eureka tuples in dependency graphs. They allow us to construct sequences of tuples, called the continuous sequences of tuples, whereby the existence of a matched pair of tuples in the sequence corresponds to a suitable eureka tuple. An extension of the basic analysis method which uses trees, instead of sequences, of tuples will also be presented. The basic and extended analysis methods will be shown to be applicable to a wide range of programs. They can be guaranteed to terminate by either bounding the search or by applying suitable restrictions on the class of applicable programs. The latter approach yields a safe automated procedure for tupling transformation.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Control primitives

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Verification