Framework for integrated intra- and inter-loop aggregation...

Details Framework for integrated intra- and inter-loop aggregation... Framework for integrated intra- and inter-loop aggregation...

2007-09-17

2011-11-08

Zhen, Wei (Department: 2191)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S151000, C717S152000, C717S159000, C708S650000, C712S022000

Reexamination Certificate

active

08056069

ABSTRACT:
A method, computer program product, and information handling system for generating loop code to execute on Single-Instruction Multiple-Datapath (SIMD) architectures, where the loop contains multiple non-stride-one memory accesses that operate over a contiguous stream of memory is disclosed. A preferred embodiment identifies groups of isomorphic statements within a loop body where the isomorphic statements operate over a contiguous stream of memory over the iteration of the loop. Those identified statements are then converted into virtual-length vector operations. Next, the hardware's available vector length is used to determine a number of virtual-length vectors to aggregate into a single vector operation for each iteration of the loop. Finally, the aggregated, vectorized loop code is converted into SIMD operations.

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/0273769 (2005-12-01), Eichenberger et al.
patent: 2005/0273770 (2005-12-01), Eichenberger et al.
patent: 2005/0283773 (2005-12-01), Eichenberger et al.
patent: 2005/0283774 (2005-12-01), Eichenberger et al.
patent: 2005/0289529 (2005-12-01), Almog et al.
“Support for the Intel Pentium 4 Processor with Hyper-Threading Technology in Intel 8.0 Compilers,” Intel Technology Journal, vol. 8, Issue 1, Feb. 18, 2004, 16 pages.
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.
Lee et al., “Simple Vector Microprocessors for Multimedia Applications,”Proceedings 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,” International Journal of Parallel Programming, vol. 28, No. 4, pp. 347-361, 2000, http://citeseer.ist.psu.edu/krall00compilation.html.
Sreraman et al., “A Vectorizing Compiler for Multimedia Extensions,”International Journal of Parallel Programming, 2000 (40 pages).
Bik et al., “Automatic Intra-Register Vectorization 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,” published by IBM Thomas J. Watson Research Center, Yorktown Heights, NY, Apr. 26, 1990, pp. 1-12.
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,”The Eleventh International Conference on Parallel Architectures and Compilation Techniques, Charlottesville, VA, Sep. 2002, pp. 1-11, http://moss.csc.ncsu.edu/pact02/papers/shin183.pdf.
Ren et al., “A Preliminary Study on the Vectorization of Multimedia Applications for Multimedia Extensions,” published by Department of Computer Science, University of Illinois at Urbana Champaign, Urbana, IL and IBM T.J. Watson Research Center, Yorktown Heights, NY, 2003, pp. 1-15, http://citeseer.ist.psu.edu/ren03preliminary.html.
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 Manual, 1999, 262 pages.
Arafeh, Bassel R., “Vectorization and parallelization interactive assistant,” 1988, ACM, pp. 573-577.
McKenney et al., “Generating Parallel Code for SIMD Machines,” 1992, ACM, pp. 59-73.
Pajuelo et al., “Speculative Dynamic Vectorization,” 2002, IEEE, pp. 271-280.
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.
Larsen et al., “Exploiting Superword Level Parallelism with Multimedia Instruction Sets,” 2000, PLDI 2000, pp. 145-156.
Lorenz et al., “Energy Aware Compilation for DSPs with SIMD Instructions,” 2002, LCTES'02-SCOPES'02, pp. 94-101.
Bik et al., “Efficient Exploitation of Parallelism on Pentium III and Pentium 4 Processor-Based Systems,” Intel Technology Journal Q1, 2001.
Schouten et al., “Inside the Intel Compiler,” Feb. 2003, Linux Journal, vol. 2003, Issue 106.
“VAST/AltiVec,” Crescent Bay Software Corp., 2003, 2 pages.

Affiliated with

Also associated with

Rating

Framework for integrated intra- and inter-loop aggregation... 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 integrated intra- and inter-loop aggregation..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Framework for integrated intra- and inter-loop aggregation... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4273651