JP5544856B2 - Arbitration device, arbitration method, and program - Google Patents

Description

  The present invention relates to an arbitration device, an arbitration method, and a program.

  With the progress of semiconductor technology, LSI (Large Scale Integration) with a high integration rate has been developed. However, due to the increase in power consumption, it has become difficult to improve the performance of LSIs by further improving the integration rate. Therefore, a multi-core configuration is used in which the number of LSI processor cores is increased and the operating frequency is kept low to suppress an increase in power consumption, and the throughput is improved by the degree of parallelism of a plurality of processor cores.

  As a router for connecting cores in an LSI having a multi-core configuration, a ring bus type router for connecting processor cores in a ring shape, or a crossbar type router for connecting cross-bars between processor cores to connect each processor core is used. It has been. The processing of such on-chip routers (especially crossbar routers) needs to acquire information from request packets, set output ports, perform crossbar arbitration, and transfer to output ports. Processing is performed by pipeline processing of three to four stages.

As a crossbar arbitration method, a random selection method that randomly selects conflicting request packets, a round robin selection method that sequentially selects conflicting request packets, and a priority selection method that selects conflicting request packets in a predetermined priority order. Is used.
Patent Document 1 discloses a method for performing bus arbitration based on the arbitration history of competing request packets.
Patent Document 2 uses a table that records the output order of request packets by processor cores involved in a specific transfer process, and outputs a request packet next to a processor core that currently uses resources. On the other hand, an arbitration method for preferentially using resources is disclosed.

JP 2001-167049 A JP 2008-299624 A

  The arbitration method based on the random selection method and the round robin selection method described above is a method of selecting a processor core on the assumption that each processor core outputs a request packet equally. For this reason, there is a problem that when an application whose request packet output is not uniform is executed for each processor core, the request packet cannot be efficiently selected. In addition, since the priority order of the processor cores is determined in advance in the arbitration method by the priority selection method, when an application that outputs a large number of request packets by a processor core having a low priority order is executed, efficient request packet selection is possible. There is a problem that it cannot be done.

The arbitration methods described in Patent Document 1 and Patent Document 2 perform arbitration based on the arbitration history of the request packet. However, since the content of processing executed per cycle of the arbitration process increases, the operation frequency of the arbitration device Cannot be increased, and communication delays may occur.
The present invention has been made in view of the above problems, and provides an arbitration device, an arbitration method, and a program that perform efficient request packet selection without increasing the execution processing content per cycle of arbitration processing. The task is to do.

The present invention has been made to solve the above-described problem, and performs resource request arbitration issued from a plurality of resource requesting devices indicating requests for use of computing resources by the resource requesting device, and An arbitration device that controls a crossbar that connects a device and the computing resource, wherein an input unit that receives input of resource requests from a plurality of the resource requesting devices and a resource request for the computing resource with the same input unit An arbitration unit that outputs a connection command for outputting the selected resource request to a calculation resource to which the resource request is issued to the crossbar, and before executing the processing by the arbitration unit, the arbitration unit The arbitration unit selects the prediction unit that predicts the resource request selected by the unit and outputs a connection command to the crossbar to output the resource request to the calculation resource to which the resource request is issued. And if the resource request and the predicted part is resource request and the predicted is different, and the interruption unit for outputting an interruption instruction to interrupt the execution of the connection instruction by the prediction unit to the crossbar, the arbitration unit in the past processing A history registration unit that registers the resource requests selected by the arbitration history storage unit in the order of selection, and the arbitration unit has the same resource request selected by the arbitration unit and the resource request predicted by the prediction unit. The connection command to the crossbar is not output, and the prediction unit is stored in the arbitration history storage unit in the same order as the last predetermined number of resource requests selected by the arbitration unit. A resource request registered immediately after the resource request is predicted as a resource request selected by the arbitration unit .
In addition, the present invention arbitrates resource requests issued from a plurality of resource requesting devices to indicate requests for use of computing resources by the resource requesting devices, and provides a crossbar for connecting the resource requesting devices and the computing resources. An arbitration device to be controlled, wherein an input unit that receives input of resource requests from a plurality of the resource requesting devices, and the input unit selects one of resource requests for the same computing resource, and the selected resource An arbitration unit that outputs a connection command that outputs a request to a calculation resource to which the resource request is issued to the crossbar, and before executing the process by the arbitration unit, predicts a resource request selected by the arbitration unit, A prediction unit that outputs a connection command for outputting the resource request to a calculation resource to which the resource request is issued to the crossbar, a resource request selected by the arbitration unit, and a resource predicted by the prediction unit When the request is different, the arbitration unit selected in the past processing for each of the resource requesting device and the interrupting unit that outputs an interrupting command for interrupting the execution of the connection command by the prediction unit to the crossbar A strength information calculation unit that calculates strength information indicating a degree that the resource request and the resource request predicted by the prediction unit are the same, and the mediation unit is based on the strength information calculated by the strength information calculation unit. The resource request to be selected is determined, and when the resource request selected by the arbitration unit and the resource request predicted by the prediction unit are the same, the connection command is not output to the crossbar. .

