JPH11212927A - Conflict arbitration method - Google Patents

Abstract

PROBLEM TO BE SOLVED: To continuously send the elements for every request and to shorten the processing time even when the elements which are continuously sent from plural processors conflict with each other. SOLUTION: A unit node.consists of the processors 1 to 4, a common memory 5 and a crossbar network 6 which connects these processors and memory together. The network 6 includes the input buffers 8 to 11 which are placed against the processors 1 to 4 respectively, a conflict arbitration circuit 12 which performs the conflict arbitration when the independent elements are transferred between the memory 5 and the processors 1 to 4 and also the conflict arbitration when the data are transferred among plural nodes where the processors 1 to 4 are connected together via an inter-node connecting device 7 and then outputs a selection signal, and a data selector part 13 which selects one of elements which are sent from the buffer 8 based on the selection signal outputted from the circuit 12 and outputs the selected element to the memory 5 or the device 7.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a contention arbitration method, and more particularly to a contention arbitration circuit in which a contention arbitration circuit transfers contention-dependent elements between a plurality of processors and a memory, and a plurality of processors form an inter-node connection device. The present invention relates to a contention arbitration method for performing contention arbitration at the time of data transfer between a plurality of nodes connected via the same device.

[0002]

2. Description of the Related Art In a conventional competitive arbitration method, the target of arbitration is often a transfer request to one type of transfer destination.
In the case of Japanese Patent Application Laid-Open No. 6-195313, a device that can cope with various cases is incorporated. However, basically, the function of requesting transfer to one type of transfer destination can be prevented from disturbing the priority order in all priority circuits by using the priority switching function, and the access performance is reduced due to contention. However, it does not correspond to an example in which the arbitration target is a transfer request to a plurality of types of transfer destinations.

As an example of a transfer request to a plurality of types of transfer destinations, although the configuration is different from that of JP-A-6-195313, FIG.
FIG. 1 shows an example of a conventional competitive arbitration circuit for controlling a high-speed crossbar switch.

[0004] This conventional high-speed crossbar switch control contention arbitration circuit is applied to a conventional information processing apparatus which performs the same service as the present invention shown in the block diagram of FIG.

First, the configuration of FIG. 6 will be described. As a whole, a plurality of processors 100, 101, 102, 1
03, a memory 104 commonly used by the processors 100, 101, 102, and 103;
A crossbar network 105 that connects between the memory devices 01, 102, and 103 and the memory 104 is a unit node, and this node is an information processing device that is connected to a plurality of nodes via an internode connection device 106. Further, the crossbar network 105 transfers input elements 107, 108, 109, 110 provided for a plurality of processors, and independent elements between the plurality of processors 100, 101, 102, 103 and the memory 104. Conflict arbitration at the time, and the processors 100, 101, 102, 1
03, a contention arbitration circuit 111 that performs contention arbitration at the time of data transfer with a plurality of nodes connected via the inter-node connection device 106, and outputs a select signal; and a transfer instruction output by the contention arbitration circuit 111. The plurality of input buffers 107, 108, 109, 11
A data selector unit 112 selects one element from elements transmitted from 0 and outputs the selected element to either the memory 104 or the inter-node connection device 106.

Next, the configuration of FIG. 7 will be described. The input buffers 107 to 110 are connected to a processor (not shown), receive transfer request data, and output data and element continuation number information (hereinafter, referred to as TAG). The request type recognition circuit 113 receives the TAG from the input buffers 107 to 110, sets the bit corresponding to the port having the request to “1”, and sends the bit to the selector 114. The selector 114 uses the output of an OR circuit (hereinafter referred to as OR) 115 as a select signal, selects the output of the request type recognition circuit 113 if this is "0", and selects the output value of the register 116 if this is "1". The priority encoder 117 is of a fixed priority type. Inverter 118
Is an inverted value of the output value of the priority encoder 117. The AND circuit 119 is connected to the selector 11
4 and the output value of the inverter 118. The register 116 inputs the output value of the AND circuit 119, and the OR 115 obtains the logical sum of the register output value. The distribution circuit 120 distributes the output of the OR 115 into 4 bits and outputs it as a Hold signal.

Next, the operation will be described. FIG. 8 is an operation diagram showing the operation state of the input buffer in clock units, and FIG. 9 is an explanatory diagram showing the bit state of each signal for each clock. 6 to 9 are used for the description.

First, at the timing of clock 0, it is assumed that "0000" is buffered in the register 116 and a request as shown in FIG. 8A is buffered in the input buffers 107 to 110. Where A1, A
2, D1 and D2 transmit a 2T request of two consecutive elements,
1, B2, B3, B4, C1, C2, C3, and C4 indicate a 4T request with four consecutive elements.

