High-level loop fusion

Details High-level loop fusion High-level loop fusion

1996-12-06

1998-10-13

Voel, Emanuel Todd

395705, 395710, 395704, G06F 944

Patent

active

058225935

ABSTRACT:
A processor is provided with a software program specifying an overall computation that includes operations. Each operation implies a set of subcomputations, without explicitly specifying a control structure for carrying out the subcomputations according to a particular sequencing. The operations include a first and a second operation, and the provided software program further specifies how the first and second operations are combined in the overall computation. For example, the first and second operations can each imply, respectively, a first and a second computational loop, the first loop including the subcomputations of the first operation, the second loop including the subcomputations of the second operation. A description of possible sequencings of subcomputations of the first and second operations is provided, to be used in implementing the specified combination of the first and second operations, the description including a set of constraints on the sequencing of subcomputations of the first and second operations. A software program is automatically generated that includes a combined operation implementing the specified combination of the first and second operations. The combined operation has a control structure for carrying out the subcomputations of the first and second operations in accordance with the constraints. This control structure can be, for example, a computational loop. If the first and second operations imply, respectively, first and second computational loops, the control structure of the combined operation can be, for example, a computational loop including a fusion of the first and second loops.

REFERENCES:
patent: 5392130 (1995-02-01), Mahoney
patent: 5448737 (1995-09-01), Burke et al.
patent: 5455898 (1995-10-01), Mahoney et al.
patent: 5457799 (1995-10-01), Srivastava
patent: 5491823 (1996-02-01), Ruttenberg
patent: 5522022 (1996-05-01), Rao et al.
patent: 5606698 (1997-02-01), Powell
patent: 5655122 (1997-08-01), Wu
patent: 5704053 (1997-12-01), Santhanam
Jeffrey D. Ullman, Principles of Database Systems, Computer Science Press, 1980, chapter 6.
Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman, Compilers: Principles, Techniques and Tools, Addison-Wesley, 1986, chapter 10.
D. F. Bacon, S. L. Graham, and O. J. Sharp, "Compiler Transformations for High-Performance Computing," ACM Computing Surveys, vol. 26, No. 4, Dec. 1994, pp. 345-420.
Francoise Bellegarde, "Rewriting Systems on FP Expressions that Reduce the Number of Sequences They Yield", Conference Record of the 1984 ACM Symposium on Lisp and Functional Programming, Austin, Texas, Aug. 6-8, 1984, pp. 63-73.
Shigeru Chiba, "A Metaobject Protocol for C++," OOPSLA '95 Proceedings (ACM), pp. 285-299.
Philip Wadler, "Deforestation: Transforming Programs to Eliminate Trees", in Proceedings of the European Symposium on Programming (H. Ganzinger, ed.; vol. 300 of the series Lecture Notes in Computer Science), Springer-Verlag, 1988, pp. 344-358.
Clifford Walinsky and Deb Banerjee, "A Functional Programming Language Compiler for Massively Parallel Computers", in Proceedings of the 1990 ACM Conference on Lisp and Functional Programming, Nice, France, Jun. 27-29, 1990, pp. 131-138.
Nils J. Nilsson, Principles of Artificial Intelligence, Tioga Publishing Co., 1980, pp. 140-145.
R. C. Waters, "Automatic Transformation of Series Expressions into Loops", ACM Transactions on Programming Languages and Systems, vol. 13, No. 1, Jan. 1991, pp. 52-98.
"Aspect-Oriented Programming"(home page), available on the World Wide Web at http://www.parc.xerox.com/spl/projects/aop.
"A Very Short Position Paper on Aspect-Oriented Programming," available on the World Wide Web at http://www.parc.xerox.com/spl/projects/aop/short-position.htm.
G. Kiczales et al., "Aspect-Oriented Programming: A Position Paper from the Xerox PARC Aspect-Oriented Programming Project," available on the World Wide Web at http://www.parc.xerox.com/spl/projects/aop/position.htm.

Affiliated with

Also associated with

Rating

High-level loop fusion does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with High-level loop fusion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High-level loop fusion will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-325045