Trace ranking in a dynamic translation system
Filing Information
- Patent Number: US6219827
- Application Number: US9041350
- Filing date: 03/12/1998
- Issue date: 04/17/2001
- Predicted expiration date: 03/12/2018
View assignee updates
analyzing 100 million+ documents to uncover your network...- U.S. Classifications: 717/4 · 711/135 · 711/134 · 711/136 · 711/133 ·
- International Classifications: --
- International Classifications: 711133-136 · 714 34- 35 · 395704 · 717 4 ·
Abstract
A method and system of trace ranking that applies artificial life principles to determine a predictively accurate ranking for cache retention or discard of traces. In a preferred embodiment, the ranking system is based upon biological modeling of ant trails. The system can enable a trace ranking policy where valuable traces can be identified to be kept in the cache as much as possible, while less valuable traces can be marked to discard. The system is further dynamic over time, whereby ranking emphasis changes in accordance with the dynamic behavior of the program. According to a preferred embodiment of the inventive trace ranking system, and analogous to the ant trail model, each trace contains counting code so that each time it is executed it increments a ranking counter by one. At predetermined intervals a dissipation factor is applied uniformly to reduce the value of all counters. By tuning the period between successive dissipation adjustments, and by tuning to a function the amount that the counters are reduced at selected dissipation operations, ranking becomes tunably predictive of the dynamic behavior of the program, analogous to the way in which the strength of a pheromone trail is predictive of the route followed by a foraging ant.References Cited
U.S. Patent Documents
| Document Number | Assignees | Inventors | Issue/Pub Date |
|---|---|---|---|
| US5305389* | Digital Equipment Corporation | Palmer | Apr 1994 |
| US5668987* | Sybase, Inc. | Schneider | Sep 1997 |
| US5822759* | Versant Object Technology | Treynor | Oct 1998 |
| US5894575* | International Business Machines Corporation | Levine et al. | Apr 1999 |
| US5943687* | Telefonakiebolaget LM Ericsson | Liedberg | Aug 1999 |
| US6041406* | Advanced Micro Devices, Inc. | Mann | Mar 2000 |
Other Publications
| Chen et al. Performance of Shared Cache on Multithreaded Architectures. IEEE. pp. 541-548, 1996.* |
| Shahrier et al. On Predictability and Optimization of Multiprogrammed Caches for Real-time Applications. IEEE, 1997.* |
| Nobue. Method and Device For Firmware Tracing. Patent Abstracts of Japan, Unexamined Applications, Section: P, Sect. No. 1439, Vol. 16, No. 5, P. 19, Oct. 1992.* |
Referenced By
| Document Number | Assignee | Inventors | Issue/Pub Date |
|---|---|---|---|
| US6470492 | Hewlett-Packard Company | Vasanth Bala et al. | Oct 2002 |
| US7191293 | ARM Limited | Daryl Wayne Bradley et al. | Mar 2007 |
| US7284238 | International Business Machines Corporation | Iwao Inagaki et al. | Oct 2007 |
Patent Family
| Document Number | Assignee | Inventors | Issue/Pub Date |
|---|---|---|---|
| JP11328031 | HEWLETT PACKARD CO | RICHARD F MAN | Nov 1999 |
| US6219827 | Hewlett-Packard Company | Richard F. Man | Apr 2001 |
Independent Claims | See all claims (34)
- 1. A method for ranking traces generated during execution of a software program, said execution monitored by a dynamic translation system, the traces stored in a cache and disposed to be periodically discarded therefrom based on said ranking, the method comprising the steps of: (a) initially assigning an preselected initial rank value to each of a plurality of traces; (b) each time one of the traces executes, increasing the rank value thereof; and (c) periodically reducing the rank value of selected traces by a dissipation factor; wherein the dissipation factor is the current value of a variable.
- 14. A method for ranking traces generated during execution of a software program, said execution monitored by a dynamic translation system, the traces stored in a cache and disposed to be periodically discarded therefrom based on said ranking, the method comprising the steps of: (a) initially assigning an preselected initial rank value of zero to each of a plurality of traces; (b) each time one of the traces executes, increasing the rank value thereof by one; (c) periodically, at regular predetermined intervals, reducing the rank value of all traces by a dissipation factor; and (d) resetting to zero those rank values having a value less than zero following step (c); wherein the dissipation factor is the current value of a variable.
- 18. A computer program product including computer readable logic recorded thereon for enabling a computer to rank traces generated during execution of software undergoing dynamic translation, the computer having a processor and memory including cache, the traces stored in the cache and disposed to be periodically discarded therefrom based on said ranking, the computer program product comprising: a computer-readable storage medium; and a computer program stored on the computer-readable storage medium, the computer program comprising: means for initially assigning a preselected initial rank value to each of a plurality of traces; means, responsive to execution of a trace in the plurality, for increasing the corresponding rank value of said executed trace; means for periodically reducing the rank value of selected traces by a dissipation factor, wherein the dissipation factor is the current value of a variable; and means for periodically adjusting the dissipation factor according to a function of selected current rank values.
- 24. A trace ranking system for use in a dynamic translation system, the dynamic translation system monitoring execution of a software program from which traces are generated and then stored in a cache, the trace ranking system comprising: means for initially assigning a preselected initial rank value to each of a plurality of traces; means, responsive to execution of a trace in the plurality, for increasing the corresponding rank value of said executed trace; means for periodically reducing the rank value of selected traces by a dissipation factor; and means for periodically and selectively discarding traces from the cache according said discarded traces current rank values; wherein the dissipation factor is the current value of a variable.
