JP2012186539A - Router device and method for controlling the same - Google Patents

Abstract

[PROBLEMS] To reduce latency without depending on a communication path of a packet passing through a router. Buffers (4_1 to 4_3) temporarily hold packets waiting for output. The preceding output detection circuit 5_1 detects a preceding output target packet that is not subject to arbitration processing based on the input state of a packet that requests output to the output P1 in a certain cycle and the storage state of the buffers 4_1 to 4_3. The output selection circuit 7_1 determines the packet to be output from the output P1 when the preceding output target packet is detected, and outputs the packet from the output P1 based on the arbitration process when the preceding output target packet is not detected And decide. The switch 9 controls wiring switching to the output P1 based on the determination of the output selection circuit 7_1.
[Selection] Figure 1

Description

  The present invention relates to a router device and a control method for the router device.

  Currently, it is possible to arrange a plurality of design modules such as processors on a single chip. New-on-Chip (hereinafter referred to as NoC) is a circuit used for coupling design modules such as arranged IP cores. The NoC is configured to include a plurality of switching circuits called routers.

  FIG. 12 is a diagram illustrating an arrangement example of IP cores and routers in a semiconductor. As illustrated, a plurality of IP cores are indirectly connected via a router. The router receives input data packetized from an adjacent router or IP core. The router determines the output direction of the received packet data, and transmits the data to the next router or destination IP core.

  There are mainly three functions of the router: route calculation, switch arbitration, and switch forwarding. A standard structure of the router is shown in FIG. The router device 1 includes a plurality of input ports (input P1 to input P3) and a plurality of output ports (output P1 to output P3). The router device 1 includes latches 2_1 to 2_3, path calculation circuits 3_1 to 3_3, buffers 4_1 to 4_3, arbitration circuits 6_1 to 6_3, a control storage circuit 8, and a switch 9. The latches 2_1 to 2_3, the path calculation circuits 3_1 to 3_3, and the buffers 4_1 to 4_3 are associated with the inputs P1 to P3, respectively. The arbitration circuits 6_1 to 6_3 are associated with the outputs P1 to P3. For example, the latch 2_1, the path calculation circuit 3_1, and the buffer 4_1 are associated with the input P1. The arbitration circuit 6_1 is associated with the output P1.

  The latches 2_1 to 2_3 temporarily hold the packets input from the corresponding input ports, and then output the packets to the corresponding path calculation circuits 3_1 to 3_3.

  The route calculation circuits 3_1 to 3_3 are circuits that perform route calculation. Hereinafter, the path calculation circuit 3_1 will be described as an example. The path calculation circuit 3_1 determines the output port number based on the information on the transmission destination IP core described in the header of the packet input from the input P1 or the information on the transmission direction. The route calculation circuit 3_1 stores the packet together with the determined output port number in the corresponding buffer 4_1.

  The buffers 4_1 to 4_3 temporarily store the packets output by the route calculation circuit in association with the output port numbers of the output destinations. The buffers 4_1 to 4_3 can hold a plurality of packets. The buffers 4_1 to 4_3 supply packets to the switch 9 in response to a packet output request from the control storage circuit 8 described later.

  The arbitration circuits 6_1 to 6_3 are circuits that select a packet that is output from the corresponding output port to the next cycle among the packets temporarily stored in the buffers 4_1 to 4_3. Hereinafter, the arbitration circuit 6_1 will be described as an example. Based on the packet stored in the buffers 4_1 to 4_3 and the output packet number of the packet, the arbitration circuit 6_1 determines a packet to be output in the next cycle from the output P1 that is the corresponding output port. The arbitration circuit 6_1 writes the input port number, to which the determined output packet is input, in the control storage circuit 8.

  The control storage circuit 8 stores the input port number to which a packet to be output by each output port is input in a certain cycle. Further, the control storage circuit 8 transmits the packet output request to the buffers 4_1 to 4_3, respectively.

  The switch 9 receives the calculated arbitration result of the arbitration circuits 6_1 to 6_3 (that is, the input port number to which a packet to be output from each output port is input) via the control storage circuit 8, and according to the arbitration result Connect the input and output ports. Specifically, the switch 9 connects the output from the buffer associated with the connection target input port to the output port that is the output destination.

  Generally, a router requires one cycle of latency for route calculation by a route calculation circuit, switch arbitration by an arbitration circuit, and switch transfer by a switch. In this case, the passing latency of the router is 3 cycles. The operation of the router apparatus shown in FIG. 13 will be described with reference to the timing chart of FIG.

  FIG. 14 is a timing chart showing an operation when the packet input to the input P1 is output from the output P3 in the router device of FIG. FIG. 14 shows signals passing through the points A to F in FIG. Here, it is assumed that no packets are stored in the buffers 4_1 to 4_3.

  The latch 2_1 holds the header of the packet input in cycle t (see FIG. 14A). The latch 2_1 outputs the header of this packet at cycle t + 1. The route calculation circuit 3_1 stores the packet header and the route calculation result in the buffer 4_1 (see FIG. 14B). The arbitration circuit 6_3 arbitrates the output packet in cycle t + 2. Thereby, in the cycle t + 2, this packet header obtains the output right. That is, this packet header is an output target from the buffer 4_1.

  The arbitration circuit 6_3 writes the arbitration result in the control storage circuit 8. Specifically, the arbitration circuit 6_3 writes in cycle t + 2 that the input port of the packet output from the output P3 is “1” (see FIG. 14D). In cycle t + 2, the instruction signal to the buffer 4_1 output from the control storage circuit 8 is “stop” (see FIG. 14E). Therefore, in the cycle t + 2, the buffer 4_1 is not regarded as a packet output. In other words, the buffer 4_1 continues to perform the same output as the cycle t + 2 in the cycle t + 3 (see FIG. 14C).

  When the arbitration circuit 6_3 inputs “1” to the control storage circuit 8, the control storage circuit 8 notifies the buffer 4_1 of an output permission (“permission”) signal (see FIG. 14E). In response to the permission signal, the buffer 4_1 determines that the packet header has been output, and updates the buffer. By this update, in cycle t + 4, buffer 4_1 outputs the data of the packet input in cycle t + 1. The data of this packet is output from the switch 9 at cycle t + 4.

  As described above, the passage latency in the router is composed of three processes: path calculation, switch arbitration, and switch transfer. When the passing latency of the router is large, improvement of the processing capacity of the semiconductor is hindered. In NoC, relay communication by a plurality of routers is premised, so the passage latency of the router occupies most of the communication latency of the entire semiconductor. For this reason, it is very important to reduce the passage latency in the router.

  Of the processes that cause passage latencies in the router, the route calculation process and the switch arbitration process target packet headers. The header is located at the forefront of the packet. The packet data following the header is stopped (stored) in the input buffer during the route calculation process and the switch arbitration process. If a part of these two processes (path calculation process and switch arbitration process) can be omitted, the communication latency can be reduced.

  As a method for omitting route calculation processing, there is a method called source routing in which all route calculations are performed in advance at a packet transmission source. Source routing is a technique that is also used in off-chip networks. In source routing, route calculation is already performed at the time of packet transmission. Therefore, each router need not calculate the route of the input packet. However, when a packet passes through a plurality of routers, a plurality of pieces of route information are stored in the packet. In this case, in order to simplify the structure of the router, the used route information is often discarded and new route information is updated.

  The route information is updated by shifting the route information in the packet. The already used route information is overwritten by the next used route information by the bit shift by the route update circuit. The delay caused by this route update is smaller than the delay caused by route calculation. Therefore, it is possible to reduce the one-cycle latency caused by route calculation in a general router.

  As a technique for reducing the latency of switch arbitration, there is a technique called a prediction router described in Non-Patent Document 1. This predictive router is a method in which the output direction of an input packet is predicted in advance in the router before the packet is input, and arbitration is speculatively completed.