At the clock 1, the value of the register 116 is "0".
000 ", the output value" 0 "of the OR 115 is distributed by the distribution circuit 701 and output as a Hold signal having a value of" 0000 ".The input buffers 107 to 110 receive the Hold signals having a value of" 0 ", respectively. The request group A1,
B1, C1, and D1 are output to the contention arbitration circuit 111 and the data selector 112. The state of the input buffer at this time is shown in FIG. In the contention arbitration circuit 111, an information portion of each request (hereinafter, referred to as TAG) is received by the request type recognition circuit 113. The request type recognition circuit 113 identifies the TAG and outputs "1111" because all the requests are valid. The selector 114 inputs the output value of the OR 115 whose value is “0” as the select signal, and outputs the output value of the request type recognition circuit 113 “
1111 "and the priority encoder 117
To enter. "1" is assigned to the priority encoder 117.
111 "is input, arbitration is performed according to a specific priority, and" 1000 "is output as a select signal. At this time, the priority encoder 117 assumes that the leftmost bit among the input 4 bits has the highest priority. In the data select 112, the select signal “100” output from the priority encoder 117 is output.
By inputting 0 ", data A1 of input port # 0 is selected and output to inter-node connecting device 106. Inverter 3
02 is an inverted value “0111” of the select signal “1000”
Is output. The AND circuit 303 outputs the output value “1111” of the selector 114 and the output value “011” of the inverter 302.
The logical AND of "1" is obtained and "0111" is output to the register 116. The state at this time is shown by a clock 1 in FIG.

At clock 2, the value of register 116 is set to "0".
111 ”, the output value of the OR 115 is“ 1 ”, and“ 1111 ”is output as a Hold signal.
Since the ld signal is received, the state of the input buffers 107 to 110 does not change. The selector 114 receives O as a control signal.
The output value “1” of R115 is input, and the value “0111” of the register 116 is selected. The priority encoder 117 inputs the output value “0111” of the selector 114 and outputs “0100” as a select signal. The data selector 112 receives the select signal “0100”, selects the data B1 in the input buffer 108, and outputs the data B1 to the inter-node connection device 106. The inverter 118 receives a select signal and outputs an inverted value “1011”.
The AND circuit 119 outputs the output value “011” of the selector 114.
The logical product of “1” and the output value “1011” of the inverter 118 is calculated, and “0011” is output to the register 116.
The state at this time is shown by clock 2 in FIG.

At the timing of clock 3, since the register value is "0011", the output value of OR 115 is "1" and "1111" is output as the Hold signal. In the input buffers 107 to 110, Hos each having a value of “1”
Since the ld signal is received, the state of the input buffer does not change. The selector 114 inputs the output value “1” of the OR 115 as a control signal and selects the value “0011” of the register 116. The priority encoder 117 inputs the output value “0011” of the selector 114 and outputs “0010” as a select signal. The data selector 112 receives the select signal “0010”, and
09 data C1 is selected and output to the inter-node connection device 106. The inverter 118 receives a select signal and outputs an inverted value “1101”. AND circuit 119
Is the output value “0011” of the selector 114 and the inverter 1
The logical product with the output value “1101” of No. 18 is obtained and “000” is obtained.
1 "is output to the register 116. The state at this time is shown by the clock 3 in FIG.

At the timing of clock 4, since the value of the register is "0001", the output value of OR 115 is "1", and "1111" is output as a Hold signal. In the input buffers 107 to 110, Hos each having a value of “1”
Since the ld signal is received, the state of the input buffer does not change. The selector 114 receives the output value “1” of the OR 115 as a control signal and selects the value “0001” of the register 116. The priority encoder 117 inputs the output value “0001” of the selector 114 and outputs “0001” as a select signal. The data selector 112 receives the select signal “0001”, and
10 data D1 is selected and output to the inter-node connection device 106. The inverter 118 receives a select signal and outputs an inverted value “1110”. AND circuit 119
Is the output value “0001” of the selector 114 and the inverter 1
AND with the output value of "1110" of "18" to obtain "000"
0 "is output to the register 116. The state at this time is shown by the clock 4 in FIG.

At the timing of clock 5, since the value of the register is "0000", the output value of OR 115 is "0" and "0000" is output as a Hold signal. In each of the input buffers 107 to 110, a Ho having a value of “0”
Since the ld signal is received, the buffered request is skewed by one step, and new requests A2, B2,
C2 and D2 are sent to the contention arbitration circuit 111 and the data selector 112. The state of each input buffer at this time is shown in FIG. In the competition arbitration circuit 111, the request type recognition circuit 113 receives the TAG sent from the input buffer. Request type recognition circuit 113
Identifies the TAG and outputs "1111" because all are valid requests. The selector 114 inputs the output value of the OR 115 having the value “0” as the select signal, and outputs the output value “111” of the request type recognition circuit 113.
1 "is input to the priority encoder 117. In the priority encoder 117," 111 "is selected.
1), arbitration is performed in accordance with a specific priority, and "1000" is output as a select signal.The data selector 112 receives the select signal "1000" output from the priority encoder 117, and outputs data A2 of the input buffer 107. And outputs the same to the inter-node connecting device 106. The inverter 118 outputs the inverted value “0111” of the select signal “1000” .The AND circuit 119 outputs the output value “11” of the selector 114.
The logical product of “11” and the output value “0111” of the inverter 118 is calculated, and “0111” is output to the register 116.
The state at this time is shown by clock 5 in FIG.

In the timing of the clock 6, the clock 2
The same operation as that of the timing of
08 data B2 is output to the inter-node connection device 106. The state at this time is shown by clock 6 in FIG.

At the timing of clock 7, clock 3
The same operation as that of the timing of
09 is output to the inter-node connection device 106. The state at this time is shown by a clock 7 in FIG.

At the timing of clock 8, clock 3
The same operation as that of the timing of
10 data D2 is output to the inter-node connection device 106. The state at this time is shown by a clock 8 in FIG.

