Method for scheduling contexts based on statistics of memory system interactions in a computer system

• US 6,442,585 B1
• Filed: 11/26/1997
• Issued: 08/27/2002
• Est. Priority Date: 11/26/1997
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Compaq Computer Corporation (HP Inc.)
• Inventors: Waldspurger, Carl A., Dean, Jeffrey A.
• Primary Examiner(s): Maung, Zarni
• Assistant Examiner(s): OPIE, GEORGE L
• Application Number:
  US08/980,105
• Time in Patent Office: 1,735 Days
• Field of Search: 709/100, 709/102, 709/104, 709/107, 709/108, 717/127, 717/131
• US Class Current: 718/108
• CPC Class Codes: G06F 12/0842 for multiprocessing or multitasking
• CPC Class Codes: G06F 9/5016 the resource being the memory

Abstract

A method schedules execution contexts in a computer system based on memory interactions. The computer system includes a processor and a hierarchical memory arranged in a plurality of levels. Memory transactions are randomly sampled for a plurality of contexts. The contexts can be threads, processes, or hardware contexts. Resource interactions of the plurality of contexts is estimated, and particular contexts are chosen to be scheduled based on the estimated resource interactions.

Claims

1. A method for scheduling contexts in a computer system including at least one processor and a hierarchical memory arranged in a plurality of levels, a plurality of memory transactions occurring within the hierarchical memory while the system operates under a real workload, the method comprising the steps of:

applying a selection function to the plurality of memory transactions as the transactions occur within the memory to determine whether to record state information for any memory transaction meeting the selection function, the state information including context of the memory transaction, the context being taken from one of a plurality of contexts for the plurality of memory transactions;

capturing and recording the state information for any transaction if any transaction meets the selection function;

estimating information relating to memory interactions among the transaction contexts by analyzing the recorded state information; and

scheduling contexts in the computer system based on the memory interaction information.

2. A method as recited in claim 1, wherein the step of estimating includes the steps of:

selecting a subset of the recorded sampled state information that is associated with at least one pair of consecutive accesses to a particular cache location of the memory hierarchy, each pair of accesses including a first access to the particular cache location by a first context, and a second access to the particular cache location by a second context, wherein the second access is a cache miss; and

statistically estimating metrics indicative of inter-context conflicts for the particular cache location based on the subset of recorded state information.

3. A method as recited in claim 2, wherein the step of scheduling includes scheduling the contexts in order to minimize inter-context conflicts.

4. A method as recited in claim 1, wherein the step of estimating includes the steps of:

selecting a subset of the recorded state information, the subset including state information associated with at least one pair of consecutive accesses to a particular cache location of the memory hierarchy during a time interval, each pair including a first and a second access to the particular cache location, wherein the second access is a cache hit;

determining contexts that usefully shared the particular cache location during the time interval; and

statistically estimating metrics indicative of inter-context sharing of the particular cache location.

5. A method as recited in claim 4, wherein the step of scheduling includes scheduling the contexts in order to maximize inter-context sharing.

6. A method as recited in claim 1, wherein the step of estimating includes the steps of:

selecting a subset of the recorded state information that is associated with at least one pair of consecutive accesses to a particular cache block of the memory hierarchy; and

estimating state transitions in the cache protocol for the particular cache block.

7. A method as recited in claim 1,

wherein the memory interaction information is dynamically estimated while processing the memory transactions;

and

wherein the contexts are dynamically scheduled in response to the dynamically estimated memory interaction information.

8. A method as recited in claim 1, wherein the step of estimating includes the steps of:

selecting a subset of the recorded state information that is associated with at least one pair of consecutive accesses to a particular cache block of the memory hierarchy; and

estimating intra-context or inter-context sharing or conflicts for the particular cache block.

9. A method as recited in claim 1, wherein the selection function is configured to select a plurality of multiple consecutive memory transactions specifying access of a particular region of a particular one of the levels of the memory hierarchy.

10. A method as recited in claim 1,

wherein the selection function is configured to select a plurality of multiple consecutive memory transactions specifying access to a particular memory location of a particular one of the levels of the memory hierarchy;

and

wherein the step of estimating includes statistically estimating metrics indicative of conflicts between at least two of the contexts for access to the particular memory location.

11. A method as recited in claim 1,

wherein the selection function is configured to select a plurality of multiple consecutive memory transactions specifying access to a particular cache region of the memory hierarchy;

and

wherein the step of estimating includes statistically estimating metrics related to state transitions in the cache protocol.

12. A method as recited in claim 1,

wherein the selection function is configured to select a plurality of multiple consecutive memory transactions specifying access to a particular cache region of the memory hierarchy;

and

wherein the step of estimating includes statistically estimating metrics indicative of cache conflict rates.

13. A method as recited in claim 1, wherein the step of scheduling includes scheduling the contexts so that the scheduled contexts have specified memory sharing.

