METHOD OF PERFORMING DISTRIBUTED MATRIX COMPUTATION USING TASK ENTANGLEMENT-BASED CODING

Abstract

A method of performing distributed matrix computation using task entanglement-based coding as a method of processing a huge amount of matrix computation in a distributed manner in a distributed computing environment is provided. A main server encodes information to be transmitted to a plurality of edge devices for distributed matrix computation on the basis of task entanglement-based coding employing a Chebyshev polynomial, thereby reducing the amount of information to be transmitted. Also, when the number of computation results received from the edge devices becomes a recovery threshold, the main server immediately performs decoding to derive a matrix computation result.

Claims

1. A method for a main server to perform distributed matrix computation using plurality of edge devices, the method comprising: a division operation of dividing first and second matrices to be computed into m first partial matrices and n second partial matrices, respectively; an encoding operation of encoding the m first partial matrices and the n second partial matrices into encoding matrices for each edge device on the basis of task entanglement-based coding employing a Chebyshev polynomial; a transmission operation of transmitting the encoded matrices for each edge device to the corresponding edge device; a reception operation of receiving matrix computation task results from the edge devices; and a decoding operation of, when a number of received matrix computation task results becomes a first recovery threshold, decoding the received matrix computation task results to recover a computation result of the first matrix and the second matrix.

2. The method of claim 1, wherein the encoding operation comprises: a first encoding operation of encoding the m first partial matrices into L.sub.2 encoding matrices for each edge device according to a determined number L (L=L.sub.1L.sub.2, L.sub.1 and L.sub.2 are coprime) of tasks on the basis of task entanglement-based coding employing a first Chebyshev polynomial with an order of L.sub.1; and a second encoding operation of encoding the n second partial matrices into L.sub.1 encoding matrices for each edge device on the basis of task entanglement-based coding employing a second Chebyshev polynomial with an order of L.sub.2.

3. The method of claim 2, wherein the encoding operation further comprises an evaluation point selection operation of selecting L.sub.2 evaluation points to be used in the first encoding operation and L.sub.1 evaluation points to be used in the second encoding operation.

4. The method of claim 3, wherein the first encoding operation comprises encoding the m first partial matrices into the L.sub.2 encoding matrices by adding a matrix obtained by encoding a random matrix on the basis of task entanglement-based coding employing the first Chebyshev polynomial with an order of L.sub.1 to encoding matrices; and the second encoding operation comprises encoding the n second partial matrices into the L.sub.1 encoding matrices by adding a matrix obtained by encoding a random matrix on the basis of task entanglement-based coding employing the second Chebyshev polynomial with an order of L.sub.2 to encoding matrices.

5. The method of claim 4, wherein the decoding operation comprises, when the number of received matrix computation task results becomes a second recovery threshold, decoding the received matrix computation task results to recover the computation result of the first matrix and the second matrix.

6. A method of performing distributed matrix computation using a main server and plurality of edge devices in a distributed computing environment in which the plurality of edge devices have a first matrix dataset and a second matrix dataset to be computed, the method comprising: a one-hot encoding operation in which the main server performs one-hot encoding on indices in the corresponding datasets of a first matrix and a second matrix to be computed; a first encoding operation in which the main server encodes a matrix obtained by performing one-hot encoding on the first matrix into a first encoding matrix for each edge device on the basis of task entanglement-based coding employing a Chebyshev polynomial; a second encoding operation in which the main server encodes a matrix obtained by performing one-hot encoding on the second matrix into a second encoding matrix for each edge device on the basis of task entanglement-based coding employing a Chebyshev polynomial; a transmission operation in which the main server transmits the matrices encoded for each edge device to the corresponding edge device; a first matrix encoding operation in which the edge devices multiply all matrices of the first matrix dataset by the first encoding matrix to encode the first matrix; a second matrix encoding operation in which the edge devices multiply all matrices of the second matrix dataset by the second encoding matrix to encode the second matrix; a matrix computation operation in which the edge devices perform a matrix computation task on the encoded first matrix and the encoded second matrix; a computation result transmission operation in which each edge device transmits a computation result to the main server; a reception operation in which the main server receives the matrix computation task results from the edge devices; and a decoding operation in which, when a number of received matrix computation task results becomes a first recovery threshold, the main server recovers a computation result of the first matrix and the second matrix by decoding the received matrix computation task results.

7. The method of claim 6, wherein the first encoding operation is an operation of encoding a matrix obtained by performing one-hot encoding on the first matrix into L.sub.2 encoding matrices for each edge device according to a determined number L (L=L.sub.1L.sub.2, L.sub.1 and L.sub.2 are coprime) of tasks on the basis of task entanglement-based coding employing a first Chebyshev polynomial with an order of L.sub.1, and the second encoding operation is an operation of encoding a matrix obtained by performing one-hot encoding on the second matrix into L.sub.1 encoding matrices for each edge device on the basis of task entanglement-based coding employing a second Chebyshev polynomial with an order of L.sub.2.

8. The method of claim 7, further comprising an evaluation point selection operation in which the main server selects L.sub.2 evaluation points to be used in the first encoding operation and L.sub.1 evaluation points to be used in the second encoding operation.

9. The method of claim 8, wherein, in the first encoding operation, the main server encodes an encoding matrix into the L.sub.2 encoding matrices by adding a matrix obtained by encoding a random matrix on the basis of task entanglement-based coding employing the first Chebyshev polynomial with an order of L.sub.1 to the encoding matrix, and in the second encoding operation, the main server encodes an encoding matrix into the L.sub.1 encoding matrices by adding a matrix obtained by encoding a random matrix on the basis of task entanglement-based coding employing the second Chebyshev polynomial with an order of L.sub.2 to the encoding matrix.

