Electrical computers and digital processing systems: processing – Architecture based instruction processing – Multiprocessor instruction
Reexamination Certificate
1999-04-28
2003-02-04
An, Meng-Al T. (Department: 2154)
Electrical computers and digital processing systems: processing
Architecture based instruction processing
Multiprocessor instruction
C712S022000, C712S225000, C712S226000, C709S248000
Reexamination Certificate
active
06516403
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to techniques for effectively controlling synchronization of multiple processors using so-called communication registers, and more specifically to a hardware arrangement for accelerating reply to a processor when the processor inquires if a critical section is available thereto.
2. Description of the Related Art
It is known in the art that in a multiple processor system, it is essential to provide synchronization between the processors when they use critical sections or critical resources. A critical section implies part of a process (task or program) that must be executed indivisibly. In order to achieve exclusive control between the cooperative processors, it is common to provide a flag bit unit including a plurality of flag bits (semaphores) which are respectively allocated to the critical sections. When a processor is going to use one critical section, the processor issues is test-and-set instruction in order to check to determine if the corresponding flag bit assumes a logic level 0 (for example) that indicates availability of the critical section. When the critical section is found available, the processor sets a logic level 1 at the flag bit in order to indicate that the critical section is rendered unavailable, after which the processor starts to use the critical section. When the processor terminates the use of the critical section, the processor sets a logic level 0 at the flag bit for releasing the exclusive use of the critical section thereby.
On the other hand, especially in the case of a supercomputer, it is advantageous to provide a plurality of high-speed registers, called “communication registers”, which are used to hold shared variables for executing synchronization controls, mutual exclusion controls, communication controls between the processors, etc. By way of example, the communication registers are disclosed in U.S. Pat. No. 5,659,784 to Inaba et al. One simple example of operation of the communication registers will be described for the sake of a better understanding of the present invention. A plurality of processors, whose number is assumed one hundred (100), sequentially access one communication register and retrieve a variable stored therein. Each time one processor retrieves the variable, the variable is incremented by one and then stored in the same communication register. The processor implements a calculation using the variable retrieved from the register. The operation of one cycle, for which all the processors have respectively retrieved the variable one time, is repeated 2
40
times (for example). This operation is referred to as a fetch-and-increment operation. In order to store such a variable whose bit length reaches more than 40, each communication register is configured so as to store a 64-bit word (for example).
In the case where the communication registers are used, it is preferable to use some of the registers so as to implement synchronization control between the processors when they use critical sections (viz, mutual extension control). In this instance, it goes without saying that there is no need for providing the flag bit unit that is dedicated to the synchronization control of the processors regarding the critical sections. More specifically, in the above case, one bit of each communication register is used or specified as a flag bit. Therefore, when a processor intends to use one critical section, the processor issues a test-and-set instruction in order to determine if the corresponding flag bit, embedded in the communication register, assumes a logic level 0 (for example) that indicates availability of the critical section. In order to check the flag bit, it is necessary to retrieve the whole content of the communication register and store the same in a suitable work space wherein the flag bit is checked to determine if the critical section is available.
It is understood that this conventional technique suffers from the problem that the flag bit information to be delivered to the processor, which has issued the test-and-set instruction, is undesirably delayed. It is known that, as the size of a program executed in parallel becomes smaller, there is a tendency that the size of each of unit tasks (unit processes) is reduced. In such a case, the frequency of issuance of the test-and-set instructions increases, which enhances the aforesaid problem of delaying an overall time of the program execution.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide techniques for rapidly providing a processor with a reply of whether or not a critical section is available when a plurality of communications registers are used for synchronization control of the processors.
The object is fulfilled by a hardware arrangement for implementing synchronization control between multiple processors, which hardware arrangement is provided with a plurality of communication registers which are arranged so as to store synchronization control data provided by the processors. A flag bit register holds a plurality of flag bits which are respectively assigned to a plurality of critical sections. Each of the flag bits indicates whether the corresponding critical section is available. In order to assure the mutual exclusion control, a flag bit access control register is provided which holds a plurality of control bits that are respectively assigned to the plurality of flag bits. Each of the control bits indicates whether a corresponding flag bit may be accessed by a processor, to thereby prevent two processors from using an identical critical section. A controller is provided so as to adequately control the above-mentioned registers. The controller sets a control bit of the access control register corresponding to a flag bit of the flag bit register during receipt of synchronization control data from a processor to prevent access to that flag bit by other processors.
One aspect of the present invention resides in a hardware arrangement for implementing synchronization control between multiple processors, comprising: a plurality of communication registers arranged so as to store synchronization control data provided by the processors; a flag bit register for holding a plurality of flag bits which are respectively assigned to a plurality of critical sections, each of the flag bits indicating whether the corresponding critical section is available; a flag bit access control register for holding a plurality of control bits which are respectively assigned to the plurality of flag bits, each of the control bits indicating whether a corresponding flag bit may be accessed by a processor to prevent two processors from using an identical critical section; and a controller for controlling the communication registers, the flag bit register, and the flag bit access control register, the controller setting a control bit of the access control register corresponding to a flag bit of the flag bit register during receipt of synchronization control data from a processor to prevent access to that flag bit by other processors.
REFERENCES:
patent: 5321825 (1994-06-01), Song
patent: 5566319 (1996-10-01), Lenze
patent: 5634037 (1997-05-01), Sasaki et al.
patent: 5659784 (1997-08-01), Inaba et al.
patent: 5787301 (1998-07-01), Arakawa et al.
patent: 5928334 (1999-07-01), Mandyam et al.
patent: 5-002568 (1993-01-01), None
patent: 7-262139 (1995-10-01), None
patent: 9-044460 (1997-02-01), None
An Meng-Al T.
Hu Jinsong
NEC Corporation
LandOfFree
System for synchronizing use of critical sections by... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for synchronizing use of critical sections by..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for synchronizing use of critical sections by... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3141381