In addition, the present invention arbitrates resource requests issued from a plurality of resource requesting devices to indicate requests for use of computing resources by the resource requesting devices, and provides a crossbar for connecting the resource requesting devices and the computing resources. An arbitration method using an arbitrating device to be controlled, wherein an input unit accepts input of resource requests from a plurality of the resource requesting devices, and the arbitration unit selects from among resource requests for the computing resources with the same input unit. The prediction unit selects one and predicts the resource request selected by the arbitration unit before executing the processing by the arbitration unit, and outputs the resource request to the calculation resource to which the resource request is issued. The connection command is output to the crossbar, and the interruption unit determines whether the prediction command to the crossbar is connected when the resource request selected by the arbitration unit is different from the resource request predicted by the prediction unit. Outputting an interrupt command to interrupt the line, the history registration unit registers the arbitration history storage unit in the order in which the arbitration unit selects the resource request selected in past processing, the arbitration unit, the arbitration unit selects When the resource request and the resource request predicted by the prediction unit are different, a connection command for outputting the selected resource request to the calculation resource to which the resource request is issued is output to the crossbar. A resource request registered immediately after the resource request stored in the arbitration history storage unit in the same order as the last predetermined number of resource requests selected by the arbitration unit is selected by the arbitration unit. It is characterized by predicting as follows.
In addition, the present invention arbitrates resource requests issued from a plurality of resource requesting devices to indicate requests for use of computing resources by the resource requesting devices, and provides a crossbar for connecting the resource requesting devices and the computing resources. An arbitration method using an arbitrating device to be controlled, wherein an input unit accepts input of resource requests from a plurality of the resource requesting devices, and the arbitration unit selects from among resource requests for the computing resources with the same input unit. One is selected, a connection command for outputting the selected resource request to the calculation resource to which the resource request is issued is output to the crossbar, and the prediction unit performs the arbitration before executing the processing by the arbitration unit. The resource request selected by the resource unit is predicted, a connection command for outputting the resource request to the calculation resource to which the resource request is issued is output to the crossbar, and the interruption unit is the resource request selected by the arbitration unit. When the resource request predicted by the prediction unit is different, the crossing bar outputs an interruption command for interrupting the execution of the connection command by the prediction unit, and the strength information calculation unit stores the past for each resource request device. In the process, the strength information indicating the degree to which the resource request selected by the arbitration unit and the resource request predicted by the prediction unit are the same is calculated, and the arbitration unit calculates the strength information calculated by the strength information calculation unit. And when the resource request selected by the arbitration unit and the resource request predicted by the prediction unit are different from each other, the selected resource request is calculated as a calculation resource to which the resource request is issued. A connection command to be output to is output to the crossbar.

In addition, the present invention arbitrates resource requests issued from a plurality of resource requesting devices to indicate requests for use of computing resources by the resource requesting devices, and provides a crossbar for connecting the resource requesting devices and the computing resources. An arbitration device to be controlled is an input unit that receives input of resource requests from a plurality of the resource requesting devices, and the input unit selects one of the resource requests for the same computing resource, and the selected resource request is Before executing the processing by the arbitration unit, the arbitration unit that outputs a connection command to be output to the calculation resource to which the resource request is issued to the crossbar, the resource request selected by the arbitration unit is predicted, and the resource request is The prediction unit that outputs a connection command to be output to the calculation resource to which the resource request is issued to the crossbar, the resource request selected by the arbitration unit is different from the resource request predicted by the prediction unit If, registered in the interruption of outputting the interrupt instruction to interrupt the execution of the connection instruction by the prediction unit with respect to the crossbar, the arbitration in the order in which the arbitration unit selects the resource request selection history storage unit in the past processing When the resource request selected by the arbitration unit and the resource request predicted by the prediction unit are the same, the arbitration unit does not output the connection command to the crossbar, and functions as a history registration unit. The prediction unit uses the arbitration unit to register resource requests registered immediately after the resource request stored in the arbitration history storage unit in the same order as the last predetermined number of resource requests selected by the arbitration unit. It is characterized by predicting as a resource requirement to be selected .

  According to the present invention, before execution of arbitration by the arbitration unit, the prediction unit predicts a resource request to be selected and outputs a connection command for causing the crossbar to output the resource request. Thereby, the arbitration device can perform efficient resource request selection without increasing the execution process content per cycle of the arbitration process.

It is a schematic block diagram which shows the structure of the crossbar arbitration apparatus by one Embodiment of this invention. It is a schematic block diagram which shows the structure of a prediction circuit. It is a figure which shows the flow of the pipeline process of an arbitration circuit. It is a 1st flowchart which shows operation | movement of an arbitration apparatus. It is a 2nd flowchart which shows operation | movement of an arbitration apparatus. It is a figure which shows the arbitration method of a request packet. It is a figure which shows the update method of intensity | strength information.

Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.
FIG. 1 is a schematic block diagram showing a configuration of a crossbar arbitration device according to an embodiment of the present invention.
The crossbar arbitration device is a router that connects a processor core and an input / output device to each other, and includes input ports 1-1 to 1-5 (hereinafter, input ports 1 to 1-5 are collectively referred to as input ports 1 to 1-5). Input side buffer units 2-1 to 2-5 (hereinafter, the input side buffer units 2-1 to 2-5 are collectively referred to as the input side buffer unit 2), the arbitrating device 3, and the crossbar. 4. Output side buffer units 5-1 to 5-5 (hereinafter, the output side buffer units 5-1 to 5-5 are collectively referred to as output side buffer unit 5), output ports 6-1 to 6-6 5 (hereinafter, the output ports 6-1 to 6-5 are collectively referred to as the output port 6).

The input port 1 inputs a request packet from each connected processor core or input / output device (hereinafter referred to as a resource request device), and outputs the request packet (resource request) to the connected input side buffer unit 2 To do. In the present embodiment, the request packet input from the resource requesting device by the input port 1 includes information indicating the output destination and strength information indicating the priority of arbitration.
The input side buffer unit 2 inputs a request packet from the connected input port 1, temporarily stores the request packet, outputs strength information included in the request packet to the arbitrating device 3, and crosses the request packet body to the crossbar. 4 is output.