Hiroya Matsutani, Michiaki Tsuji, Hideharu Amano, Tsutomu Yoshinaga, Low Latency On-Chip Router Architecture with Prediction Mechanism, IEICE Tech. 108, no. 28

  In the method of the prediction router described in Non-Patent Document 1 described above, it is necessary to redo switch arbitration when the predicted output direction is incorrect. When switch arbitration is performed again, latency is not reduced because all switch arbitration is executed. This prediction failure occurs due to factors such as lack of regularity in the packet output direction. For this reason, in this predictive router method, the effect of latency reduction depends on the communication path of packets passing through the router. Therefore, there is a problem that the latency cannot be sufficiently reduced depending on the communication path of the packet passing through the router.

One aspect of the router device according to the present invention is:
A router device having a plurality of input ports and a first output port, and performing an arbitration process for controlling the output authority of the first output port,
When an input packet requesting output to the first output port in a certain cycle is the only packet requesting output to the first output port in the router device, the packet is subjected to the arbitration process. It is determined as a preceding output target packet to be output without being targeted.

One aspect of the routing method according to the present invention is as follows.
A control method of a router device having a plurality of input ports and a first output port, and performing an arbitration process for controlling the output authority of the first output port,
When an input packet requesting output to the first output port in a certain cycle is the only packet requesting output to the first output port, the packet is not subjected to the arbitration process. It is determined to be the preceding output target packet to be output.

  In the present invention, the router device determines whether or not the input packet is the only packet requesting output to the first output port. If it is the only packet, it can be output immediately without being subject to arbitration processing. As described above, the router device according to the present invention detects the preceding output target packet according to the packet input status and the packet holding status, and does not need to perform the detection process using the packet communication path. For this reason, the arbitration process can be omitted without depending on the communication path of each packet.

  According to the present invention, it is possible to provide a router device and a router control method capable of reducing latency without depending on a communication path of a packet passing through the router.

1 is a block diagram illustrating a configuration of a router device according to a first exemplary embodiment; 3 is a flowchart showing packet output control by the router device according to the first exemplary embodiment; 3 is a flowchart showing a preceding output determination process by the router device according to the first exemplary embodiment; 3 is a time chart illustrating an operation of the router device according to the first exemplary embodiment; FIG. 3 is a block diagram illustrating a configuration of a router device according to a second exemplary embodiment. 7 is a time chart illustrating an operation of the router device according to the second exemplary embodiment; FIG. 6 is a block diagram illustrating a configuration of a router device according to a third exemplary embodiment. 10 is a flowchart illustrating packet output control by the router device according to the third exemplary embodiment; 10 is a flowchart illustrating a preceding output determination process by a router device according to a third embodiment; 10 is a time chart illustrating an operation of the router device according to the third exemplary embodiment; FIG. 6 is a block diagram illustrating a configuration of a router device according to a fourth exemplary embodiment. It is a figure of the example of arrangement | positioning of the IP core and router in a standard semiconductor. It is a block diagram which shows the structure of a standard router apparatus. It is a time chart which shows operation | movement of a standard router apparatus.

