Variational path profiling

Details Variational path profiling Variational path profiling

2005-04-26

2009-10-20

Zhen, Wei Y (Department: 2191)

Data processing: software development, installation, and managem

Software program development tool

Software project management

Reexamination Certificate

active

07607119

ABSTRACT:
A run time software test tool instruments a program to perform a low overhead profiling of the program's execution, which records the execution time of frequent acyclic control flow paths using hardware performance counters. An analysis of the profiling data is performed to identify those program paths that have significant variation in execution time across different dynamic traversals in the same program run. This variation (measured as the difference between the fastest execution of that path and slower executions) represents the potential speedup that potentially could be achieved if the paths were optimized (such as by the addition of simple pre-fetch optimizations) to do away with these variations. The variational paths are identified to the programmer to guide optimization.

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), 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: 6148437 (2000-11-01), Shah et al.
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: 6404455 (2002-06-01), Ito et al.
patent: 6560693 (2003-05-01), Puzak 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: 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: 7181730 (2007-02-01), Pitsianis et al.
patent: 2002/0133639 (2002-09-01), Breslau et al.
patent: 2002/0144245 (2002-10-01), Lueh
patent: 2003/0145314 (2003-07-01), Nguyen 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/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/0215880 (2004-10-01), Chilimbi et al.
patent: 2004/0216091 (2004-10-01), Groeschel
patent: 2005/0091645 (2005-04-01), Chilimbi et al.
patent: 2005/0246696 (2005-11-01), Alexander et al.
patent: 2006/0155791 (2006-07-01), Tene et al.
Ammons et al., “Improving Data-Flow Analysis with Path Profiles,”SIGPLAN '98,pp. 72-84 (1998).
Ammons et al., “Exploiting Hardware Performance Counters with Flow and Context Sensitive Profiling,”ACM SIGPLAN,vol. 32, No. 5, pp. 85-96 (1997).
Anderson et al., Continuous Profiling: Where Have All the Cycles Gone?ACM Transactions on Computer Systems,vol. 15, No. 4, pp. 357-390 (1997).
Arnold et al., “A Framework for Reducing the Cost of Instrumented Code,”PLDI,pp. 1-12 (2001).
Ball et al., “Efficient Path Profiling,”IEEE,pp. 46-57 (1996).
Dean et al., “ProfileMe:Hardware Support for Instruction-Level Profiling on Out-of-Order Processors,”IEEE(1997).
Eeckhout et al., “Workload Design: Selecting Representative Program-Input Pairs,”Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques(2002).
Hirzel et al., “Bursty Tracing: A Framework for Low-Overhead Temporal Profiling,”Microsoft Research(2001).
“Technologies for Measuring Software Performance,”Intel Corporation(2003).
Larus, “Whole Program Paths,”SIGPLAN '99 Conference on Programming Languages and Design(1999).
Melski et al., “Interprocedural Path Profiling”,University of Wisconsin,pp. 1-50 (1998).
Mowry et al., “Predicting Data Cache Misses in Non-Numeric Applications Through Correlation Profiling,”International Symposium on Microarchitecture(1997).
Srivastava et al., “Vulcan Binary Transformation in a Distributed Environment,”MSR-TR-2001-50, Microsoft Research(2001).
“JProfiler Manual,”ejtechnologies,GmbH, pp. 1-141 (2004).
Zorn et al., “A Memory Allocation Profiler for C and Lisp Programs,” published Feb. 16, 1988, pp. 1-18.
English et al., “Loge: a self-organizing disk controller,”Proc. USENIX Winter 1992 Tech. Conf.,San Francisco, pp. 237-251 (Jan. 1992).
Hatfield et al., “Program Restructuring for Virtual Memory,”IBM Sys. J.,No. 3, pp. 168-192 (1971).
Kroeger et al., “Predicting Future File-system Actions from Prior Events,”Proc. USENIX Annual Tech. Conf.,San Diego, pp. 1-10 (Jan. 1996).
Palmer et al., “Fido: A Cache that Learns to Fetch,”Proc. 17th Int'l Conf. on Very Large Databases,Barcelona, pp. 255-264 (Sep. 1991).
Patterson et al., “Informed Prefetching and Caching,”Proc. 15th ACM Symp. on Operating System Principles,Copper Mountain Resort, CO, pp. 79-95 (Dec. 1995).
Staelin et al., “Smart Filesystems,”Proc. USENIX—Winter '91,Dallas, TX, pp. 45-51 (1991).
Tait et al., “Detection and Exploitation of File Working Sets,”IEEE,pp. 2-9 (1991).
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.
Annavaram et al., “Data Prefetching by Dependence Graph Precomputation”, IEEE (2001), pp. 52-61.
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.
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 (1998), 11 pages.
Chen et al., “Reducing Memory Latency via Non-Blocking and Prefetching Caches”, ACM (1992), pp. 51-61.
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 (2002), 11 pages.
Chilimbi, “Efficient Representations and Abstractions for Quantifying and Exploiting Data Reference Locality”, ACM (2001), pp. 191-202.
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., “On the Stability of Temporal Data Reference Profiles”, PACT (Sep. 2001), 10 pages.
Chilimbi et al., “Using Generational Garbage Collection to Implement Cache-Conscious Data Placement”,Proceedings of the First International Symposium on Memory Management(Oct. 1998

Affiliated with

Also associated with

Rating

Variational 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 Variational path profiling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Variational path profiling will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4054751