The arbitrating device 3 arbitrates the request packet based on the strength information input from the input side buffer unit 2, and outputs a connection command for transferring the request packet selected by the arbitration to the output port 6 to the crossbar 4. In addition, the strength information associated with each processor core is updated and output to the output port 6.
The crossbar 4 receives a connection command from the arbitration device 3 and outputs a request packet input from the input buffer unit 2 to the output buffer unit 5 based on the connection command.
The output buffer unit 5 receives a request packet from the crossbar 4, temporarily stores the request packet, and outputs the request packet to the connected output port 6.
The output port 6 receives a request packet from the connected output-side buffer unit 5 and strength information from the arbitration device 3, and sends a request packet including the strength information to a connected processor core or input / output device (hereinafter referred to as calculation). Resource).

  The processor core and the input / output device connected to the input port 1 and the output port 6 are connected to a shared memory (not shown). Then, the processor core and the input / output device read the strength information associated with the own device from the memory. Further, the processor core and the input / output device overwrite and record the intensity information output from the output port 6 in the memory. Thereby, the processor core and the input / output device can reflect the strength information updated by the arbitrating device 3 in the next input.

The input side buffer unit 2 includes an input buffer 21, an input side FIFO buffer control circuit 22, a FIFO buffer 23, an output side FIFO buffer control circuit 24, and an output buffer 25.
The input buffer 21 temporarily stores request packets input from the input port 1.
The input side FIFO buffer control circuit 22 takes out the request packet stored in the input buffer 21 and registers it in the FIFO buffer 23.
The FIFO buffer 23 temporarily stores the request packet recorded by the input side FIFO buffer control circuit 22.
The output side FIFO buffer control circuit 24 takes out the request packet first registered in the FIFO buffer 23 and registers it in the output buffer 25. Here, “take out” indicates that the request packet is read from the FIFO buffer 23 and the read request packet is deleted from the FIFO buffer 23.
The output buffer 25 temporarily stores request packets to be output to the arbitrating device 3 and the crossbar 4.

The arbitrating device 3 includes strength input buffers 31-1 to 31-5 (hereinafter, the strength input buffers 31-1 to 31-5 are collectively referred to as strength input buffers 31), a request input buffer 32, and a buffer registration circuit. 33, the arbitration buffer circuit 34, the prediction circuit 35, the arbitration circuit 36, the strength update circuit 37, the strength output buffers 38-1 to 38-5 (hereinafter, the strength output buffers 38-1 to 38-5 are collectively referred to as strength outputs). A buffer 38).
The strength input buffer 31 receives the strength information included in the request packet from the corresponding input side buffer unit 2 and temporarily stores it.
The request input buffer 32 receives the request packet body from the input side buffer unit 2 and temporarily stores it.

The buffer registration circuit 33 extracts the strength information stored in the strength input buffer 31 and registers it in the arbitration buffer circuit 34 in association with the identification information of the input port 1 that is the input source.
The arbitration buffer circuit 34 stores the identification information of the input port 1 that is the input source of the request packet to be arbitrated and the strength information of the request packet in association with each other.
The prediction circuit 35 predicts which request packet the arbitration circuit 36 will select based on the information of the request packet to be arbitrated stored in the arbitration buffer circuit 34 and the past arbitration result by the arbitration circuit 36. Selection control information indicating the result is output to the arbitration circuit 36. Here, the selection control information indicates a request packet predicted by the prediction circuit 35 and its strength information.

  The arbitration circuit 36 extracts the strength information stored in the strength input buffer 31, arbitrates the request packet based on the strength information, and outputs a connection command for transferring the request packet to the output port 6 to the crossbar 4. Further, the arbitration circuit 36 inputs selection control information from the prediction circuit 35 and outputs a connection command for transferring the request packet indicated by the selection control information to the output port 6 to the crossbar 4. Then, the arbitration circuit 36 outputs the arbitration result to the prediction circuit 35. Here, the arbitration result indicates a request packet in which the arbitration circuit 36 outputs a connection command and its strength information. The arbitration result is output to the prediction circuit 35 and the strength update circuit 37 every time a connection command is output by the arbitration circuit 36. Further, the arbitration circuit 36 determines whether or not the prediction result indicated by the selection control information input from the prediction circuit 35 is incorrect. If the prediction result is incorrect, the arbitration circuit 36 outputs the connection output to the crossbar 4 based on the selection control information. Outputs an interrupt instruction that interrupts execution of the instruction.

The strength update circuit 37 updates the strength information when the request packet indicated by the selection control information input from the prediction circuit 35 matches the request packet indicated by the arbitration result input from the arbitration circuit 36, and outputs it to the strength output buffer 38. To do.
The strength output buffer 38 receives strength information from the strength update circuit 37, temporarily stores the strength information, and outputs the strength information to the connected output port 6.

FIG. 2 is a schematic block diagram illustrating the configuration of the prediction circuit.
The prediction circuit 35 includes a temporary request storage unit 351, a history registration unit 352, an arbitration history storage unit 353, a history search buffer 354, a search unit 355, and a prediction unit 356.

  The temporary request storage unit 351 receives an arbitration result from the arbitration circuit 36 and stores the arbitration result. The temporary request storage unit 351 stores the order of input of arbitration results. When the remaining storage capacity of the temporary request storage unit 351 reaches a predetermined amount due to the input of a new arbitration result, the temporary request storage unit 351 The mediation result registered first is deleted and the newly entered mediation result is stored. Note that in the present embodiment, the storage capacity of the temporary request storage unit 351 only needs to be able to store at least three arbitration results.