10. The method of claim 9, wherein the decoding operation comprises decoding the received matrix computation task results to recover the computation result of the first matrix and the second matrix when the number of matrix computation task results received by the main server becomes a second recovery threshold.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0043] FIG. 1 is a comparison between examples of processing distributed matrix multiplication in a distributed computing environment.

[0044] FIG. 2 is a comparison between a conventional task coding scheme and a task coding scheme of the present invention.

[0045] FIG. 3 is a flowchart illustrating distributed matrix multiplication according to a first exemplary embodiment of the present invention.

[0046] FIG. 4 is a diagram illustrating the concept of distributed matrix multiplication according to a second exemplary embodiment of the present invention.

[0047] FIG. 5 is a flowchart illustrating distributed matrix multiplication according to the second exemplary embodiment of the present invention.

[0048] Throughout the drawings and the detailed description, unless otherwise described, the same drawing reference numerals will be understood to refer to the same elements, features, and structures. The relative size and depiction of these elements may be exaggerated for clarity, illustration, and convenience.

DETAILED DESCRIPTION

[0049] The above-described and additional aspects are embodied through embodiments described with reference to the accompanying drawings. It will be understood that components of each of the embodiments may be combined in various ways within one embodiment unless otherwise stated or contradicted one another. Each of blocks in a block diagram may be a representation of a physical part in some cases, but may be a logical representation of a portion of a function of one physical part or a function of a plurality of physical parts in other cases. In some cases, the block or an entry of a portion of the block may be a set of program instructions. All or some of the blocks may be implemented as hardware, software, or a combination thereof.

[0050] As used herein, A and B are matrices defined as A∈F.sup.a×b and B∈F.sup.b×c, respectively.

[0051] FIG. 1 is a comparison between examples of processing distributed matrix multiplication in a distributed computing environment. FIG. 1 shows various examples of processing matrix multiplication, which is a fundamental building block of machine learning and deep learning, in a distributed manner. The examples correspond to distributed matrix multiplication of C=A×B (A and B are matrices). FIG. 1 shows various examples of task assignment for solving the problem of a straggler which processes a given task much slower than other edge devices.

[0052] In FIG. 1, one main server and four workers, that is, edge devices, are shown in common.

[0053] In FIG. 1A, a computation task is copied and assigned to several workers. The main server divides a matrix A into two partial matrices A.sub.1 and A.sub.2 having the same size, divides an A×B task into an A.sub.1×B task and an A.sub.2×B task, assigns each of the divided tasks to two workers such that a computation result, a matrix C, may be obtained without delay even when one straggler occurs in each task. However, when both of two workers W.sub.3 and W.sub.4 in charge of the same task perform calculation slowly as shown in FIG. 1A, the main server does not obtain a final result until task results are received from the two workers, and there is still the problem of stragglers.

[0054] In FIG. 1B, the main server assigns tasks using maximum distance separable (MDS) code. When task results are received from two fast workers, the main server may decode a final result C. Accordingly, FIG. 1B allows two stragglers.

[0055] FIG. 1C is an example of encoding both input matrices A and B using a polynomial function and assigning matrix multiplication to workers as one task. In FIG. 1C, a task result of the fastest worker is used to decode a final result C.

[0056] In both FIGS. 1B and 1C, computation results of stragglers of which tasks are not finished are not used, and thus resources are wasted.

[0057] Meanwhile, FIG. 1D is an example of task assignment used in the present invention. The main server encodes two small tasks in half the size of an original task and assigns the two small tasks to each worker. In this case, as soon as one of the two assigned tasks is finished, each worker transmits the task result to the main server. The main server may decode a final result using two task results of a worker W.sub.1 and a result of one of two tasks of workers W.sub.2, W.sub.3, and W.sub.4. As a result, this approach can reduce the overall processing time in a distributed computing environment fully using computing resources.

[0058] A method of performing distributed matrix computation using task entanglement-based coding according to a first exemplary embodiment of the present invention is a method for a main server to perform distributed matrix computation using a plurality of edge devices and includes a division operation, an encoding operation, a transmission operation, a reception operation, and a decoding operation.

[0059] The main server and the edge devices are computing devices encompassing hardware and software. The computing devices include a processor and a memory which is connected to the processor and includes program instructions executable by the processor. In addition to the processor and the memory, the computing devices may further include a graphics processing unit (GPU), a storage, a display, an input device, etc. The processor executes the program instructions, and the memory is connected to the processor and stores the program instructions executable by the processor, data to be used in computation by the processor, data processed by the processor, etc.

[0060] The main server and the edge devices are connected through a network. In the division operation, the main server divides first and second matrices to be computed into m first partial matrices and n second partial matrices, respectively. When the first matrix is A and the second matrix is B, [Equation 1] may be acquired.

[00001]$\begin{array}{cc}A=\left[\begin{array}{c}{A}_1\\ .Math.\\ A_m\end{array}\right],B=\left[\begin{array}{ccc}{B}_1& .Math.& B_n\end{array}\right]& \left[\mathrm{Equation}1\right]\end{array}$

[0061] A.sub.1 is a first partial matrix of A, A.sub.m is an m.sup.th partial matrix of A, B.sub.1 is a first partial matrix of B, and B.sub.n is an n.sup.th partial matrix of B.

[0062] When A.sub.w (w∈[1:m]) is defined as a partial matrix of A,

[00002]$A_w\in {𝔽}^{\frac{a}{m}\times b},$

and when B.sub.z (z∈[1:n]) is defined as a partial matrix of B,

[00003]$B_z\in {𝔽}^{b\times \frac{c}{n}}.$

[0063] m and n are values determined in advance by considering the sizes of the input matrices A and B, a distributed computing environment, etc.

