Profile-driven data layout optimization

Details Profile-driven data layout optimization Profile-driven data layout optimization

2006-03-14

2006-03-14

Dam, Tuan (Department: 2191)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S151000, C711S165000

Reexamination Certificate

active

07013459

ABSTRACT:
Data layout optimization arranges data members within memory to enhance software performance. Profiling data is consulted to determine how to group data members for an object class into groups. One technique groups the data members based on how frequently the data members are referenced in memory. Another technique groups the data members based on their affinities for one another in time as determined by observing when references to the data members take place. A variety of options when collecting the profiling data and grouping the data members is supported. The data member grouping is recorded in metadata associated with a definition of the object class. At runtime, a class loader places the data members of an object in memory according to the metadata. Data members of different groups can be placed in separately-loadable units of memory in the memory system. Subsequently, when the data members are referenced in memory, more frequently referenced data members, including those that tend to be referenced at times close to each other, reside at neighboring locations in the memory system.

REFERENCES:
patent: 5075848 (1991-12-01), Lai et al.
patent: 5579520 (1996-11-01), Bennett
patent: 5752038 (1998-05-01), Blake et al.
patent: 5790858 (1998-08-01), Vogel
patent: 5790865 (1998-08-01), Smaalders et al.
patent: 5884316 (1999-03-01), Bernstein et al.
patent: 6059838 (2000-05-01), Fraley et al.
patent: 6189141 (2001-02-01), Benitez et al.
patent: 6230312 (2001-05-01), Hunt
patent: 6263491 (2001-07-01), Hunt
patent: 6269477 (2001-07-01), Fitzgerald et al.
patent: 6321240 (2001-11-01), Chilimbi et al.
patent: 6324620 (2001-11-01), Christenson et al.
patent: 6332275 (2001-12-01), Tsai et al.
patent: 6381628 (2002-04-01), Hunt
patent: 6381735 (2002-04-01), Hunt
patent: 6381739 (2002-04-01), Breternitz et al.
patent: 6381740 (2002-04-01), Miller et al.
patent: 6401097 (2002-06-01), McCotter et al.
patent: 6499137 (2002-12-01), Hunt
patent: 6594678 (2003-07-01), Stoutamire et al.
patent: 6629123 (2003-09-01), Hunt
patent: 6631496 (2003-10-01), Li et al.
patent: 6651243 (2003-11-01), Berry et al.
patent: 6658648 (2003-12-01), Douceur et al.
patent: 6681387 (2004-01-01), Hwu et al.
patent: 0 755 003 (1997-01-01), None
T.M. Chilimbi and J. R. Larus, “Using Generational Garbage Collection To Implement Cache-Conscious Data Placement”, 1998, ACM, p. 37-48.
B. Calder, C. Krintz, S. John, T. Austin, “Cache-Conscious Data Placement”, 1998, ACM, p. 139-149.
S. Carr, K. S. McKinley, C-W Tseng, “Compiler Optimizations for Improving Data Locality”, 1994, ACM, p. 252-262.
C-K Luk, T. C. Mowry, “Memory Forwarding: Enabling Aggressive Layout Optimizations by Guaranteeing the Safety of Data Relocation”, 1999, IEEE, p. 88-99.
U.S. Appl. No. 09/196,836, filed Nov. 20, 1998, Hunt.
U.S. Appl. No. 09/197,080, filed Nov. 20, 1998, Hunt.
“Basic Techniques for Design and Analysis of Algorithms,”The Computer Science and Engineering Handbook, Tucker (ed.), CRC Press, pp. 64-85, 1997.
“BIBOP (also known as big bag of pages),” p. 1, Dec. 20, 2000.
“Big bag of pages,” http://wombat.doc.ic.ac.uk/foldoc/foldoc.cgi?Big+bag+of+pages, p. 1, Mar. 3, 2000.
“Graph and Network Algorithms,”The Computer Science and Engineering Handbook, Tucker (ed.), CRC Press, pp. 203-225, 1997.
“Memory Management,”Microsoft Win32 Programmer's Reference, vol. 2, System Services, Multimedia, Extensions, and Application Notes, Microsoft Press, pp. 3-16, 1993.
Babonneau et al., “Automatic and general solution to the adaptation of programs in a paging environment,”Proceedings of the Sixth Symposium on Operating Systems Principles, West Lafayette, In, vol. 11, No. 5: 109-116, Nov. 16-18, 1977.
Baier, “Dynamic Improvement of Locality in Virtual Memory Systems,”IEEE Transactions on Software Engineering, vol. SE-2, No. 1, pp. 54-62, Mar. 1976.
Baker, Jr. et al., “Optimizing Allocation and Garbage Collection of Spaces,” http://linux.rice.edu/˜rahul/hbaker/OptAlloc.html, pp. 1-4, 1979.
Brewer, “High-Level Optimization Via Automated Statistical Modeling,”Proceedings of the Fifth ACM SIGPLAN Symposium on Principles&Practice of Parallel Programming, pp. 80-91, 1995.
Burger et al., “Memory Systems,”The Computer Science and Engineering Handbook, Tucker (ed.), CRC Press, pp. 447-461, 1997.
Calder et al., “Cache-Conscious Data Placement,” ACM, pp. 139-149, 1998.
Carr et al., “Compiler Optimizations for Improving Data Locality,” ACM, pp. 252-262, 1994.
Chilimbi et al., “Using Generational Garbage Collection to Implement Cache-Conscious Data Placement,” ACM, pp. 37-48, 1998.
Denning, “Virtual Memory,”The Computer Science and Engineering Handbook, Tucker (ed.), CRC Press, pp. 1747-1760, 1997.
Franz et al., “Splitting Data Objects to Increase Cache Utilization,”Technical Report-University of California-Department of Information and Computer Science, No. 98-34: Oct. 1-11, 1998, URL:http://www.ics.uci.edu/z/pubs-pdf/ICS-TR-98-34.pdf.
Gloy et al., “Procedure Placement Using Temporal Ordering Information,”IEEE, pp. 303-313, 1997.
Gosling et al., “The Java Language Environment. A White Paper,”Sun Delivers Java Workshop: 1, 4-85, Oct. 1, 1995.
Hanson, “A Portable Storage Management System for the Icon Programming Language,”Software-Practice and Experience, vol. 10, pp. 489-500, 1980.
Kistler et al., “Automated Layout of Data Members for Type-Safe Languages,”Technical Report(Revised Version)-University of California-Department of Information and Computer Science: Sep. 1-10, 1998, URL:http://caesar.ics.uci.edu/kistler/papers/ics-tr-98-22-R.pdf.
Kistler et al., “Computing the Similarity of Profiling Data,”Proceedings of the Workshop on Profile and Feedback-Directed Compilation, Paris, France, pp. 1-6, Sep. 1998.
Kistler et al., “The Case for Dynamic Optimization,” Department of Information and Computer Science, pp. 1-21, May 12, 1999.
Luk et al., “Memory Forwarding: Enabling Aggressive Layout Optimizations by Guaranteeing the Safety of Data Relocation,”IEEE Proceedings, 26thAnnual International Symposium on Computer Architecture, pp. 88-99, May 1999.
Norman et al., “Memory Tracing of Algebraic Calculations,”Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation, pp. 113-119, 1996.
Reiss, “Software Tools and Environments,”The Computer Science and Engineering Handbook, Tucker (ed.), CRC Press, pp. 2419-2439, 1997.
Seidl et al., “Segregating Heap Objects by Reference Behavior and Lifetime,”Proceeding of the Eighth International Conference on Architectural Support for Programming Languages and Operating Systems: Oct. 1-12, 1998.
Tomiyama et al., “Code Placement Techniques for Cache Miss Rate Reduction,”ACM Trans. Des. Autom. Electron. Syst. 2, 4:410-429, Oct., 1997.
Xia et al., “Instruction Prefetching of Systems Codes With Layout Optimized for Reduced Cache Misses,”Proceedings of the 23rdAnnual International Symposium on Computer Architecture, pp. 271-282, 1996.

Affiliated with

Also associated with

Rating

Profile-driven data layout optimization does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Profile-driven data layout optimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Profile-driven data layout optimization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3564731