The history registration unit 352 reads the arbitration result newly stored in the temporary request storage unit 351 and records the arbitration result in the arbitration history storage unit 353.
The arbitration history storage unit 353 inputs the arbitration result from the history registration unit 352, and stores the arbitration result and an index number indicating the input order of the arbitration result in association with each other. The arbitration history storage unit 353 stores the input order of the arbitration results. When the remaining storage capacity of the arbitration history storage unit 353 reaches a predetermined amount due to the input of a new arbitration result, the arbitration history storage unit 353 The mediation result registered first is deleted and the newly entered mediation result is stored. Note that the storage capacity of the arbitration history storage unit 353 is preferably larger than the storage capacity of the temporary request storage unit 351.

The history search buffer 354 reads the last three arbitration results registered from the temporary request storage unit 351 and temporarily stores them until the search by the search unit 355 is completed.
The search unit 355 searches the arbitration results stored in the arbitration history storage unit 353 for arbitration results having the same combination as the three arbitration results stored in the history search buffer 354.
The prediction unit 356 predicts which request packet is output by the arbitration of the arbitration circuit 36 based on the search result by the search unit 355 and the strength information newly registered in the arbitration buffer circuit 34. The selection control information indicating the received request packet is output to the arbitration circuit 36 and the strength update circuit 37.

  In the arbitration device 3 according to the present embodiment, the strength input buffer 31 receives input of strength information from a plurality of processor cores and input / output devices. Next, the arbitration circuit 36 selects one of the strength information associated with the request packets for the same computing resource by the strength input buffer 31, and selects the request packet associated with the selected strength information as the request packet. Is output to the crossbar 4 to be output to the calculation resource of the issue destination.

On the other hand, the prediction circuit 35 predicts the request packet selected by the arbitration circuit 36 before executing the process by the arbitration circuit 36, and outputs a connection instruction for outputting the request packet to the calculation resource of the request packet issue destination. Output to the crossbar 4.
Then, when the selected request packet and the request packet predicted by the prediction circuit 35 are different, the arbitration circuit 36 outputs an interruption command for interrupting the execution of the connection command by the prediction circuit 35 to the crossbar 4.
The arbitration circuit 36 does not output a connection command to the crossbar 4 when the selected request packet and the request packet predicted by the prediction circuit 35 are the same.

  As a result, it is possible to select request packets efficiently without increasing the content of execution processing per cycle of arbitration processing. The reason why the arbitration process can be speeded up by the arbitration device according to the present embodiment will be described below.

FIG. 3 is a diagram illustrating a flow of pipeline processing of the arbitration circuit.
The arbitration circuit 36 arbitrates request packets by four-stage pipeline processing. That is, the arbitration circuit 36 is based on the port information reading stage X0 that reads the identification information of the output port 6 that is the output destination from the request packet, the output port setting stage X1 that sets the request packet to the output port 6 according to the read identification information, and the intensity information. The arbitration process is performed by sequentially executing the crossbar setting pre-processing stage X2 and the crossbar setting post-processing stage X3 that perform arbitration. Then, the arbitration circuit executes a packet transmission stage XT that outputs a connection command for outputting the request packet selected by the arbitration to the crossbar 4 after arbitration by four-stage pipeline processing. Therefore, the arbitration circuit 36 executes the arbitration process in five cycles. This is equal to the number of cycles required for the conventional arbitration method.

On the other hand, since the prediction circuit 35 generates selection control information in advance, the arbitration circuit 36 executes a control information reading stage P0 that reads a request packet selected from the selection control information generated by the prediction circuit 35, and the read request packet The packet transmission stage XT is output to output a connection command for outputting to the crossbar 4. Thereby, the arbitration circuit 36 can execute the arbitration process in two cycles. Therefore, when the request packet predicted by the prediction circuit 35 matches the request packet selected by the arbitration by the arbitration circuit 36, that is, when the prediction by the prediction circuit 35 is correct, the arbitration process is performed at high speed for three cycles. be able to.
That is, the more accurate the prediction by the prediction circuit 35 is, the faster the arbitration processing by the arbitration device is.

  When the request packet predicted by the prediction circuit 35 and the request packet selected by the arbitration by the arbitration circuit 36 do not match, that is, when the prediction by the prediction circuit 35 is not satisfied, the arbitration circuit 36 generates the prediction circuit 35. The interruption command for interrupting the execution of the connection command output based on the selected control information is output to the crossbar 4 and the connection command is output again. At this time, since the arbitration circuit 36 executes the output of the interruption command and the output of the connection command in parallel, the arbitration process is performed in five cycles. For this reason, even if the prediction by the prediction circuit 35 is lost, no delay occurs compared to the conventional arbitration process.

