JPH0325558A - Main storage access request selecting system for multiprocessor system - Google Patents

Abstract

PURPOSE:To evade the overrun of a main storage access request and to prevent the lowering of the capacity of a system and the increment of queue time by providing a means which processes the request issued first in point of time preferentially when the main storage access requests issued from a large number of processors are selected. CONSTITUTION:Two request holding registers A12 and B13 are provided in a request sequence control circuit 1 which sends the request issued first in point of time preferentially to a priority control circuit 2a, and each request holding register is comprised of the corresponding number of flip-flop at every processor. And the request is held with those request holding registers A12 and B13, and the sequence of the request can be guaranteed. Also, a request stopping circuit 10 and a request selector 11 are provided in the request sequence control circuit 1. Thereby, it is possible to process the request issued first preferentially, and to prevent the overrun of the request occurring, and to evade a state where one processor is made awaited for a long time.

Description

Detailed Description of the Invention [Field of Industrial Application] The present invention provides a main memory access method that selects main memory access requests output from each processor in an optimal manner in a multiprocessor system equipped with a plurality of processors. This relates to a request selection method.

[Conventional technology]

FIG. 4 shows an example of the structure of a conventional main memory access request selection device disclosed as a prior art in Japanese Patent Laid-Open No. 63-86062. In the figure, 2b is a priority control circuit, 3 is a request reception register, 4 is a priority counter, 5 is a lock register, 6 is a pipeline, 7 is a bank busy display circuit, and 8 is a main memory access activation register.

In this structure, main memory access requests from each processor are buffered in the request receiving register 3 corresponding to each processor. In the illustrated example,
Since the number of processors is assumed to be four, there are four request reception registers 3, RRO to RR4. The buffered main memory access request is sent to the priority control circuit 2b. The priority control circuit 2b selects only one request among the main memory access requests sent from each request receiving register 3.

The pipeline 6 holds the access that activated the main memory \iNII for each stage. The priority counter 4 is an n-bit counter that dynamically determines the priority among processors, and the priority is changed every time a request is selected. Assuming that the processors are PO to P3, the priority control circuit 2b decodes the n bits of the priority counter 4 to designate the following priorities.

Counter 4 2-pit output Priority 00: PO PI P2 P3
01 :PI P2 P3 P41
0 :P2 P3 PO P111
:P3 PO PI P2 Pang Busy display circuit 7 has a flag that holds the busy time of each bank corresponding to the bank of the main memory, and access to a bank where this flag is on is inhibited for a period of time until this flag turns off. be done.

The lock register 5 holds the address of a locked bank or the address of each cache block, and locking of each bank or block is realized. While the value of this lock register 5 is valid, accesses to the same bank or block are inhibited except by the processor that issued the lock instruction. The lock register 5 is invalidated by a lock release request from the processor that activated the lock.

[Problem to be solved by the invention]

In the conventional access request selection method described above, only the priority order among processors was dynamically changed, so $11! When a request occurs, a processor assigned a lower priority may be forced to wait until its own priority becomes higher. This means that even if a request from a low-priority processor is issued earlier than a request from a high-priority processor, it may be overtaken by a request from a high-priority processor. It means that. An example in which such a state occurs will be explained with reference to FIG. 5. Here, from time To to T3, the priority control circuit 2b divides the time required for one request selection, and for each time, each request is The status of the request from the processor is shown. The state of request i is “d”
S n indicates a state in which a request is being selected and processed in the priority control circuit 2b, and 'W' indicates a state in which the request is being waited at the entrance of the priority control circuit 2b. In this example, a request from processor P3 has been waiting for a long time. The example operation in this case will be explained time by time.

TO: Processor P2 and processor P3 issue requests simultaneously. At this time, since processor P2 has a higher priority, the request from processor P2 is selected.

T1: Requests from processor P3 continue to be issued. Further, at this point, a request is issued from processor P1. At this time, since the processor P1 has a higher priority, the request from the processor P1 is selected, and at this point, the request is overtaken.

T2: Requests from processor P3 continue to be issued. Furthermore, at this point, a request is issued from processor PO. At this time, processor P
Since O has a higher priority, the request of processor PO is selected, and at this point, request overtaking occurs again.