[0064] In the encoding operation, the main server encodes the m first partial matrices and the n second partial matrices into encoding matrices for each edge device on the basis of task entanglement-based coding employing a Chebyshev polynomial. In other words, the main server encodes the matrices A and B to be computed in the encoding operation using a Chebyshev polynomial. When the encoded matrices are à and {tilde over (B)},

[00004]${\tilde{A}}_{i,j}\in {𝔽}^{\frac{a}{m}\times b}\mathrm{and}{\tilde{B}}_{i,j}\in {𝔽}^{b\times \frac{c}{n}}$

The main server encodes the matrices A and B to be computed for each edge device and encodes the matrices A and B into a plurality of encoding matrices even for one device.

[0065] According to the first exemplary embodiment of the present invention, the encoding operation may include a first encoding operation and a second encoding operation.

[0066] In the first encoding operation, the main server encodes the m first partial matrices into L.sub.2 encoding matrices for each edge device according to a determined number L (L=L.sub.1L.sub.2, L.sub.1 and L.sub.2 are coprime) of tasks on the basis of task entanglement-based coding employing a first Chebyshev polynomial with an order of L.sub.1.

[0067] A task assigned to an edge device for distributed matrix multiplication by the main server is a multiplication operation of encoded matrices. One task requires two encoded matrices. Therefore, when it is determined that L tasks are required for a multiplication operation between the two input matrices A and B, the main server transmits two encoded matrices for each task, that is, 2L encoded matrices, to the edge devices according to the related art.

[0068] The present invention employs a method of allowing repeated use of one encoded matrix in several tasks on the basis of task entanglement of L (L=L.sub.1L.sub.2, L.sub.1 and L.sub.2 are coprime) tasks such that L tasks can be performed as long as L.sub.1+L.sub.2 encoded matrices are received. Task entanglement means that tasks are entangled and several tasks are performed using the same encoded matrix. [Equation 2] below is a condition of task entanglement of matrices obtained by encoding the matrices A and B.

Ã.sub.t,x=Ã.sub.i,x+L.sub.1.sub.×(y−1), {tilde over (B)}.sub.i,x+L.sub.×(y−i), i∈[1:W], ∀×∈[1: L.sub.2], ∀y∈[1:L.sub.1]  (2)

[0069] W is the number of edge devices.

[0070] FIG. 2 is a comparison between a conventional coding scheme and a task coding scheme of the present invention. FIG. 2A shows the conventional coding scheme, and six tasks {tilde over (C)}.sub.i,1, {tilde over (C)}.sub.i,2, {tilde over (C)}.sub.i,3, {tilde over (C)}.sub.i,4, {tilde over (C)}.sub.i,5, and {tilde over (C)}.sub.i,6 performed at an i.sup.th edge device involve six encoded matrices Ã.sub.i,1, Ã.sub.i,2, Ã.sub.i,3, Ã.sub.i,4, Ã.sub.i,5, and Ã.sub.i,6 for the matrix A and six encoded matrices {tilde over (B)}.sub.i,1, {tilde over (B)}.sub.i,2, {tilde over (B)}.sub.i,3, {tilde over (B)}.sub.i,4, {tilde over (B)}.sub.i,5, and {tilde over (B)}.sub.i,6 for the matrix B. On the other hand, the task entanglement-based coding scheme of the present invention involves three encoded matrices Ã.sub.i,1, Ã.sub.i,2, and Ã.sub.i,3 for the matrix A and two encoded matrices {tilde over (B)}.sub.i,1 and {tilde over (B)}.sub.i,4 for the matrix B. Here, the condition of task entanglement is Ã.sub.i,1=Ã.sub.i,4, Ã.sub.i,2=Ã.sub.i,5, Ã.sub.i,3=Ã.sub.i,6, {tilde over (B)}.sub.i,1={tilde over (B)}.sub.i,2={tilde over (B)}.sub.i,3, and {tilde over (B)}.sub.i,4={tilde over (B)}.sub.i,5={tilde over (B)}.sub.i,6.

[0071] In the first encoding operation, the main server encodes a first partial matrix of the matrix A employing a Chebyshev polynomial through the encoding function p.sub.A(x) of [Equation 3].

[00005]$\begin{array}{cc}{p}_A\left(x\right)=\underset{w=1}{\overset{m}{.Math.}}{A}_w{f\left(x\right)}^{w-1},p_B\left(x\right)=\underset{z=1}{\overset{n}{.Math.}}{B}_z{g\left(x\right)}^{z-1}& \left[\mathrm{Equation}3\right]\end{array}$

[0072] f(x) is a Chebyshev polynomial with an order of L.sub.1, and g(x) is a Chebyshev polynomial with an order of L.sub.2.

[0073] The main server selects L evaluation points x.sub.i,j (j∈[1:L]) for each edge device, finds L.sub.2 evaluation points for a first matrix (m first partial matrices) according to the task entanglement condition of [Equation 2], and encodes the L.sub.2 evaluation points into L.sub.2 encoding matrices through the encoding function p.sub.A.

[0074] In the second encoding operation, the main server encodes the n second partial matrices into L.sub.1 encoding matrices for each edge device on the basis of task entanglement-based coding employing a second Chebyshev polynomial with an order of L.sub.2.

[0075] The main server finds L.sub.1 evaluation points for a second matrix (n second partial matrices) for each edge device according to the task entanglement condition of [Equation 2] from the same L evaluation points x.sub.i,j (j∈[1:L]) as used in the first encoding operation and encodes the L.sub.1 evaluation points into L.sub.1 encoding matrices through an encoding function p.sub.B.

[0076] According to the first exemplary embodiment of the present invention, the encoding operation may further include an evaluation point selection operation.

[0077] In the evaluation point selection operation, the main server selects L.sub.2 evaluation points to be used in the first encoding operation and L.sub.1 evaluation points to be used in the second encoding operation. The evaluation point selection operation is performed before encoding is performed

