Method and Apparatus for Execution of a Process

• US 20080222362A1
• Filed: 05/27/2008
• Published: 09/11/2008
• Est. Priority Date: 05/01/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Smith, John R., Lang, Christian A., Chang, Yuan-Chi, Stanoi, Ioana R.
• Granted Patent: US 8,171,226 B2
• Time in Patent Office: Days
• US Class Current: 711/133
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 2212/602 Details relating to cache prefetching
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/10 Office automation; Time management

Abstract

Techniques are provided for enabling execution of a process employing a cache Method steps can include obtaining a first probability of accessing a given artifact in a state S_i, obtaining a second probability of using a predicate from a current state S_c in the state S_i, determining a benefit of prefetching the given artifact using the predicate based on at least the first probability and the second probability, and whether and/or when a cache replacement should be conducted, based at least on the benefit determined.

Claims

1. A method for enabling execution of a process employing a cache, comprising:

obtaining a first probability of accessing a given artifact in a state S_i;

obtaining a second probability of using a predicate from a current state S_c in said state S_i;

determining a benefit of prefetching said given artifact using said predicate based on at least said first probability and said second probability; and

evaluating at least one of;

(i) whether and

(ii) when

a cache replacement should be conducted for the cache, based at least on said benefit determined in said step of determining said benefit

2. The method of claim 1, wherein:

said obtaining of said first and second probabilities is conducted to yield additional artifacts that are candidates for prefetching;

said step of determining said benefit of prefetching includes determining additional benefits for said additional artifacts; and

said evaluating step is based at least on said additional benefits.

3. The method of claim 2, wherein said evaluating step is further based at least on an approximate time until execution.

4. The method of claim 2, wherein said evaluating step is further based at least on a retrieval cost.

5. The method of claim 2, wherein said step of obtaining said first probability comprises estimating said first probability based on at least one of knowledge of said current state S_c and knowledge of structure of the process

6. The method of claim 5, wherein said step of obtaining said first probability further comprises estimating said first probability based on knowledge of past traces of the process

7. The method of claim 2, wherein said step of obtaining said second probability comprises:

calculating correlations between a plurality of predicates in a plurality of different states, said predicate from said current state S_c being one of said plurality of predicates, said current state S_c and said state S_i being ones of said plurality of different states, said calculation being based on stored past traces of the process; and

estimating said second probability of using said predicate from said current state S_c in said state S_i, said estimating being based on said correlations from said step of calculating said correlations.

8. The method of claim 2, wherein:

the process facilitates user-initiated queries, refresh background queries, and prefetch background queries; and

said step of determining said benefit comprises at least assigning priority for incoming ones of said refresh background queries and said prefetch background queries

9. The method of claim 8, wherein said evaluating step comprises:

instantiating a data structure that stores said refresh background queries and said prefetch background queries in priority, each of said refresh background queries and said prefetch background queries having a priority number;

running a thread to select a highest priority one of said refresh background queries and said prefetch background queries; and

responsive to receipt of an input query, recalculating said priorities of said refresh background queries and said prefetch background queries and reordering said refresh background queries and said prefetch background queries in accordance with said recalculating.

10. The method of claim 9, wherein said user-initiated queries are assigned a higher priority than said refresh background queries and said prefetch background queries

11. An apparatus for enabling execution of a process, comprising:

a process module configured to maintain current state information;

a data mining engine coupled to said process module to obtain historical data therefrom;

a prediction module coupled to said data mining engine to obtain query data therefrom; and

a process interpreter and prefetching engine coupled to said process module and said prediction module to obtain prioritization knowledge therefrom and configured to time and send queries based on said prioritization knowledge.

12. The apparatus of claim 11, wherein said process module comprises a process execution time engine and an active process model, each coupled to said data mining engine.

13. The apparatus of claim 12, wherein said active process model is configured to coordinate a run-time of the process

14. The apparatus of claim 13, wherein said process execution time engine is coupled to said process interpreter and prefetching engine for monitoring.

15. The apparatus of claim 14, further comprising a business artifact pool configured for input to said process interpreter and prefetching engine

16. The apparatus of claim 11, wherein said query data from said data mining engine comprises access probability, query confidence data, task timing data, and query timing data.

17. The apparatus of claim 16, wherein said query timing data is based on query semantic knowledge and expected query selectivity.

18. The apparatus of claim 11, wherein said prediction module comprises a prediction table configured to maintain priority metadata.

19. A computer program product comprising a computer useable medium having computer useable program code for enabling execution of a process employing a cache, said computer program product including:

computer useable program code for obtaining a first probability of accessing a given artifact in a state S_i;

computer useable program code for obtaining a second probability of using a predicate from a current state S_c in said state S_i;

computer useable program code for determining a benefit of prefetching said given artifact using said predicate based on at least said first probability and said second probability; and

computer useable program code for evaluating at least one of;

(i) whether and

(ii) when

a cache replacement should be conducted for the cache, based at least on said benefit prefetching said artifact.

20. An apparatus for enabling execution of a process employing a cache, comprising:

a memory; and

at least one processor coupled to said memory and operative to;

obtain a first probability of accessing a given artifact in a state S_i;

obtain a second probability of using a predicate from a current state S_c in said state S_i;

determine a benefit of prefetching said given artifact using said predicate based on at least said first probability and said second probability; and

evaluate at least one of;

(i) whether and

(ii) when

a cache replacement should be conducted for the cache based at least on said benefit of prefetching said artifact.