At the timing of the clock 9, since the value of the register is "0000", the output value of the OR 115 is "0", and "0000" is output as the Hold signal. Each of the input buffers 107 to 110 has an H value of “0”.
old signal, the buffered request is skewed by one step, and new requests B3 and C3
To the contention arbitration circuit 111 and the data selector 112. The state of the input buffer at this time is shown in FIG. In the competition arbitration circuit 111, the input buffer 1
The TAG transmitted from 07 to 110 is received by the request type recognition circuit 113. The request type recognition circuit 113 identifies the TAG and outputs “0110”.
The selector 114 inputs the output value of the OR 115 whose value is “0” as the select signal, selects the output value “0110” of the request type recognition circuit 113, and inputs it to the priority encoder 117. The priority encoder 117 inputs “0110”, performs arbitration in accordance with a specific priority order, and outputs “0110” as a select signal.
The data selector 112 inputs the select signal "0100" output from the priority encoder 117, selects the data B3 of the input buffer 108, and outputs the data B3 to the inter-node connecting device 106.
The inverter 118 outputs an inverted value “1011” of the select signal “0100”. The logical product circuit 119 calculates the logical product of the output value “0110” of the selector 114 and the output value “1011” of the inverter 118, and stores “AND” in the register 116.
0010 "is output. The state at this time is shown by a clock 9 in FIG.

At the timing of the clock 10, since the value of the register 116 is "0010", the output value of the OR 115 is "1", and "1111" is output as a Hold signal. Each of the input buffers 107 to 110 receives a Hold signal having a value of “1”, so that the state of the input buffer does not change. The selector 114 receives O as a control signal.
The output value "1" of R115 is input, and the value "0010" of the register 116 is selected. The priority encoder 117 inputs the output value “0010” of the selector 114 and outputs “0010” as a select signal. The data selector 112 receives the select signal “0010”, selects the data C3 in the input buffer 109, and outputs the data C3 to the inter-node connecting device 106. The inverter 118 receives a select signal and outputs an inverted value “1101”.
The AND circuit 119 outputs the output value “001” of the selector 114.
The logical product of "0" and the output value "1101" of the inverter 118 is calculated, and "0000" is output to the register 116.
The state at this time is shown by a clock 10 in FIG.

At the timing of clock 11, since the register value is "0000", the output value of OR 115 is "0".
And outputs “0000” as a Hold signal.
Each of the input buffers 107 to 110 receives a Hold signal whose value is “0”, so that the buffered request is skewed by one step and new requests B4 and C
4 is sent to the contention arbitration circuit 111 and the data selector 112. The state of the input buffer at this time is shown in FIG. In the contention arbitration circuit 111, the TAG sent from the input buffer is recognized by the request type recognition circuit 113.
Receive at. The request type recognition circuit 113 identifies the TAG and outputs “0110”. The selector 114 inputs the output value of the OR 115 whose value is “0” as the select signal, and outputs the output value of the request type recognition circuit 113 “
0110 ”and the priority encoder 117
To enter. "0" is assigned to the priority encoder 117.
110 "is input, arbitration is performed in accordance with a specific priority, and" 0100 "is output as a select signal.The data selector 112 receives the select signal" 0100 "output from the priority encoder 117, and outputs data B4 of the input buffer 108. And outputs it to the inter-node connecting device 106. The inverter 118 outputs an inverted value “1011” of the select signal “0100” .The AND circuit 119 outputs the output value “01” of the selector 114.
The logical product of "10" and the output value "1011" of the inverter 118 is calculated, and "0010" is output to the register 116.
The state at this time is shown by a clock 11 in FIG.

At the timing of the clock 12, since the value of the register 116 is "0010", the output value of the OR 115 is "1", and "1111" is output as a Hold signal. Each of the input buffers 107 to 110 receives a Hold signal having a value of “1”, so that the state of each input buffer does not change. The selector 114 inputs the output value “1” of the OR 115 as a control signal and selects the value “0010” of the register 116. The priority encoder 117 inputs the output value “0010” of the selector 114 and outputs “0010” as a select signal. The data selector 112 receives the select signal “0010”, selects the data C4 in the input buffer 109, and outputs the data C4 to the inter-node connecting device 106. The inverter 118 receives a select signal and outputs an inverted value “1101”.
The AND circuit 119 outputs the output value “001” of the selector 114.
The logical product of "0" and the output value "1101" of the inverter 118 is calculated, and "0000" is output to the register 116.
The state at this time is shown by a clock 12 in FIG.

The processing of the request group has been completed by the above series of operations. FIG. 9B shows the order of data output to the inter-node connecting device 106. Figure 9 (b)
When attention is paid to the requests B1 to B4, it can be understood that the requests are not continuously transmitted to the processor.

Since the operation is performed as described above, the data transmission order is as shown in FIG.

FIG. 10 is a comparison diagram showing the operation results of the present invention and the conventional circuit in the form of a time chart. FIG. 10A shows the operation result of the embodiment of the present invention, and FIG.
FIG. 7B shows the operation result of the circuit shown in FIG.

FIG. 10 shows an operation result when an instruction is executed for the circuit shown in FIG. 7 such that processing using 4T request data takes 4 cycles and processing using 2T request data takes 2 cycles. It is shown in FIG.

[0025]