<Embodiment 1>

  The router device according to the embodiment of the present invention determines whether or not an input packet is the only packet that requests output to a predetermined output port in a certain cycle. If it is the only packet, the router device immediately outputs it without performing arbitration processing. For this reason, the router device according to the present embodiment can omit the arbitration process without depending on the communication path of each packet.

  Details of the router device according to the embodiment of the present invention will be described below with reference to the drawings. FIG. 1 is a block diagram showing the configuration of the router device according to the present embodiment. The router device 1 is a router device having three input ports (input P1 to input P3) and three output ports (output P1 to output P3). The router device 1 includes latches 2_1 to 2_3, path calculation circuits 3_1 to 3_3, buffers 4_1 to 4_3, preceding output detection circuits 5_1 to 5_3, arbitration circuits 6_1 to 6_3, output selection circuits 7_1 to 7_3, a control storage circuit 8, and a switch 9 is provided.

  The latch 2_1 temporarily holds the packet (specifically, packet header and packet data) input from the input P1, and supplies the packet to the path calculation circuit 3_1. Since the latch 2_1 temporarily holds the packet, the output timing of the packet from the router device 1 can be adjusted. The latch 2_2 and the latch 2_3 are latches corresponding to the input P2 and the input P3, respectively, and the operation is the same as that of the latch 2_1.

  The route calculation circuit 3_1 is a route for specifying the output target port of the packet from the packet input from the latch 2_1. Specifically, the route calculation circuit 3_1 reads the header of the packet and specifies an output port to be output from the read information. The route calculation circuit 3_1 writes the output port number and the packet, which are the route calculation results, into the buffer 4_1. Further, the path calculation circuit 3_1 supplies the presence / absence of a packet input to the input P1, the output port number as a path calculation result when there is a packet input, and the preceding output detection circuit 5_1. The route calculation circuit 3_2 and the route calculation circuit 3_3 are route calculation circuits corresponding to the latch 2_2 and the latch 2_3, respectively, and their operations are the same as those of the route calculation circuit 3_1.

  The buffer 4_1 stores a packet waiting for output in association with the output port number. The buffer 4_1 is a storage unit in FIFO (First In First Out) format. The buffer 4_1 notifies the arbitration circuits 6_1 to 6_3, which will be described later, of the packet storage status (information on the presence or absence of a packet, and the information including the output port number of the packet located at the head if a packet is stored). Furthermore, the buffer 4_1 supplies a packet to be output to the switch 9 in response to an output command from the control storage circuit 8 described later. The packet stored in the buffer 4_1 is deleted only when it is output to the outside of the router device 1 through the switch 9. The buffer 4_2 and the buffer 4_3 are buffers corresponding to the input P2 and the input P3, respectively, and their functions are the same as those of the buffer 4_1.

  In this example, the configuration is described as having a buffer for each input port, but the present invention is not necessarily limited thereto. For example, it may be configured as one buffer that holds packets in association with the output destination port number.

  The preceding output detection circuit 5_1 is a circuit that determines whether or not there is a packet to be a preceding output target. The preceding output target packet is a packet that is directly output from the output port without performing packet arbitration. Specifically, the preceding output detection circuit 5_1 has only one packet that is input from any of the input ports in a certain cycle and requests output to the output P1, in which each of the buffers 4_1 to 4_3 is empty. Whether or not. When the condition is satisfied, the preceding output detection circuit 5_1 sets the only packet input from the input port as the subject of preceding output.

  Preceding output detection circuit 5_1 receives from packet calculation circuit 3_1 the presence / absence of a packet input to input P1 every cycle and the output port number that is the path calculation result when there is a packet input. Similarly, the preceding output detection circuit 5_1 receives from the path calculation circuit 3_2 the presence / absence of a packet input to the input P2 every cycle and the output port number that is the path calculation result when there is a packet input. Preceding output detection circuit 5_1 receives, from cycle calculation circuit 3_3, whether or not a packet is input to input P3 every cycle and an output port number that is a path calculation result when there is a packet input. Based on these inputs, the preceding output detection circuit 5_1 determines whether there is a preceding output target packet for the output P1 every cycle. A detailed determination method will be described later with reference to FIG.

  The preceding output detection circuit 5_1 supplies the result of the preceding output determination regarding the output P1 to the output selection circuit 7_1 every cycle. Specifically, the preceding output detection circuit 5_1 has one packet that requests output to the output P1 in a certain cycle, and when the buffers 4_1 to 4_3 are all empty, the relevant packet (preceding output target packet) Is notified to the output selection circuit 7_1. In other cases, the preceding output detection circuit 5_1 notifies the output selection circuit 7_1 that there is no packet to be preceded output. The preceding output detection circuit 5_2 and the preceding output detection circuit 5_3 are determination circuits corresponding to the outputs P2 and P3, respectively, and their functions are the same as those of the preceding output detection circuit 5_1. The output destination of the determination result by the preceding output detection circuit 5_2 is the output selection circuit 7_2. The output destination of the determination result by the preceding output detection circuit 5_3 is the output selection circuit 7_3.

  The arbitration circuit 6_1 is a circuit that selects a packet to be output by the output P1 in the next cycle from information on the packet stored in the head of the buffers 4_1 to 4_3. The arbitration circuit 6_1 has a function equivalent to that of an arbitration circuit included in a general router device. The arbitration circuit 6_1 performs arbitration when a packet having the output P1 as an output destination exists at the head position of any of the buffers 4_1 to 4_3, and outputs the input port number to which the packet obtained the output right by the arbitration is input. This is notified to the selection circuit 7_1. The arbitration circuit 6_1 notifies the output selection circuit 7_1 that there is no packet to be output when there is no packet having the output P1 as the output destination in any of the buffers 4_1 to 4_3. The arbitration circuit 6_2 and the arbitration circuit 6_3 are arbitration circuits corresponding to the output P2 and the output P3, respectively, and their functions are the same as those of the arbitration circuit 6_1.

  The output selection circuit 7_1 receives input from the preceding output detection circuit 5_1 (presence / absence of a preceding output target packet or, if there is a preceding output target packet, the number of an input port to which the packet is input), and an arbitration circuit 6_1. A circuit for determining a packet output from the output P1 in the next cycle based on the input (the number of the input port to which the packet to be output from the output P1 in the next cycle is input or that there is no packet to be output) It is. Details of the output selection circuit 7_1 will be described later with reference to FIG. The output selection circuit 7_1 writes the input port number to which the packet to be output from the output P1 in the next cycle is input to the control storage circuit 8. The output selection circuit 7_2 and the output selection circuit 7_3 are selection circuits corresponding to the output P2 and the output P3, respectively, and their functions are the same as those of the output selection circuit 7_1.

  The control storage circuit 8 stores the input port number to which the packet to be output in the next cycle is input for each output port. The control storage circuit 8 supplies an output permission signal to the buffer corresponding to the written input port number. Furthermore, the control storage unit 8 notifies the switch 9 of the input port number for which the packet to be output in the next cycle is input for each output port.

  The switch 9 changes the connection between the buffer connected to each input port and each output port based on the notified information. Thus, the packet selected by each output selection circuit is output from the router device 1.

  Next, packet output control by the router device 1 according to the present embodiment will be described with reference to the flowchart of FIG. Each preceding output detection circuit (in the following example, description will be given by using the preceding output detection circuit 5_1 as an example), the presence / absence of an input packet in a certain cycle from the path calculation circuit (3_1 to 3_3) corresponding to each input port, and If there is an input packet, the output port number of the output destination is input (S1). Further, the preceding output detection circuit 5_1 is notified of the packet storage status of each buffer from the buffers 4_1 to 4_3 (S1).

  The preceding output detection circuit 5_1 determines whether there is a packet that can be output in advance based on these inputs, that is, whether the preceding output detection circuit 5_1 has a packet that may be output without being subjected to arbitration processing. It is determined whether or not (S2). Details of the processing (preceding output determination) will be described later with reference to FIG. When there is a packet that can be output in advance, the preceding output detection circuit 5_1 notifies the output selection circuit 7_1 of a signal notifying that the target exists together with the input port number to which the packet is input (S2). On the other hand, when there is no packet that can be output in advance, the output detector 5_1 notifies the output selection circuit 7_1 that there is no packet that can be output in advance (S2).

  In parallel with S1 and S2, in detail, in the same cycle as the cycle in which S1 and S2 are performed, each arbitration circuit (in the following example, the arbitration circuit 6_1 will be described as an example) is connected to the buffers 4_1 to 4_3. The packet stored at the head is read, and it is determined whether there is a packet whose output destination is the corresponding output port (S3). When there is a target packet (S3: Yes), the arbitration circuit 6_1 performs a packet arbitration process for selecting a packet to be output in the next cycle from the determination target packet (S4). On the other hand, when there is no target packet (S3: No), the arbitration circuit 6_1 does not perform the packet arbitration process. The arbitration circuit 6_1 notifies the output selection circuit 7_1 of the presence / absence of the arbitration process and the input packet number as the arbitration result when the arbitration process is performed.

  Subsequently, the processing of S5 to S9 is performed by each output selection circuit (in the following description, the output selection circuit 7_1 will be described as an example). The output selection circuit 7_1 receives from the preceding output detection circuit 5_1 the presence / absence of a packet that is a target of the preceding output, and if there is such a target, the input port number of the packet. Further, the output selection circuit 7_1 receives from the arbitration circuit 6_1 the presence / absence of the arbitration process, and the input packet number that is the arbitration result when the arbitration process is performed.

  The output selection circuit 7_1 first determines whether or not the arbitration process has been performed in the arbitration circuit 6_1 (S5). When the arbitration process is performed (S5: Yes), the output selection circuit 7_1 stores the input port number input from the arbitration circuit 6_1 in the control storage circuit 8 as an output target of the output P1 (S6).

  On the other hand, when the arbitration process has not been performed (S5: No), the output selection circuit 7_1 determines whether or not there is a packet that is a target of the preceding output (S7). When there is a packet that is a target of the preceding output (S7: Yes), the output selection circuit 7_1 stores the input port number, to which the preceding output target packet is input, in the control storage circuit 8 as an output target of the output P1. (S8). When there is no packet that is a target of the preceding output (S7: No), the output selection circuit 7_1 stores in the control storage circuit 8 that there is no output target of the output P1 in the next cycle (S9).

  Next, details of the preceding output determination by the preceding output detection circuit 5_1 will be described with reference to the flowchart of FIG. The same processing is performed for the preceding output detection circuit 5_2 and the preceding output detection circuit 5_3.

  The preceding output detection circuit 5_1 determines whether or not the buffer 4_1 corresponding to the input P1 is empty (S11). When the buffer 4_1 is not empty (S11: No), the preceding output detection circuit 5_1 does not set a packet that is a candidate for preceding output. On the other hand, when the buffer 4_1 is empty (S11: Yes), the preceding output detection circuit 5_1 checks the packet input status with respect to the input P1, and checks whether or not the packet header is included in the input data (S12). .

  When the packet header is not included in the input data (S12: No), the preceding output detection circuit 5_1 does not set a packet that is a candidate for preceding output. When the packet header is included in the input data (S12: Yes), the preceding output detection circuit 5_1 determines whether or not the output port number calculated by the path calculation circuit 3_1 is equal to the port number of the output P1 ( S13).

  If the port numbers do not match (S13: No), the preceding output detection circuit 5_1 does not set a packet that is a candidate for preceding output. When the port numbers match (S13: Yes), the preceding output detection circuit 5_1 determines that the packet input from the input P1 is a candidate for preceding output (S14).

  In the above-described S11 to S14, the preceding output detection circuit 5_1 performed the preceding output candidate determination process regarding the input P1. In parallel with this processing, the preceding output detection circuit 5_1 performs processing (S15 to S18) corresponding to the input P2 and processing (S19 to S22) corresponding to the input P3.

  The preceding output detection circuit 5_1 checks whether the sum of the preceding output candidate packets selected from all the input ports is one (S23). When there is one preceding output candidate packet (S23: Yes), the preceding output detection circuit 5_1 determines the packet as a preceding output target packet (S24). When the number of the preceding output candidate packets is not one (S23: No), the preceding output detection circuit 5_1 determines that there is no packet to be the preceding output target (S25). When there are a plurality of prior output candidate packets, these packets are subjected to arbitration by the arbitration circuit in the next cycle.

  As described above, the preceding output detection circuit 5_1 determines whether or not the buffer is empty in the determination of the preceding output target packet (S11, S15, and S19). If all the buffers are empty, the arbitration process is not performed. Therefore, the output selection circuit 7_1 may perform the processes of S6 and S7 shown in FIG. 2 in the reverse order. That is, the output selection circuit 7_1 may refer to the packet arbitration result after determining whether there is a preceding output target packet.

  Next, a specific operation example of the router device according to the present embodiment will be described with reference to FIGS. 1 and 4. FIG. 4 is a time chart showing an operation example of the router device 1 when a packet from the input P1 to the output P3 is input in the cycle t and the packet is transferred. In this example, no packets are stored in the buffers 4_1 to 4_3. Furthermore, in this example, there is no input from other input ports (input P2, input P3) in cycle t. A to H in FIG. 4 indicate passing signals at points (A to H) in FIG.

  First, in a cycle t, a packet header is input to the latch 2_1 from the input P1 (see FIG. 4A). The header of this packet is output from the latch 2_1 in cycle t + 1. The header of the output packet is stored in the buffer 4_1 after the route calculation is performed by the route calculation circuit 3_1 (see FIG. 4B).

  Simultaneously with the storage in the buffer 4_1, the header of the packet is also supplied to the preceding output detection circuit 5_3 (see FIG. 4B). The preceding output detection circuit 5_3 determines the preceding output of the output P3 using the header of this packet.

  The preceding output detection circuit 5_3 performs the preceding output determination in cycle t + 1. In this example, the buffers 4_1 to 4_3 are all empty, and there is no input from the input P2 and the input P3 in the cycle t. Therefore, the preceding output detection circuit 5_3 outputs the input port number (1) (see FIG. 4C). .

  In parallel with the preceding output determination by the preceding output detection circuit 5_3, the arbitration circuit 6_3 performs an arbitration process using the packet stored at the head position of the buffers 4_1 to 4_3. In this example, no packets are stored in the buffers 4_1 to 4_3. Therefore, it is notified by the signal D or the like that there is no packet in the buffer (“none”). Therefore, the arbitration circuit 6_3 outputs a signal indicating that packet arbitration has not been performed to the output selection circuit 7_3 in cycle t + 1.

  In cycle t + 1, “1” is input from the preceding output detection circuit 5_3 and “none” is input from the arbitration circuit 6_3 to the output selection circuit 7_3. Thereby, the output selection circuit 7_3 executes S7 and S8 in FIG. 2, and inputs the input port number “1” of the preceding output target to the control storage circuit 8 in the cycle t + 1 (see FIG. 4F).

  The control storage circuit 8 permits the buffer 4_1 to output a packet in the cycle t + 2 (see FIG. 4G). As a result, the header of the packet stored in the buffer 4_1, that is, the header of the packet that has been subject to preceding output is supplied to the switch without being subject to arbitration by the arbitration circuit (see FIG. 4D). The packet that has passed through the switch is output from the router device 1 (see FIG. 4H).

  Then, the effect of the router apparatus 1 concerning this Embodiment is demonstrated anew. As described above, the preceding output detection circuit determines from the input state (that is, whether or not there is one) of input packets whose output destination is a certain output port (first output port) and the packet storage state of the buffer. A prior output target packet that is not subject to arbitration is detected. The preceding output target packet is output without being subject to arbitration processing. The detection of the preceding output target packet does not use the input state of the packet. As a result, the arbitration process can be omitted without depending on the packet communication path, and the latency of the router device can be reduced.