Next, the operation of the arbitration device according to the present embodiment will be described.
FIG. 4 is a first flowchart showing the operation of the arbitration device.
FIG. 5 is a second flowchart showing the operation of the arbitration device.
First, when a resource requesting device issues a request packet for the same computing resource, the request packet is registered in the input side buffer unit 2 via the input port 1 connected to the resource requesting device that issued the request packet. Then, the strength information included in the request packet registered in the input port 1 is input to the strength input buffer 31 of the arbitration device 3, and the main body of the request packet is input to the request input buffer 32 of the arbitration device 3 (step) S1). Then, the buffer registration circuit 33 extracts the strength information from the request input buffer 32 and registers it in the arbitration buffer circuit 34.

  Next, the prediction circuit 35 reads the last three arbitration results registered among the past arbitration results stored in the temporary request storage unit 351 of its own circuit, and records them in the history search buffer 354 (step S2). Here, the last three arbitration results registered are read by reading the three arbitration results with the newest input order stored in the temporary request storage unit 351. Next, the search unit 355 of the prediction circuit 35 searches for a combination of arbitration results stored in the history search buffer 354 from past arbitration results stored in the arbitration history storage unit 353 (step S3). Specifically, the last three arbitration results registered in the temporary request storage unit 351 are input from “input port 1-4”, “input port 1-5”, and “input port 1-1” in the order of registration. In the case of indicating that the information is registered in the history search buffer 354, the search unit 355 has the arbitration history storage unit 353 set to “input port 1-4”, “input port 1-5”, “input port 1”. The arbitration results stored in the order of “−1” are searched.

  Next, the search unit 355 determines whether the same combination as the arbitration result stored in the history search buffer 354 is stored in the arbitration history storage unit 353 as a result of the search executed in step S3 (step S4). . However, the arbitration result stored at the end of the arbitration history storage unit 353 always matches the arbitration result stored in the history search buffer 354, but the arbitration result is excluded from the search result.

  When the search unit 355 determines that the same combination as the arbitration result stored in the history search buffer 354 is stored in the arbitration history storage unit 353 (step S4: YES), the prediction unit 356 is searched by the search unit 355. The arbitration result registered in the arbitration history storage unit 353 is read immediately after the arbitration result (step S5). Specifically, the prediction unit 356 reads an index number indicating the input order associated with the arbitration result searched by the search unit 355, and stores the arbitration result associated with the index number next to the index number. Read from the unit 353. When a plurality of mediation results are retrieved by the search unit 355, the prediction unit 356 reads all mediation results registered immediately after each mediation result.

  Next, the prediction unit 356 reads the strength information from the arbitration buffer circuit 34, and determines whether there is a match between the issuer of the read strength information and the issuer of the arbitration result read in step S5. (Step S6). If the prediction unit 356 determines that there is a match between issuers (step S6: YES), the prediction unit 356 predicts that the matching request packet is selected by the arbitration circuit 36 (step S7). When there are a plurality of items with the same issuer, it is predicted that a request packet from the most frequently issued issuer will be selected from the search results by the search unit 355, and selection control information indicating the predicted request packet is selected. Generate.

  On the other hand, when the search unit 355 determines in step S4 that the same combination as the arbitration result stored in the history search buffer 354 is not stored in the arbitration history storage unit 353 (step S4: NO), or in step S6 When the prediction unit 356 determines that there is no request packet whose issuer matches the read strength information (step S6: NO), the prediction unit 356 selects the request selected by the arbitration circuit 36 based on the round robin algorithm. The packet is predicted, and selection control information indicating the predicted request packet is generated (step S8).

  When the prediction unit 356 generates selection control information in step S7 or step S8, the arbitration circuit 36 reads the selection control information generated by the prediction unit 356 (step S9), and outputs the request packet indicated by the selection control information to the output port 6 The connection command to be transferred to is output to the crossbar 4 (step S10). That is, the P0 stage and XT stage processes shown in FIG. 3 are executed.

  In parallel with the processing of steps S9 and S10, the arbitration circuit 36 reads the request packet body from the request input buffer 32, reads the port information of the output port included in the request packet (step S11), and reads the read output port. The output port is set according to the port information (step S12), and the arbitration process of the request packet is executed (step S13). That is, the X0 stage, X1 stage, X2 stage, and X3 stage shown in FIG. 3 are executed.

Here, a request packet arbitration method by the arbitration circuit 36 will be described.
The arbitration circuit 36 reads the strength information associated with the request packet stored in the request input buffer 32 from the strength input buffer 31. Then, the arbitration circuit 36 selects a request packet having the largest value indicated by the strength information. When there are a plurality of request packets associated with the strength information having the maximum value, the arbitration circuit 36 determines which request packet to select based on the round robin algorithm.

FIG. 6 is a diagram illustrating a request packet arbitration method.
Here, a request packet arbitration method will be specifically described. As illustrated in FIG. 6, the request input buffer 32 stores request packets input from the input ports 1-1 to 1-5.
The intensity information associated with the request packet input from the input port 1-1 and the request packet input from the input port 1-2 is “3”. The intensity information associated with the request packet input from the input port 1-3 is “5”. The intensity information associated with the request packet input from the input port 1-4 is “4”. The intensity information associated with the request packet input from the input port 1-5 is “1”.

  In this case, the arbitration circuit 36 extracts the one having the maximum value from the intensity information. Here, the strength information “5” associated with the request packet input from the input port 1-3 is the maximum. Therefore, the arbitration circuit 36 extracts the request packet input from the input port 1-3 from the request input buffer 32, and selects the request packet as an arbitration result.

  At the time of the next arbitration, since the request packet input from the input port 1-3 has already been extracted, the strength information “4” associated with the request packet input from the input port 1-4 is the maximum. Therefore, the arbitration circuit 36 extracts the request packet input from the input port 1-4 from the request input buffer 32, and selects the request packet as an arbitration result.

  At the time of the next arbitration, since the request packet input from the input port 1-3 and the input port 1-4 has already been taken out, it is associated with the request packet input from the input port 1-1 and the input port 1-2. The intensity information “3” is the maximum. Therefore, the arbitration circuit 36 takes out one of the request packets input from the input port 1-1 or the input port 1-2 based on the round robin algorithm, and selects the request packet as an arbitration result. In FIG. 6, the request packet input from the input port 1-1 is selected.