According to the above-described conventional contention arbitration method, when a conflict occurs between continuous elements sent from a plurality of processors, the continuous elements become discontinuous and the inter-node connection device becomes inconsistent. Will be sent out. For this reason, when the processor of another node executes an instruction using the received data, it is necessary to wait for all the discontinuous request elements to arrive, leading to a problem of an increase in processing time.

[0026] An object of the present invention is to continuously transmit elements for each request even if there is a conflict between continuous elements sent from a plurality of processors. Is to provide a competitive arbitration method capable of shortening the time.

[0027]

A contention arbitration method according to the present invention comprises a plurality of processors, a memory commonly used by the plurality of processors, and a crossbar network connecting between the plurality of processors and the memory. In a contention arbitration method in an information processing device in which a unit consisting of a node is connected to a plurality of nodes via an inter-node connection device, the crossbar network includes an input provided corresponding to the plurality of processors. Between a buffer and a plurality of nodes connected by the plurality of processors and the memory via the inter-node connection device, in which contention arbitration at the time of transfer of elements each being independent data between the plurality of processors and the memory and the plurality of processors are connected via the inter-node connection device; And performs a contention arbitration during data transfer, and outputs a select signal for selecting and instructing one of the elements to be transferred. A arbitration circuit for selecting one of the elements sent from the plurality of input buffers in accordance with a select signal instructing a transfer output from the contention arbitration circuit, and selecting one of the memory and the inter-node connection device; The contention arbitration circuit requests the transfer and instructs the transfer in ascending order of the number of consecutive elements among the competing data.

According to the contention arbitration method of the present invention, the contention arbitration circuit outputs an active holding signal to an input buffer in which an element other than the processing target is present during the processing of the element, and holds the buffered element. Control may be performed.

According to the contention arbitration method of the present invention, the processor
When transmitting transfer data composed of an arbitrary number of elements to the memory or the inter-node connecting device, the transfer data may be transmitted by adding the number of elements and the destination device name to each element of the transfer data.

According to the contention arbitration method of the present invention, when the destination device name of the transfer data added to the transfer data is an inter-node connection device, the contention arbitration circuit of the processor selected by the contention arbitration between the processors. All elements of the data may be transmitted, and after the transmission is completed, the contention arbitration between the processors may be performed again.

According to the conflict arbitration method of the present invention, when the destination device name of the transfer data added to the transfer data is a memory, the conflict arbitration circuit selects one element of the processor selected by the conflict arbitration between the processors. , The contention arbitration between processors may be performed again.

According to the contention arbitration method of the present invention, the input buffer stores data sent from the processor, sends the number of elements and the destination device name to the contention arbitration circuit, and sends the elements to the data selector. When the holding signal output from the contention arbitration circuit is active, the buffered element may be held.

[0033]

Next, embodiments of the present invention will be described with reference to the drawings.

FIG. 1 is a block diagram showing a first embodiment of the present invention.

In the apparatus to which the present invention is applied, first, a unit node is divided into a plurality of processors 1, 2, 3, 4; a memory 5 commonly used by the processors 1, 2, 3, 4; This is an information processing apparatus configured with a crossbar network 6 that connects between 2, 3, 4 and the memory 5, and this node is connected to a plurality of nodes via an inter-node connection device 7. Further, the crossbar network 6 includes input buffers 8, 9, 1 provided for a plurality of processors.
0, 11 and a plurality of processors 1, 2, 3, 4 and the arbitration at the time of transfer of independent elements between the memory 5 and the processors 1, 2, 3, 4 respectively. A contention arbitration circuit 12 that performs contention arbitration during data transfer with a plurality of nodes connected via the same and outputs a select signal, and a plurality of input buffers in accordance with a select signal output from the contention arbitration circuit 12 that indicates transfer. 8,
It comprises a data selector unit 13 for selecting one element from among the elements sent from 9, 10 and 11 and outputting the selected element to one of the memory 5 and the node connection device 7.

The general operation will be described below using an example of instruction transfer between nodes.

Processors 1, 2, 3, and 4 store data and TA
A 2T request consisting of G and a 2T request outputted continuously for two elements and a 4T request outputted continuously for four elements are outputted to the input buffers 8, 9, 10 and 11. Input buffer 8,
Reference numerals 9, 10, and 11 denote FIFO-controlled buffers for buffering 2T requests and 4T requests.
G is the contention arbitration circuit 12 and data is the data selector 1
Output to 3. Also, input buffers 8, 9, 10, 11
Receives the Hold signal output from the contention arbitration circuit 12, and if the Hold signal is "0", the buffered request is skewed by one step to output the next request. If the Hold signal is "1", the buffer is output. Keep the contents of the ring. The contention arbitration circuit 12 receives the TAG sent from the input buffers 8, 9, 10, and 11 to perform contention arbitration, and sends a select signal to the data selector unit 13. Further, the contention arbitration circuit 12 checks the contention between a plurality of requests sent from the input buffers 8, 9, 10, and 11, and sends the data of the input buffer having a higher priority to the inter-node connecting device 7 with priority. Select signal to the data selector unit 13 to make the input buffer individually Ho in accordance with the processing state of the contention request.
Sends the ld signal to control the input buffer. The data selector 13 selects the data by inputting the select signal sent from the contention arbitration circuit 12 and sends the data to the inter-node connecting device 7.

Next, the configuration of the contention arbitration circuit will be described. FIG. 2 is a circuit diagram of the contention arbitration circuit shown in FIG.