[0078] A Chebyshev polynomial used in task entanglement-based coding is a polynomial for which the commutative law holds, and a Chebyshev polynomial with an order of d has different real roots at (−1, 1). Using these characteristics in the evaluation point selection operation, the main server calculates L evaluation points for L tasks and then selects L.sub.1+L.sub.2 evaluation points according to the condition of task entanglement. A procedure for calculating an evaluation point is as follows.

[0079] f(x) is a Chebyshev polynomial with an order of L.sub.1, and g(x) is a Chebyshev polynomial with an order of L.sub.2.

[0080] i) An arbitrary value t between (−1, 1) is selected for the i.sup.th edge device. As t.sub.i, a value other than those selected by other edge devices is selected. In other words, when a≠b, t.sub.a≠t.sub.b.

[0081] ii) {tilde over (x)}.sub.i,k(k∈[1:L.sub.1], the root of f(x)=t.sub.i is calculated.

[0082] iii) x.sub.i,j,k (j∈[1:L.sub.2], k∈[1:L.sub.1), the root of g(x)={tilde over (x)}.sub.i,k(k∈[1:L.sub.1] is calculated. iv) x.sub.i,j,k is redisposed with respect to j to satisfy f(x.sub.i,j,k)={tilde over (x)}.sub.i,j. In other words, x.sub.i,j,k is redisposed to satisfy the condition of task entanglement.

[0083] The process from i) to iv) is repeated for each edge device. In the encoding operation, the main server performs encoding by inserting an x value of an evaluation point to a variable x of the encoding functions. Accordingly, the main server generates L.sub.2 encoded matrices for the first matrix A and generates L.sub.1 encoded matrices for the second matrix B.

[0084] In the transmission operation, the main server transmits the encoded matrices for each edge device to the corresponding edge device. Accordingly, the main server transmits L.sub.1+L.sub.2 encoded matrices to each edge device. While the related art involves transmitting 2L encoded matrices for L tasks, the number of pieces of transmission data is reduced to L.sub.1+L.sub.2 according to the present invention.

[0085] Each edge device performs matrix multiplication using encoded matrices received from the main server. In other words, the i.sup.th edge device performs L tasks, computation of {tilde over (c)}.sub.i,j,k=Ã.sub.i,j×{tilde over (B)}.sub.i,k, by multiplying an encoded matrix Ã.sub.i,j and {tilde over (B)}.sub.i,k (j∈[1:L.sub.2], k∈[1:L.sub.1]) received from the main server. As soon as each task is finished, the edge device transmits the computation result to the main server.

[0086] In the reception operation, the main server receives matrix computation task results from the edge devices.

[0087] In the decoding operation, when the number of received matrix computation task results becomes a first recovery threshold, the main server decodes the received matrix computation task results to recover a computation result of the first matrix and the second matrix. In other words, when as many computation results as the first recovery threshold are received from all the edge devices, the main server immediately performs decoding. Since encoding matrices are generated in the size of 1/m or 1/n from the original matrices, the computation amount of one task performed at an edge device becomes 1/mn of the original computation amount. Accordingly, the main server can recover a final target value when computation values of mn encoded matrices are acquired, and thus the first recovery threshold may be calculated as m×n.

[0088] A final computation result may be represented using multiplication of partial matrices as shown in [Equation 4].

[00006]$\begin{array}{cc}c=\left[\begin{array}{ccc}{A}_1{B}_1& .Math.& A_1{B}_n\\ .Math.& \ddots & .Math.\\ A_m{B}_1& .Math.& A_m{B}_n\end{array}\right]& \left[\mathrm{Equation}4\right]\end{array}$

[0089] Therefore, the final computation result may be calculated using [Equation 5], and each coefficient matrix may be extracted using repeated divisions and the like of f(x) and g(x). Specifically, A.sub.mB.sub.n may be calculated as a quotient by dividing p.sub.C(x) by f(x).sup.m−1g(x).sup.n−1, and A.sub.m−1B.sub.n Bn may be calculated as a quotient by dividing the remainder by f(x).sup.m−2g(x).sup.n−1. In this way, each coefficient matrix is extracted using repeated divisions.

p.sub.C(x)=p.sub.A(x)×p.sub.B(x)=A.sub.1B.sub.1+ . . . +A.sub.mB.sub.nf(x).sup.m−1g(x).sup.n−1   (5)

[0090] According to the first exemplary embodiment of the present invention, in the first encoding operation, the main server may add a matrix obtained by encoding a random matrix on the basis of task entanglement-based coding employing a first Chebyshev polynomial with an order of L.sub.1 to an encoding matrix as shown in [Equation 6], thereby encoding the encoding matrix into L.sub.2 encoding matrices. In the second encoding operation, the main server may add a matrix obtained by encoding a random matrix on the basis of task entanglement-based coding employing a second Chebyshev polynomial with an order of L.sub.2 to the encoding matrix as shown in [Equation 6], thereby encoding the encoding matrix into L.sub.1 encoding matrices. In other words, the main server may apply a security restriction in the first encoding operation and the second encoding operation.

[00007]$\begin{array}{cc}{p}_A\left(x\right)=\underset{w=1}{\overset{m}{.Math.}}{A}_w{f\left(x\right)}^{w-1}+\underset{w=1}{\overset{{\mathrm{EL}}_2}{.Math.}}{Z}_w{f\left(x\right)}^{m+w-1},p_B\left(x\right)=\underset{z=1}{\overset{n}{.Math.}}{B}_z{g\left(x\right)}^{z-1}+\underset{z=1}{\overset{{\mathrm{EL}}_1}{.Math.}}{Z}_z{g\left(x\right)}^{n+z-1}& \left[\mathrm{Equation}6\right]\end{array}$