<Embodiment 2>
Embodiment 2 of the present invention is characterized in that it corresponds to the source routing method. More specifically, route information is embedded in each packet input to the router device, and the router device includes route update information for updating the route information. Thereby, the route calculation process can be reduced and the structure of the router can be simplified.

  The basic configuration of the router device 1 according to the present embodiment will be described with reference to FIG. In FIG. 5, the processing units and circuits having the same names and the same reference numerals perform the same processing as in the first embodiment. Therefore, the overlapping description is omitted as appropriate.

  The router device 1 includes buffers 4_1 to 4_3, preceding output detection circuits 5_1 to 5_3, arbitration circuits 6_1 to 6_3, output selection circuits 7_1 to 7_3, a control storage circuit 8, a switch 9, and path update circuits 10_1 to 10. 10_3. The router device 1 has a configuration that does not include a latch and a route calculation circuit. Since the latch does not have a path calculation circuit, it becomes unnecessary because the delay constraint from the input port to the buffer is relaxed. As a result, the router device 1 according to the present embodiment can reduce the latency required for passing through the router by one cycle compared to the router device 1 according to the first embodiment.

  In each packet input to the router device 1, route information according to an existing source routing method is embedded. This eliminates the need for packet route calculation processing in the router device 1. The route update circuits 10_1 to 10_3 are circuits that delete route information that has already passed from supplied packets. Since the route information deletion processing by the route update circuits 10_1 to 10_3 is realized by simple processing such as bit shift as described above, the processing is completed in a very short time compared to the route calculation processing. The route update circuits 10_1 to 10_3 can be realized by applying existing technologies, respectively.

  Next, a specific operation example of the router device 1 according to the present embodiment will be described with reference to the time chart of FIG. 6 in addition to FIG. FIG. 6 is a time chart showing an operation example of the router device 1 when a packet from the input P1 to the output P3 is input in the cycle t and the packet is transferred. In this example, no packets are stored in the buffers 4_1 to 4_3. Furthermore, in this example, there is no input from other input ports (input P2, input P3) in cycle t. A to H in FIG. 6 indicate passing signals at points (A to H) in FIG.

  First, in a cycle t, a packet header is input from the input P1 to the buffer 4_1 (see FIG. 6A). At the same time, the header information of the input packet is supplied to the preceding output detection circuit 5_3. The preceding output detection circuit 5_3 outputs “1” as the preceding output target in the cycle t to the output selection circuit 7_3 (see FIG. 6B). At the same timing, the arbitration circuit 6_3 outputs “no” indicating that the arbitration target packet is not in the buffer to the output selection circuit 7_3 (see FIG. 6D). As a result, the output selection circuit 7_3 determines that the packet input in the cycle t is an output packet in the cycle t + 1, and outputs the input port number “1” in which this packet is input to the control storage circuit 8 (see FIG. 6E). ).

  The control storage circuit 8 permits the buffer 4_1 to output a packet in the cycle t + 1 (see FIG. 4F). As a result, the header of the packet stored in the buffer 4_1 is supplied to the path update circuit 10_1 (see FIG. 6C). The path update circuit 10_1 updates the path information in the header of the input packet. The path update circuit 10_1 supplies the header of this packet to the switch 9 after the path update (see FIG. 6G). The packet that has passed through the switch is output from the router device 1 (see FIG. 6H).

  As described above, the router device 1 according to the present embodiment employs the source routing method and does not have a route calculation circuit and a latch. The processing by the route update circuits 10_1 to 10_3 is processing for overwriting route information and has very little influence on the operating frequency of the router. For this reason, compared with the router apparatus 1 concerning Embodiment 1, the router apparatus 1 concerning this Embodiment can reduce the latency required for a router passage.

