Dynamic temporal optimization framework

Details Dynamic temporal optimization framework Dynamic temporal optimization framework

2006-11-21

2006-11-21

Zhen, Wei (Department: 2191)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S153000, C717S155000

Reexamination Certificate

active

07140008

ABSTRACT:
A temporal profiling framework useful for dynamic optimization with hot data stream prefetching provides profiling of longer bursts and lower overhead. For profiling longer bursts, the framework employs a profiling phase counter, as well as a checking phase counter, to control transitions to and from instrumented code for sampling bursts of a program execution trace. The temporal profiling framework further intelligently eliminates some checks at procedure entries and loop back-edges, while still avoiding unbounded execution without executing checks for transition to and from instrumented code. Fast hot data stream detection analyzes a grammar of a profiled data reference sequence, calculating a heat metric for recurring subsequences based on length and number of unique occurrences outside of other hot data streams in the sequence with sufficiently low-overhead to permit use in a dynamic optimization framework.

REFERENCES:
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: 5953524 (1999-09-01), Meng et al.
patent: 5960198 (1999-09-01), Roediger et al.
patent: 6026234 (2000-02-01), Hanson et al.
patent: 6079032 (2000-06-01), Peri
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: 6560693 (2003-05-01), Puzak et al.
patent: 6571318 (2003-05-01), Sander et al.
patent: 6651243 (2003-11-01), Berry et al.
patent: 6675374 (2004-01-01), Pieper et al.
patent: 6704860 (2004-03-01), Moore
patent: 6848029 (2005-01-01), Coldewey
patent: 6951015 (2005-09-01), Thompson
patent: 2002/0144245 (2002-10-01), Lueh
patent: 2004/0015930 (2004-01-01), Wu
patent: 2004/0025145 (2004-02-01), Dawson
patent: 2004/0103408 (2004-05-01), Chilimbi et al.
patent: 2004/0215880 (2004-10-01), Chilimbi et al.
patent: 2005/0091645 (2005-04-01), Chilimbi et al.
Arnold et al.,A Framework for Reducing the Cost of Instrumented Code, Rutgers University Technical Report DCS-TR-424(Nov. 2000).
Karlsson et al.,A Prefetching Technique for Irregular Accesses to Linked Data Structures, Sixth International Symposium on High-Performance Computer Architecture(Jan. 2000).
Cooksey et al.,A Stateless, Content-Directed Data Prefetching Mechanism, ACM(2002).
Klaiber et al.,An Architecture for Software-Controlled Data Prefetching, ACM(1991).
Rubin et al.,An Efficient Profile-Analysis Framework for Data-Layout Optimizations, POPL(Jan. 2002).
Hirzel et al.,Bursty Tracing: A Framework for Low-Overhead Temporal Profiling, 4thACM Workshop on Feedback-Directed and Dynamic Optimization(Dec. 2001).
Luk et al.,Compiler-Based Prefetching for Recursive Data Structures, ACM(1996).
Anderson et al.,Continuous Profiling: Where Have All the Cycles Gone? ACM(Nov. 1997).
Cahoon et al.,Data Flow Analysis for Software Prefetching Linked Data Structures in Java, IEEE(2001).
Vanderwiel et al.,Data Prefetch Mechanisms, ACM Computing Surveys, vol. 32, No. 2 (Jun. 2000).
Annavaram et al.,Data Prefetching by Dependence Graph Precomputation, IEEE(2001).
Mowry et al.,Design and Evaluation of a Compiler Algorithm for Prefetching, ACM(1992).
Chilimbi et al.,Dynamic Hot Data Stream Prefetching for General-Purpose Programs, ACM, (2002).
Bala et al.,Dynamo: A Transparent Dynamic Optimization System, ACM(2000).
Roth et al.,Effective Jump-Pointer Prefetching for Linked Data Structures, IEEE(1999).
Ball et al.,Efficient Path Profiling, IEEE(1996).
Chilimbi,Efficient Representations and Abstractions for Quantifying and Exploiting Data Reference Locality, ACMI(2001).
Jouppi,Improving Direct-Mapped Cache Performance by the Addition of a Small Fully-Associative Cache and Prefetch Buffers, IEEE(1990).
Saavedra et al.,Improving the Effectiveness of Software Prefetching With Adaptive Execution, IEEE(1996).
Chilimbi et al.,On the Stability of Temporal Data Reference Profiles, PACT(Sep. 2001).
Joseph et al.,Prefetching Using Markov Predictors, ACM(1997).
Chen et al.,Reducing Memory Latency via Non-Blocking and Prefetching Caches, ACM(1992).
Stoutchinin et al.,Speculative Prefetching of Induction Pointers, Proceedings of 10thInternational Conference on Compiler Construction(2001).
Srivastava et al.,Vulcan Binary Transformation in a Distributed Environment, Microsoft Research, MSR-TR-99-76(Apr. 20, 2001).
Deaver et al.,Wiggins/Redstone: An On-line Program Specializer, Proceedings of the IEEE Hot Chips XI Conference(Aug. 1999).
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.
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.
Calder et al., “Cache-Conscious Data Placement”, ACM (1998), 11 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., “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.
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.
Crescenzi at al., “A Compendium of NP Optimization Problems,” [Downloaded from the World Wide Web on Dec. 12, 2003], 20 pages.
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.
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

Affiliated with

Also associated with

Rating

Dynamic temporal optimization framework does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Dynamic temporal optimization framework, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic temporal optimization framework will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3674589