Token manager for execution of global operations utilizing multiple tokens

Abstract

Serialization of global operations within a multi-processor system is achieved utilizing a plurality of tokens each permitting completion of a single global operation, requiring a bus master to acquire the token for completion of each individual global operation initiated by that bus master. A combined token and operation request, in which a token request and an operation request are transmitted in a single bus transaction, is employed once for a global operation, to initiate the global operation for the first time. A token manager determines whether a token is available or all are checked out and responds to the token portion of the combined request. Snoopers respond to the operation portion of the combined request depending on whether they are busy. If at least the token portion of the combined request is acknowledged or if a token request is acknowledged, the combined response will include a token number for the token granted to the bus master initiating the global operation. The token manager allows only n bus masters to own a token at a time (where n is the number of token supported), and infers release of a token from a combined response acknowledging a combined request or an operation request containing the token number assigned to a global operation.

Claims

What is claimed is:

1. A method of enabling global operations within a multiprocessor system, comprising:

supporting a bus transaction including a token request portion for seeking one of a plurality of tokens within the multiprocessor system required to complete one global operation and an operation request portion for identifying a global operation to be processed with a token, if granted;

supporting a first combined response to the bus transaction acknowledging both the token request portion and the operation request portion;

supporting a second combined response to the bus transaction acknowledging the token request portion but retrying the operation request portion; and

supporting a third combined response to the bus transaction retrying both the token request portion and the operation request portion.

2. The method of claim 1, wherein the bus transaction is a first bus transaction, the method further comprising:

supporting a second bus transaction including a token request for seeking the single token without an operation request.

3. The method of claim 2, further comprising:

supporting a third bus transaction including an operation request identifying the global operation to be processed without a token request.

4. The method of claim 3, further comprising: responsive to receiving an acknowledge response to both the token request portion and the operation request portion of the first bus transaction from all bus participants, driving the first combined response to the first bus transaction.

5. The method of claim 4, further comprising:

responsive to receiving an acknowledge response to the token request portion of the first bus transaction from all bus participants but a retry response to the operation request portion of the first bus transaction from at least one bus participant, driving the second combined response to the first bus transaction.

6. The method of claim 5, further comprising:

responsive to receiving a retry response to the token request portion of the first bus transaction from at least one bus participant, driving the third combined response to the first bus transaction.

7. A bus protocol for global operations within a multiprocessor system, comprising:

a bus transaction including a token request portion for seeking a single token within the multiprocessor system required to complete one global operation and an operation request portion for identifying a global operation to be processed with the token;

a first combined response to the bus transaction acknowledging both the token request portion and the operation request portion;

a second combined response to the bus transaction acknowledging the token request portion but retrying the operation request portion; and

a third combined response to the bus transaction retrying both the token request portion and the operation request portion.

8. The bus protocol of claim 7, wherein the bus transaction is a first bus transaction, the bus protocol further comprising:

a second bus transaction including a token request for seeking the single token without an operation request.

9. The bus protocol of claim 8, further comprising:

a third bus transaction including an operation request identifying the global operation to be processed without a token request.

10. The bus protocol of claim 9, wherein the first combined response to the first bus transaction is driven in response to receiving an acknowledge response to both the token request portion and the operation request portion of the first bus transaction from all bus participants.

11. The bus protocol of claim 10, wherein the second combined response to the first bus transaction is driven in response to receiving an acknowledge response to the token request portion of the first bus transaction from all bus participants but a retry response to the operation request portion of the first bus transaction from at least one bus participant.

12. The bus protocol of claim 11, wherein the third combined response to the first bus transaction is driven in response to receiving a retry response to the token request portion of the first bus transaction from at least one bus participant.

13. A method of serializing global operations within a multiprocessor system, comprising:

responsive to detecting a bus transaction including a token request portion seeking a single token within the multiprocessor system required to complete one global operation and an operation request portion identifying a global operation to be processed with the token, determining whether the token is available;

responsive to determining that the token is not available, driving a retry response to the bus transaction, producing a combined response to the bus transaction retrying both the token request portion and the operation request portion; and

responsive to determining that the token is available, driving an acknowledge response to the bus transaction, producing a combined response to the bus transaction acknowledging at least the token request portion.

14. The method of claim 13, further comprising:

after driving an acknowledge response to the bus transaction, determining whether a combined response to the bus transaction acknowledges the operation request portion; and

responsive to determining that the combined response to the bus transaction acknowledges the operation request portion, treating the token as released.

15. The method of claim 14, further comprising:

responsive to determining that the combined response to the bus transaction retries the operation request portion, determining whether a combined response to a subsequent bus transaction acknowledges an operation request within the subsequent bus transaction including an address and a processor identifier from the bus transaction; and

responsive to determining that the combined response to the subsequent bus transaction acknowledges the operation request within the subsequent bus transaction, treating the token as released.

