Framework for efficient code generation using loop peeling...

Details Framework for efficient code generation using loop peeling... Framework for efficient code generation using loop peeling...

2008-07-01

2008-07-01

Bullock, Jr., Lewis A. (Department: 2193)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S150000, C717S151000, C717S159000, C717S161000, C712S022000, C712S241000

Reexamination Certificate

active

10918879

ABSTRACT:
A system and method is provided for vectorizing misaligned references in compiled code for SIMD architectures that support only aligned loads and stores. In this framework, a loop is first simdized as if the memory unit imposes no alignment constraints. The compiler then inserts data reorganization operations to satisfy the actual alignment requirements of the hardware. Finally, the code generation algorithm generates SIMD codes based on the data reorganization graph, addressing realistic issues such as runtime alignments, unknown loop bounds, residual iteration counts, and multiple statements with arbitrary alignment combinations. Loop peeling is used to reduce the computational overhead associated with misaligned data. A loop prologue and epilogue are peeled from individual iterations in the simdized loop, and vector-splicing instructions are applied to the peeled iterations, while the steady-state loop body incurs no additional computational overhead.

REFERENCES:
patent: 4710872 (1987-12-01), Scarborough
patent: 5247645 (1993-09-01), Mirza et al.
patent: 5349665 (1994-09-01), Endo
patent: 5440687 (1995-08-01), Coleman et al.
patent: 5481746 (1996-01-01), Schiffleger et al.
patent: 5522074 (1996-05-01), Endo
patent: 5802375 (1998-09-01), Ngo et al.
patent: 5933650 (1999-08-01), van Hook et al.
patent: 5996057 (1999-11-01), Scales, III et al.
patent: 6113650 (2000-09-01), Sakai
patent: 6202141 (2001-03-01), Diefendorff et al.
patent: 6266758 (2001-07-01), van Hook et al.
patent: 6334176 (2001-12-01), Scales, III et al.
patent: 6484255 (2002-11-01), Dulong
patent: 6550059 (2003-04-01), Choe et al.
patent: 7020873 (2006-03-01), Bik et al.
patent: 7168069 (2007-01-01), Sigmund
patent: 7219212 (2007-05-01), Sanghavi et al.
patent: 7275147 (2007-09-01), Tavares
patent: 2003/0120889 (2003-06-01), Roussel et al.
patent: 2003/0167460 (2003-09-01), Desai et al.
patent: 2003/0204840 (2003-10-01), Wu
patent: 2004/0001066 (2004-01-01), Bik et al.
patent: 2004/0003381 (2004-01-01), Suzuki et al.
patent: 2004/0006667 (2004-01-01), Bik et al.
patent: 2004/0025150 (2004-02-01), Heishi et al.
patent: 2004/0098709 (2004-05-01), Kyo
patent: 2005/0097301 (2005-05-01), Ben-David et al.
patent: 2005/0289529 (2005-12-01), Almog et al.
Lee et al., “Simple Vector Microprocessors for Multimedia Applications,”Preceedings of the 31stAnnual International Symposium on Microarchitecture, Dec. 1998 (12 pages).
Cheong et al., “An Optimizer for Multimedia Instruction Sets,” Stanford University, Aug. 14, 1997.
Krall et al., “Compilation Techniques for Multimedia Processors,” 14 pages.
Sreraman et al., “A Vectorizing Compiler for Multimedia Extensions,”International Journal of Parallel Programming, 2000 (40 pages).
Bik et al., “Automatic Intra-Register Vectorizatoin for the Intel Architecture,”International Journal of Parallel Programming, vol. 30, No. 2, Apr. 2002 (p. 65-98).
O'Brien, “Predictive Commoning: A method of optimizing loops containing references to consecutive array elements,” 12 pages.
Larsen et al., “Increasing and Detecting Memory Address Congruence,”Proceedings of 11thInternational Conference on Parallel Architectures and Compilation Techniques, Sep. 2002, 11 pages.
Naishlos, “Vectorizing for a SIMdD DSP Architecture,” Cases '03, Oct. 30-Nov. 1, 2003,ACM, pp. 2-11.
Shin et al., “Compiler-Controlled Caching in Superword Register Files for Multimedia Extension Architectures,” 11 pages.
Ren et al., “A Preliminary Study on the Vectorization of Multimedia Applications for Multimedia Extensions,” 15 pages.
Eichenberger et al., Vectorization for SIMD Architectures with Alignment Constraints,PLDI'04, Jun. 9-11, 2004, p. 82-93.
Chatterjee et al., “Modeling Data-Parallel Programs with the Alignment-Distribution Graph,”6thAnnual Workshop on Languages and Compilers for Parallelism, Aug. 1993, 28 pages.
Allen et al., “Automatic Translation of Fortran Programs to Vector Form,”ACM Transactions on Programming Languages and Systems, v. 9, No. 4, Oct. 1987, p. 491-542.
AltiVec™ Technology Programming Interface Manuel, 1999, 262 pages.
Arafeh et al., “Vectorization and Parallelization Interactive Assistant,” 1988, ACM 0-89791-260-8/88/0002/0573, pp. 573-577.
McKenney et al., “Generating Parallel Code for SIMD Machines,” ACM Letters on Programming Languages and Systems, vol. 1, No. 1, Jan. 1992, pp. 59-73.
Pajuelo et al., “Speculative Dynamic Vectorization,” 2002, IEEE 1063-6897/02, pp. 271-280.
Naishlos et al., “Vectorizing for a SIMdD DSP Architecture,” CASES '03, Oct. 30-Nov. 1, 2003, ACM 1-58113-676-5/03/0010, pp. 2-11.
Scarborough et al., “A Vectorizing Fortran Compiler,” Mar. 1986, IBM Journal of Research and Development, vol. 30, Issue 2, pp. 163-171.
Levine et al., “A Comparative Study of Automatic Vectorizing Compilers,” 1991, Parallel Computing, vol. 17.
Cukic et al., “Automatic Array Alignment as a Step in Hierarchical Program Transformation,” Apr. 1994, Proceedings of the Eighth International Parallel Processing Symposium.
Lee et al., “Automatic Data and Computation Decomposition on Distributed Memory Parallel Computers,” Jan. 2002, ACM Transactions on Programming Languages and Systems, vol. 24, No. 1, pp. 1-50.

Affiliated with

Also associated with

Rating

Framework for efficient code generation using loop peeling... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Framework for efficient code generation using loop peeling..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Framework for efficient code generation using loop peeling... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3925682