T3: Requests from processor P3 continue to be issued. At this point, processor P3 has the highest priority, so a request from processor P3 is selected for the first time at this point. Having a request from one processor wait for a long time in this way poses a problem in that system performance deteriorates when a high priority processor specifies a lock area. Specifically, the following occurs.

(1) In the main memory area locked by processor Pi,
Processor Pj tries to access that area, but
Canceled because it is locked.

(2) Processor Pj attempts to access the same location again. (3) Processor Pi issues an unlock request.

(4) Since the priority of processor Pj is higher than that of processor i, the request from processor Pj is given priority and is canceled by accessing the locked area again.

In this way, the processor issuing the lock release request waits for a long time until its priority level is raised, and as a result, useless requests like (4) above are accepted many times, which reduces the performance of the entire system. There is a problem in that it leads to a decrease in

Furthermore, in the above example, as the number of processors increases, the time it takes to raise the priority level increases, so there is a need for a request selection method that does not increase waiting time even when the number of processors increases. The present invention has been made to solve the above-mentioned problems, and provides a main memory access request selection method for a multiprocessor system that can avoid request overtaking and prevent system performance from deteriorating and waiting time from increasing. It is intended to.

[Means for Solving the Problems] The present invention provides a means for selecting an access request issued earlier in time in addition to a means for selecting an access request to the main memory according to the priority order. It is something. That is, the priority of main memory access requests generated from each processor is dynamically changed at regular intervals, and according to the priority, a unique request is selected from among the requests issued simultaneously by multiple processors. , a request selection means (4l! priority control circuit 2a) that outputs a notification signal representing the selected request, and a first request holding means that temporarily holds requests issued from each processor at an arbitrary time. (request holding register A12), receives and holds the request held in this first request holding means, sends the held request to the request selection means, and furthermore, among the held requests, the a second request holding means (request holding register latch B13) that erases the request indicated by the notification signal and receives the request held in the first request holding means again when there is no longer a held request; 1st. Request switching means (request selector 1) for directly transferring requests from each processor to the request selection means when no requests are held in both of the second request holding means
1>.

(Operation) When requests are generated simultaneously from two or more processors, the requests from each processor are sent to the first request holding means. At this time, if there is no request pending in the second request holding means, requests from each processor are simultaneously sent to the request selection means.

The request selection means selects the only request with the highest priority among the plurality of requests according to the priority determined by the counter. The selected request is sent to each component such as the pipeline (6), and at the same time,
The second factor is which processor's request was selected.
The request holding means is notified. Therefore, the second request holding means deletes the request corresponding to the selected processor among the held requests. When selecting the next request, if all the requests in the second request holding means are not erased, the requests held in the second request holding means are sent to the request selection means again.

Request selection continues until all requests held in the second request holding means are deleted.

On the other hand, while the request held in the second request holding means is sent to the request selection means, the requests issued from each processor are set in the first request holding means. When selecting a request, if all requests in the second request holding means have been deleted, the contents of the first request holding means are copied to the second request holding means, and the contents of the first request holding means are not deleted. It will be done. The above operation is repeated for subsequent request options.

By using 411 in this way, it is possible to process requests issued earlier in time with priority, preventing requests from being overtaken, and avoiding one processor from having to wait for a long time. can.

(Embodiment) FIG. 1 is a block diagram showing an example of the basic structure of the present invention. The illustrated configuration is an improved version of the conventional main memory access request selection @ configuration example shown in FIG. Accordingly, components designated by reference numbers 2 to 8 are used in common in both figures. However, in the priority order circuit 2a in FIG. 1, the request suppression means based on bank pidgey or lock detection is removed, and the request suppression means is transferred to the request order control circuit 1.

Also, in FIG. 1, the newly added circuit is in the request order 111JI! 1 circuit 1. The request order control circuit 1 is a mechanism that sends requests issued earlier in time to the priority control circuit 1 with priority. In the request order control circuit 1, there is a request holding register A12.
There are two holding registers, ie, request holding register 813, and request holding register 813, and each request holding register is composed of 7 flips, the number of which corresponds to each processor.