16. The method of claim 14, further comprising:

after retrying the token request portion of the bus transaction, responsive to detecting a subsequent bus transaction including a token request seeking the token, determining whether the token is available;

responsive to determining that the token is not available, driving a retry response to the subsequent bus transaction; and

responsive to determining that the token is available, driving an acknowledge response to the subsequent bus transaction.

17. The method of claim 16, further comprising:

after acknowledging the subsequent bus transaction, responsive to detecting a combined response acknowledging an operation request including a processor identifier matching a processor identifier for the subsequent bus transaction, treating the token as released.

18. A system for serializing global operations within a multiprocessor system, comprising:

a bus coupled to at least one bus master and at least one snooper; and

a token manager for the bus, wherein the token manager:

responsive to detecting a bus transaction on the bus including a token request portion seeking a single token within the multiprocessor system required to complete one global operation and an operation request portion identifying a global operation to be processed with the token, determines whether the token is available;

responsive to determining that the token is not available, drives a retry response to the bus transaction, producing a combined response to the bus transaction retrying both the token request portion and the operation request portion; and

responsive to determining that the token is available, drives an acknowledge response to the bus transaction, producing a combined response to the bus transaction acknowledging at least the token request portion.

19. The system of claim 18, wherein the token manager, after driving an acknowledge response to the bus transaction, determines whether a combined response to the bus transaction acknowledges the operation request portion, and

responsive to determining that the combined response to the bus transaction acknowledges the operation request portion, treats the token as released.

20. The system of claim 19, wherein the token manager, responsive to determining that the combined response to the bus transaction retries the operation request portion, determining whether a combined response to a subsequent bus transaction acknowledges an operation request within the subsequent bus transaction including an address and a processor identifier from the bus transaction, and

responsive to determining that the combined response to the subsequent bus transaction acknowledges the operation request within the subsequent bus transaction, treats the token as released.

21. The system of claim 19, wherein the token manager, after retrying the token request portion of the bus transaction, responsive to detecting a subsequent bus transaction including a token request seeking the token, determines whether the token is available, and

responsive to determining that the token is not available, drives a retry response to the subsequent bus transaction, and

responsive to determining that the token is available, drives an acknowledge response to the subsequent bus transaction.

22. The system of claim 21, wherein the token manager, after acknowledging the subsequent bus transaction, responsive to detecting a combined response acknowledging an operation request including a processor identifier matching a processor identifier for the subsequent bus transaction, treats the token as released.

Description

BACKGROUND OF THE INVENTION

1. Technical Field

The present invention generally relates to performance of global operations in multiprocessor systems and in particular to employing tokens to permit speculative execution of global operations within multiprocessor systems. Still more particularly, the present invention relates to implementing a bus protocol and token manager employing tokens for speculative execution of global operations within a multiprocessor system.

2. Description of the Related Art

Many operations performed within multiprocessor systems may be executed locally by a single processor without immediately involving or affecting other processors within the system. For example, a processor may write a modified cache line to a local cache without making the write operation immediately visible to all other processors. A write-back of the modified data to system memory may be deferred until a later time or combined, through a modified intervention, with a subsequent read operation by a different processor for the same cache line.

However, processors within multiprocessor systems periodically execute operations which must be globally visible to all other processors within the system. By their nature, these operations require the involvement of all other processors. For example, within the PowerPC architecture, a processor may execute an instruction cache clock invalidate (ICBI), translation lookaside buffer invalidate (TLBI), or synchronization (SYNCH) operation. A synchronizing operation, for instance, may be employed to allow prior instructions within an instruction stream executing on a pipelined, out-of-order multiprocessor system to complete before performing a context switch.

Existing designs for multiprocessor systems support global operations by implementing a queue for such operations within each processor for every other processor within the system. That is, a processor within a system having three other processors will include three queues for snooping global operations. The depth of each snoop queue will equal the latency of the combined response in order to prevent system livelocks. Thus, where a system requires five bus cycles to generate a combined response to an address transaction, the global operation queues will have a pipeline which is five levels deep.

This approach to supporting global operations is extremely hardware intensive and is not scalable. As the operating frequency and the number of processors within a system increases, driving the latency of a combined response up to close to 100 cycles, the approach described above becomes unwieldy. As the window for the combined response becomes larger, snooper implementations become more complex and costly.

It would be desirable, therefore, to to broadcast global operations in a highly scalable multiprocessor system while keeping masters and snoopers as simple as possible but also preventing system livelocks. It would also be desirable to decouple the depth of snoop queues from the width of address to combined response windows, and to maintain high frequency operation while increasing the number of processor in a system supporting global operations.

SUMMARY OF THE INVENTION

It is therefore one object of the present invention to provide improved performance of global operations in multiprocessor systems.

