Token-based serialisation of instructions in a multiprocessor system

• US 5,761,734 A
• Filed: 08/13/1996
• Issued: 06/02/1998
• Est. Priority Date: 08/13/1996
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Getzlaff, Klaus-Joerg, Tast, Hans-Werner, Pfeffer, Erwin, Gaertner, Ute
• Primary Examiner(s): Treat, William M.
• Application Number:
  US08/689,762
• Time in Patent Office: 658 Days
• Field of Search: 395/377, 395/200.31, 395/676, 395/800.18, 711/163, 711/164, 711/141
• US Class Current: 711/164
• CPC Class Codes: G06F 12/1072 Decentralised address translation, e.g. in distributed shared memory systems
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A process is disclosed to serialize instructions that are to be processed serially in a multiprocessor system, with the use of a token, where the token can be assigned on request to one of the processors, which thereupon has the right to execute the command. If the command consists of dristibuted tasks, the token remains blocked until the last dependent task belonging to the command has also been executed. It is only then that the token can be assigned to another instruction. Moreover, a device is described to manage this token, which features three states: a first state, in which the token is available, a second state, in which the token is assigned to one of the processors, and a third state, in which the token is blocked, because dependent tasks still have to be carried out. Moreover, a circuit is disclosed with which the token principle that is introduced can be implemented in a simple manner. The token is only available if none of the processors i is in possession of the token and if no dependent task is pending at any of the processors. The OR chaining of signals to form a signal C which is set if the token is not available represents the basic circuitry with which the serialisation of commands consisting of distributed tasks is carried out. The invention is applied particularly in the case of commands such as IPTE (invalidate page-table entry) and SSKE (set storage key extended), which modify the address translation tables in the memory that are used in common by all processors.

Claims

1. Device to manage a token for the serialisation of instructions which are to be processed serially in a multiprocessor system, characterised in that a processor can only execute one of the instructions which are to be processed serially if it is in possession of a token, and the device to manage the token features the following states:

a first state, in which the token is not assigned to any of the processors, and the token can be assigned to a processor which requests the token;

a second state, in which the token is assigned to one of the processors, and the token cannot be assigned to a processor which requests the token; and

a third state, in which the token is not assigned to any of the processors, and the token cannot be assigned to a processor which requests the token.

2. Device to manage a token according to claim 1, characterised in that the multiprocessor system comprises n processors:

for each processor I, for which an Ai signal is available which is set when processor i is in possession of the token;

for each processor i, for which a Bi signal is available, which is set when a task which has not yet been completely executed is pending at processor i, which task must be serialised with the execution of one of the instructions which are to be processed serially, on account of which the token cannot be assigned to a processor which requests the token;

and a signal C is available, which is common to the entire multiprocessor system, and which results from the OR chaining of the A1, . . . An, B1, . . . Bn signals of all processors, which have been listed already, and which is set when the token cannot be assigned to a requesting processor;

where the first status of the device to manage a token is characterised in that none of the signals A1, . . . An, B1, . . . Bn is set;

where the second state of the device to manage a token is characterised in that one of the signals A1, . . . An is set;

and where the third state of the device to manage a token is characterised in that none of the signals A1, . . . An is set, but at least one of the signals B1, . . . Bn is set.

3. Device to manage a token according to claim 2, characterised in that for each processor i, one signal Ci is available which results from an OR chaining of the Ai and Bi signals;

and the C signal which is common to the entire multiprocessor system results from an OR chaining of the C1, . . . Cn signals of all the processors.

4. Device to manage a token according to claim 2, characterised in that for each processor i, one signal is available which is set when the processor i requests the token,

and which is present together with the inverted C signal at the input of an AND gate whose output is the Ai signal.

5. Device to manage a token according to claim 1, characterised in that the instructions which are to be processed serially comprise a first task to be executed on the initiating processor as well as dependent tasks to be executed on the responder processors,

where the token must be assigned to the initiating processor so that the initiating processor can execute the first task,

and where the token cannot be assigned to a processor which requests the token until the completion of all dependent tasks.

6. Device to manage a token according to claim 5, characterised in that an instruction buffer is allocated to every processor in the multiprocessor system,

during the execution of the first task, the initiating processor writes commands and/or addresses into the instruction buffers of the responder processors, which commands and/or addresses specify the dependent tasks to be executed on the responder processors.

7. Device to manage a token according to claim 5, characterised in that during the execution of a first task, the initiating processor writes commands and/or addresses into the instruction buffers of the responder processors by means of a Broadcast Forced Operation, which commands and/or addresses specify the dependent tasks to be executed on the responder processors.

8. Device to manage a token according to claim 5, characterised in that during the execution of the first task, the initiating processor writes commands and/or addresses into the instruction buffers of the responder processors,

where the Bi signal is also set with the writing into the instruction buffer of the responder processor i.

9. Device to manage a token according to claim 8, characterised in that on completion of the dependent task pending at the responder processor i, (the Bi signal is reset).

10. Device to manage a token according to claim 5, characterised in that the dependent tasks are inserted and executed at an interruptible point in the instruction flow of the responder processors.