These request holding registers A12.813 hold requests and guarantee the order of requests.

Further, the request order control circuit 1 is provided with a request stop @path 10 and a request selector 11.

In the above configuration, when requests are issued from two or more processors at the same time, the requests from each processor are sent to the request 1/sequence control circuit 1 via the request reception register 3 corresponding to each processor. It will be done. In the request order control circuit 1, if there is no pending request at this point, the requests from each processor are simultaneously sent to the priority control circuit 2a. At the same time, in the request order lIjlJID circuit 1, a flip-flop corresponding to the processor that issued the request in the request holding register B13 is set.

The priority control circuit 2a selects a unique request from a plurality of requests according to the priority determined by the priority counter 4. The selected request is sent to each component such as the pipeline 6, and at the same time the signal Im
9, the request order control circuit 1 is notified of which processor's request has been selected. The flip 7 flop corresponding to the notified request is reset.

When selecting the next request, request holding register 8
If all 13 flip-flops have not been reset, the requests remaining in the request holding register B13 are sent to the priority control circuit 2a. Then, the same request selection is made again in the request holding register 813.
This continues until all of the flip-flops are reset, and during this time, the request 1. set in the request holding register B13 is sent to the invasion priority control circuit 2a.

On the other hand, while the request from the request holding register 813 is sent to the priority control circuit 2a, the requests issued from each processor are sent to the request holding register A.
Set to 12. At the time of request selection, if all seven flip-flops of the request holding register B13 have been reset, the contents of the request holding register AI2 are copied to the request holding register 813, and all seven flip-flops of the request holding register AI2 are reset. The above operation is repeated for subsequent request selections.

In this way, the request {・holding register A12, 813
111Jl1] By newly providing the circuit 1, requests issued earlier in time can be processed with priority.

FIG. 2 is a diagram illustrating the issuance of requests from each processor and the processing status in order in the example of the configuration of the present invention shown in FIG. Note that the symbols used in Figure 2 have exactly the same meaning as the symbols shown in Figure 5. Below, the operation of the configuration example of the present invention will be explained for each time.

TO=Processor P2 and processor P3 issue requests simultaneously. At this time, since processor P2 has a higher priority, processor P2's request l
・is selected.

D1: Requests from processor P3 continue to be issued. Furthermore, at this point, a request is issued from processor P1. At this time, processor P1
has a higher priority, but since the request from processor P3 has been issued earlier, request I from processor P3 is selected and is made to wait for the request from processor P1. Therefore, overtaking of requests as in the conventional example shown in FIG. 5 does not occur at this point.

T2: IK1 continuous request 1 from processor P1
・continues to be published. Furthermore, at this point, a request is issued from the processor PO. At this time, processor PO has a higher priority, but since processor P1's request was issued earlier, processor P1
request is selected and processor PO's request 1 is selected.
・Has to wait. T3: Request 1 from the processor PO continues to be issued. At this point, there are no requests other than the request from the processor PO, so the request from the processor PO is selected.

In this way, by giving priority to requests issued earlier in time, overtaking of requests is prevented, and
It is possible to avoid having one processor wait for a long time.

FIG. 3 is a circuit diagram specifically showing the details of the 4M loop in FIG. WJ1. In FIG. 3, 1 is a request order control circuit, and 2a is a priority control circuit.

The request order control circuit 1 receives main memory access requests from each processor and sends the requests to the priority lvItl1 circuit 2a in a determined order. The priority control circuit 282a selects only one request, and the selection result is sent to the next component, and a signal is also sent to the request order control circuit 1! Feedback is provided via i19. Below, request order control circuit 1
The internal structure of will be explained.

The lowest request sent from each processor is A.
The signal is input to the ND circuit 16. The other input of the AND circuit 16 is a signal line from the request stop circuit 10,
When the request stopping circuit 10 decides to stop the request, the AND circuit 16 stops the request. Conditions for stopping a request include the following.

(1) When attempting to access a bank that is in a bank busy state.

{2} When a processor other than the processor that placed the lock attempts to access the locked main storage area.

