JP7684261B2 - A transmitting device that pre-discards packets to be transmitted - Google Patents

Description

This disclosure relates to a technique for pre-discarding packets to be transmitted in order to avoid congestion.

Non-Patent Document 1 discloses a configuration for performing distributed deep learning (DDL) of a neural network (NN). In DDL, the processing performed for learning one NN is divided and executed by multiple processing devices. In DDL, a processing device generally requires information obtained by processing performed by other processing devices in order to execute the processing assigned to the processing device. For this reason, in DDL, packets are sent and received between processing devices. In the following description, a processing device that sends packets to other processing devices is referred to as a "sending device", and a processing device that receives packets from other processing devices is referred to as a "receiving device". Note that each of the multiple processing devices can function as both a "sending device" and a "receiving device".

For example, a packet transmitted from a transmitting device during forward propagation in learning a NN contains information indicating the output value of the layer for which the transmitting device is responsible for processing among the multiple layers of the NN. Also, during backward propagation, a packet transmitted from a transmitting device contains information indicating the error of the layer for which the transmitting device is responsible for processing. Non-Patent Document 1 discloses a configuration in which processing devices are connected by optical paths. Also, Non-Patent Document 2 discloses a configuration in which a transmitting device discards some of the packets to be transmitted to a receiving device in order to avoid congestion in a DDL. It is known that in a DDL, even if some of the information transmitted from a transmitting device to a receiving device is missing, this does not have a significant impact on learning.