The input buffers 8, 9, 10, and 11 are connected to a processor (not shown), receive transfer request data, and output data and TAG. The contention arbitration circuit 12 of the present embodiment has four request input ports,
It is assumed that T requests and 4T requests can be processed.

The contention arbitration circuit 12 individually recognizes requests input to the four request receiving ports (input ports), and outputs “1” to the bit corresponding to the port to which the 4T request is input on the signal line 51. The request type recognition circuit 14 that outputs “1” to the bit corresponding to the port to which the 2T request has been input,
An output signal of an input OR circuit (hereinafter referred to as a two-input OR) 15 is input as a selection signal. If the selection signal is "0", the value of the signal line 51 is selected. A selector 17 for selecting and outputting the output signal of the holding register 16 and an output signal of the input OR circuit 15 are input as selection signals. If the selection signal is "0", the value of the signal line 52 is selected and the selection signal is output. If "1", a selector 19 for selecting and outputting an output signal of the conflict information holding register 18;
The value of the output signal line 53 of the counter control circuit 20 is input as a selection signal. If the selection signal is "0", the output signal of the selector 17 is selected. If the selection signal is "1", the selector 1 is selected.
9, the priority encoder input selector 21 for selecting and outputting an output signal of the priority encoder 9 and the output signal of the priority encoder input selector 21 are input, and only the bit corresponding to the youngest request reception port (input port) number is set to "1". A fixed-priority priority encoder 22 that outputs a select signal to the data selector 13, an inverter 23 that receives an output value of the priority encoder 22 and outputs an inverted value thereof, and an output signal of the priority encoder input selector 21. AND circuit 24 that outputs a logical product of the output signal of inverter 23 and H that holds and outputs the output value of inverter 23
The output signal of the register 25 for generating the old signal and the output signal of the AND circuit 26 are input as a selection signal, and the value of the selection signal is “0”.
In the case of, the selector 27 for selecting the output signal of the selector 17 and selecting and outputting the output signal of the AND circuit 24 when the value of the selection signal is "1";
The output signal of the AND circuit 28 is input as a selection signal, and when the value of the selection signal is "0", the output signal of the selector 19 is selected. When the value of the selection signal is "1", the output signal of the AND circuit 24 is output. And a selector 29 for inputting the conflict information holding register that outputs the selected value to the register 18 for holding the conflict information, a register 16 for holding and outputting the output value of the selector 27 for inputting the conflict information holding register, A conflict information holding register 18 for holding and outputting the output value of the conflict information holding register input selector 29; an output signal of the conflict information holding register 16 and an output signal of the conflict information holding register 18; A four-input OR circuit (hereinafter referred to as a four-input OR) 30 for taking the logical sum of the four types of signals of the value of the signal line 51 and the value of the signal line 52 for each bit and outputting the result;
The logical product of the input OR 30 and the output signal of the Hold signal generation register 25 is obtained and the input buffers 8, 9, 10, 1 are calculated.
1, an AND circuit 31 that outputs a Hold signal;
4-input O which takes the logical sum of the output signals of the conflict information holding register 16 and outputs it to the signal line 54 and the 2-input OR 15
R32 is a logical OR of the output signal of the conflict information holding register 18 and is output to the signal line 55 and the two-input OR15, and the logical sum of the output value of the four-input OR32 and the output value of the four-input OR33. A two-input OR 15 which outputs the selected signal as a selection signal to the selectors 17 and 19; an OR 34 which takes the logical sum of the 4-bit output values of the selector 17 and outputs the result to the counter control circuit 20;
OR35 which takes the logical sum of the output values of the OR and outputs it to the counter control circuit 20, and the output signals of the ORs 34 and 35 and the state value "
The output signal of the 0 "recognition circuit 36 is input, and values are output to the output signal line 53 and the signal lines 56 and 57 according to a predetermined definition between the input and the operation shown in FIG. A counter control circuit 20 that issues an instruction to set a value or a subtraction instruction to the subtraction counter 37,
A function of setting a value in the counter or decrementing the value of the counter by "1" in accordance with an instruction from the counter control circuit 20 and a function of receiving a decrement instruction when the value of the counter becomes "0"
It has a function to hold 0 and changes the counter value to the state value "0".
When the counter value output from the subtraction counter 37 is input to the recognition circuit 36 and the state value "1" recognition circuit 38, and the counter value is "1", the logical product circuits 26 and 28 output "1". The state value "1" recognizing circuit 38 for outputting "" and the counter control circuit 2 when the counter value output from the subtraction counter 37 is inputted and the counter value is "0".
A state value "0" recognition circuit 36 that outputs a value "1" to 0;
A logical product circuit 26 which takes the logical product of the output value of the state value "1" recognizing circuit 38 and the value of the signal line 56 and sends it as a selection signal to the conflict information holding register input selector 27;
An AND circuit 28 which takes the logical product of the output value of the 1 "recognizing circuit 38 and the value of the signal line 57 and sends it to the competitive information holding register input selector 29 as a selection signal.

Next, the operation of the first embodiment of the present invention will be described. 3 and 4 are operation diagrams showing the operation state of the input buffer in units of clocks, and FIG. 5 is an explanatory diagram showing the bit state of each signal for each clock. 1 to 5 are used for the description.

