Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
2007-09-26
2011-12-27
Khatri, Anil (Department: 2191)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S150000, C717S160000
Reexamination Certificate
active
08087011
ABSTRACT:
Mechanisms for domain stretching for an advanced dual-representation polyhedral loop transformation framework are provided. The mechanisms of the illustrative embodiments address the weaknesses of the known polyhedral loop transformation based approaches by providing mechanisms for performing code generation transformations on individual statement instances in an intermediate representation generated by the polyhedral loop transformation optimization of the source code. These code generation transformations have the important property that they do not change program order of the statements in the intermediate representation. This property allows the result of the code generation transformations to be provided back to the polyhedral loop transformation mechanisms in a program statement view, via a new re-entrance path of the illustrative embodiments, for additional optimization. In addition, mechanisms are provided for stretching the domains of statements in a program loop view of the source code to thereby normalize the domains.
REFERENCES:
patent: 4802091 (1989-01-01), Cocke et al.
patent: 5287510 (1994-02-01), Hall et al.
patent: 5293631 (1994-03-01), Rau et al.
patent: 5475842 (1995-12-01), Gilbert et al.
patent: 5535393 (1996-07-01), Reeve et al.
patent: 5808915 (1998-09-01), Troyanovsky
patent: 5812852 (1998-09-01), Poulsen et al.
patent: 5822593 (1998-10-01), Lamping et al.
patent: 5881291 (1999-03-01), Piazza
patent: 5946484 (1999-08-01), Brandes
patent: 5999737 (1999-12-01), Srivastava
patent: 6026240 (2000-02-01), Subramanian
patent: 6038398 (2000-03-01), Schooler
patent: 6058266 (2000-05-01), Megiddo et al.
patent: 6064819 (2000-05-01), Franssen et al.
patent: 6078745 (2000-06-01), De Greef et al.
patent: 6106575 (2000-08-01), Hardwick
patent: 6226790 (2001-05-01), Wolf et al.
patent: 6247173 (2001-06-01), Subrahmanyam
patent: 6253373 (2001-06-01), Peri
patent: 6282706 (2001-08-01), Chauvel et al.
patent: 6286135 (2001-09-01), Santhanam
patent: 6339840 (2002-01-01), Kothari et al.
patent: 6357041 (2002-03-01), Pingali et al.
patent: 6367071 (2002-04-01), Cao et al.
patent: 6427234 (2002-07-01), Chambers et al.
patent: 6507947 (2003-01-01), Schreiber et al.
patent: 6588009 (2003-07-01), Guffens et al.
patent: 6651246 (2003-11-01), Archambault et al.
patent: 6654952 (2003-11-01), Nair et al.
patent: 6745384 (2004-06-01), Biggerstaff
patent: 6772415 (2004-08-01), Danckaert et al.
patent: 6948160 (2005-09-01), Click et al.
patent: 6952821 (2005-10-01), Schreiber
patent: 7000213 (2006-02-01), Banerjee et al.
patent: 7107199 (2006-09-01), Schreiber et al.
patent: 7162716 (2007-01-01), Glanville et al.
patent: 7254679 (2007-08-01), Richter et al.
patent: 7484079 (2009-01-01), Gupta et al.
patent: 2001/0032332 (2001-10-01), Ward et al.
patent: 2003/0200538 (2003-10-01), Ebeling et al.
patent: 2004/0003386 (2004-01-01), Tal et al.
patent: 2004/0019883 (2004-01-01), Banerjee et al.
patent: 2004/0068718 (2004-04-01), Cronquist et al.
patent: 2005/0273770 (2005-12-01), Eichenberger et al.
patent: 2005/0273772 (2005-12-01), Matsakis et al.
patent: 2007/0174829 (2007-07-01), Brockmeyer et al.
patent: 2008/0263530 (2008-10-01), Rahavan et al.
patent: 2009/0083702 (2009-03-01), Eichenberger et al.
patent: 2009/0083722 (2009-03-01), Eichenberger et al.
patent: 2009/0083724 (2009-03-01), Eichenberger et al.
Lin et al, “Optimal simultaneous mapping and clustering for FPGA delay optimization”, ACM DAC pp. 472-477, 2006.
Gottlob et al, “Normalization and optimization of schema mappings”, The VLDB Journal, pp. 277-302, 2011.
Jeffords et al, “Using invariants to optimize formal specifications before code synthesis”, IEEE, pp. 73-82, 2004.
Hazelwood et al, “Exploring code cache eviction granularities in dynamic optimization systems”, IEEE CGO, pp. 1-11, 2004.
Vasilache et al., “Polyhedral Code Generation in the Real World”, INRIA, 2006, available at http://hal.inria.fr/inria-00001106/en/, 15 pages.
Bastoul et al., “Putting Polyhedral Loop Transformations to Work”, Workshop on Languages and Compilers for Parallel Computing (LCPC'03), LNCS, Springer-Verlag, College Station, Texas, Oct. 2003, pp. 23-30.
Bastoul, Cedric, “Code Generation in the Polyhedral Model is Easier Than You Think”, PACT'13 IEEE International Conference on Parallel Architecture and Compilation Techniques, Juan-les-Pins, Sep. 2004, pp. 7-16.
Girbal et al., “Semi-Automatic Composition of Loop Transformations for Deep Parallelism and Memory Hierarchies”, International Journal of Parallel Programming, vol. 34, No. 3, Jun. 2006, pp. 261-317.
Quillere et al., “Generation of Efficient Nested Loops from Polyhedra”, International Journal of Parallel Programming, Oct. 2000, 30 pages.
Vasilache, Nicolas, “Scalable Program Optimization Techniques in the Polyhedral Model”, Thesis for Doctor of Philosophy, to be Defended on Sep. 28, 2007, Universite de Paris-SUD, U.F.R. Scientifique d'Orsay, Irina Futurs, 216 pages.
U.S. Appl. No. 11/861,449, filed Sep. 26, 2007, Eichenberger et al.
U.S. Appl. No. 11/861,493, filed Sep. 26, 2007, Eichenberger et al.
U.S. Appl. No. 11/861,512, filed Sep. 26, 2007, Eichenberger et al.
Interview Summary mailed Apr. 20, 2011 for U.S. Appl. No. 11/361,512; 3 pages.
Notice of Atlowance mailed Jun. 23, 2011 for U.S. Appl. No. 11/861,512; 10 pages.
Office Action mailed May 10, 2011 for U.S. Appl. No. 11/861,493; 16 pages.
Kandemir, Mahmut et al., “Improving Memory Energy Using Access Pattern Classification”, Nov. 2001, pp. 201-206, <http://delivery.acm.org/10.1145/610000/603136/p201-kandemir.pdf>.
Quillere, Fabien et al., “Optimizing Memory Usage in the Polyhedral Model”, Sep. 2000, pp. 773-815, <http://delivery.acm.org/10.1145/370000/365152/p773-quillere.pdf>.
U.S. Appl. No. 11/861,449, Image File Wrapper printed Apr. 14, 2011, 1 page.
U.S. Appl. No. 11/861,493, Image File Wrapper printed Apr. 14, 2011, 1 page.
U.S. Appl. No. 11/861,512, Image File Wrapper printed Apr. 20, 2011, 2 pages.
Notice of Allowance mailed Jul. 22, 2011 for U.S. Appl. No. 11/861,449, 20 pages.
Notice of Allowance mailed Aug. 24, 2011 for U.S. Appl. No. 11/861,493, 13 pages.
Response to Office Action filed with the USPTO on Aug. 10, 2011 for U.S. Appl. No. 11/851,493, 26 pages.
Hu, Ying et al., “Theory and Algorithms for the Generation and Validation of Speculative Loop Optimizations”, IEEE, Sep. 23, 2004, 9 pages.
Saltz, Joel H. et al., “Run-Time Parallelization and Scheduling of Loops”, IEEE Transactions on Computers, vol. 40, No. 5, May 1991, 10 pages.
Eichenberger Alexandre E.
O'Brien John K. P.
O'Brien Kathryn M.
Vasilache Nicolas T.
International Business Machines - Corporation
Khatri Anil
Talpis Matthew B.
Walder, Jr. Stephen J.
LandOfFree
Domain stretching for an advanced dual-representation... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Domain stretching for an advanced dual-representation..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Domain stretching for an advanced dual-representation... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4309971