When executing the arbitration process in step S13, the arbitration circuit 36 determines whether or not the request packet indicated by the selection control information input from the prediction circuit 35 matches the request packet selected by the arbitration process (step S14). .
If the arbitration circuit 36 determines that the request packets do not match (step S14: NO), the arbitration circuit 36 outputs the interrupt command for interrupting the execution of the connection command output in step S10 and the request packet selected by the arbitration process in step S13. A connection command to be transferred to the port 6 is output to the crossbar 4 (step S15).

  On the other hand, if the arbitration circuit 36 determines in step S14 that the request packets match (step S14: YES), the strength update circuit 37 updates the strength information associated with each request packet and records it in the strength output buffer 38. (Step S16).

Hereinafter, a method for updating the strength information by the strength update circuit 37 will be described.
FIG. 7 is a diagram illustrating a method for updating the intensity information.
The strength update circuit 37 stores, in the internal memory, the target level indicating the level of prediction when the request packet input from the input port 1 is predicted to be selected in association with each of the input ports 1. To do.
Next, the strength update circuit 37 inputs information indicating whether or not the request packet indicated by the selection control information output from the prediction circuit 35 matches the request packet selected by the arbitration process from the arbitration circuit 36. When the strength update circuit 37 determines that the request packets match, the strength update circuit 37 increases the target level associated with the selected request packet, decreases the other target levels, and overwrites and records in the internal memory. . According to the example shown in FIG. 7, the target moderateness of the selected request packet is increased by “4”, and the target intermediate levels of other request packets are decreased by “1”.
On the other hand, if the strength update circuit 37 determines that the request packets do not match, the strength update circuit 37 does not perform the target increase / decrease process.

Then, the strength update circuit 37 determines the value of the strength information based on the target level after the target level increase / decrease process. According to the example shown in FIG. 7, when the target degree is less than 20, the value indicated by the strength information is “1”, and when the target degree is 20 or more and less than 40, the value indicated by the intensity information is “2”. When the target degree is 40 or more and less than 60, the value indicated by the strength information is “3”. When the target degree is 60 or more and less than 80, the value indicated by the strength information is “4” and the target degree is 80. In the above case, the value indicated by the intensity information is “5”.
That is, the intensity information value increases only when the prediction by the prediction circuit 35 is correct. Therefore, the arbitration circuit 36 preferentially selects request packets that are more likely to be predicted. Therefore, the probability that the prediction by the prediction circuit 35 is correct increases, and the arbitration processing by the arbitration device 3 can be speeded up.

  In addition, since the strength information is generated by performing the rounding process on the target moderateness without using the target moderateness as it is as the strength information, the selection by the arbitration circuit 36 can be made random. As a result, even when the application to be executed is changed to an application that outputs a large number of request packets from the resource requesting device with a low target level, the request packet is selected by the resource requesting device with a low target level. Therefore, the arbitration process is repeated, so that the target level of the resource requesting device is improved, so that efficient selection can be performed.

Here, a method for updating the intensity information will be specifically described. As shown in FIG. 7, the internal memory of the strength update circuit 37 stores a target level in association with each of the input ports 1-1 to 1-5.
The target intermediate level of the input port 1-1 is “19”. The target intermediate level of the input port 1-2 is “11”. The target intermediate level of the input ports 1-3 is “13”. The target intermediate level of the input ports 1-4 is “43”. The target intermediate level of the input port 1-5 is “14”.

Then, the strength update circuit 37 selects the request packet input from the input port 1-4 from the arbitration circuit 36, and confirms that the request packet matches the request packet indicated by the selection control information output from the prediction circuit 35. Enter the information shown. As a result, the strength update circuit 37 increases the target level associated with the input port 1-4 by “4” to update it to “47”, and decreases the other target levels by “1”.
Next, the strength update circuit 37 updates the strength information associated with the request packet selected according to the target moderate value. That is, the strength update circuit 37 updates the strength information of the request packet input from the input port 1-4 to “1” because the target intermediate level of the input port 1-4 is “18”, that is, less than 20.

Next, the strength update circuit 37 selects the request packet input from the input port 1-1 from the arbitration circuit 36, and the request packet matches the request packet indicated by the selection control information output from the prediction circuit 35. Enter the information indicating. As a result, the strength update circuit 37 increases the target level associated with the input port 1-1 by “4” to update it to “22”, and decreases the other target levels by “1”.
Next, the strength update circuit 37 sets the strength information of the request packet input from the input port 1-4 to “2” because the target intermediate level of the input port 1-1 is “22”, that is, 20 or more and less than 40. Update.

  Next, the strength update circuit 37 selects the request packet input from the input port 1-3 from the arbitration circuit 36, and the request packet does not match the request packet indicated by the selection control information output from the prediction circuit 35. Enter the information indicating that In this case, the strength update circuit 37 does not update the target level and strength information.