FIG. 3A is an image of the first request group stored in the input buffer. A1, A
2, D1 and D2 indicate 2T requests, and B1,
B2, B3, B4, C1, C2, C3, and C4 indicate 4T requests. In the initial state, it is assumed that the registers of the contention arbitration unit are all 0 values.

In the first clock, the requests A1, B
The TAG sections 1, 1, and 1 are sent to the contention arbitration section. H
The initial value “0000” of the old signal generation register 25
The AND circuit 31 receives the value “0” as the Hold signal.
The request type recognizing circuit 14 inputs a TAG from each input port to identify the request type, and sets a bit corresponding to the port to which the 4T requests B1 and C1 are input to "1". 0110 ”is output to the selector 17 and the value“ 1 ”in which the bit corresponding to the port to which the 2T requests A1 and D1 are input is set to“ 1 ”
001 "is output to the input section selector 19. At the time of clock 0, the conflict information holding register 16,
Since the value of 18 is “0000”, the 4-input OR 32, 33
Is "0", and the values of the signal lines 54 and 55 are also "0". The output value of the 4-input OR 32, 33 is "
Since it is "0", the output value of the two-input OR 15 is "0".
Since the output value of the two-input OR 15 is “0”, the selector 1
7, 19 select and output the output values of the signal lines 51, 52. The ORs 34 and 35 output the output signal “0110” of the selector 17 and the output signal “100” of the selector 19, respectively.
1 "is input, and both OR34 and 35 output" 1 ".
At the time of clock 0, the count value of the subtraction counter 37 is “
Since the state value is "0", the state value "1" recognition circuit 38 outputs "0" and the state value "0" recognition circuit 36 outputs "1" .The counter control circuit 20 determines in advance as shown in FIG. Based on the relationship between the input state and the operation, the value "0" is output as a select signal to the priority encoder input selector 21 via the signal line 53, and "3" is set to the subtraction counter 37. Since the selector 21 receives "0" as a select signal from the counter control circuit 20, the selector 21 selects the output value "0110" of the selector 17. The priority encoder 22 arbitrates the contention arbitration information input from the priority encoder input selector 21 and performs contention. Only the bit corresponding to the youngest input port in the arbitration information is set to "1". "0100" to be output to the data selector section 13 as the select signal. The data selector section 13 receives the select signal, B1 of the input buffer 9
And outputs it to the inter-node connecting device 7.
The select signal output from the priority encoder 22 is also input to the Hold signal generation register 25 via the inverter 23. Through the inverter 23 and the AND circuit 24, new conflict information "0010" not selected at the first clock is generated, and the selector 27 and the selector 29 for inputting the conflict information holding register are generated.
Is input to The output value of the state value "1" recognition circuit 38 is "
0 ", the output values of the AND circuits 26 and 28 are" 0 ".
0 ", the selector 2 for inputting the conflict information holding register.
7 and 29 select the output values of the selectors 17 and 19, respectively, and send them to the registers 16 and 18. At this time, the value of each register and the output data are shown by clock 1 in FIGS. 5 (a) and 5 (b). FIG. 3A shows the state of the input buffer.

At the second clock, the output values of the four-input ORs 32 and 33 are both "in response to the values of the registers 16 and 18".
Since it is "1", the output value of the two-input OR 15 is "1".
Since the output value of the input OR15 is "1", the selectors 17, 1
Reference numeral 9 selects the output values of the registers 16 and 18, respectively. OR 34, 35 and state value "0" recognition circuit 3
6 are "1", "1" and "0", respectively.
Based on the relationship between the predetermined input state and the operation shown in FIG. 5C, the priority encoder input selector 21 sends a value "
The output value “0110” of the selector 17 is input to the priority encoder 22, and “0100” is output as the select signal.
Since the output values of 6 and 28 are "0", the selectors 27 and 29 select the output values of the selectors 17 and 19, respectively, and send them to the registers 16 and 18 for holding the conflict information. At this time, the values and output data of the respective registers are shown by clock 2 in FIGS. 5A and 5B. The state of the input buffer is shown in FIG.

At the third clock, the output values of the four-input ORs 32 and 33 are both "in response to the values of the registers 16 and 18".
Since it is "1", the output value of the two-input OR 15 is "1".
Since the output value of the input OR15 is "1", the selectors 17, 1
Reference numeral 9 selects the output values of the registers 16 and 18, respectively. OR 34, 35 and state value "0" recognition circuit 3
6 are "1", "1" and "0", respectively.
Based on the relationship between the predetermined input state and the operation shown in FIG. 5C, the priority encoder input selector 21 sends a value "
0 is output to the priority encoder, and the output value “0110” of the selector 17 is input to the priority encoder, and “0100” is output as the select signal.
Becomes "1" and the output of the state value "1" recognition circuit 38 becomes "1", so that the output value of the AND circuit 26 becomes "1".
The output value of the AND circuit 28 is "0". Selector 27
Then, the output value “0010” of the AND circuit 24 is selected and sent to the register 16. The selector 29 selects the output value “1001” of the selector 19 and sends it to the register 18. At this time, the value of each register and the output data are shown by clock 3 in FIGS. 5A and 5B. The state of the input buffer is shown in FIG.