Therefore, the request stop circuit 10 receives bank address, lock address, and busy-punk address signals. The request that has passed through the AND circuit 16 is also sent to the request selector 11. The request selector 11 is a selector for immediately sending the request that has passed the AND circuit i116 to the priority control circuit 2a when no request remains in the request holding register B13.

Switching of the request selector 11 is determined by the output of the NOR circuit 18. When the NOR circuit 18 does not leave request 1 in the request holding register B13,
That is, when all the flip-flops 15 in the request holding register 813 are reset, a signal is output, the request selector 11 is switched, and the AND circuit 1
6 is immediately sent to the priority $811 circuit 2a.

The request held in the request holding register AI2 is copied to the request register B13 if no request remains in the request holding register B13 when the next request 1/selection is activated. After the copy is completed, all flip-flops 14 in the request holding register A12 are reset. Request 1/Request held in holding register A12 is AND
It is sent to the request holding register B13 via the circuit 17. The AND circuit 17 receives the request selection activation signal and passes the request only when it receives a signal from the NoR circuit 18 indicating that no request remains in the request holding register B13. AND circuit 1
The conditions for 7 are generated in the ANO circuit 19.

If a request remains in the request holding register B13, the request selector 11 sends the request from the request holding register B13 to the priority control circuit 2a. Priority lllllJ1m! 1 circuit 2a selects only one request according to the priority specified by the priority counter 4.

The only selected request is notified to the request holding register B13 via the signal line 9. In the request holding register 813, the flip-flop 15 corresponding to the processor that issued the request selected by the priority control circuit 2a is reset.

In this way, the request held in the request holding register B13 is reset every time a request is selected, and when the request in the request holding register B13 finally becomes empty, the request held in the request holding register AI2 is reset as a request again. Holding register B
Copied to 13. Furthermore, if the request in the copied request holding register A12 is empty, the request selector 11 sends the request from the AND circuit 16 directly to the priority control circuit 2a.

(Effects of the Invention) As is clear from the above description, according to the present invention, when selecting main memory access requests issued from a large number of processors, priority is given to requests issued earlier in time. Since the means is provided, requests can be prevented from being overtaken, and one processor can be prevented from being kept waiting for a long time.

Therefore, unnecessary requests that occur due to the processor issuing the lock release request being forced to wait for a long time until its priority level is increased will no longer be made, and a decline in the performance of the entire system can be prevented. It becomes possible.

[Brief explanation of drawings]

FIG. 1 is a block diagram showing an embodiment of the basic configuration of the present invention, FIG. 2 is an explanatory diagram showing request issuance and processing timing from each processor in the configuration example of FIG. 1,
FIG. 3 is a circuit diagram showing an example of the detailed configuration of the embodiment shown in FIG. 1, FIG. 4 is a block diagram showing the configuration of a conventional main memory access request 1/selection device, and FIG. FIG. 2 is an explanatory diagram showing request issuance and processing timing from each processor in the conventional configuration shown. 1...Request order control circuit, 2a...Priority! IJa11 circuit, 3... request reception register,
4...Priority counter, 5...Lock register,
6... Pipeline, 7... Bank busy display circuit, 8... Main memory access activation register, 11... Request selector, 12... Request holding register A113... Request 1/holding register B ．． In addition, in the figures, the same or equivalent parts are indicated by the same symbols.

Claims (1)

[Claims] Access to a multiprocessor system that includes a plurality of processors and a main memory that can be commonly accessed by each processor, and that controls contention for main memory access requests generated from each processor at arbitrary times. In the request selection method, the priority of main memory access requests issued by each processor is dynamically changed at regular intervals, and the only request among requests issued simultaneously by multiple processors is selected according to the priority. request selection means for selecting and outputting a notification signal representing the selected request; first request holding means for temporarily holding requests issued from each processor at an arbitrary time; Receive and hold the request held in the holding means, send the held request to the request selection means, erase the request indicated by the notification signal among the held requests, and further hold the request. a second request holding means that receives the request held in the first request holding means again when the previously held request is no longer held; 1. A main memory access request selection method for a multiprocessor system, comprising request switching means for directly transferring a request from a processor to the request selection means.