<Embodiment 3>
The router device according to the third embodiment of the present invention is characterized in that it can appropriately handle a packet (hereinafter referred to as a priority packet) to be transmitted with priority over a normal packet. Specifically, in the router device according to the present embodiment, the preceding output determination circuit determines whether or not the input packet is a priority packet, and the output selection circuit prioritizes the normal packet as an output target. judge. As a result, it is possible to output the priority packet that has just been input from the input port in preference to the normal packet already stored in the buffer. In the following, the router device according to the present embodiment will be described focusing on the differences from the first and second embodiments.

  FIG. 7 is a diagram illustrating a configuration of the router device according to the present embodiment. In FIG. 7, the processing units and circuits having the same names and the same reference numerals perform the same processing as in the first embodiment. Therefore, the overlapping description is omitted as appropriate. The buffer input from each input port is a normal packet or a priority packet, and can be distinguished by referring to a packet header, for example.

  The router device 1 includes latches 2_1 to 2_3, path calculation circuits 3_1 to 3_3, buffers 4_1 to 4_3, priority buffers 11_1 to 11_3, priority preceding output detection circuits 12_1 to 12_3, buffer selection circuits 13_1 to 13_3, Arbitration circuits 6_1 to 6_3, priority output selection circuits 14_1 to 14_3, a control storage circuit 8, and a switch 9 are provided.

  The priority buffers 11_1 to 11_3 are storage units corresponding to the inputs P1 to P3, respectively, and store priority packets in a FIFO format. Further, the priority buffers 11_1 to 11_3 notify the storage status of priority packets to the priority advance output detection circuits 12_1 to 12_3 described later for each cycle. When the priority buffers 11_1 to 11_3 output a packet via the switch 9, the priority buffers 11_1 to 11_3 delete the packet from the buffer.

  The priority preceding output detection circuit 12_1 corresponds to the output P1, and is a circuit obtained by partially changing the processing of the preceding output detection circuit 5_1. The priority preceding output detection circuit 12_1 is notified of the packet storage status from the priority buffers 11_1 to 11_3, the presence / absence of input of the priority packet from each of the route calculation circuits 3_1 to 3_3, and the output port number when there is a priority packet. Is supplied.

  The priority / preceding output detection circuit 12_1 determines whether or not only one priority packet having the output P1 as an output destination is input from each input port in a certain cycle, and whether or not a packet is stored at the head of the priority buffers 11_1 to 11_3. To determine. That is, the priority preceding output detection circuit 12_1 sets the priority packet as a processing target. The priority predecessor detection circuit 12_1 has one packet requesting output to the output P1 in a certain cycle, and when all of the priority buffers 11_1 to 11_3 are empty, the priority output of the input port to which the packet is input is output. This is notified to the selection circuit 14_1. In other cases, the priority preceding output detection circuit 12_1 notifies the priority output selecting circuit 14_1 that there is no packet to be subject to preceding output. Details of the processing performed by the priority preceding output detection circuit 12_1 will be described later with reference to FIG.

  The priority preceding output detection circuit 12_2 and the priority preceding output detection circuit 12_3 are determination circuits corresponding to the output P2 and the output P3, respectively, and their operations are the same as those of the priority preceding output detection circuit 12_1.

  The buffer selection circuit 13_1 is a circuit provided in association with the priority buffer 11_1 and the buffer 4_1. An output permission signal is supplied from the control storage circuit 8 to the buffer selection circuit 13_1. The buffer selection circuit 13_1 takes out the packet from the head of the priority buffer 11_1 and supplies it to the switch 9. When the priority buffer 11_1 is empty, the buffer selection circuit 13_1 takes out the packet from the buffer 4_1 and supplies the packet to the switch 9. The buffer selection circuit 13_2 is a circuit provided in association with the priority buffer 11_2 and the buffer 4_2, and the operation thereof is the same as that of the buffer selection circuit 13_1. The buffer selection circuit 13_3 is a circuit provided in association with the priority buffer 11_3 and the buffer 4_3, and the operation thereof is the same as that of the buffer selection circuit 13_1.

  The arbitration circuit 6_1 performs packet arbitration using a packet located at the head of the priority buffers 11_1 to 11_3 and a packet located at the head of the buffers 4_1 to 4_3. At this time, the arbitration circuit 6_1 performs arbitration so that priority is given to the priority packet. The same applies to the arbitration circuit 6_2 and the arbitration circuit 6_3.

  The priority output selection circuit 14_1 is a selection circuit corresponding to the output P1, and is a circuit obtained by partially changing the processing of the output selection circuit 7_1. The priority output selection circuit 14_1 selects a packet to be output in the next cycle based on the input from the arbitration circuit 6_1 and the input from the priority preceding output detection circuit 12_2, and the number of the input port to which the packet is input Is notified to the control storage circuit 8.

  The operations of the control memory circuit 8 and the switch 9 are the same as those in the first and second embodiments. The control storage circuit 8 supplies an output instruction signal to the buffer selection circuits 13_1 to 13_3 corresponding to the inputs of the priority output selection circuits 14_1 to 14_3. Further, the control storage unit 8 notifies the switch 9 for each output port of the input port number to which the stored packet to be output in the next cycle is input. The switch 9 switches the wiring according to the input from the control storage circuit 8 and outputs the packet from the output port.

  Next, packet output control by the router device 1 according to the present embodiment will be described with reference to the flowchart of FIG.

  In each priority preceding output detection circuit (in the following example, description will be given by taking the priority preceding output detection circuit 12_1 as an example), input of a priority packet in a certain cycle from the path calculation circuit (3_1 to 3_3) corresponding to each input port. Presence / absence, and if a priority packet is received, the output port number of the output destination of the priority packet is input (S1). Further, the priority preceding output detection circuit 12_1 is notified of the packet storage status of each buffer from the priority buffers 11_1 to 11_3 (S31).

  Based on these inputs, the priority / preceding output detection circuit 12_1 determines whether there is a priority packet that can be output in advance (S32). Details of the determination process (S32) will be described later with reference to FIG.

  If there is a priority packet that can be output in advance, the priority output detection circuit 12_1 notifies the priority output selection circuit 14_1 of a signal notifying that the target exists together with the input port number to which the priority packet is input (S32). ). On the other hand, when there is no packet that can be output in advance, the priority output detection circuit 12_1 notifies the priority output selection circuit 14_1 that there is no priority packet that can be output in advance (S32).

  In parallel with S31 and S32, in detail, in the same cycle as that in which S31 and S32 are performed, each arbitration circuit (in the following example, the arbitration circuit 6_1 will be described as an example) includes buffers 4_1 to 4_3 and Of the packets stored at the head of the priority buffers 11_1 to 11_3, it is determined whether there is a packet whose output destination is the corresponding output port, that is, whether there is a packet to be arbitrated (S33).

  When there is a packet to be arbitrated (S33: Yes), the arbitration circuit 6_1 performs an arbitration process for selecting a packet to be output in the next cycle from the packet to be arbitrated in such a way as to give priority to the priority packet ( S34). On the other hand, when there is no packet to be arbitrated (S33: No), the arbitration circuit 6_1 does not perform the packet arbitration process. The arbitration circuit 6_1 notifies the priority output selection circuit 14_1 of the presence / absence of the arbitration process and the input packet number as the arbitration result when the arbitration process is performed.

  The subsequent processes of S35 to S41 are performed by each priority output selection circuit (in the following description, the priority output selection circuit 14_1 will be described as an example). The priority output selection circuit 14_1 first determines whether or not the priority packet has acquired the output right in the arbitration circuit 6_1 (S35). When the priority packet has acquired the output right (S35: Yes), the priority output selection circuit 14_1 stores the input port number to which the priority packet for which the output right has been input is input in the control storage circuit 8 (S36).

  On the other hand, when the priority packet has not acquired the output right (S35: No), the priority output selection circuit 14_1 determines whether or not there is a priority packet that is a target for preceding output in the priority preceding output detection circuit 12_1. (S37).

  When there is a priority packet that is a target of priority output (S37: Yes), the priority output selection circuit 14_1 stores the input port number to which the priority packet that is a target of priority output is input in the control storage circuit 8 ( S38).

  When there is no priority packet targeted for preceding output (S37: No), the priority output selection circuit 14_1 determines whether or not the normal packet has acquired the output right in the arbitration circuit 6_1 (S39).

  When the normal packet has acquired the output right (S39: Yes), the priority output selection circuit 14_1 stores the input port number to which the normal packet from which the output right has been input is input in the control storage circuit 8 (S40). .

  On the other hand, when the normal packet does not acquire the output right (S39: No), the priority output selection circuit 14_1 writes in the control storage circuit 8 that there is no packet to be output in the next cycle from the output P1 (S41). ).

  Next, details of the priority preceding output determination process (S32) will be described with reference to the flowchart of FIG. The priority output selection circuit 14_1 determines whether or not the priority buffer 11_1 corresponding to the input P1 is empty (S51).

  When the priority buffer 11_1 is not empty (S51: No), the priority output selection circuit 14_1 does not set the preceding output target. On the other hand, when the priority buffer 11_1 is empty (S51: Yes), the priority preceding output detection circuit 12_1 determines whether the header of the priority packet is input to the input P1 (S52).

  When the header of the priority packet is not input (S52: No), the priority output selection circuit 14_1 does not set the preceding output target. On the other hand, when the header of the priority packet is input (S52: Yes), the priority output selection circuit 14_1 determines whether or not the output port number calculated by the path calculation circuit 3_1 is equal to the port number of the output P1. (S53).

  When the port numbers do not match (S53: No), the priority output selection circuit 14_1 does not set the preceding output target. On the other hand, if the port numbers match (S53: Yes), the priority output selection circuit 14_1 determines that the priority packet input from the input P1 is a preceding output candidate (S54).

  In the above-described S51 to S54, the priority output selection circuit 14_1 has performed the preceding output candidate determination process for the input P1. In parallel with this processing, the priority output selection circuit 14_1 performs processing corresponding to the input P2 (S55 to S58) and processing corresponding to the input P3 (S59 to S62).

  The priority output selection circuit 14_1 confirms whether or not the sum of the preceding output candidate packets selected from all the input ports is one (S63). When there is one priority packet of the preceding output candidate (S63: Yes), the priority output selecting circuit 14_1 determines the priority packet as a preceding output target packet (S64). On the other hand, when there is not one priority packet of the preceding output candidate (S63: No), the priority output selection circuit 14_1 determines that there is no priority packet to be the preceding output target (S65). When there are a plurality of priority packets that are prior output candidates, these priority packets are subjected to arbitration by the arbitration circuit in the next cycle.

  Next, a specific operation example of the router device according to the present embodiment will be described with reference to FIGS. 7 and 10. FIG. 10 is a time chart illustrating an operation example when a priority packet having the output P3 as the output destination is input in the cycle t. In this example, a normal packet is input from the input P2 in the cycle t-1, and stored in the buffer 4_2. Furthermore, in this example, there is no input from other input ports (input P2, input P3) in cycle t. The priority buffers 11_1 to 11_3 are empty. A to I in FIG. 10 indicate passing signals at points (A to I) in FIG.

  In cycle t, the header of the priority packet is input from the input P1 to the latch 2_1 (see FIG. 10A). The header of this priority packet is output from the latch 2_1 in cycle t + 1. The header of the output priority packet is stored in the priority buffer 11_1 after the route calculation is performed by the route calculation circuit 3_1 (see FIG. 10B).

  Simultaneously with the storage in the priority buffer 11_1, the header of the priority packet is also supplied to the priority preceding output detection circuit 12_3. The priority / preceding output detection circuit 12_3 determines whether there is a priority packet to be output in advance from the header of the priority packet input from each path calculation circuit and the buffer storage status of the priority buffers 11_1 to 11_3. Since the priority buffers 11_1 to 11_3 are empty, the priority / preceding output detection circuit 12_3 determines that the priority packet input in the cycle t is a preceding output target, and sets the input port number “1” to the priority output selection circuit 14_3 in the cycle t + 1. (See FIG. 10C).

  In cycle t + 1, the arbitration circuit 6_3 performs an arbitration process. The arbitration circuit 6_3 is notified of the packet storage status from each priority buffer and buffer. For example, the arbitration circuit 6_3 is notified that there is no packet stored in the priority packet 11_1 corresponding to the input P1 in the cycle t (see FIG. 10D). Arbitration circuit 6_3 is notified that there is a packet whose output destination is output P3 in buffer 4_2 corresponding to input P2 in cycle t (see FIG. 10E).

  The arbitration circuit 6_3 notifies the priority output selection circuit 14_3 that the output right has been given to the normal packet (“2N”) of the input P2 as a result of the arbitration process in the cycle t + 1 (see FIG. 10F).

  In the cycle t + 1, the priority output selection circuit 14_3 selects an output target packet in the cycle t based on the input ("1") from the priority preceding output detection circuit 12_3 and the input ("2N") from the arbitration circuit 6_3. The priority packet is input from the input P1. That is, the priority output selection circuit 14_3 outputs “1” to the control storage circuit 8 in the cycle t + 1 (see FIG. 10G).

  The control storage circuit 8 notifies the buffer selection circuit 13_1 of an output permission signal in cycle t + 2 (see FIG. 10H). As a result, the header of the packet stored in the priority buffer 11_1, that is, the header of the priority packet targeted for preceding output is supplied to the switch without being subject to arbitration by the arbitration circuit. The header of the packet that has passed through the switch is output from the router device 1 in cycle t + 2 (see FIG. 10I).

  Next, the effect of the router device according to this embodiment will be described. As shown in FIG. 10, the router device according to the present embodiment selects an output packet so as to output a priority packet in preference to a normal packet that has already been stored. As a result, the arbitration process can be shortened and a packet having a high priority can be preferentially output.

