Profile-driven data layout optimization

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

2005-02-28

2009-02-24

Zhen, Wei Y (Department: 2191)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S151000, C711S165000

Reexamination Certificate

active

07496909

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: 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: 6546553 (2003-04-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: 6681387 (2004-01-01), Hwu et al.
patent: 6862729 (2005-03-01), Kuch et al.
patent: 6983463 (2006-01-01), Hunt
patent: 7013459 (2006-03-01), Kuch et al.
patent: 7039919 (2006-05-01), Hunt
patent: 0 755 003 (1997-01-01), None
Chilimbi, et al. “Using Generational Garbage Collection To Implement Cache-Conscious Data Placement”, 1998, ACM, p. 37-48.
U.S. Appl. No. 08/931,861, filed Sep. 16, 1997, Douceur et al.
Norman and Fitch, “Memory Tracing of Algebraic Calculations,”Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation, pp. 113-119, 1996.
Xia and Torrellas, “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.
Tomiyama and Yasuura, “Code Placement Techniques for Cache Miss Rate Reduction,”ACM Trans. Des. Autom. Electron. Syst. 2, 4:410-429, Oct. 1997.
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.
“Basic Techniques for Design and Analysis of Algorithms,”The Computer Science and Engineering Handbook, Tucker (ed.), CRC Press, pp. 64-85, 1997.
“Graph and Network Algorithms,”The Computer Science and Engineering Handbook, Tucker (ed.), CRC Press, pp. 203-225, 1997.
Burger et al., “Memory Systems,”The Computer Science and Engineering Handbook, Tucker (ed.), CRC Press, pp. 447-461, 1997.
Denning, “Virtual Memory,”The Computer Science and Engineering Handbook, Tucker (ed.), CRC Press, pp. 1747-1760, 1997.
Reiss, “Software Tools and Environments,”The Computer Science and Engineering Handbook, Tucker (ed.), CRC Press, pp. 2419-2439, 1997.
Gloy et al., “Procedure Placement Using Temporal Ordering Information,”IEEE, pp. 303-313, 1997.
“Memory Management,”Microsoft Win32 Programmer's Reference, vol. 2, System Services, Multimedia, Extensions, and Application Notes, Microsoft Press, pp. 3-16, 1993.
Baker, Jr. et al., “Optimizing Allocation and Garbage Collection of Spaces,” http://linux.rice.edu/˜rahul/hbaker/OptAlloc.html, pp. 1-4, 1979.
“BIBOP (also known as big bag of pages),” p. 1, Dec. 20, 2000.
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.
Hanson, “A Portable Storage Management System for the Icon Programming Language,”Software-Practice and Experience, vol. 10, pp. 489-500, 1980.
Baier, “Dynamic Improvement of Locality in Virtual Memory Systems,”IEEE Transactions on Software Engineering, vol. SE-2, No. 1, pp. 54-62, Mar. 1976.
Kistler et al., “The Case for Dynamic Optimization,” Department of Information and Computer Science, pp. 1-21, May 12, 1999.
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.
“Big bag of pages,” http://wombat.doc.ic.ac.uk/foldoc/foldoc.cgi?Big+bag+of+pages, p. 1, Mar. 3, 2000.
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: 1-12, Oct. 1998.
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: 1-10, Sep. 1998, URL:http://caesar.ics.uci.edu/kistler/papers/ics-tr-98-22-R.pdf.
Franz et al., “Splitting Data Objects to Increase Cache Utilization,”Technical Report- University of California-Department of Information and Computer Science, No. 98-34: 1-11, Oct. 1998, URL:http://www.ics.uci.edu/z/pubs-pdf/ICS-TR-98-34.pdf.
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.
Gosling et al., “The Java Language Environment. A White Paper,”Sun Delivers Java Workshop: 1, 4-85, Oct. 1, 1995.
Δ 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.
Chilimbi et al., “Cache-Conscious Structure Definition,”Proceedings of the ACM SIGPLAN '99 Conference on Programming Language Design and Implementation(PLDI)SigPlan Notices, pp. 13-24, May 1999.

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-4095091