14. A method as recited in claim 1, wherein the step of scheduling includes scheduling the contexts so that the contexts that underutilize their allocated memory are favored in the scheduling order.

15. A method of scheduling as recited in claim 1,

further comprising:

prior to applying the selection function, applying a trigger function to the plurality of memory transactions to find any transactions that match the trigger function; and

counting any memory transactions that match the trigger function; and

wherein the step of applying a selection function includes applying the selection function to any matching transactions, after a given number of matching transactions has occurred.

16. A method of scheduling as recited in claim 15,

wherein the selection function includes a register that stores a number indicating a region of memory;

and

wherein memory transactions that occur within the indicated region of memory meet the selection function.

17. A method of scheduling as recited in claim 16, wherein the number indicating a region of memory is randomly modified to cause the regions of memory, within which transactions meeting the selection occur, to be randomized.

18. A method of scheduling as recited in claim 15, wherein the given number of matching transactions is a number chosen randomly from an interval of numbers.

19. A method for scheduling contexts in a computer system including at least one processor and a hierarchical memory arranged in a plurality of levels, a plurality of memory transactions occurring within the hierarchical memory while the system operates under a real workload, the method comprising the steps of:

applying a selection function to the plurality of memory transactions as the transactions occur within the memory to determine whether to record state information for any memory transaction meeting the selection function, the state information including context of the memory transaction, the context being taken from one of a plurality of contexts for the plurality of memory transactions;

capturing and recording the state information for any transaction if any transaction meets the selection function;

estimating information relating to memory reference patterns among the transaction contexts by analyzing the recorded information; and

determining a scheduling order for the plurality of contexts based on the estimated memory reference pattern information such that the scheduled contexts have compatible estimated memory reference patterns.

20. A method as recited in claim 19, wherein the step of determining includes determining a scheduling order for each of the plurality of contexts such that the scheduled contexts have minimal memory conflicts.

21. A method as recited in claim 19, wherein the step of determining includes determining a scheduling order for each of the plurality of contexts such that the scheduled contexts have specified memory sharing.

22. A method as recited in claim, 19, wherein the step of determining includes determining a scheduling order for each of the plurality of contexts such that the contexts that underutilize their allocated memory are favored in the scheduling order.

23. A method as recited in claim 19, wherein the memory reference pattern information includes cache memory reference pattern information.

24. A method as recited in claim 19, wherein the step of estimating includes the steps of:

selecting a subset of the recorded state information that is associated with at least one pair of consecutive accesses to a particular cache location of the memory hierarchy, each pair of accesses including a first access to the particular cache location by a first context and a second access to the particular cache location by a second context, wherein the second access is a cache miss; and

statistically estimating metrics indicative of inter-context conflicts for the particular cache location based on the subset of recorded state information.

25. A method as recited in claim 19,

wherein the memory reference pattern information is dynamically estimated while processing the memory transactions;

and

wherein the contexts are dynamically scheduled in response to the dynamically estimated resource interactions.

26. A method as recited in claim 19, wherein particular ones of the plurality of contexts are scheduled for concurrent execution on the processor.

27. A method as recited in claim 19, wherein the step of estimating comprises the steps of:

selecting a subset of the recorded state information, the subset including state information associated with at least one pair of consecutive accesses to a particular cache location of the memory hierarchy during an interval time, each pair including a first access and a second access to the particular cache location, wherein the second access is a cache hit; and

determining contexts that usefully shared the particular cache location during the interval time; and

statistically estimating metrics indicative of inter-context sharing of the particular cache location.

28. A method as recited in claim 19, wherein the step of estimating includes the steps of:

selecting a subset of the recorded state information that is associated with at least one pair of consecutive accesses to a particular cache block of the memory hierarchy; and

estimating state transitions in the cache protocol for the particular cache block to determine the estimated memory reference pattern information.

29. A method as recited in claim 19, wherein the step of estimating includes the steps of:

selecting a subset of the recorded state information that is associated with at least one pair of consecutive accesses to a particular cache block of the memory hierarchy; and

statistically estimating information indicative of intra-context or inter-context sharing or conflicts for the particular cache block.

30. A method as recited in claim 19, wherein the selection function is configured to select a plurality of multiple consecutive memory transactions specifying access of a particular region of a particular one of the levels of the memory hierarchy.

31. A method as recited in claim 19,

wherein the selection function is configured to select a plurality of multiple consecutive memory transactions specifying access of a particular memory location of a particular one of the levels of the memory hierarchy;

and

wherein the step of estimating includes statistically estimating metrics indicative of conflicts of access to the particular memory location between at least two of the contexts in order to determine the estimated memory reference pattern information.

32. A method as recited in claim 19,

wherein the selection function is configured to select a plurality of multiple consecutive memory transactions specifying access to a particular memory location of a particular one of the levels of the memory hierarchy;

and

wherein the step of estimating includes statistically estimating metrics indicative of a sharing of the particular memory location by at least two of the contexts.