<Embodiment 4>
The router device according to the present embodiment corresponds to a priority packet and corresponds to a source routing method. FIG. 11 shows the configuration of the router apparatus according to this embodiment. In FIG. 11, processing units and circuits having the same name and the same reference numerals perform the same processing as in the first, second, and third embodiments. Therefore, the overlapping description is omitted as appropriate.

  The router device 1 includes buffers 4_1 to 4_3, priority buffers 11_1 to 11_3, priority preceding output detection circuits 12_1 to 12_3, buffer selection circuits 13_1 to 13_3, arbitration circuits 6_1 to 6_3, and priority output selection circuits 14_1 to 14_3. And path update circuits 10_1 to 10_3, a control storage circuit 8, and a switch 9. Since the operation of each circuit and processing unit is the same as in the first to third embodiments, detailed description thereof is omitted.

  The router device 1 according to the present embodiment includes priority buffers 11_1 to 11_3 as in the third embodiment, and can preferentially process priority packets over already stored normal packets. Furthermore, since the router device 1 according to the present embodiment is configured to include the route update circuits 10_1 to 10_3 as in the second embodiment, the latency required for passing through the router can be reduced.

  Note that the present invention is not limited to the above-described embodiment, and can be changed as appropriate without departing from the spirit of the present invention. For example, in the above-described example, the router apparatus having three output ports has been described. However, the present invention is not limited to this, and the present invention can be applied to a router apparatus having one or more arbitrary number of output ports. Further, the router device can be configured to notify the switch or the like of the determination result of the output selection circuit or the priority output selection circuit without using the control storage circuit.

