A partial evaluator for data flow graphs

ABSTRACT

It has been shown that control flow decisions often reduce the amount of fine-grain, or instruction-level parallelism in many computations. There exists various architectural solutions to this problem, such as branch prediction and speculative execution. Here we present an alternative solution, based on the use of partial evaluation for statically increasing the parallelism of a computation. In particular we explore the capability of a partial evaluator to remove control flow decisions. A partial evaluator is described, which specializes data flow graphs produced by a compiler for a fine-grained processor array. The data flow graphs can be viewed as the equivalent of a machine-code program for conventional processor, and consequently some aspects of the architecture can be taken into account by the partial evaluator. Results from the use of the partial evaluator show that it can significantly improve the performance of a computation. The performance improvement is partly due to improved parallelism, but mostly due to a reduce dynamic instruction count, i.e. a reduction in the number of operations executed.

REFERENCES

• BW90: Andrew Berlin , Daniel Weise, Compiling Scientific Code Using Partial Evaluation, Computer, v.23 n.12, p.25-37, December 1990 [doi>10.1109/2.62091]
• CP90: David E. Culler , Gregory M. Papadopoulos, The explicit token store, Journal of Parallel and Distributed Computing, v.10 n.4, p.289-308, Dec. 1990 [doi>10.1016/0743-7315(90)90031-J]
• CSS+91: David E. Culler , Anurag Sah , Klaus E. Schauser , Thorsten von Eicken , John Wawrzynek, Fine-grain parallelism with minimal hardware support: a compiler-controlled threaded abstract machine, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.164-175, April 08-11, 1991, Santa Clara, California, United States
• Jon87: Nell D. Jones. Automatic Program Specialization: A Reexamination From Basic Principles. In A.P. Ershov D. BjOrner and N.D. Jones, editors, Partial Evaluation and Mixed Computation, pages 225-282. Elsevier Science Publishers B.V. (North-Holland), October 1987.
• Kun88: S. Y. Kung, VLSI array processors, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• Lis91: Björn Lisper, Detecting static algorithms by partial evaluation, ACM SIGPLAN Notices, v.26 n.9, p.31-42, Sept. 1991
• LW92: Monica S. Lam , Robert P. Wilson, Limits of control flow on parallelism, Proceedings of the 19th annual international symposium on Computer architecture, p.46-57, May 19-21, 1992, Queensland, Australia
• RP89: A. Rogers , K. Pingali, Process decomposition through locality of reference, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.69-80, June 19-23, 1989, Portland, Oregon, United States
• Ses87: Peter Sestoft. Automatic Call Unfolding in a Partial Evaluator. In A.P. Ershov D. Bjerner and N.D. Jones, editors, Partial Evaluation and Mixed Computation, pages 485-506. Elsevier Science Publishers B.V. (North-Holland), October 1987.
• Vas92: Jonas Vasell. Three Specialized Computer Architectures for Functional Program Execution. PhD thesis, Dept. of Computer Engineering, Chalmers University of Technology, S-412 96 GSteborg, Sweden, September 1992.
• VV91a: Jonas Vasell and Jesper Vasell. A Functional Programming Technique for Programmable Wavefront Arrays. In E.F. Deprettere, editor, Algorithms and Parallel VLSI Architectures, volume B, pages 283-292. Elsevier Science Publishers B.V., Amsterdam, The Netherlands, 1991.
• VV91b: Jonas Vasell , Jesper Vasell, The function processor: an architecture for efficient execution of recursive functions, Proceedings on Parallel architectures and languages Europe : volume I: parallel architectures and algorithms: volume I: parallel architectures and algorithms, p.101-118, June 1991, Eindhoven, The Netherlands
• VV92: Jesper Vasell , Jonas Vasell, The Function Processor: a data-driven processor array for irregular computations, Future Generation Computer Systems, v.8 n.4, p.321-335, Sept. 1992 [doi>10.1016/0167-739X(92)90066-K]
• Wal91: David W. Wall, Limits of instruction-level parallelism, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.176-188, April 08-11, 1991, Santa Clara, California, United States
• WCRS91: Daniel Weise , Roland Conybeare , Erik Ruf , Scott Seligman, Automatic online partial evaluation, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.165-191, June 1991, Cambridge, Massachusetts, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Data-flow architectures

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Compilers

General Terms:
Design, Performance