At the fourth clock, the values of the registers 16 and 18 are received, and the output values of the 4-input ORs 32 and 33 are both "
Since it is "1", the output value of the two-input OR 15 is "1".
Since the output value of the input OR15 is "1", the selectors 17, 1
Reference numeral 9 selects the output values of the registers 16 and 18, respectively. OR 34, 35 and state value "0" recognition circuit 3
6 are "1", "1" and "0", respectively.
Based on the relationship between the predetermined input state and the operation shown in FIG. 5C, the priority encoder input selector 21 sends a value "
The output value "0010" of the selector 17 is input to the priority encoder, and "0010" is output as the select signal.The selector 27 selects the output value "0010" of the AND circuit 24. The selector 29 selects the output value "1001" of the selector 19 and sends it to the register 18. At this time, the values and output data of each register are shown in FIGS. 3) shows the clock 4. The state of the input buffer is shown in FIG.

At the fifth clock, the output values of the four-input ORs 32 and 33 are both "in response to the values of the registers 16 and 18".
Since it is "1", the output value of the two-input OR 15 is "1".
Since the output value of the input OR15 is "1", the selectors 17, 1
Reference numeral 9 selects the output values of the registers 16 and 18, respectively. Since the counter value of the subtraction counter 37 is "0" and the output values of the ORs 34 and 35 and the state value "0" recognition circuit 36 are "1", "1" and "1", respectively, FIG.
Based on the relationship between the predetermined input state and the operation shown in FIG. 11C, the value “0” is output as a select signal to the priority encoder input selector 21 via the signal line 53, and at the same time, the subtraction counter 37 "3" is set. Selector 1 is assigned to priority encoder 22.
7, an output value “0010” is input, and “0010” is output as a select signal. Since the output values of the AND circuits 26 and 28 are "0", the selectors 27 and 29 select the output values of the selectors 17 and 19, respectively, and send them to the registers 16 and 18 for holding the conflict information. At this time, the value and output data of each register are shown by clock 5 in FIGS. 5A and 5B. The state of the input buffer is shown in FIG.

At the sixth clock, the output value “0110” of the selector 17 is input to the priority encoder 22 and “0010” is output as the select signal.
Since the output values of the AND circuits 26 and 28 are "0", the selectors 27 and 29 select the output values of the selectors 17 and 19, respectively, and send them to the registers 16 and 18 for holding the conflict information. At this time, the value of each register and the output data are shown by the clock 6 in FIGS. 5A and 5B. The state of the input buffer is shown in FIG.

At the seventh clock, the output value “0010” of the selector 17 is input to the priority encoder 22 and “0010” is output as the select signal.
Since the value of the subtraction counter 37 becomes "1" and the output of the state value "1" recognition circuit 38 becomes "1", the output value of the AND circuit 26 is "1" and the output value of the AND circuit 28 is "0". ". In the selector 27, the output value “000” of the AND circuit 24
"0" is selected and sent to the register 16. At this time, the value of each register and the output data are shown by the clock 7 in FIGS. 5 (a) and 5 (b). The results are shown in FIG.

At the eighth clock, the value of the register 16 is set to “0”.
000 ", the output value of the 4-input OR 32 becomes" 0 ", and the 4-input OR 32 receives the value" 1001 "of the register 18.
Since the output value of 33 is "1", the output value of the two-input OR 15 is "1". Since the output value of the two-input OR 15 is "1", the selectors 17 and 19 select the output values of the registers 16 and 18, respectively. The output values of the ORs 34 and 35 and the state value “0” recognition circuit 36 are “1” and “1”, respectively.
Since the values are 1 "and" 0 ", the value" 0 "is supplied as a select signal to the priority encoder input selector 21 via the signal line 53 based on the relationship between the predetermined input state and the operation shown in FIG. The output value “0010” of the selector 17 is input to the priority encoder, and “0100” is output as the select signal.The selector 29 outputs the output value “1001” of the selector 19.
And sends it to the register 18. At this time, the values and output data of each register are shown in FIGS. 5 (a) and 5 (b).
Clock 8 of FIG. FIG. 3 shows the state of the input buffer.
This is shown in FIG.

At the ninth clock, the value of the register 16 "00"
The output value of the 4-input OR 32 receiving "00" becomes "0", and the 4-input OR receiving the value "1001" of the register 18 is obtained.
Since the output value of 33 is "1", the output value of the two-input OR 15 is "1". Since the output value of the two-input OR 15 is "1", the selectors 17 and 19 select the output values of the registers 16 and 18, respectively. The output values of the ORs 34 and 35 and the state value "0" recognition circuit 36 are "0" and "0", respectively.
1 ”and“ 1 ”, the value“ 1 ”is supplied as a select signal to the priority encoder input selector 21 via the signal line 53 based on the relationship between the predetermined input state and the operation shown in FIG. Is output and "1" is set in the subtraction counter 37. The output value "1001" of the selector 17 is input to the priority encoder 22, and "1000" is output as the select signal. , And 28 output "0", the selectors 27 and 29 select the output values of the selectors 17 and 19, respectively, and send them to the conflict information holding registers 16 and 18. At this time, the values and output data of each register are output. FIG.
The clock 9 is shown in the diagrams (a) and (b). The state of the input buffer is shown in FIG.

The state values and output data of 10 to 12 clocks are shown in FIGS. 5A and 5B. The state of the input buffer is shown in the order of clocks in FIG. 4 (j) to (l).

By performing the above operation, it is possible to output to the inter-node connecting device 7 while maintaining the continuity of the elements even when a conflict occurs between the elements. For example, a time chart when an instruction sequence is executed in which processing using data of a 4T request sent to another inter-node connection device takes four cycles and processing using data of a 2T request takes two cycles. If shown, FIG. 10 (a)
become that way.