DESCRIPTION OF SYMBOLS 1 Router apparatus 2_1-2_3 Latch 3_1-3_3 Path | route calculation circuit 4_1-4_3 Buffer 5_1-5_3 Precedence output detection circuit 6_1-6_3 Arbitration circuit 7_1-7_3 Output selection circuit 8 Control storage circuit 9 Switch 10_1-10_3 Path | route update circuit 11_1-11_3 Priority buffers 12_1 to 12_3 Priority preceding output detection circuits 13_1 to 13_3 Buffer selection circuits 14_1 to 14_3 Priority output selection circuits

Claims (10)

A router device having a plurality of input ports and a first output port, and performing an arbitration process for controlling the output authority of the first output port,
When an input packet requesting output to the first output port in a certain cycle is the only packet requesting output to the first output port in the router device, the packet is subjected to the arbitration process. A router device that determines a prior output target packet to be output without being targeted. A storage unit temporarily holding a packet waiting to be output;
A preceding output detection circuit for detecting the preceding output target packet based on an input state of a packet requesting output to the first output port in the cycle and a storage state of the storage unit;
When the preceding output target packet is detected, the packet is determined as a packet to be output from the first output port, and when the preceding output target packet is not detected, the first output is performed based on the arbitration process. An output selection circuit for determining a packet to be output from the port;
A switch unit for controlling the switching of the wiring to the first output port based on the determination of the output selection unit,
The router device according to claim 1. In the cycle, the preceding output detection circuit, when there is no packet waiting for output in the storage unit and there is one packet whose output destination is the first output port, Is detected as the preceding output target packet,
The router device according to claim 2. The preceding output detection circuit, when there is no priority packet to be preferentially transmitted to the storage unit in the cycle and there is one input of the priority packet having the first output port as an output destination Detecting the priority packet as the preceding output target packet;
The router device according to claim 2. Comprising an arbitration circuit for performing the arbitration process;
The arbitration circuit preferentially grants the output authority from the first output port to the priority packet;
The router device according to claim 4. A control storage circuit for storing information of a packet related to the output of the first output port in a cycle unit and notifying the switch unit of the information;
The output selection unit writes determination information of a packet to be output from the first output port into the control storage circuit;
The router device according to any one of claims 2 to 5, wherein: A second output port;
A path calculation circuit that determines an output port to be output from header information of a packet input to any of the plurality of input packets,
The router device according to any one of claims 2 to 6, wherein: A second output port;
Communication path information is included in the packet input to the router device;
The router device according to any one of claims 2 to 6, wherein: Comprising a route update circuit for deleting information relating to a route that has already passed from the communication route information;
The router device according to claim 8. A control method of a router device having a plurality of input ports and a first output port, and performing an arbitration process for controlling the output authority of the first output port,
When an input packet requesting output to the first output port in a certain cycle is the only packet requesting output to the first output port in the router device, the packet is subjected to the arbitration process. A control method for determining a prior output target packet to be output without being targeted.

Images