11. Device to manage a token according to claim 5, characterised in that the multiprocessor system comprises a memory,

in order to address the memory, a translation of virtual addresses into real ones can be undertaken with the help of address translation tables,

address translations which have already been carried out are stored in one of the address translation caches, each of which is assigned to one of the processors,

the instruction that is to be processed serially is an instruction to invalidate a page-table entry (IPTE),

where the initiating processor invalidates the page-table entry during the execution of the first task,

and where, during the execution of the dependent tasks, the other processors invalidate corresponding entries in the address translation caches assigned to them.

12. Device to manage a token according to claim 5, characterised in that the multiprocessor system comprises a memory,

in order to address the memory, a translation of virtual addresses into real ones can be undertaken with the help of address translation tables,

address translations which have already been carried out are stored in address translation caches, each of which is assigned to one of the processors,

key information to stipulate the access rights of the individual processors to a page is stored in a part of the memory, namely the key storage,

the instruction that is to be processed serially is an instruction to modify the key information (SSKE),

where the initiating processor modifies the key information in the key storage during the execution of the first task, and where, during the execution of the dependent tasks, the other processors modify the key information in the address translation caches that are assigned to them.

13. Process to serialise instructions which are to be processed serially in a multiprocessor system,

in which the execution of one of the instructions that are to be processed serially comprises the execution of a first task on an initiating processor,

in which the initiating processor can only execute the first task if it is in possession of a token, and

in which the token, if it is available, can be assigned to precisely one of the processors,

which comprises the following steps:

request for the token by the initiating processor;

assignment of the token to the initiating processor, if the token is available;

execution of the instruction that is to be processed serially;

replacement of the token after the completion of the first task of the instruction that is to be processed serially, whereby the token does not necessarily have to become available to other processors;

establishment of the availability of the token after the completion of the instruction that is to be processed serially.

14. Process to serialise instructions that are to be processed serially, according to claim 13, characterised in that one Ai signal is available for each processor i,

on allocation of the token to the initiating processor i, the signal Ai (token received) is set,

and the signal Ai is reset on replacement of the token after the completion of the first task.

15. Process to serialise instructions that are to be processed serially, according to claim 13, characterised in that the execution of the instructions that are to be processed serially comprises the execution of the first task on the initiating processor as well as the execution of dependent tasks on responder processors;

and

the availability of the token is established on conclusion of all dependent tasks.

16. Process to serialise instructions that are to be processed serially, according to claim 15, characterised in that one Bi signal is available for each processor i, the Bi signal is set if the execution of a dependent task is pending at the processor i,

the Bi signal is reset on completion of the execution of the dependent task.

17. Process to serialise instructions that are to be processed serially, according to claim 15, characterised in that the dependent tasks are inserted and executed at an interruptible point of the instruction flow of the responder processors.

18. Process to serialise instructions that are to be processed serially, according to claim 15, characterised in that an instruction buffer is assigned to each processor in the multiprocessor system,

during the execution of the first task, the initiating processor writes commands and/or addresses into the instruction buffers of the responder processors, which commands and/or addresses specify the dependent tasks to be executed on the responder processors.

19. Process to serialise instructions that are to be processed serially, according to claim 15, characterised in that during the execution of the first task, the initiating processor writes commands and/or addresses into the instruction buffers of the responder processors by means of a Broadcast Forced Operation, which commands and/or addresses specify the dependent tasks to be executed on the responder processors.

20. Process to serialise instructions that are to be processed serially, according to claim 18, characterised in that the Bi signal is also set with the writing into the instruction buffer of the responder processor I.

21. Process to serialise instructions that are to be processed serially, according to claim 15, characterised in that the multiprocessor system comprises a memory,

in order to address the memory, a translation of virtual addresses into real ones can be undertaken with the help of address translation tables,

address translations which have already been carried out are stored in address translation caches, each of which is assigned to one of the processors,

the instruction that is to be processed serially is an instruction to invalidate a page-table entry (IPTE),

where the initiating processor invalidates the page-table entry during the execution of the first task,

and where, during the execution of the dependent tasks, the other processors invalidate corresponding entries in the address translation caches assigned to them.

22. Process to serialise instructions that are to be processed serially, according to claim 15, characterised in that the multiprocessor system comprises a memory,

in order to address the memory, a translation of virtual addresses into real ones can be undertaken with the help of address translation tables,

address translations which have already been carried out are stored in address translation caches, each of which is assigned to one of the processors,

key information to stipulate the access rights of the individual processors to a page is stored in a part of the memory, namely the key storage,

the instruction that is to be processed serially is an instruction to modify the key information (SSKE),

where the initiating processor modifies the key information in the key storage during the execution of the first task,

and where, during the execution of dependent tasks, the other processors modify the key information in the address translation caches that are assigned to them.

23. Process to serialise instructions that are to be processed serially, according to claim 21, characterised in that the address translation cache is n-fold associative,

and an instruction which requires more than n address translations is serialised with the instruction to invalidate a page-table entry (IPTE).

24. Process to serialise instructions that are to be processed serially, according to claim 23, characterised in that the token must be assigned to a processor i in order that the processor i can execute the instruction which requires more than n address translations.