It is another object of the present invention to provide a mechanism for employing tokens to permit speculative execution of global operations within multiprocessor systems.

It is yet another object of the present invention to provide a bus protocol and token manager employing tokens for speculative execution of global operations within a multiprocessor system.

The foregoing objects are achieved as is now described. Serialization of global operations within a multiprocessor system is achieved utilizing a plurality of tokens each permitting completion of a single global operation, requiring a bus master to acquire the token for completion of each individual global operation initiated by that bus master. A combined token and operation request, in which a token request and an operation request are transmitted in a single bus transaction, is employed once for a global operation, to initiate the global operation for the first time. A token manager determines whether a token is available or all are checked out and responds to the token portion of the combined request. Snoopers respond to the operation portion of the combined request depending on whether they are busy. If at least the token portion of the combined request is acknowledged or if a token request is acknowledged, the combined response will include a token number for the token granted to the bus master initiating the global operation. The token manager allows only n bus masters to own a token at a time (where n is the number of token supported), and infers release of a token from a combined response acknowledging a combined request or an operation request containing the token number assigned to a global operation.

The above as well as additional objects, features, and advantages of the present invention will become apparent in the following detailed written description.

BRIEF DESCRIPTION OF THE DRAWINGS

The novel features believed characteristic of the invention are set forth in the appended claims. The invention itself however, as well as a preferred mode of use, further objects and advantages thereof, will best be understood by reference to the following detailed description of an illustrative embodiment when read in conjunction with the accompanying drawings, wherein:

FIG. 1 depicts a block diagram of a data processing system in which a preferred embodiment of the present invention may be implemented;

FIG. 2 is an address bus transaction data structure employed for global operations within a multiprocessor system in accordance with a preferred embodiment of the present invention;

FIG. 3 depicts a timing diagram for a hypothetical sequence of global operations within a multiprocessor system in accordance with a preferred embodiment of the present invention;

FIG. 4 is a high level flowchart for a process within a bus master of issuing global operations in a system employing a single token limited to one operation in accordance with a preferred embodiment of the present invention;

FIGS. 5A-5C depict a high level flow chart for a process within a bus participant of snooping global operations in a system employing a single token limited to one operation in accordance with a preferred embodiment of the present invention; and

FIG. 6 is a state diagram for token control logic in a system employing a single token for global operation limited to one operation in accordance with a preferred embodiment of the present invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

With reference now to the figures, and in particular with reference to FIG. 1, a block diagram of a data processing system in which a preferred embodiment of the present invention may be implemented is depicted. Data processing system 100 is a symmetric multiprocessor (SMP) system including a plurality of processors 102aa through 102an and 102ma through 102mn (where "m" and "n" are integer-valued variables). Each processor 102aa-102mn includes a respective level one (L1) cache 104aa-104mn, preferably on chip with the processor and bifurcated into separate instruction and data caches. Each processor 102aa-102mn is coupled via a processor bus 106aa-106l to a level two cache 108a-108l (where "l" is an integer-valued variable), which are in-line caches shared by multiple processors in the exemplary embodiment.

Although in the exemplary embodiment only two processors are depicted as sharing each L2 cache, and only two L2 caches are depicted, those skilled in the art will appreciate that additional processors and L2 caches may be utilized in a multiprocessor data processing system in accordance with the present invention. For example, each L2 cache may be shared by four processors, and a total of sixteen L2 caches may be provided.

Each L2 cache 108a-108l is connected to a level three (L3) cache 110a-110l and to system bus 112. L3 caches 110a-110l are actually in-line caches rather than lookaside caches as FIG. 1 suggests, but operations received from a vertical L2 cache (e.g., L2 cache 108a) are initiated both within the L3 cache 110a and on system bus 112 concurrently to reduce latency. If the operation produces a cache hit within the L3 cache 110a, the operation is cancelled or aborted on system bus 112. On the other hand, if the operation produces a cache miss within the L3 cache 110a, the operation is allowed to proceed on system bus 112.

The lower cache levels--L2 caches 108a-108l and L3 caches 110a-110l--are employed to stage data to the L1 caches 104a-104l and typically have progressively larger storage capacities but longer access latencies. L2 caches 108a-108l and L3 caches 110a-110l thus serve as intermediate storage between processors 102aa-102mn and system memory 114, which typically has a much larger storage capacity but may have an access latency many times that of L3 caches 100a-110l. Both the number of levels in the cache hierarchy and the cache hierarchy configuration (i.e, shared versus private, in-line versus lookaside) employed in data processing system 100 may vary.

L2 caches 108a-108l and L3 caches 110a-110l are connected to system memory 114 via system bus 112. Also connected to system bus 112 may be a memory mapped device 116, such as a graphics adapter providing a connection for a display (not shown), and input/output (I/O) bus bridge 118. I/O bus bridge 118 couples system bus 112 to I/O bus 120, which may provide connections for I/O devices 122, such as a keyboard and mouse, and nonvolatile storage 124, such as a hard disk drive. System bus 112, I/O bus bridge 118, and I/O bus 120 thus form an interconnect coupling the attached devices, for which alternative implementations are known in the art.