[0091] Z.sub.w and Z.sub.z are random matrices, and E is the number of colluding edge devices.

[0092] As coefficients, the encoding functions employ first matrices A and B and a matrix Z in which each element has a random value. Since each element value of the matrix Z is extracted from a random distribution, the matrix Z has the largest entropy according to information theory. The encoding functions of [Equation 6] ensure complete data security in distributed computing and distributed machine learning. According to information theory, this can be proved by a zero-knowledge proof proposed by Shannon. This represents that each edge device cannot acquire any information from encoded matrices assigned for a task and may be mathematized as shown in [Equation 7].

[00008]$\begin{array}{cc}I\left({\left\{{\left\{{\tilde{A}}_{i,j}\right\}}_{j=1}^L\right\}}_{\forall i\in s},{\left\{{\left\{{\tilde{B}}_{i,j}\right\}}_{j=1}^L\right\}}_{\forall i\in z};A,B\right)=0,\forall \epsilon \subset \left[1:W\right],.Math.\epsilon .Math.=E& \left[\mathrm{Equation}7\right]\end{array}$

[0093] [Equation 7] represents that mutual information between a set of matrices à and {tilde over (B)}, which are assigned to all the edge devices for L tasks, and the original matrices A and B is 0. In other words, even when all E colluding edge devices share assigned matrices with each other and collude to infer the original matrices, according to information theory, it is never possible to obtain the original matrices. This is because a random matrix Z used in the encoding functions has greater entropy than the input matrices A and B.

[0094] In this case, when the number of received matrix computation task results becomes a second recovery threshold in the decoding operation, the main server decodes the received matrix computation task results to recover a computation result of the first matrix and the second matrix. The first recovery threshold corresponds to the same number of inner products as the original matrix multiplication. However, when a random matrix is added for encoding, the number of inner products which is approximately linearly proportional to the number of assigned tasks becomes the second recovery threshold as shown in [Equation 8], and a final result may be recovered from a computation result corresponding to the second recovery threshold.

R=(m+EL.sub.2)(n+EL.sub.1)≅(m+E√{square root over (L)})(n+E√{square root over (L)})   (8)

[0095] E is the number of edge servers which collude with each other to leak matrix information.

[0096] On the other hand, in the case of an encoding method employing a polynomial according to the related art, when a security restriction is applied, decoding involves as many inner product results as R=(m+EL)(n+EL).

[0097] FIG. 3 is a flowchart illustrating distributed matrix multiplication according to the first exemplary embodiment of the present invention. The main server receives a first matrix and a second matrix to be computed and divides the first matrix and the second matrix into m first partial matrices and n second partial matrices, respectively (S1000).

[0098] The main server selects L.sub.2 evaluation points to be used in a first encoding operation and L.sub.1 evaluation points to be used in a second encoding operation for L tasks of each edge device (S1010). Here, the evaluation points satisfy the task entanglement condition of [Equation 2]. For each edge device, the main server encodes the first matrix into L.sub.2 encoding matrices to which security is applied on the basis of task entanglement-based coding employing a first Chebyshev polynomial with an order of L.sub.1 as shown in [Equation 6] (S1020) and encodes the second matrix into L.sub.1 encoding matrices to which security is applied on the basis of task entanglement-based coding employing a second Chebyshev polynomial with an order of L.sub.2 as shown in [Equation 6] (S1030). The main server transmits L.sub.1+L.sub.2 matrices encoded for each edge device to the corresponding edge device (S1040). Each edge device performs L computation tasks using the received encoded matrices. As soon as each individual computation task is finished, each edge device transmits the computation result to the main server (S1050). The main server receives matrix computation task results from edge devices (S1060). When the number of received matrix computation task results becomes a second recovery threshold, the main server recovers a computation result of the first matrix and the second matrix by decoding the received matrix computation task results (S1070).

[0099] FIG. 4 is a diagram illustrating the concept of distributed matrix multiplication according to a second exemplary embodiment of the present invention. The example of

[0100] FIG. 4 is a distributed matrix multiplication method that is applicable when edge devices may access a matrix dataset in which matrices to be computed are stored, that is, matrix libraries, or store matrix datasets on their own. In other words, in the second exemplary embodiment, the main server does not transmit data to be computed to each edge device for matrix computation, but edge devices may access matrix datasets. Accordingly, indices in matrix datasets to be computed are transmitted so that distributed matrix computation may be performed.

[0101] When edge devices may access matrix libraries, the main server may transmit a request (query) to perform matrix computation to the edge devices. In this case, the edge devices perform matrix computation according to the request such that distributed computing is performed. The edge devices may infer which data is to be computed by the main server from the received request. When the main server requests matrix computation by simply transmitting indices in a dataset of matrix data used in computation, the edge devices may infer information requested by the main server very easily. The edge devices may find a computation preference of the main server, and private information may leak. Accordingly, when desired matrix computation is requested by encoding index information in a desired matrix dataset for private information protection, the private information of the main server can be protected. Here, a constraint on private information protection is represented by [Equation 9] below.

I(,r;{Q.sub.A.sup.(q)(x.sub.i,j)}.sub.j=1.sup.L, {Q.sub.B.sup.(r)(x.sub.i,j)}.sub.j=1.sup.L, A, B)=0   (9)

[0102] A and B are matrix libraries, and q and r are an A matrix library index and a B matrix library index, respectively. I(x;y) is a function representing the information amount of x that may be inferred when y is known. The above equation means that no information on q or r is obtained even when {Q.sub.A.sup.(q)(x.sub.i,j)}.sub.j=1.sup.L, {Q.sub.B.sup.(r)(x.sub.i,j)}.sub.j=1.sup.L, A, B is known.