C. Wang, et. al. , “Acceleration and Efficiency Warranty for Distributed Machine Learning Jobs over Data Center Network with Optical Circuit Switching”, 2021 Optical Fiber Communications Conference and Exhibition (OFC), 2021, pp. 1-3 Jiacheng Xia, et. al. , 2019. Rethinking Transport Layer Design for Distributed Machine Learning. In Proceedings of the 3rd Asia-Pacific Workshop on Networking 2019 (APNet'19), Association for Computing Machinery, New York, USA, 22-28

However, if a transmitting device discards a large number of packets to avoid congestion, a lot of information will be lost at the receiving device, and the performance of the processing results at the receiving device may deteriorate. On the other hand, if the transmitting device does not discard enough packets, congestion will not be avoided and it will take a long time for the receiving device to obtain the processing results that receive those packets.

This disclosure provides a technology for a transmitting device that pre-discards packets to be transmitted, without degrading the processing results in a receiving device, and preventing the time it takes for the processing results to be obtained in the receiving device from increasing.

According to one aspect of the present disclosure, a transmitting device includes a generating means for generating a plurality of first packets based on information to be transmitted to a receiving device, a control means for setting a discard rate, a transmitting means for discarding a portion of the plurality of first packets according to the discard rate and transmitting the remaining plurality of second packets to the receiving device, and an acquiring means for acquiring from the receiving device first information corresponding to a period during which the plurality of second packets are received by the receiving device and second information indicating the performance of the result of processing performed by the receiving device based on the plurality of second packets, and the control means controls the discard rate based on the first information and the second information.

According to the present disclosure, in a transmitting device that pre-discards packets to be transmitted, it is possible to prevent degradation of the processing results in the receiving device and to prevent the time it takes for the processing results to be obtained in the receiving device from increasing.

FIG. 2 is a diagram illustrating the configuration of a transmitting device and a receiving device according to an embodiment. 11 is a flowchart of a process performed by a transmitting device according to an embodiment. 6 is a flowchart of a process performed by a control unit according to an embodiment. 6 is a flowchart of a process performed by a control unit according to an embodiment.

The following embodiments are described in detail with reference to the attached drawings. Note that the following embodiments do not limit the invention according to the claims, and not all combinations of features described in the embodiments are necessarily essential to the invention. Two or more of the features described in the embodiments may be combined in any desired manner. In addition, the same reference numbers are used for the same or similar configurations, and duplicate descriptions will be omitted.

The following describes an embodiment using an example in which DDL is performed by multiple processing devices. As described above, in DDL, packets are transmitted and received between multiple processing devices. In this embodiment, a processing device that transmits packets is referred to as a transmitting device, and a processing device that receives packets is referred to as a receiving device. Each processing device can function as both a transmitting device and a receiving device. There are multiple pairs of transmitting devices and receiving devices, but the processing that the transmitting device performs to transmit packets to the receiving device is the same for all pairs. Therefore, the following describes only one pair of transmitting device 1 and receiving device 2 shown in Figure 1.

First, the terminology used in this embodiment will be explained. Deep learning of a NN is performed by forward propagation of output values of each layer using training data, and backward propagation of errors based on the results of the forward propagation. In the following, the process of performing forward propagation and backward propagation of errors based on the results of the forward propagation, up to updating each weight of the NN, is referred to as one "stage." In deep learning, this stage is repeated.

At each stage, the transmitting device 1 transmits multiple packets to the receiving device 2. The multiple packets include the processing results of the transmitting device 1, such as the output value of the layer that the transmitting device 1 is responsible for processing among the multiple layers of the NN, and errors. The processing results are used for processing at the receiving device 2. In this embodiment, the "delay" is the period from the timing when the receiving device 2 starts receiving the first packet from the transmitting device 1 to the timing when the receiving device 2 completes receiving the last packet in one stage. In other words, the "delay" in this embodiment corresponds to the reception period during which the receiving device 2 receives packets from the transmitting device 1. Note that the amount of data transmitted from the transmitting device 1 to the receiving device 2 is constant at each stage. Since the amount of data transmitted from the transmitting device 1 to the receiving device 2 is constant at each stage, if there is no congestion on the network path from the transmitting device 1 to the receiving device 2, the delay is approximately constant at each stage. On the other hand, if congestion occurs on the network path from the transmitting device 1 to the receiving device 2, the delay becomes larger compared to when there is no congestion. Note that, in general, the higher the degree of congestion, the larger the delay.

At each stage, when the transmission of a packet from the transmitting device 1 to the receiving device 2 is completed, the receiving device 2 performs a predetermined process. When the receiving device 2 completes the predetermined process, it evaluates the performance of the processing result and determines an evaluation value. Any method for evaluating performance may be used. For example, in DDL, each receiving device 2 receives an error for each stage. The error generally becomes smaller the more times a stage is repeated, but if the receiving device 2 does not receive enough information required for processing, the degree of reduction in error from the previous stage may become smaller, or in some cases may even increase. Therefore, the performance of each stage can be evaluated based on the difference in error between two successive stages to determine an evaluation value.

The operation of the transmitting device 1 and the receiving device 2 in one stage will be described below with reference to FIG. 1. The source unit 10 of the transmitting device 1 packetizes information obtained as a result of processing performed by the transmitting device 1 in a certain stage that needs to be transmitted to the receiving device 2, and outputs the packet to the packet discarding unit 11. The memory unit 12 stores the packet discard rate R. The packet discarding unit 11 discards some of the multiple packets from the source unit 10 based on the discard rate R, and transmits the remaining multiple packets to the receiving device 2. For example, if the packet discard rate R is 1% and 100 packets are received from the source unit 10, the packet discarding unit 11 discards one of the packets and transmits the remaining 99 packets to the receiving device 2.

The receiving unit 20 of the receiving device 2 receives packets from the transmitting device 1 and outputs them to the processing unit 21. The processing unit 21 executes a predetermined process given to the receiving device 2 using the packets from the transmitting device 1. The receiving unit 20 also measures the delay L described above based on the received packets and notifies the transmitting device 1. Furthermore, the processing unit 21 determines the performance evaluation value P described above based on the results of the predetermined process and notifies the transmitting device 1. The control unit 13 of the transmitting device 1 updates the discard rate R based on the delay L and evaluation value P acquired from the receiving device 2 and stores it in the memory unit 12. This discard rate R is used in the next stage. The control unit 13 controls the overall operation performed by the transmitting device 1.

2 is a flowchart of the process executed by the transmitting device 1. In the flowchart of FIG. 2, each stage is denoted as the s-th stage, where s is an integer equal to or greater than 0. The discard rate R used in the s-th stage is denoted as _Rs , and the delay L and evaluation value P notified from the receiving device 2 in the s-th stage are denoted as delay _Ls and evaluation value _Ps . The discard rate R0 in the first stage, i.e., the 0th stage, is set to ₀ .

In S10, the control unit 13 initializes an index s indicating the number of times a stage is repeated to 0. In S11, the packet discard unit 11 transmits the remaining packets to the receiving device 2 while discarding packets from the source unit 10 at a discard rate _Rs . In the case of the 0th stage, the discard rate _Rs is 0, so the packet discard unit 11 transmits all packets from the source unit 10 to the receiving device 2. In S12, the control unit 13 acquires the delay _Ls and evaluation value _Ps at the sth stage from the receiving device 2.

The control unit 13 judges whether s=0 in S13, that is, whether the stage is the 0th stage. If the stage is the 0th stage, the control unit 13 sets the discard rate R ₁ in the next stage, that is, the first stage, to a predetermined value R _p in S14. On the other hand, if the stage is not the 0th stage, the control unit 13 obtains the discard rate R _s+1 in the next stage, that is, the (s+1)th stage, based on the delay L _s-1 and evaluation value P s _-1 in the previous stage and the delay L _s and evaluation value P _s in the current stage in S15. The control unit 13 judges whether the current stage is the final stage in S16. If the current stage is not the final stage, the control unit 13 increments the index s by 1 in S17 and repeats the process from S11. On the other hand, if the current stage is the final stage, the control unit 13 ends the process of FIG. 2.

3 is a flowchart of the process in S15 of FIG. 2. In S20, the control unit 13 compares the evaluation value P _s in the sth stage with the evaluation value P _s-1 in the (s-1)th stage, and judges whether the evaluation value P _s is worse than the evaluation value P _s-1 and the degree of deterioration is greater than a first threshold value. In other words, the control unit 13 judges whether the performance in the sth stage is worse than the first threshold value compared to the performance in the (s-1)th stage. If the performance in the sth stage is worse than the first threshold value compared to the previous stage, the control unit 13 judges that the discard rate R _s is too large. Therefore, in S22, the control unit 13 reduces the discard rate R _s+1 in the next (s+1)th stage by a predetermined value R _p2 from the discard rate R _s in the current sth stage.

On the other hand, if the performance in the sth stage is not deteriorated by more than the first threshold value compared to the previous stage, the control unit 13 compares the delay L _s in the sth stage with the delay L _s-1 in the (s-1)th stage in S21, and judges whether the delay L _s has increased from the delay L _s-1 and the degree of increase is greater than the second threshold value. That is, it judges whether the delay in the sth stage has increased by more than the second threshold value compared to the delay in the (s-1)th stage. If the delay in the sth stage has increased by more than the second threshold value compared to the previous stage, the control unit 13 judges that the discard rate R _s is too small. Therefore, in S23, the control unit 13 increases the discard rate R _s+1 in the next (s+1)th stage by a predetermined value R _p1 from the discard rate R _s in the current sth stage. On the other hand, if the delay in the sth stage has not increased by more than the second threshold value with respect to the previous stage, the control unit 13 determines that the current discard rate _Rs is appropriate. In this case, the control unit 13 determines in S24 that the current discard rate _Rs should be used in the (s+1)th stage without being changed.

By controlling the discard rate R in the above manner, it is possible to control the discard rate R so as to suppress delays and suppress degradation of performance. By suppressing delays, that is, by suppressing an increase in the period in which the receiving device 2 receives information from the transmitting device 1, it is possible to suppress an increase in the time it takes for the receiving device to obtain processing results. In addition, by suppressing degradation of performance, it is possible to suppress deterioration of the processing results in the receiving device 2.

Since the discard rate R cannot be a negative value, if the discard rate R _s+1 is a negative value in S22, the control unit 13 sets the discard rate R _s+1 to 0. Alternatively, an upper limit value of the discard rate R may be determined, and if the discard rate R _s+1 exceeds the upper limit value in S23, the control unit 13 may set the discard rate R _s+1 to the upper limit value. Also, the predetermined values R _p , R _p+1 , and R _p+2 may be the same value or different values.

<Modification>
In Fig. 3, if the delay in the sth stage has increased by more than the second threshold value compared to the previous stage in S21, the control unit 13 increases the discard rate R in the next stage by a predetermined value in S23, and if not, determines to use the discard rate R as it is in the next stage without changing it in S24. In this modification, when the kth stage (k is an integer of 2 or more) is reached, the delay _Ls in the current sth stage is compared with the delay in the past k stages to determine the discard rate Rs ₊₁ in the next (s+1)th stage. The process up to the kth stage is the same as that in Fig. 3.

FIG. 4 shows a flowchart of the process performed by the control unit 13 in S15 of FIG. 2 in this modification. In this modification, S15 of FIG. 2 becomes "determine R _s+1 based on L _s to L _s-k and P _s and P _s-1 ". In FIG. 4, the same step numbers are given to the same process steps as in the flowchart of FIG. 3. The difference from the flowchart of FIG. 3 is that S21 in FIG. 3 becomes S30. In S30, the control unit 13 compares the delay L _s with the delays L _s-1 , L _s-2 , ..., L _s-k in the past k stages. Then, if the increase in the delay L _s for at least one of the delays L _s-1 , L _s-2 , ..., L _s-k is greater than the second threshold, the control unit 13 increases the discard rate R in the next stage by a predetermined value in S23. On the other hand, if the increase in delay _Ls for all of delays Ls _-1 , Ls _-2 , ..., Ls _-k is not greater than the second threshold, the control unit 13 decides in S24 to use the discard rate R as it is in the next stage without changing it.

In this modified example, the discard rate R is controlled based on the results of a comparison with the delay L not only in the previous stage but also in multiple previous stages, so that the discard rate R can be controlled to further optimize the delay while suppressing performance degradation.

Note that, although the embodiment has been described using an example of performing DDL, the present disclosure can be applied to applications in which the loss of some information is not a problem. An example of such an application is the distribution of content such as video and music. In content distribution, the loss of a small amount of information does not make it impossible to view the content. In content distribution, the content can be divided into blocks of a predetermined amount of data, and the transmission of one block can be considered as one stage.

The transmitting device 1 according to the present disclosure may be realized by a computer program that, when executed by one or more processors of a device having one or more processors, causes the device to function as the transmitting device 1. The computer program may include program instructions that are executable by one or more processors. The computer program may be stored on a computer-readable non-transitory storage medium or may be distributed via a network.

With the above configuration, a transmitting device that discards packets to be transmitted in advance can prevent degradation of the processing results in the receiving device and prevent the time it takes for the processing results to be obtained in the receiving device from increasing. This makes it possible to contribute to Goal 9 of the United Nations-led Sustainable Development Goals (SDGs), which is to "build resilient infrastructure, promote sustainable industrialization and foster innovation."

The invention is not limited to the above-described embodiment, and various modifications and variations are possible within the scope of the invention.

10: Source unit, 11: Packet discard unit, 13: Control unit

Claims (7)

A generating means for generating a plurality of first packets based on information to be transmitted to a receiving device;
A control means for setting a discard rate;
a transmitting means for discarding a portion of the plurality of first packets in accordance with the discard rate and transmitting the remaining plurality of second packets to the receiving device;
an acquisition means for acquiring, from the receiving device, first information corresponding to a period during which the receiving device receives the plurality of second packets, and second information indicating performance of a result of processing performed by the receiving device based on the plurality of second packets;
Equipped with
The control means controls the discard rate based on the first information and the second information. The transmitting device repeatedly executes a plurality of stages,
each of the plurality of stages includes discarding a portion of the plurality of first packets according to the discard rate and transmitting the remaining plurality of second packets to the receiving device, and acquiring the first information and the second information from the receiving device;
2. The transmitting device according to claim 1, wherein the control means, when the second information acquired in the first stage indicates that the performance indicated by the second information acquired in the second stage immediately preceding the first stage is significantly deteriorated by more than a first threshold value, reduces the discard rate in a third stage performed after the first stage by a first predetermined value compared to the discard rate in the first stage. The control means increases the discard rate in the third stage by a second predetermined value from the discard rate in the first stage when the second information acquired in the first stage indicates that the performance indicated by the second information acquired in the second stage has not deteriorated by more than the first threshold value, and when the first information acquired in the first stage indicates that the performance indicated by the first information acquired in the second stage has increased by more than the second threshold value for the reception period indicated by the first information acquired in the second stage. The transmission device according to claim 2. The control means increases the discard rate in the third stage by a second predetermined value from the discard rate in the first stage when the second information acquired in the first stage indicates that the performance indicated by the second information acquired in the second stage has not deteriorated by more than the first threshold value, and when the first information acquired in the first stage indicates that the reception period indicated by at least one of the first information pieces among the multiple first information pieces acquired in each of the multiple stages executed before the first stage has increased by more than the second threshold value. The transmission device according to claim 2. The transmitting device according to claim 2, wherein the control means sets the discard rate in the third stage to be the same as the discard rate in the first stage when the second information acquired in the first stage indicates that the performance indicated by the second information acquired in the second stage has not deteriorated by more than the first threshold value, and when the first information acquired in the first stage indicates that the performance indicated by the first information acquired in the second stage has not increased by more than the second threshold value for the reception period indicated by the first information acquired in the second stage. The control means, when the second information acquired in the first stage indicates that the performance indicated by the second information acquired in the second stage has not deteriorated by more than the first threshold value with respect to the performance indicated by the second information acquired in the second stage, and when the first information acquired in the first stage indicates that the performance has not increased by more than the second threshold value with respect to all reception periods indicated by the multiple pieces of first information acquired in each of the multiple stages executed before the first stage, sets the discard rate in the third stage to be the same as the discard rate in the first stage. The transmission device according to claim 2. A computer program that, when executed by one or more processors of a device having one or more processors, causes the device to function as a transmitting device according to any one of claims 1 to 6.

Images