Dynamic prefetching of hot data streams

Details Dynamic prefetching of hot data streams Dynamic prefetching of hot data streams

2005-11-15

2011-10-25

Bullock, Jr., Lewis (Department: 2193)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S151000, C717S153000, C711S213000, C712S207000

Reexamination Certificate

active

08046752

ABSTRACT:
A method and system for creating and injecting code into a running program that identifies a hot data stream, and prefetching data elements in the stream so they are available when needed by the processor. The injected code identifies the first few elements in a hot data stream (i.e. the prefix), and prefetches the balance of the elements in the stream (i.e., the suffix). Since the hot data stream identification code and prefetch code is injected at run time, pointer related time-dependencies inherent in earlier prefetch systems are eliminated. A global deterministic finite state machine (DFSM) is used to help create conceptual logic used to generate the code injected into the program for prefix detection.

REFERENCES:
patent: 4862373 (1989-08-01), Meng et al.
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/0182654 (2003-09-01), Dmitriev
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/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), Ganapathy 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.
patent: 2008/0005208 (2008-01-01), Vaswani et al.
Gonzalez et al. “Eliminating Cache Conflict Misses Through XOR-Based Placement Functions”, 1997.
Zorn et al., “A Memory Allocation Profiler for C and Lisp Programs,” published Feb. 16, 1988, pp. 1-18.
Diwan et al., “Memory-System Performance of Programs with Intensive Heap Allocation,” ACM TOCS vol. 13, Issue 3, Aug. 1995, ISSN: 0734-2071, 30 pages.
Cifuentes, “Structuring Decompiled Graphs,” Technical Report May 1994, Faculty of Information Technology, Queensland University of Technology, GPO Box 2434, Brisbane 4001, Australia (Apr. 1994), 15 pages.
Hauck, “Configuration Prefetch for Single Context Reconfigurable Coprocessors,” In Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays (Feb. 1998), pp. 65-74.
Ung et al., “Optimising Hot Paths in a Dynamic Binary Translator,” In Workshop on Binary Translation, Oct. 2000, pp. 55-65.
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.
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

Affiliated with

Also associated with

Rating

Dynamic prefetching 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 Dynamic prefetching of hot data streams, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic prefetching of hot data streams will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4288905