[0103] A distributed matrix computation method employing task entanglement-based coding according to the second exemplary embodiment is a method of performing distributed matrix computation using a main server and a plurality of edge devices in a distributed computing environment in which the plurality of edge devices have a first matrix dataset and a second matrix dataset to be computed. The distributed matrix computation method includes a one-hot encoding operation, a first encoding operation, a second encoding operation, a transmission operation, a first matrix encoding operation, a second matrix encoding operation, a matrix computation operation, a computation result transmission operation, a reception operation, and a decoding operation.

[0104] In the one-hot encoding operation, the main server performs one-hot encoding on indices in corresponding datasets of a first matrix and a second matrix to be computed.

[0105] Since the indices are scalar values, the main server performs one-hot encoding on the indices so that the indices may become suitable for use in matrix computation.

[0106] In the first encoding operation, the main server encodes a matrix obtained by performing one-hot encoding on the first matrix into a first encoding matrix for each edge device on the basis of task entanglement-based coding employing a Chebyshev polynomial. In other words, the main server encodes a matrix obtained by performing one-hot encoding on indices in a first matrix dataset of the first matrix to be computed into Q.sub.A.sup.(q)(x.sub.i,j) as shown in [Equation 10] below. In the second encoding operation, the main server encodes a matrix obtained by performing one-hot encoding on the second matrix into a second encoding matrix for each edge device on the basis of task entanglement-based coding employing a Chebyshev polynomial. In other words, the main server encodes a matrix obtained by performing one-hot encoding on indices in a second matrix dataset of the second matrix to be computed into Q.sub.B.sup.(r)(x.sub.i,j) as shown in [Equation 10] below.

[00009]$\begin{array}{cc}{Q}_A^{\left(q\right)}\left(x_{i,j}\right)=\left[\begin{array}{c}{\theta }_A{f}^{c_1}\left(x_{i,j}\right)\\ .Math.\\ {\theta }_A{f}^{c_s+m-1}\left(x_{i,j}\right)\end{array}\right],Q_B^{\left(r\right)}\left(x_{i,j}\right)=\left[\begin{array}{c}{\theta }_B{g}^{c_2}\left(x_{i,j}\right)\\ .Math.\\ {\theta }_B{g}^{c_2+n-1}\left(x_{i,j}\right)\end{array}\right]& \left[\mathrm{Equation}10\right]\end{array}$

[0107] c.sub.1 and c.sub.2 are arbitrary constants which are set according to each situation, and m and n are the number of parts into which the first matrix will be divided and the number of parts into which the second matrix will be divided, respectively. θ.sub.A and θ.sub.B are one-hot encoded matrices. f(x) is a Chebyshev polynomial with an order of L.sub.1, and g(x) is a Chebyshev polynomial with an order of L.sub.2.

[0108] According to the second exemplary embodiment of the present invention, the first encoding operation is an operation of encoding the matrix obtained by performing one-hot encoding on the first matrix into L.sub.2 encoding matrices for each edge device according to a determined number L (L=L.sub.1L.sub.2, L.sub.1 and L.sub.2 are coprime) of tasks on the basis of task entanglement-based coding employing a first Chebyshev polynomial with an order of L.sub.1, and the second encoding operation is an operation of encoding the matrix obtained by performing one-hot encoding on the second matrix into L.sub.1 encoding matrices for each edge device on the basis of task entanglement-based coding employing a second Chebyshev polynomial with an order of L.sub.2. [Equation 11] below is a task entanglement condition of a matrix obtained by encoding a matrix obtained by performing one-hot encoding on indices in matrix libraries of matrices A and B.

Q.sub.A.sup.(q)(x.sub.i,j)=Q.sub.A.sup.(q)(x.sub.i,j+L.sub.2.sub.×(t−1)), Q.sub.B.sup.(r)(x.sub.i,j)=Q.sub.B.sup.(r)(x.sub.i,j+L.sub.2.sub.×(t−1)), i∈[1:W], ∀.sub.S∈[1:L.sub.2], ∀.sub.t∈[1:L.sub.1]  (11)

[0109] W is the number of edge devices.

[0110] The main server selects L evaluation points x.sub.i,j (j∈[1:L]) for each edge device, finds evaluation points of the L.sub.2 matrices obtained by performing one-hot encoding on the first matrix according to the task entanglement condition, and encodes the evaluation points into Q.sub.A.sup.(q)(x.sub.i,j) as shown in [Equation 10]. Also, the main server finds evaluation points of the L.sub.1 matrices obtained by performing one-hot encoding on the second matrix according to the task entanglement condition at the same L evaluation points x.sub.i,j (j∈[1:L]) and encodes the L.sub.1 evaluation points into as shown in [Equation 1].

[0111] According to the second exemplary embodiment of the present invention, the encoding operation may further include an evaluation point selection operation. In the evaluation point selection operation, the main server selects L.sub.2 evaluation points to be used in the first encoding operation and L.sub.1 evaluation points to be used in the second encoding operation for each edge device. The evaluation point selection operation is performed before encoding is performed.

[0112] In the transmission operation, the main server transmits the matrices encoded for each edge device to the corresponding edge device. Accordingly, the main server transmits L.sub.1+L.sub.2 encoded matrices to each edge device. While the related art involves transmitting 2L encoded matrices for L tasks, the number of pieces of transmission data is reduced to L.sub.1+L.sub.2 according to the present invention.

[0113] In the first matrix encoding operation, the edge devices multiply all matrices of the first matrix dataset by the first encoding matrix as shown in [Equation 12] to encode the first matrix. Each edge device does not know which matrix of the first matrix dataset is used in the computation. Like in the first exemplary embodiment, the first matrix is divided into m parts in the second exemplary embodiment. In other words, each of the matrices in the first matrix dataset is divided into m parts, and then encoding is performed.

