Cache-conscious coallocation of hot data streams

Details Cache-conscious coallocation of hot data streams Cache-conscious coallocation of hot data streams

2008-03-11

2008-03-11

An, Meng-Al T. (Department: 2193)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S151000, C711S118000, C711S119000, C711S151000

Reexamination Certificate

active

07343598

ABSTRACT:
Techniques and tools for coallocating objects and/or object fields for the sake of cache performance are described. For example, a tool improves cache performance by coallocating contemporaneously accessed heap objects. The tool analyzes object accesses to identify hot data streams in a profile run of a program. The tool directs allocations for objects in a given hot data steam to the same sequentially allocated arena, separating intervening allocations coming from other allocation sites. The tool enforces the solution by redirecting heap allocations to a run-time coallocation library. The tool and analysis extend to coallocation at object field granularity. The resulting field coallocation solution generalizes common data restructuring techniques and provides insight into object restructuring by breaking down the coallocation benefit on a per-technique basis.

REFERENCES:
patent: 5220667 (1993-06-01), Ichieda
patent: 5333311 (1994-07-01), Whipple, II
patent: 5713008 (1998-01-01), Falkner
patent: 5740443 (1998-04-01), Carini
patent: 5774685 (1998-06-01), Dubey
patent: 5815720 (1998-09-01), Buzbee
patent: 5909578 (1999-06-01), Buzbee
patent: 5925100 (1999-07-01), Drewry et al.
patent: 5940618 (1999-08-01), Blandy et al.
patent: 5950003 (1999-09-01), Kaneshiro et al.
patent: 5950007 (1999-09-01), Nishiyama et al.
patent: 5953524 (1999-09-01), Meng et al.
patent: 5960198 (1999-09-01), Roediger et al.
patent: 6026234 (2000-02-01), Hanson et al.
patent: 6073232 (2000-06-01), Kroeker et al.
patent: 6079032 (2000-06-01), Peri
patent: 6122638 (2000-09-01), Huber et al.
patent: 6148437 (2000-11-01), Shah et al.
patent: 6311260 (2001-10-01), Stone et al.
patent: 6321240 (2001-11-01), Chilimbi et al.
patent: 6330556 (2001-12-01), Chilimbi et al.
patent: 6360361 (2002-03-01), Larus et al.
patent: 6404455 (2002-06-01), Ito et al.
patent: 6405292 (2002-06-01), Joseph et al.
patent: 6560693 (2003-05-01), Puzak et al.
patent: 6571318 (2003-05-01), Sander et al.
patent: 6628835 (2003-09-01), Brill et al.
patent: 6651243 (2003-11-01), Berry et al.
patent: 6658652 (2003-12-01), Alexander et al.
patent: 6675374 (2004-01-01), Pieper et al.
patent: 6704860 (2004-03-01), Moore
patent: 6848029 (2005-01-01), Coldewey
patent: 6886167 (2005-04-01), Breslau et al.
patent: 6951015 (2005-09-01), Thompson
patent: 7032217 (2006-04-01), Wu
patent: 2002/0133639 (2002-09-01), Breslau et al.
patent: 2002/0144245 (2002-10-01), Lueh
patent: 2003/0163658 (2003-08-01), Lanzatella et al.
patent: 2004/0015897 (2004-01-01), Thompson et al.
patent: 2004/0015930 (2004-01-01), Wu
patent: 2004/0025145 (2004-02-01), Dawson
patent: 2004/0103401 (2004-05-01), Chilimbi et al.
patent: 2004/0103408 (2004-05-01), Chilimbi et al.
patent: 2004/0111444 (2004-06-01), Garthwaite
patent: 2004/0133556 (2004-07-01), Wolczko et al.
patent: 2005/0091645 (2005-04-01), Chilimbi et al.
patent: 2005/0246696 (2005-11-01), Alexander et al.
U.S. Appl. No. 11/134,812, filed May 20, 2005, Ganapathy et al.
U.S. Appl. No. 11/134,796, filed May 20, 2005, Shankar et al.
U.S. Appl. No. 11/115,924, filed Apr. 26, 2005, Chilimbi et al.
Ammons et al., “Exploiting Hardware Performance Counters with Flow and Context Sensitive Profiling”, PLDI (Jun. 1997), 12 pages.
Ammons et al., “Improving Data-Flow Analysis with Path Profiles,”SIGPLAN '98(1998), pp. 72-84.
Anderson et al., “Continuous Profiling: Where Have All the Cycles Gone?”, ACM (Nov. 1997), pp. 357-390.
Annavaram et al., “Data Prefetching by Dependence Graph Precomputation”, IEEE (2001), pp. 52-61.
Arnold et al., “A Framework for Reducing the Cost of Instrumented Code”,Rutgers University Technical Report DCS-TR-424(Nov. 2000), pp. 1-10.
Bala et al., “Dynamo: A Transparent Dynamic Optimization System”, ACM (2000), pp. 1-12.
Balakrishnan et al., “Analyzing Memory Accesses in χ86 Binary Executables”,Proc. 13th Intl. Conference on Compiler Construction, LNCS 2985 (Apr. 2004), pp. 5-23.
Ball et al., “Efficient Path Profiling”, IEEE (1996), pp. 46-57.
Bush et al., “A Static Analyzer for Finding Dynamic Programming Errors”,Software: Practice and Experience(2000), pp. 775-802.
Cahoon et al., “Data Flow Analysis for Software Prefetching Linked Data Structures in Java”, IEEE (2001), 12 pages.
Chen et al., “Reducing Memory Latency via Non-Blocking and Prefetching Caches”, ACM (1992), pp. 51-61.
Chilimbi et al., “Dynamic Hot Data Stream Prefetching for General-Purpose Programs”, ACM (2002), 11 pages.
Chilimbi et al., “Low-Overhead Memory Leak Detection Using Adaptive Statistical Profiling”,Proc. 11th Intl. Conference on Architectural Support for Programming Language and Operating Systems(ASPLOS), (Oct. 2004), pp. 156-164.
Chilimbi et al., “Using Generational Garbage Collection to Implement Cache-Conscious Data Placement”,Proceedings of the First International Symposium on Memory Management(Oct. 1998), vol. 34(3), pp. 37-48.
Cooksey et al., “A Stateless, Content-Directed Data Prefetching Mechanism”, ACM (2002), pp. 279-290.
Cowan et al., “Buffer Overflows: Attacks and Defenses for the Vulnerability of the Decade”,DARPA information survivability conference and expo(DISCEX) (2000), pp. 1-11.
Dean et al., “ProfileMe: Hardware Support for Instruction-Level Profiling on Out-of-Order Processors”,Proc. 30th Annual Intl. Symp. On Microarchitecture(Dec. 1997), 12 pages.
Deaver et al., “Wiggins/Restone: An On-line Program Specializer”,Proceedings of the IEEE Hot Chips XI Conference(Aug. 1999), 29 pages.
Demsky et al., “Automatic Detection and Repair of Errors in Data Structures”,Proceedings of 18th ACM SIGPLAN Conference on Object-Oriented Programming Systems, Language and Applications(OOPLSA) (Oct. 2003), pp. 78-95.
Demsky et al., “Role-Based Exploration of Object-Oriented Programs”,Proceedings of 24th International Conference on Software Engineering(ISCE) (May 2002), pp. 313-334.
Dor et al., “Cleanness Checking of String Manipulations in C Programs via Integer Analysis”,Proc. 8th Int'l Static Analysis Symposium(Jun. 2001), 19 pages.
Dor et al., “CSSV: Towards a Realistic Tool for Statically Detecting All Buffer Overflows in C”,PLDI'03(Jun. 9-11, 2003), pp. 155-167.
Duesterwald et al., “Software profiling for hot path prediction: Less is more”,Ninth International Conference on Architectural Support for Programming Languages and Operating Systems(Nov. 2000), pp. 202-211.
Edwards, “Black-Box Testing Using Flowgraphs: An Experimental Assessment of Effectiveness and Automation Potential”,Software Testing, Verification and Reliability, vol. 10, No. 4 (Dec. 2000), pp. 249-262.
Eeckhout et al., “Workload Design: Selecting Representative Program-Input Pairs”,Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques(2002), 12 pages.
Ernst, “Dynamically Discovering Likely Program Invariants”,PhD Thesis, University of Washington(Aug. 2000), pp. 1-127.
Evans et al., “Improving Security Using Extensible Lightweight Static Analysis”,IEEE Software(Jan./Feb. 2002), pp. 42-51.
Evans et al., “LCLint: A Tool for Using Specifications to Check Code”,SIGSOFT Symposium on the Foundations of Software Engineering(Dec. 1994), 10 pages.
Evans et al., “Splint Manual, Version 3.1.1-1”,Secure Programming Group, University of Virginia Department of Computer Science(Jun. 5, 2003), 121 pages.
Evans, “Static Detection of Dynamic Memory Errors”,SIGPLAN Conf. on Programming Language and Design Implementation(May 1996), 10 pages.
Evans, “Using Specifications to Check Source Code”,TR-628, MIT Lab for Computer Science(Jun. 1994), 97 pages.
Foster et al., “A Theory of Type Qualifiers”,Proc. ACM SIGPLAN '99 Conf. on Programming Language and Design Implementation(PLDI) (May 1

Affiliated with

Also associated with

Rating

Cache-conscious coallocation of hot data streams does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Cache-conscious coallocation of hot data streams, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cache-conscious coallocation of hot data streams will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2806411