1) Field of the Invention
The present invention relates to a technique for, in a device, for example, provided with a register for retaining a request at the final stage of a pipeline register including a number of multi-stage registers, making a Judgment about the entry (storage) into the register in a stage in which the request is retained halfway in the pipeline register.
2) Description of the Related Art
Conventionally, there is a pipeline device provided with a queue for retaining a request at the final stage of a pipeline register including a number of multi-stage registers and functioning as a shift register (for example, refer to Patent Document 1 mentioned below).
A conventional information processing system provided with such a pipeline processor is shown in FIG. 9. As shown in FIG. 9, an information processing system 100 comprises a plurality of (eight, here) pipeline processors 110-0 to 110-7 (denoted by SB (System Board) 0 to SB7 in the figure), and the plurality of pipeline processors 110-0 to 110-7 (hereinafter, denoted simply by a symbol “110” for description when it is not necessary in particular to distinguish the plurality of pipeline processors 110-0 to 110-7 from each other) execute a pipeline process in synchronization with each other at the same time, and each of the plurality of pipeline processors 110-0 to 110-7 is connected to two operation sections (denoted by CPU (Central Processing Unit) in the figure) A-0 to A-7 and B-0 to B-7 (hereinafter, denoted simply by a symbol “A and B” for description when it is not necessary in particular to distinguish the operation sections A-0 to A-7 and B-0 to B-7 from each other) via data buses (FSB: Front Side Bus) 111-0 to 110-7 (hereinafter, denoted simply by a symbol “111” for description when it is not necessary in particular to distinguish the data buses 111-0 to 111-7 from each other).
Note that, each of the plurality of pipeline processors 110-0 to 110-7 is connected to the corresponding one of the data buses 111-0 to 111-7 having the same last number of the symbol as that of the pipeline processor and further, each of the plurality of pipeline processors 110-0 to 110-7 is connected to corresponding two of the operation sections A-0 to A-7 and B-0 to B-7 having the same last number of the symbol as that of the pipeline processor via the data bus 111.
For example, the pipeline processor 110-0 is connected to the operation sections A-0 and B-0 via the data bus 111-0, the pipeline processor 110-1 is connected to the operation sections A-1 and B-1 via the data bus 111-1, and the pipeline processor 110-7 is connected to the operation sections A-7 and B-7 via the data bus 111-7.
In FIG. 9, for simplification of the figure, the pipeline processors 110-2, 110-3, 110-4, 110-5, and 110-6, and the data buses 111-2, 111-3, 111-4, 111-5, and 111-6, and the operation sections A-2, B-2, A-3, B-3, A-4, B-4, A-5, B-5, A-6, and B-6 are not shown.
The information processing system 100 comprises a controller (denoted by XB (Crossbar Board) in the figure) 120 for notifying the plurality of pipeline processors 110 of a request and making one of the plurality of pipeline processors 110 deal with the request.
In the information processing system 100, a selection section 121 of a controller 120 selects a request out of requests REQ0 to REQn with respect to the controller 120, taking into account each priority of the requests REQ0 to REQn, and simultaneously notifies the corresponding pipeline processors 110-0 to 110-7 of the selected request using GSA (Global System Address)-SB0 to GSA-SB7.
Then, each pipeline processor 110 retains the notified request by means of a pipeline register 112 including a number of registers 112a. At this time, each pipeline processor 110 retains the request while sequentially moving the request from the upstream side to the downstream side of the plurality of registers 112a with the same timing as that of the other pipeline processors 110 based on the system clock (synchronization signal) in the information processing system 100.
On the other hand, an LCST (Local Cache Status) generation logic 114 of each pipeline processor 110 retrieves a storage section (denoted by TAG in the figure) with the same timing as that of the other pipeline processors 110 and judges whether or not the data to be used by the request is retained in the storage section of the subordinate operation sections A and B.
Further, the LCST generation logic 114 judges whether or not a request queue (denoted by SLVQ_FSB (Slave Request Queue) in the figure) 117, which will be described later, can store the request (that is, whether or not the request queue 117 is in a busy state)
Then, a condition generation section (denoted by “condition generation” in the figure) 115 of the LCST generation logic 114 determines an operation as to whether or not the request is a valid request that can be dealt with based on the judgment result as to whether or not the cache is hit by the LCST generation logic 114 and the judgment result as to whether or not the request queue 117 is in a busy state.
Next, the LCST generation logic 114 further transmits the TAG information of itself (that is, information as to whether or not the cache is hit as a result of the above-mentioned retrieval by the storage section 113) and the operation determining information as to whether or not the request is a valid request that can be dealt with, to the controller 120 using LCST-SB0 to LCST-SB7.
Then, an LCST summarizing logic 122 of the controller 120 summarizes the information transmitted from the plurality of pipeline processors 110, and a GCST (Global Cache Status) generation logic 123 makes a total judgment about the information transmitted from each pipeline processor 110, determines the operation as the information processing system 100 for making one of the plurality of pipeline processors 110 deal with the request, and notifies the corresponding pipeline processor 110 of the determined operation using GCST-SB0 to GCST-SB7.
Moreover, the controller 120 also comprises a pipeline register 124 including a number of registers 124a and the pipeline register 124 retains the request while sequentially moving the request from the upstream side to the downstream side based on the system clock in order to synchronize with each pipeline processor 110 during the period of time from the notification of the request to each pipeline processor 110 until the transmission of the operation determining information about the request from each pipeline processor 110.
Then, a GCST judgment logic 116 of each pipeline processor 110 receives a determined operation notified from the controller 120 using corresponding GCST-SB0 to GCST-SB7 and judges whether or not the request is stored in the request queue 117 provided at the subsequent stage of the pipeline register 112 based on the received determined operation.
In other words, the pipeline processor 110 among the plurality of pipeline processors 110, which obtains an operation permission (that is, the pipeline processor 110 that is determined to deal with the request), stores the request in the request queue 117.
Here, the request queue 117 is a register for retaining a request by the FIFO (First In First Out) method, and the request is retained in the request queue 117 and thereby is delivered to the operation sections A and B via the data bus 111 and executed.
The pipeline register 112 of each pipeline processor 110 retains the request while sequentially moving the request from the upstream side to the downstream side based on the system clock in order to absorb the time lag between the receipt of the request from the controller 120 until the decision of the operation of itself (that is, during the period of time of the retrieval of the TAG information retained in the storage 113).
Further, the pipeline register 112 of each pipeline processor 110 retains the request while sequentially moving the request from the upstream side to the downstream side based on the system clock in order to synchronize with the controller 120 during the period of time from the transmission of the operation determining information of itself etc. by the LCST generation logic 114 to the controller 120 until the reception of the determined operation by the GCST judgment logic 116 from the GCST generation logic 123.
As described above, in the information processing system 100, it is necessary for the LCST generation logic 114 (condition generation section 115) to make a judgment about the entry (storage) of the request into the request queue in a stage in which the request is retained halfway in the pipeline register 112 in each pipeline processor 110.
In other words, it is necessary for each pipeline processor 110 to determine an operation as to whether or not the request is a valid request that can be dealt with by itself (that is, whether or not the request can be executed by its subordinate operation sections A and B) in a stage in which the request is retained halfway in the pipeline register 112.
Moreover, since the final determination of the operation as to whether or not the request is actually dealt with is performed by the GCST generation logic 123 of the controller 120 and is made clear in each pipeline processor when the request passes through the final stage of the pipeline register 112, it is necessary for the LCST generation logic 114 of each pipeline processor 110 to make a judgment as to whether or not the request queue 117 is in a busy state while taking into account the other requests retained in the register 112a interposed between the condition generation section 115 and the request queue 117.
In other words, it is necessary for the LCST generation logic 114 to make a judgment in advance as to whether or not the request queue 117 is in a busy state when storing the request into the request queue 117, and thereby avoiding such a situation in which the request queue 117 is in a busy state when the request is actually stored into the request queue 117.
Here, by referring to FIG. 10, a concrete busy state judgment method of the request queue 117 by the LCST generation logic 114 is explained below.
As shown in FIG. 10, when the request queue 117 has m stages (m is an integer not less than 1: that is, m requests can be put into entry), there are n stages of the register 112a in the pipeline register 112 between the condition generation section 115 and the request queue 117 (n is an integer not less than 1), and x stages of the request queue 117 (x is an integer; x<m) are occupied by valid requests (that is, there exist x valid entries), the LCST generation logic 114 makes a judgment about the busy state of the request queue 117 under the condition shown by the following expression (X) on the assumption that all of the n stages of the register 112a have the valid request.x+n=m  (X)
In other words, if the sum of x, which is the number of valid entries in the request queue 117 and n, which is the number of stages of the register 112a between the condition generation section 115 and the request queue 117 is equal to m, which the total number of entries in the request queue 117, the LCST generation logic 114 makes a judgment that the request queue 117 is in a busy state.
In addition, conventionally, a technique for counting the number of valid entries (x stages in FIG. 10) in a queue (register) for retaining a request has been proposed (for example, refer to Patent Documents 1 and 2 mentioned below).
However, the busy judgment method by the LCST generation logic 114 described above by referring to FIG. 10 may sometimes judge a queue to be in a busy state even when it is not in a busy state actually, because invalid entries present in the n stages of the register 112a are dealt as valid entries, and it is not possible to effectively utilize the number of entries in the request queue 117.
Further, the busy judgment method described above cannot be applied to a case where n, which is the number of stages of the register 112a between the condition generation section 115 and the request queue 117, is equal to or greater than m, which is the total number of entries in the request queue, because the LCST generation logic 114 always detects a busy state.
Therefore, a method is conceivable in which a judgment is made as to whether or not all the n stages of the register 112a retain the valid entry each time when the condition generation section 115 determines an operation, but this method requires a circuit etc. for making a judgment as to whether each register 112a retains a valid or an invalid request, therefore, the hardware resources will be increased and the manufacturing cost will be increased.
[Patent Document 1]
Japanese Patent Laid-open No. HEI 4-367031
[Patent document 2]
Japanese Patent Laid-open No. SHOWA 64-10332
USPTO Backgrounds
USPTO Backgrounds