Next, the strength update circuit 37 selects the request packet input from the input port 1-5 from the arbitration circuit 36, and the request packet matches the request packet indicated by the selection control information output from the prediction circuit 35. Enter the information indicating. As a result, the strength update circuit 37 updates the target level associated with the input ports 1-5 to “16” by increasing the target level by “4”, and decreases the other target levels by “1”.
Next, the strength update circuit 37 updates the strength information of the request packet input from the input port 1-4 to “1” because the target intermediate level of the input port 1-1 is “16”, that is, less than 20. .
By repeating such processing, the arbitration circuit 36 preferentially selects request packets that are more likely to be predicted, and the arbitration device 3 can perform arbitration processing at high speed.

  When the arbitration circuit 36 outputs an interruption command and a connection command in step S15, or when the strength update circuit 37 updates the strength information in step S16, the arbitration circuit 36 adds the end of the temporary request storage unit 351 of the prediction circuit 35. The arbitration result is recorded in (Step S17). Next, the history registration unit 352 records the arbitration result newly recorded in the temporary request storage unit 351 at the end of the arbitration history storage unit 353 (step S18).

  Then, the prediction circuit 35 determines whether or not the arbitration circuit 36 has completed the arbitration of all request packets (step S19). For example, the arbitration circuit 36 can determine whether the arbitration is completed by determining whether a request packet is stored in the request input buffer 32. In step S13, the request packets selected by the arbitration process are sequentially extracted from the request input buffer 32. Therefore, if there is a request packet that has not been arbitrated, the request packet is stored in the request input buffer 32. Will be. Therefore, when the request packet is stored in the request input buffer 32, the prediction circuit 35 determines that the arbitration of the request packet has not ended.

  When the prediction circuit 35 determines that there is a request packet for which arbitration has not ended (step S19: NO), the process returns to step S2 to perform arbitration for the next request packet. On the other hand, when the prediction circuit 35 determines that the arbitration for all request packets has been completed (step S19: YES), the process ends.

  As described above, according to the present embodiment, before the arbitration circuit 36 executes the arbitration, the prediction circuit 35 predicts the selected request packet and outputs a connection command for causing the crossbar 4 to output the request packet. To do. As a result, the arbitrating device 3 can efficiently select a request packet without increasing the execution process content per cycle of the arbitration process.

As described above, the embodiment of the present invention has been described in detail with reference to the drawings. However, the specific configuration is not limited to the above, and various design changes and the like can be made without departing from the scope of the present invention. It is possible to
For example, in this embodiment, when the search unit 355 determines in step S4 that the same combination as the arbitration result stored in the history search buffer 354 is not stored in the arbitration history storage unit 353, or prediction is performed in step S6. A case where the prediction unit 356 predicts a request packet selected by the arbitration circuit 36 based on a round-robin algorithm when the unit 356 determines that there is no request packet whose issuer matches the read strength information. Although described above, the present invention is not limited to this. For example, a request packet may be selected at random, and the selected request packet may be a request packet predicted to be selected by the arbitration circuit 36.

  In the present embodiment, when the arbitration circuit 36 performs the arbitration process, when there are a plurality of request packets associated with the strength information having the maximum value, the arbitration circuit 36 determines which request based on the round robin algorithm. The case of determining whether to select a packet has been described, but the present invention is not limited to this. For example, the arbitration circuit 36 may select a request packet at random.

  Further, in the present embodiment, the case where the resource requesting device gives strength information to the request packet and outputs the request packet to the crossbar arbitration device is described. However, the present invention is not limited to this. The arbitration circuit 36 of the arbitration device 3 includes the strength information storage unit that inputs the packet to the crossbar arbitration device, and the arbitration device 3 stores the strength information in association with the identification information of the input port 1. Even if the arbitration process is performed based on the intensity information read from the storage unit, the same effect as in the present embodiment can be obtained.

  In the present embodiment, the case has been described where the history search buffer 354 of the prediction circuit 35 stores the three arbitration histories stored at the end of the temporary request storage unit 351 in step S2, but the present invention is not limited thereto. Four or more arbitration histories may be stored, or one or two may be stored.

  The arbitration device 3 described above has a computer system inside. The operation of each circuit described above is stored in a computer-readable recording medium in the form of a program, and the above processing is performed by the computer reading and executing the program. Here, the computer-readable recording medium means a magnetic disk, a magneto-optical disk, a CD-ROM, a DVD-ROM, a semiconductor memory, or the like. Alternatively, the computer program may be distributed to the computer via a communication line, and the computer that has received the distribution may execute the program.

  The program may be for realizing a part of the functions described above. Furthermore, what can implement | achieve the function mentioned above in combination with the program already recorded on the computer system, and what is called a difference file (difference program) may be sufficient.

  DESCRIPTION OF SYMBOLS 1, 1-1 to 1-5 ... Input port 2, 2-1 to 2-5 ... Input side buffer part 3 ... Arbitration apparatus 4 ... Crossbar 5, 5-1 to 5-5 ... Output side buffer part 6, 6 -1-6-5 ... output port 21 ... input buffer 22 ... input side FIFO buffer control circuit 23 ... FIFO buffer 24 ... output side FIFO buffer control circuit 25 ... output buffer 31, 31-1 to 31-5 ... intensity input buffer 32 ... Request input buffer 33 ... Buffer registration circuit 34 ... Arbitration buffer circuit 35 ... Prediction circuit 36 ... Arbitration circuit 37 ... Strength update circuit 38, 38-1 to 38-5 ... Strength output buffer 351 ... Temporary request storage unit 352 ... History Registration unit 353 ... arbitration history storage unit 354 ... history search buffer 355 ... search unit 356 ... prediction unit

Claims (5)