An example in which the processors 1 to 4 send data to the memory 5 will be described. Since the processors 1 to 4 send out the element whose destination device name is the memory 5, the contention arbitration circuit 12 of the present invention re-generates the processor every time when sending out one element of the processor selected by the contention arbitration between the processors. In order to perform contention arbitration between data, data is sent to the memory 5 in a single element unit. FIG. 5 shows the result of processing this data by the contention arbitration method according to the embodiment of the present invention.
The results are shown in FIG.

[0055]

As described above, the present invention provides an input buffer provided for a plurality of processors in a crossbar network, and a method for transferring independent elements between a plurality of processors and a memory. Contention arbitration circuit that performs a contention arbitration and a contention arbitration circuit that performs a data arbitration at the time of data transfer with a plurality of nodes connected via a node-to-node connection device, and outputs a select signal. A data selector unit for selecting one element from elements sent from a plurality of input buffers in accordance with a select signal instructing transfer and outputting the selected element to one of a memory and an inter-node connection device; Requests the transfer, and instructs the transfer in order from the largest number of contiguous elements among the competing data. Even if a conflict between elements of successive transmitted from the processor, by transmitting continuously successive elements for each request, there is the effect that the processing time of the entire information processing apparatus becomes possible shortened.

[Brief description of the drawings]

FIG. 1 is a block diagram showing a first embodiment of the present invention.

FIG. 2 is a circuit diagram of a contention arbitration circuit shown in FIG. 1;

FIG. 3 is an operation diagram showing operation states of an input buffer in clock units (a to h);

FIG. 4 is an operation diagram (i to l) showing an operation state of an input buffer in clock units;

FIG. 5 is an explanatory diagram showing a bit state of each signal for each clock.

FIG. 6 is a block diagram of a conventional information processing apparatus that performs a service similar to the present invention.

FIG. 7 is a circuit diagram of a conventional competitive arbitration circuit for controlling a high-speed crossbar switch.

FIG. 8 is an operation diagram showing the operation state of the input buffer in clock units.

FIG. 9 is an explanatory diagram showing a bit state of each signal for each clock.

FIG. 10 is a comparison diagram displaying the operation results of the present invention and the conventional circuit in a time chart format.

[Explanation of symbols]

 1, 2, 3, 4 Processor 5 Memory 6 Crossbar Network 7 Node Connection Device 8, 9, 10, 11 Input Buffer 12 Competition Arbitration Circuit 13 Data Selector 14 Request Type Recognition Circuit 15 2-Input OR Circuit (2-Input OR) ) 16, 18, 25 Registers 17, 19, 27, 29 Selector 20 Counter control circuit 21 Priority encoder input selector 22 Priority encoder 23 Inverter 24, 26, 28, 31 Logical product circuit 30, 32, 333 4-input logical sum circuit ( 4 input OR) 34, 35 OR circuit (OR) 36 State value "0" recognition circuit 37 Subtraction counter 38 State value "1" recognition circuit 51, 52, 54, 55, 56, 57 Signal line 53 Output signal line

Claims (6)

[Claims] A unit consisting of a plurality of processors, a memory commonly used by the plurality of processors, and a crossbar network connecting the plurality of processors and the memory is referred to as a node. In a contention arbitration method in an information processing device connected to a plurality of nodes via a connection device, the crossbar network includes an input buffer provided corresponding to a plurality of the processors, and a plurality of the processors and the memory. Contention arbitration during transfer of elements each having independent data between them, and contention arbitration at the time of data transfer between a plurality of processors connected to the plurality of nodes via the inter-node connection device, and transfer. A competing arbitration circuit for outputting a select signal for selecting and instructing one of the elements to be output. A data selector unit for selecting one element from among a plurality of elements sent from the plurality of input buffers in accordance with a select signal instructing the transfer and outputting the selected element to either the memory or the inter-node connection device. A contention arbitration circuit for requesting the data transfer and instructing the data transfer in order of the number of continuous elements among the data competing for the data transfer. 2. A contention arbitration circuit outputs an active holding signal to an input buffer in which an element other than a processing target exists during processing of an element, and controls to hold the buffered element. The contention arbitration method according to claim 1, wherein: 3. When a processor transmits transfer data composed of an arbitrary number of elements to a memory or an inter-node connecting device, the processor adds a number of elements and a destination device name to each element of the transfer data. 2. The contention arbitration method according to claim 1, wherein the contention is transmitted. 4. When the destination device name of the transfer data added to the transfer data is an inter-node connection device, the contention arbitration circuit deletes all elements of the data of the processor selected by the contention arbitration between the processors. 2. The contention arbitration between processors is performed again after the transmission, and after the transmission is completed.
The competitive arbitration method described. 5. When the destination device name of the transfer data added to the transfer data is a memory, each time the contention arbitration circuit sends one element of the processor selected by the contention arbitration between the processors, the contention arbitration circuit is re-started. 2. The contention arbitration method according to claim 1, wherein contention arbitration between processors is performed. 6. An input buffer stores data sent from a processor, sends out the number of elements and a destination device name to a contention arbitration circuit, sends out an element to a data selector section, and outputs data from the contention arbitration circuit. 2. The contention arbitration method according to claim 1, wherein the buffered element is held when the held signal is active.