[00010]$\begin{array}{cc}{\tilde{A}}_{i,j}=p_A\left(x_{i,j}\right)=\underset{k=1}{\overset{m}{.Math.}}\left(\left[\begin{array}{ccc}{A}_{1,k}^T& .Math.& A_{a,k}^T\end{array}\right]\times \left({Q_{A,k}^{\left(q\right)}\left(x_{i,j}\right)}^T.Math.l_{b\times b}\right)\right)& \left[\mathrm{Equation}12\right]\end{array}$

[0114] α is the number of A matrices in the first matrix dataset. A.sub.1,k, . . . , and A.sub.α,k correspond to a k.sup.th partial matrix of the matrices in the first matrix dataset, and Q.sub.A,k.sup.(q)(x.sub.i,j) is a k.sup.th partial matrix of Q.sub.A.sup.(q)(x.sub.i,j).

[0115] In the second matrix encoding operation, the edge devices multiply all matrices of the second matrix dataset by the second encoding matrix as shown in [Equation 13] to encode the second matrix. Likewise, each edge device does not know which matrix of the second matrix dataset is used in the computation. Like in the first exemplary embodiment, the second matrix is divided into n parts in the second exemplary embodiment. In other words, each of the matrices in the second matrix dataset is divided into n parts, and then encoding is performed.

[00011]$\begin{array}{cc}{\tilde{B}}_{i,j}=p_B\left(x_{i,j}\right)=\underset{k=1}{\overset{n}{.Math.}}\left(\left[\begin{array}{ccc}{B}_{1,k}^T& .Math.& B_{\beta ,k}^T\end{array}\right]\times \left({Q_{B,k}^{\left(r\right)}\left(x_{i,j}\right)}^T.Math.l_{\frac{c}{n}\times \frac{c}{n}}\right)\right)& \left[\mathrm{Equation}13\right]\end{array}$

[0116] β is the number of B matrices in the second matrix dataset. B.sub.1,k, . . . , and B.sub.β,k correspond to a k.sup.th partial matrix of all the matrices in the second matrix dataset, and Q.sub.B,k.sup.(r)(x.sub.i,j) is a k.sup.th partial matrix of Q.sub.B.sup.(r)(x.sub.i,j).

[0117] In the matrix computation operation, the edge devices perform a matrix computation task on the encoded first matrix and the encoded second matrix.

[0118] In the computation result transmission operation, each edge device transmits a computation result to the main server.

[0119] In the reception operation, the main server receives the matrix computation task results from the edge devices.

[0120] In the decoding operation, when the number of received matrix computation task results becomes a first recovery threshold, the main server recovers a computation result of the first matrix and the second matrix by decoding the received matrix computation task results. In other words, when as many computation results as the first recovery threshold are received from all the edge devices, the main server immediately performs decoding. Since encoding matrices are generated in the size of 1/m or 1/n from the original matrices, the computation amount of one task performed at an edge device becomes 1/mn of the original computation amount. Accordingly, the main server can recover a final target value when computation values of mn encoded matrices are acquired. Consequently, the first recovery threshold may be calculated as m×n.

[0121] A final computation result may be represented using multiplication of partial matrices as shown in [Equation 4].

[0122] Therefore, the final computation result may be calculated using [Equation 14], and each coefficient matrix may be extracted using repeated divisions and the like of f(x) and g(x). Specifically, A.sub.mB.sub.n may be calculated as a quotient by dividing p.sub.C(x) by

[00012]${f\left(x\right)}^{L_2\left(\frac{n-1}{L_1}+T\right)+m-1}{g\left(x\right)}^{L_1\left(\frac{m-1}{L_2}+T\right)+n-1}.$

In this way, each coefficient matrix may be extracted using repeated divisions.

