Methods and products for processing loop nests

Details Methods and products for processing loop nests Methods and products for processing loop nests

2004-09-20

2009-12-08

Mitchell, Jason (Department: 2193)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S152000, C717S153000, C717S160000

Reexamination Certificate

active

07631305

ABSTRACT:
Methods and products for processing a software kernel of instructions are disclosed. The software kernel has stages representing a loop nest. The software kernel is processed by partitioning iterations of an outermost loop into groups with each group representing iterations of the outermost loop, running the software kernel and rotating a register file for each stage of the software kernel preceding an innermost loop to generate code to prepare for filling and executing instructions in software pipelines for a current group, running the software kernel for each stage of the software kernel in the innermost loop to generate code to fill the software pipelines for the current group with the register file being rotated after at least one run of the software kernel for the innermost loop, and repeatedly running the software kernel to unroll inner loops to generate code to further fill the software pipelines for the current group.

REFERENCES:
patent: 5802375 (1998-09-01), Ngo et al.
patent: 5958048 (1999-09-01), Babaian et al.
patent: 6182210 (2001-01-01), Akkary et al.
patent: 6192515 (2001-02-01), Doshi et al.
patent: 6230317 (2001-05-01), Wu
patent: 6438747 (2002-08-01), Schreiber et al.
patent: 6820250 (2004-11-01), Muthukumar et al.
patent: 6957304 (2005-10-01), Wilkerson
patent: 2002/0055964 (2002-05-01), Luk et al.
patent: 1294345 (2001-05-01), None
Unger, A., Zehendner, E., and Ungerer, T. 2000. A combined compiler and architecture technique to control multithreaded execution of branches and loop iterations. SIGARCH Comput. Archit. News 28, 1 (Mar. 2000), 53-61. DOI=http://doi.acm.org/10.1145/346023.346044.
Tzi-Cker Chiueh, Multi-Threaded Vectorization, Computer Architecture News, Association for Computing Machinery, vol. 19, No. 3, May 1, 1991, pp. 352-361.
International Search Report for PCT International Application No. PCT/US2004/030634 mailed Aug. 31, 2005.
A. Aiken and A. Nicolau, Fine-grain parallelization and the wavefront method, Languages and Compilers for Parallel Computing, MIT Press, 1990, pp. 1-16.
A. Aiken, A. Nicolau and S. Novack, Resource-constrained software pipelining, IEEE Transactions on Parallel and Distributed Systems, 6(12):1248-1270, Dec. 1995.
V. H. Allan, R. B. Jones, R. M. Lee and S. J. Allan, Software pipelining, ACM Computing Surveys, 27(3):367-432, Sep. 1995.
S. Carr, C. Ding and P. Sweany, Improving software pipelining with unroll-and-jam, In Proc. 29thAnnual Hawaii International Conference on Systems Sciences, pp. 183-192, 1996.
S. Carr and K. Kennedy, Improving the ratio of memory operations to floating-point operations in loops, ACM Trans. on Programming Languages and Systems, 16(6):1768-1810, Nov. 1994.
A. Darte and Y. Roberts, Constructive methods for scheduling uniform loop nests, IEEE Transactions on Parallel and Distributed Systems, 5(8):814-822, Aug. 1994.
G. R. Gao, Q. Ning and V. Van Dongen, Software pipelining for nested loops, ACAPS Tech. Memo 53, Sch. of Comp. Sci., McGill U., Montreal, Quebec, May 1993.
R. Govindarajan, E. R. Altman and G. R. Gao, A framework for resource-constrained rate-optimal software pipelining, IEEE Trans. on Parallel and Distrib. Systems, 7(11):1133-1149, Nov. 1996.
R. A. Huff, Lifetime-sensitive modulo scheduling, In Proc. of the ACM SIGPLAN '93 Conf. on Programming Language Design and Implementation, pp. 258-267, Albuquerque, New Mexico, Jun. 1993.
M. Lam, Software pipelining: An effective scheduling technique for VLIW machines, In Proc. of the SIGPLAN '88 Conf. on Programming Language Design and Implementation, pp. 318-328, Atlanta, Georgia, Jun. 1988.
L. Lamport, The parallel execution of DO loops, Comm. of the ACM, 17(2):83-93, Feb. 1974.
S. -M. Moon and K. Ebcioglu, Parallelizing nonnumerical code with selective scheduling and software pipelining, ACM Transactions on Programming Languages and Systems, 19(6):853-898, Nov. 1997.
K. Muthukumar and G. Doski, Software pipelining of nested loops, Lecture Notes in Computer Science, 2027:165-??, 2001.
D. Petkov, R. Harr and S. Amarasinghe, Efficient pipelining of nested loops: unroll-and-squash, In 16thInternational Parallel and Distributed Processing Symposium (IPDPS '02 (IPPS and SPDP)), pp. 19-29, Washington—Brussels—Tokyo, Apr. 2002, IEEE.
J. Ramanujam, Optimal software pipelining of nested loops, In Proc. of the 8thIntl. Parallel Processing Symp., pp. 335-342, Cancun, Mexico, Apr. 1994, IEEE Comp. Soc.
B. R. Rau, Iterative modulo scheduling: An algorithm for software pipelining loops, In Proc. of the 27thAnn. Intl. Symp. on Microarchitecture, pp. 63-74, San Jose, Calif., Nov.-Dec. 1994.
B. R. Rau and J. A. Fisher, Instruction-level parallel processing: History, overview and perspective, J. of Supercomputing, 7:9-50, May 1993.
H. Rong, Software Pipelining of Loop Nests, PhD thesis, Tsinghua University, Beijing, China, 2001.
J. Wang and G. R. Gao, Pipelining-dovetailing: A transformation to enhance software pipelining for nested loops, In Proc. of the 6thIntl. Conf. on Compiler Construction, Lec. Notes in Comp. Sci., pp. 1-17, Linkoping, Sweden, Apr. 1996.
M. E. Wolf and M. S. Lam, A data locality optimizing algorithm, In Proc. of the ACM SIGPLAN '91 Conf. on Programming Language Design and Implementation, pp. 30-44, Toronto, Canada, Jun. 1991.
M. E. Wolf, D. E. Maydan and D.-K. Chen, Combining loop transformations considering caches and scheduling, In Proc. of the 29thAnn. Intl. Symp. on Microarchitecture, pp. 274-286, Paris, Dec. 1996.

Affiliated with

Also associated with

Rating

Methods and products for processing loop nests does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Methods and products for processing loop nests, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and products for processing loop nests will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4149211