High speed methods for maintaining a summary of thread activity for multiprocessor computer systems

• US 6,886,162 B1
• Filed: 07/31/1998
• Issued: 04/26/2005
• Est. Priority Date: 08/29/1997
• Status: Expired due to Fees

• Current Assignee: Sequent Computer Systems, Inc. (International Business Machines Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: McKenney, Paul E.
• Primary Examiner(s): BANANKHAH, MAJID A
• Application Number:
  US09/127,085
• Time in Patent Office: 2,461 Days
• Field of Search: 718/100, 718/102, 718/104, 718/106, 718/107, 711/120, 711/121, 711/124, 711/147, 711/149, 711/158, 709/100, 709/101, 709/102, 709/103, 709/104, 709/106, 709/108, 709/105
• US Class Current: 718/102
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A high-speed method for maintaining a summary of thread activity reduces the number of remote-memory operations for an n processor, multiple node computer system from n² to (2n−1) operations. The method uses a hierarchical summary of-thread-activity data structure that includes structures such as first and second level bit masks. The first level bit mask is accessible to all nodes and contains a bit per node, the bit indicating whether the corresponding node contains a processor that has not yet passed through a quiescent state. The second level bit mask is local to each node and contains a bit per processor per node, the bit indicating whether the corresponding processor has not yet passed through a quiescent state. The method includes determining from a data structure on the processor'"'"'s node (such as a second level bitmask) if the processor has passed through a quiescent state. If so, it is then determined from the data structure if all other processors on its node have passed through a quiescent state. If so, it is then indicated in a data structure accessible to all nodes (such as the first level bitmask) that all processors on the processor'"'"'s node have passed through a quiescent state. The local generation number can also be stored in the data structure accessible to all nodes. If a processor determines from this data structure that the processor is the last processor to pass through a quiescent state, the processor updates the data structure for storing a number of the current generation stored in the memory of each node.

Claims

1. In a multiprocessor computer system having multiple interconnected processing nodes cach with one or more processors and physical memory, a data structure for storing execution history data indicating of states of threads that are used for providing mutual exclusion between current and next generation data elements, comprising:

a first level bit mask stored in physical memory accessibe to all nodes and containing a bit per node, the bit indicating whether the corresponding nodes contains a processor that has not yet passed through a quiescent state; and

a second level bit mask stored in the physical memory of each processing node and containing a bit per processor associated with a particular node identified in the first level bit mask, the bit indicating whether the corresponding processor has not yet passed through a quiescent state.

2. In a multiprocessor computer system having multiple interconnected processing nodes each with one or more processors and physical memory, a data structure stored in the physical memory on each node for storing a number of the current generation of data elements being processed by a processor on a node, the data structure comprising a variable stored in the physical memory of each node and containing the current generation number, wherein the current generation number on the nodes are updated in lockstep so that the nodes have local access to copies of the current generation number.

3. In a multiprocessor computer system having multiple interconnected processing nodes each with one or more processors and physical memory, a method for a processor to maintain a summary of thread activity as part of a method for providing mutual exclusion between current and next generation data elements, comprising:

determining from a first data structure on the processor'"'"'s node if the processor has passed through a quiescent state;

if so, determining from a second data structure on the processor'"'"'s node if all other processors on its node have passed through a quiescent state; and

if so, indicating in a third data structure accessible to all nodes that all processors on the processor'"'"'s node have passed through a quiescent state.

4. The method of claim 3 wherein if the processor determines from the first data structure on the processor'"'"'s node that the processor has not passed through a quiescent state, having a callback processor check if the processor has passed through a quiescent state and, if so, having the processor indicate in the data structure that it has passed through a quiescent state.

5. The method of claim 3 wherein if the processor determines from the third data structure accessible to all nodes that the processor is the last processor to pass through a quiescent state, having the processor update a fourth data structure stored in the memory of each node for storing a number of the current generation of elements being processed on the node.

6. The method of claim 3 wherein if the processor determines from the third data structure accessible to all nodes that it is the last processor to pass through a quiescent state, having a callback processor determine if them are callbacks waiting for a subsequent generation, and, if so, updating the first data structure on each node and the third data structure accessible to all nodes to indicate that all processors need to pass through an additional quiescent state.

7. The method of claim 3, wherein the first, second, and third data structures are the same data structure.

8. The method of claim 3, wherein the first and second data structures are the same data structure.

9. The method of claim 3, wherein the second and third data structures are the same data structure.

10. The method of claim 3, wherein the first and third data structures are the same data structure.