[00013]$\begin{array}{cc}{p}_C\left(x\right)=p_A\left(x\right)\times p_B\left(x\right)=\underset{i=1}{\overset{m}{.Math.}}\underset{j=1}{\overset{n}{.Math.}}{A}_{q,i}{B}_{r,j}{f\left(x\right)}^{L_2\left(\frac{n-1}{L_1}+T\right)+i-1}{g\left(x\right)}^{L_1\left(\frac{m-1}{L_2}+T\right)+j-1}+\underset{i=1}{\overset{m}{.Math.}}\underset{k=1}{\overset{L_{i}T}{.Math.}}{A}_{q,i}{\zeta }_{B,k}{f\left(x\right)}^{L_2\left(\frac{n-1}{L_2}+T\right)+i-1}{g\left(x\right)}^{k-1}+\underset{j=1}{\overset{n}{.Math.}}\underset{i=1}{\overset{L_{2}T}{.Math.}}{B}_{r,j}{\zeta }_{A,i}{f\left(x\right)}^{l-1}{g\left(x\right)}^{L_2\left(\frac{m-1}{L_2}+T\right)+j-1}+{.Math.}_{k=1}^{L_{1}T}{.Math.}_{i=1}^{L_{2}T}{\zeta }_{A,i}{\zeta }_{B,k}{f\left(x\right)}^{i-1}{g\left(x\right)}^{k-1}& \left[\mathrm{Equation}14\right]\end{array}$$\mathrm{Here},{\zeta }_{A,i}={.Math.}_{k=1}^m(\left[\begin{array}{ccc}{A}_{1,k}^T& .Math.& A_{\alpha ,k}^T\end{array}\right]\times \left(z_{k,i}^T.Math.I_{b\times b}\right)\mathrm{and}{\zeta }_{B,k}={.Math.}_{t=1}^n\left(.Math.\begin{array}{ccc}{B}_{1,i}& .Math.& B_{\beta ,i}\end{array}.Math.\times \left(z_{m+i,k}^T.Math.l_{\frac{c}{n}\times \frac{c}{n}}\right)\right).$

[0123] According to the second exemplary embodiment of the present invention, the main server may encode an encoding matrix into the L.sub.2 encoding matrices by adding a matrix obtained by encoding a random matrix on the basis of task entanglement-based coding employing the first Chebyshev polynomial with an order of L.sub.1 to the encoding matrix in the first encoding operation as shown in [Equation 15] and may encode an encoding matrix into the L.sub.1 encoding matrices by adding a matrix obtained by encoding a random matrix on the basis of task entanglement-based coding employing the second Chebyshev polynomial with an order of L.sub.2, to the encoding matrix in the second encoding operation as shown in [Equation 15]. In other words, the main server may apply a security restriction in the first encoding operation and the second encoding operation.

[00014]$\begin{array}{cc}{Q}_A^{\left(q\right)}\left(x_{i,j}\right)=\left[\begin{array}{c}{.Math.}_{i=1}^{L_2}{Z}_{i,l}{f}^{i-1}\left(x_{i,j}\right)+{\theta }_A{f}^{c_1+L_2}\left(x_{i,j}\right)\\ .Math.\\ {.Math.}_{i=1}^{L_2}{Z}_{m,l}{f}^{i-1}\left(x_{i,j}\right)+{\theta }_A{f}^{c_1+L_2+m-1}\left(x_{i,j}\right)\end{array}\right]& \left[\mathrm{Equation}15\right]\end{array}$$Q_B^{\left(r\right)}\left(x_{i,j}\right)=\left[\begin{array}{c}{.Math.}_{i=1}^{L_1}{Z}_{m+1,l}{g}^{i-1}\left(x_{i,j}\right)+{\theta }_B{g}^{c_2+L_2}\left(x_{i,j}\right)\\ .Math.\\ {.Math.}_{i=1}^{L_1}{Z}_{m+n,l}{g}^{i-1}\left(x_{i,j}\right)+{\theta }_B{f}^{c_2+L_2+n-1}\left(x_{i,j}\right)\end{array}\right]$

[0124] Z is a random matrix.

[0125] As coefficients, the encoding functions employ a matrix Z in which each element has a random value. Since each element value of the matrix Z is extracted from a random distribution, the matrix Z has the largest entropy according to information theory. The encoding functions of [Equation 15] ensure complete data security in distributed computing and distributed machine learning. According to information theory, this can be proved by a zero-knowledge proof proposed by Shannon. This represents that each edge device cannot acquire any information from encoded matrices assigned for a task and may be mathematized as shown in [Equation 7].

[0126] In this case, when the number of received matrix computation task results becomes a second recovery threshold in the decoding operation, the main server decodes the received matrix computation task results to recover a computation result of the first matrix and the second matrix. The first recovery threshold corresponds to the same number of inner products as the original matrix multiplication. However, when a random matrix is added for encoding, the number of inner products which is approximately linearly proportional to the number of assigned tasks becomes the second recovery threshold as shown in [Equation 16], and a final result may be recovered from a computation result corresponding to the second recovery threshold.

R=2L.sub.1L.sub.2T+2(m−1)L.sub.1+2(n−1)L.sub.2+1   (16)

[0127] On the other hand, in the case of an encoding method employing a polynomial according to the related art, when a security restriction is applied, decoding involves as many inner product results as R=(m+EL)(n+EL).

[0128] FIG. 5 is a flowchart illustrating distributed matrix multiplication according to the second exemplary embodiment of the present invention. The main server determines indices in a first matrix dataset and a second matrix dataset of a first matrix and a second matrix to be computed (S2000). Also, the main server determines m and n that are the number of parts into which the first matrix will be divided and the number of parts into which the second matrix will be divided, respectively. The main server performs one-hot encoding on the determined indices (S2010). For L tasks of each edge device, the main server selects L.sub.2 evaluation points to be used in encoding one-hot encoded matrices with respect to the first matrix and L.sub.1 evaluation points to be used in encoding one-hot encoded matrices with respect to the second matrix (S2020). Here, the evaluation points satisfy a task entanglement condition. For each edge device, the main server encodes a matrix obtained by performing one-hot encoding on the first matrix into L.sub.2 encoding matrices to which security is applied on the basis of task entanglement-based coding employing a first Chebyshev polynomial with an order of L.sub.1 as shown in [Equation 13] (S2030) and encodes the second matrix into L.sub.1 encoding matrices to which security is applied on the basis of task entanglement-based coding employing a second Chebyshev polynomial with an order of L.sub.2 as shown in [Equation 13] (S2040). The main server transmits L.sub.1+L.sub.2 matrices encoded for each edge device to the corresponding edge device (S2050). The edge devices encode the first matrix by multiplying all matrices in the first matrix dataset by a first encoding matrix as shown in [Equation 11] (S2060), encode the second matrix by multiplying all matrices in the second matrix dataset by a second encoding matrix as shown in [Equation 12] (S2070), and then perform matrix computation tasks on the encoded first matrix and the encoded second matrix. As soon as each individual computation task is finished, each edge device transmits the computation result to the main server (S2080). The main server receives matrix computation task results from edge devices (S2090). When the number of received matrix computation task results becomes a second recovery threshold, the main server recovers a computation result of the first matrix and the second matrix by decoding the received matrix computation task results (S2100).

[0129] The present invention can increase overall matrix computation speed without the problem of stragglers using a task encoding scheme based on Chebyshev polynomial codes.

[0130] Also, according to the present invention, calculation results of stragglers are not ignored, and partial calculation results of stragglers can be used.

[0131] Further, according to the present invention, it is possible to reduce the amount of information that a main server transmits to edge devices using task entanglement-based coding.

[0132] While the present invention has been described with reference to the embodiments and drawings, the present invention is not limited thereto and should be construed as including various modifications that can be clearly derived from the embodiments by those of ordinary skill in the art. The claims are intended to encompass such modifications.