Non-volatile storage 124 stores an operating system and other software controlling operation of system 100, which are loaded into system memory 114 in response to system 100 being powered on. Those skilled in the art will recognize that data processing system 100 may include many additional components not shown in FIG. 1, such as serial and parallel ports, connections to networks or attached devices, a memory controller regulating access to system memory 114, etc. Such modifications and variations are within the spirit and scope of the present invention.

Each processor 102aa-102mn may initiate operations which must be globally visible within data processing system 100. A processor initiating such an operations will begin a bus transaction on a corresponding processor bus to an L2 cache, which will in turn begin a corresponding system bus transaction on system bus 112. Other L2 caches not sharing a common processor bus with the processor initiating the operation will snoop the operation off the system bus 112 and initiate a correpsonding bus transaction on the respective processor bus coupled to the L2 cache. The global operation is performed as described in further detail below.

Referring to FIG. 2, an address bus transaction data structure employed for global operations within a multi-processor system in accordance with a preferred embodiment of the present invention is illustrated. Address bus transaction data structure 202 iillustrates the token bus protocol address/response definitions for a system supporting multiple tokens limited to only one global operation per token. Address bus transaction data structure 202, which is employed on the processor and system address buses for global operations, includes: an address 202a for the target of the operation, if any; a tag 202b including a processor identifier for the processor within the system which initiates the operation; a transaction type identifier 202c designating the type of operation being initiated (i.e., ICBI, TLBI, etc.); and token management flags 202d for requesting a operation, a token, etc.

The present invention employs tokens to prevent system livelocks by conflicting global operations. Each device within the storage hierarchy which is capable of initiating a global operation on a lower level bus (processors 102aa-102mn and L2 caches 108a-108l in the exemplary embodiment of FIG. 1) contains bus interface logic for driving address bus transaction data structure 202 and for receiving and appropriately reacting to the combined response, as well as snoop logic for detecting address bus transaction data structure 202 and for driving an appropriate snoop response. Each device within the storage hierarchy which receives global operations from a higher level bus (L2 caches 108a-108l, L3 caches 100a--110l, and system memory 114 in the exemplary embodiment of FIG. 1) contains bus interface logic for detecting address bus data structure 202 and for driving an appropriate response. Additionally, a token manager is implemented, typically integrated with the bus arbitration function in a bus controller.

A bus master must request and receive a token for a global operation from the token manager before the operation may be completed. If a token is not received by the bus master, the operation must be retried. The token manager controls granting of the tokens to prevent conflict between global operations, granting a token only when available (i.e., not currently being utilized) and refusing token requests until the appropriate token is released by a current owner. The token manager thus ensures serialization of global operations.

In the present invention, a token request is submitted with the address transaction data structure 202 initiating a global operation, so that a token required to perform the operation is requested simultaneously with an attempt to initiate the operation. This avoids the latency required to request and receive a token before issuing the operation, which may then be retried anyway. Such latency may be significant as the combined response window approaches 100 cycles in systems having many processors (e.g., 128-way SMP systems).

The token management flags 202d are employed to request initiation or completion of a global operation. The token request and the operation request may be made jointly or separately to allow completion of operations which were speculatively started but retried, as described below. The possible permutations of token management flags are detailed in Table I, together with the significance of the combined flag states as an indicator of the type of request being made and the possible combined responses to each supported request are also listed. Note that token requests (only) and combined token and operation requests do not requests a specific token (merely the next available token), but that an operation request (only) contains the token number within token management flags 202d.

      TABLE 1
       Flags    Request Type         Possible combined response
        10      Token request        retry or ack
        11      Token + Op request   token ack/snoop retry
                                     ack (token & snoop)
                                     retry (token & snoop)
        01      Op request           retry or ack

• Inventors
  Arimilli, Ravi Kumar; Dodson, John Steven; Joyner, Jody B.; Lewis, Jerry Don;
• Assignee
  International Business Machines Corporation (Armonk, NY)
• Published
  Oct-1-2002
• Current US Classes:
  370/450
  710/105
  710/107
  718/100
• Application #
  435926
• International Classes
  G06F 013/14; G06F 009/50
• Field of Search
  710/107 710/40 710/110 710/5 710/240 710/105 709/100 709/201 709/209 712/30 712/31 712/220 370/450
• Examiner
  Ray; Gopal C.
• Agent
  Salys; Casimer K. Bracewell & Patterson, L.L.P.
• US Patent References:
  4870704
  5568620
  5682512
  5761734
  5774700
  5852747
  5903738
  6079013
  6119219
  6141743