Data structure path profiling

Details Data structure path profiling Data structure path profiling

2011-04-12

2011-04-12

Dam, Tuan Q (Department: 2192)

Data processing: software development, installation, and managem

Software program development tool

Testing or debugging

C717S133000, C717S153000, C717S157000, C717S158000

Reexamination Certificate

active

07926043

ABSTRACT:
The described technology provides data structure path profiling. An instrumented version of a program is created that calls a profiler runtime when pointer based data structures are allocated or accessed via pointers. A model of the heap is created and nodes in the model data structures are assigned unique identifiers. Paths traversed through the model data structures are assigned unique identifiers. The paths are counted in order to identify paths through the data structure model that are traversed frequently. The model is useful for providing information about high frequency data paths to the program developer and for various optimization purposes, such as prefetching and or increasing data locality during garbage collection.

REFERENCES:
patent: 4862373 (1989-08-01), Meng
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), Urquhart 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: 6145121 (2000-11-01), Levy et al.
patent: 6148437 (2000-11-01), Shah et al.
patent: 6189036 (2001-02-01), Kao
patent: 6216219 (2001-04-01), Cai et al.
patent: 6233678 (2001-05-01), Bala
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: 6370684 (2002-04-01), De Pauw et al.
patent: 6381735 (2002-04-01), Hunt
patent: 6404455 (2002-06-01), Ito et al.
patent: 6446257 (2002-09-01), Pradhan et al.
patent: 6560693 (2003-05-01), Puzak et al.
patent: 6560773 (2003-05-01), Alexander et al.
patent: 6571318 (2003-05-01), Sander et al.
patent: 6598141 (2003-07-01), Dussud 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: 6738968 (2004-05-01), Bosworth et al.
patent: 6848029 (2005-01-01), Coldewey
patent: 6886167 (2005-04-01), Breslau et al.
patent: 6904590 (2005-06-01), Ball et al.
patent: 6951015 (2005-09-01), Thompson
patent: 6957422 (2005-10-01), Hunt
patent: 7032217 (2006-04-01), Wu
patent: 7058936 (2006-06-01), Chilimbi et al.
patent: 7140008 (2006-11-01), Chilimbi et al.
patent: 7159038 (2007-01-01), Rychlicki
patent: 7181730 (2007-02-01), Pitsianis et al.
patent: 7293260 (2007-11-01), Dmitriev
patent: 7296180 (2007-11-01), Waterhouse et al.
patent: 7343598 (2008-03-01), Chilimbi et al.
patent: 7401324 (2008-07-01), Dmitriev
patent: 7506317 (2009-03-01), Liang et al.
patent: 7587709 (2009-09-01), Chilimbi et al.
patent: 7607119 (2009-10-01), Perelman et al.
patent: 7770153 (2010-08-01), Chilimbi et al.
patent: 2002/0133639 (2002-09-01), Breslau et al.
patent: 2002/0144245 (2002-10-01), Lueh
patent: 2002/0178401 (2002-11-01), Ball et al.
patent: 2003/0145314 (2003-07-01), Nguyen et al.
patent: 2003/0204840 (2003-10-01), Wu
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/0078381 (2004-04-01), Blandy et al.
patent: 2004/0088699 (2004-05-01), Suresh
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: 2004/0181782 (2004-09-01), Findeisen
patent: 2004/0215880 (2004-10-01), Chilimbi et al.
patent: 2004/0216091 (2004-10-01), Groeschel
patent: 2005/0086648 (2005-04-01), Andrews et al.
patent: 2005/0091645 (2005-04-01), Chilimbi et al.
patent: 2005/0149904 (2005-07-01), Ball et al.
patent: 2005/0182603 (2005-08-01), Freitas et al.
patent: 2005/0235257 (2005-10-01), Ball et al.
patent: 2005/0246696 (2005-11-01), Alexander et al.
patent: 2006/0070040 (2006-03-01), Chilimbi et al.
patent: 2006/0155791 (2006-07-01), Tene et al.
patent: 2006/0242636 (2006-10-01), Chilimbi et al.
patent: 2006/0265438 (2006-11-01), Shankar et al.
patent: 2006/0265694 (2006-11-01), Chilimbi et al.
patent: 2007/0083856 (2007-04-01), Chilimbi et al.
patent: 2007/0169000 (2007-07-01), Havin et al.
patent: 2007/0244942 (2007-10-01), McCamant et al.
Trishul Chilimbi,Efficient Representations and Abstractions for Quantifying and Exploiting Data Reference Locality, Symposium of Programming Languages Design and Implementation, 2001, 12 pages.
Easwarman Raman,Recursive Data Structure Profiling, Workshops on Memory System Performance, 2005, 10 pages.
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.
Bacon, “A unified theory of garbage collection,” ACM, Oct. 2004, 19 pages.
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.
Ball et al., “Generating abstract explanations of spurious counterexamples in C programs,” Technical Report MSR-TR-2002-09, 13 pages, Jan. 22, 2002.
Ball et al., “The SLAM project: Debugging system software via static analysis,” Jan. 2002, 3 pages.
Ball et al., “Boolean programs: A model and process for software analysis,” Technical Report MSR-TR-2000-14, 29 pages, Feb. 29, 2000 (updated Mar. 28, 2000).
Ball et al., “Plymorphic Predicate Abstraction,” Technical Report MSR-TR-2001-10, 22 pages, Jun. 17, 2002.
Ball et al., “SLAM and static driver verifier: Technology transfer of formal methods inside Microsoft,” Technical Report MSR-TR-2004-08, 20 pages, Jan. 28, 2004.
Berger et al., “Composing High-Performance Memory Allocators”, ACM (2001), 11 pages.
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.
Calder et al., “Cache-Conscious Data Placement”, ACM (Oct. 1998), 11 pages.
Chen et al., “Reducing Memory Latency via Non-Blocking and Prefetching Caches”, ACM (1992), pp. 51-61.
Chen, “Using build integrated static checking to preserve correctness invariants,” ACM, Oct. 2004, 10 pages.
Chilimbi et al., “Cache-Conscious Structure Definition”,Proceedings of the ACM SIGPLAN '99(May 1999), 12 pages.
Chilimbi et al., “Cache-Conscious Structure Layout”,Proc. ACM SIGPLAN '99 Conf. on Programming Language Design and Impl., (May 1999), 12 pages.
Chilimbi et al., “Dynamic Hot Data Stream Prefetching for General-Purpose Programs”, ACM (Jun. 2002), 11 pages.
Chilimbi et al., “HeapMD: Identifying Heap-based Bugs Using Anomaly Detection,” ACM (Oct. 2006) 10 pages.
Chilimbi et al., “Low-Overhead Memory Leak Detection Using Adaptive Statistical Pro

Affiliated with

Also associated with

Rating

Data structure path profiling does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Data structure path profiling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data structure path profiling will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2741164