An arbitration device that arbitrates resource requests issued from a plurality of resource requesting devices and that indicates requests for use of computing resources by the resource requesting devices, and controls a crossbar that connects the resource requesting devices and the computing resources. And
An input unit that receives input of resource requests from a plurality of the resource requesting devices;
An arbitration unit for selecting one of resource requests for the same computing resource by the input unit and outputting a connection command for outputting the selected resource request to a computing resource to which the resource request is issued; ,
Before executing the processing by the arbitration unit, a prediction unit that predicts a resource request selected by the arbitration unit and outputs a connection instruction to the crossbar to output the resource request to a calculation resource to which the resource request is issued. When,
When the resource request selected by the arbitration unit is different from the resource request predicted by the prediction unit, an interruption unit that outputs an interruption command for interrupting execution of the connection command by the prediction unit to the crossbar ;
A history registration unit for registering in the arbitration history storage unit in the order in which the resource requests selected by the arbitration unit in the past processing are selected ;
The arbitration unit does not output the connection command to the crossbar when the resource request selected by the arbitration unit and the resource request predicted by the prediction unit are the same ,
The prediction unit includes resource requests registered immediately after resource requests stored in the arbitration history storage unit in the same order as the last predetermined number of resource requests selected by the arbitration unit. An arbitration device that predicts a resource request selected by An arbitration device that arbitrates resource requests issued from a plurality of resource requesting devices and that indicates requests for use of computing resources by the resource requesting devices, and controls a crossbar that connects the resource requesting devices and the computing resources. And
An input unit that receives input of resource requests from a plurality of the resource requesting devices;
An arbitration unit for selecting one of resource requests for the same computing resource by the input unit and outputting a connection command for outputting the selected resource request to a computing resource to which the resource request is issued; ,
Before executing the processing by the arbitration unit, a prediction unit that predicts a resource request selected by the arbitration unit and outputs a connection instruction to the crossbar to output the resource request to a calculation resource to which the resource request is issued. When,
When the resource request selected by the arbitration unit is different from the resource request predicted by the prediction unit, an interruption unit that outputs an interruption command for interrupting execution of the connection command by the prediction unit to the crossbar;
Wherein each resource requesting device, in the past the process, and a strength information calculation unit for calculating a strength information indicating the degree of resource requests and said prediction unit and the resource request the arbitration unit selects predicts are the same,
The arbitration unit determines a resource request to be selected based on the strength information calculated by the strength information calculation unit, and the resource request selected by the arbitration unit and the resource request predicted by the prediction unit are the same In addition, the arbitration device does not output the connection command to the crossbar . Uses an arbitration device that arbitrates resource requests issued by a plurality of resource requesting devices and indicates a request for use of the computing resource by the resource requesting device, and controls a crossbar connecting the resource requesting device and the computing resource. The mediation method,
The input unit receives input of resource requests from the plurality of resource requesting devices,
The arbitration unit selects one of the resource requests for the calculation resources having the same input unit,
The prediction unit predicts a resource request selected by the arbitration unit before executing the processing by the arbitration unit, and outputs a connection instruction to the crossbar to output the resource request to a calculation resource to which the resource request is issued. Output,
The interruption unit, when the resource request selected by the arbitration unit and the resource request predicted by the prediction unit are different, outputs an interruption command to interrupt the execution of the connection command by the prediction unit to the crossbar,
The history registration unit registers the resource request selected by the arbitration unit in the past processing in the order of selection in the arbitration history storage unit,
The arbitration unit, when the resource request selected by the arbitration unit and the resource request predicted by the prediction unit are different, outputs a connection instruction to output the selected resource request to a calculation resource to which the resource request is issued. Output to the crossbar ,
The prediction unit includes resource requests registered immediately after resource requests stored in the arbitration history storage unit in the same order as the last predetermined number of resource requests selected by the arbitration unit. An arbitration method characterized by predicting as a resource request selected by . Uses an arbitration device that arbitrates resource requests issued by a plurality of resource requesting devices and indicates a request for use of the computing resource by the resource requesting device, and controls a crossbar connecting the resource requesting device and the computing resource. The mediation method,
The input unit receives input of resource requests from the plurality of resource requesting devices,
The arbitration unit selects one of the resource requests for the same computing resource by the input unit, and outputs a connection command for outputting the selected resource request to the computing resource to which the resource request is issued to the crossbar. And
The prediction unit predicts a resource request selected by the arbitration unit before executing the processing by the arbitration unit, and outputs a connection instruction to the crossbar to output the resource request to a calculation resource to which the resource request is issued. Output,
The interruption unit, when the resource request selected by the arbitration unit and the resource request predicted by the prediction unit are different, outputs an interruption command to interrupt the execution of the connection command by the prediction unit to the crossbar,
The strength information calculation unit calculates strength information indicating the degree to which the resource request selected by the arbitration unit and the resource request predicted by the prediction unit are the same in the past processing for each resource requesting device,
The arbitration unit determines a resource request to be selected based on the strength information calculated by the strength information calculation unit, and when the resource request selected by the arbitration unit and the resource request predicted by the prediction unit are different, An arbitration method comprising: outputting to the crossbar a connection command for outputting the selected resource request to a calculation resource to which the resource request is issued. An arbitration device that issues a resource request indicating a request for use of a computing resource by the resource requesting device issued from a plurality of resource requesting devices, and controls a crossbar that connects the resource requesting device and the computing resource,
An input unit for receiving input of resource requests from a plurality of the resource requesting devices;
An arbitration unit that selects one of resource requests for the same computing resource by the input unit and outputs a connection command for outputting the selected resource request to a computing resource to which the resource request is issued;
Before executing the processing by the arbitration unit, a prediction unit that predicts a resource request selected by the arbitration unit and outputs a connection instruction to the crossbar to output the resource request to a calculation resource to which the resource request is issued. ,
When the resource request selected by the arbitration unit is different from the resource request predicted by the prediction unit , an interruption unit that outputs an interruption command for interrupting execution of a connection command by the prediction unit to the crossbar ;
Function as a history registration unit that registers in the arbitration history storage unit in the order of selection of resource requests selected by the arbitration unit in the past processing ;
The arbitration unit does not output the connection command to the crossbar when the resource request selected by the arbitration unit and the resource request predicted by the prediction unit are the same ,
The prediction unit includes resource requests registered immediately after resource requests stored in the arbitration history storage unit in the same order as the last predetermined number of resource requests selected by the arbitration unit. A program characterized by predicting as a resource request selected by .

Images