Patent Description:
Number precision used in a neural network is gradually decreasing in a <NUM>-bit floating-point number (FP32) within a range that allows the accuracy of the neural network to improve an operation speed of an operator and reduce power consumption. Recently, research has been conducted on various ways to accelerate a computing operation by reducing the precision in a neural network while maintaining a certain level of accuracy of the neural network even with bit precision less than FP32. <NPL> describes the TF-Net pipeline to efficiently deploy sub-byte deep neural networks (DNNs) on microcontrollers. Due to the constrained computation resources, it is challenging to execute large DNN models on microcontrollers. Using sub-byte low-precision input activations and weights is a typical method to reduce DNN computation. But on byte-addressable microcontrollers, the sub-byte computation is not well supported. The sub-byte inputs and weights need to be unpacked from bitstreams before computation, which incurs significant computation and energy overhead.

A number of the weights and a number of the activations to be respectively arranged in the input registers may be determined based on a number of bits of each of the weights, a number of bits of each of the activations, and a number of bits of each of the input registers.

The preset bit range may be based on a preset interval between the weights or activations respectively arranged in the input registers, and a bit position of an activation or weight arranged at an uppermost bit in each of the input registers.

The outputting may include setting, as <NUM>, a remaining bit value in the preset bit range in the output register, and shifting the value in the preset bit range to a lower bit position.

In response to all the weights and activations not being available to be arranged in the input registers the arranging may include sequentially arranging corresponding portions of the weights and activations in the input registers, respectively, the performing may include sequentially performing multiplications between the corresponding portions of the weights and activations sequentially arranged in the respective input registers, and accumulating results of the multiplications in the output register, and the outputting may include outputting, as the result of the dot product, a value in a preset bit range from the output register.

The outputting may include outputting the result of the dot product by setting, as <NUM>, a remaining bit value in the preset bit range in the output register, and shifting the value in the preset bit range to a lower bit position.

The minimum operation unit may be one of <NUM> bits, <NUM> bits, <NUM> bits, and <NUM> bits.

A number of the weights and a number of the activation to be respectively arranged in the input registers may be determined based on a number of bits of each of the weights, a number of bits of each of the activations, and a number of bits of each of the input registers.

The processor may be configured to generate the preset interval based on dividing a difference between the number of bits of the first input register and a number of bits of the activations by one less than a depth of the first input register.

<FIG> illustrates an example of a neural network.

Referring to <FIG>, a neural network <NUM> includes a plurality of layers. The neural network <NUM> includes an input layer <NUM>, a plurality of hidden layers <NUM> and <NUM>, and an output layer <NUM>. The neural network <NUM> may be used to perform a data inference. The data inference may include, for example, pattern recognition (e.g., object recognition, facial identification, etc.), sequence recognition (e.g., speech, gesture, and written text recognition, machine translation, machine interpretation, etc.), control (e.g., vehicle control, process control, etc.), recommendation services, decision making, medical diagnoses, financial applications, data mining, and the like.

Each layer may include a plurality of nodes each referred to as an artificial neuron. Each node may indicate an operation or computation unit having at least one input and output, and the nodes may be connected to one another.

The input layer <NUM> may include one or more nodes to which data is directly input without being through a connection to another node. The output layer <NUM> may include one or more output nodes that are not connected to another node. The hidden layers <NUM> and <NUM> may be the remaining layers of the neural network <NUM> from which the input layer <NUM> and the output layer <NUM> are excluded, and include nodes corresponding to an input node or output node in a relationship with another node. The neural network <NUM> is illustrated merely as an example in <FIG> for the convenience of description, and thus the scope of examples is not limited to the illustrated structure of the neural network <NUM> and a structure of a neural network used may vary according to examples. According to examples, the number of hidden layers included in the neural network <NUM>, the number of nodes included in each layer, and/or a connection between the nodes may vary. A neural network including a plurality of hidden layers, such as, for example, the neural network <NUM>, may also be referred to as a deep neural network (DNN).

The neural network <NUM> may include for example, any one or any combination of a convolutional neural network (CNN), and a recurrent neural network (RNN), a perceptron, a multilayer perceptron, a feedforward (FF) network, a radial basis function (RBF) network, a deep FF (DFF) network, a long short-term memory (LSTM), a gated recurrent unit (GRU), an autoencoder (AE), a variational AE (VAE), a denoising AE (DAE), a sparse AE (SAE), a Markov chain (MC), a Hopfield network (HN), a Boltzmann machine (BM), a restricted BM (RBM), a deep belief network (DBN), a deep convolutional network (DCN), a deconvolutional network (DN), a deep convolutional inverse graphics network (DCIGN), a generative adversarial network (GAN), a liquid state machine (LSM), an extreme learning machine (ELM), an echo state network (ESN), a deep residual network (DRN), a differentiable neural computer (DNC), a neural turning machine (NTM), a capsule network (CN), a Kohonen network (KN), and an attention network (AN). In an example, at least a portion of the plurality of layers in the neural network <NUM> may correspond to the CNN, and another portion thereof may correspond to the FCN. In this case, the CNN may be referred to as convolutional layers, and the FCN may be referred to as fully connected layers.

A weight may be set for a connection between nodes. For example, a weight may be set for a connection between a node included in the input layer <NUM> and another node included in the hidden layer <NUM>. The weight may be adjusted or changed. The weight may determine the influence of a related data value on a final result as it increases, decreases, or maintains the data value. The weight may correspond to a parameter of the neural network <NUM>.

To each node included in one layer, weighted values of nodes included in a previous layer may be input. A weighted value may refer to a value obtained as a value of a node included in the previous layer is multiplied by a weight. A process in which weighted data is input from a layer to a subsequent layer of the layer may be referred to as propagation. For example, a value y to be propagated, to the subsequent layer, from a node to which weighted data is propagated from the nodes included in the previous layer may be determined as represented by Equation <NUM>.

In Equation <NUM>, ai denotes a value of an ith node included in a previous layer and is also referred to as an activation. wi denotes a weight that is set for a connection to the ith node included in the previous layer. b denotes a bias, and f denotes an activation function. The activation function f may correspond to sigmoid, hyperbolic tangent (tanh), or a rectified linear unit (ReLU), but not be limited thereto.

In Equation <NUM>, <MAT> is represented as a dot product operation w · a between a weight vector (w = [wo, w<NUM>,. , wn-<NUM>]) and an activation vector (a = [a<NUM>, a<NUM>,. , an-<NUM>]).

A weight and activation may be represented by a small number of bits to improve an operation speed of the neural network <NUM> and to reduce power consumption. In general, a weight and activation may be represented in FP32 which is a floating format that represents data by <NUM> bits, or in BF16 which is a brain floating-point format that represents data by <NUM> bits. These formats may facilitate the performance of an operation by an operator configured to perform neural network-based operations because the formats represent data by a multiple of a minimum operation unit (e.g., <NUM>, <NUM>, <NUM>, and <NUM> bits), and increase the accuracy in inferences because the formats accurately represent data using a relatively great number of bits. However, using these formats, a great amount of time and resources (e.g., power consumption, memory, etc.) may be used to train a neural network or perform inferences using the neural network, and an operation may not be readily performed in an environment such as a mobile device, which has limited computational limited resources.

In an example, inferences or learning (or training) may be performed by representing weights and activations by a smaller number of bits (e.g., <NUM>-<NUM> bits) than a minimum operation unit of an operator within a range that allows the accuracy in inferences of a neural network. In addition, a dot product of vectors represented by a smaller number of bits than the minimum operation unit may be performed more rapidly with fewer resources by accelerating, by a typical operator without a separate operator, a dot product between a weight vector and an activation vector that are represented by a smaller number of bits than the minimum operation unit, for example, a sum of products (of multiplications) between corresponding weights and activations. Examples will be described in detail hereinafter.

<FIG> illustrates an example of sub-byte parallelism.

Reference numerals <NUM>, <NUM>, and <NUM> depict instances of how an operator (e.g., multiplier) with a minimum operation unit of <NUM> bits multiplies values stored in <NUM>-bit input registers (e.g., weight register and activation register) will be described hereinafter with reference to <FIG>. Although weights w<NUM>, w<NUM>, w<NUM>, and w<NUM> and activations a<NUM>, a<NUM>, a<NUM>, and as are illustrated in <FIG> as being represented by <NUM> bits which is a smaller number of bits than the minimum operation unit, examples of the bit number are not limited thereto.

The first case <NUM> is an example where only one weight w<NUM> and activation a<NUM> are input to the input registers, and zero (<NUM>) is input to remaining bits. When the operator multiplies values stored in the input registers, woao is obtained as an operation result. Most of the bits in the input registers are filled with zeros (<NUM>) and not used for the operation, and thus resources may be wasted, and the operation may not be accelerated to be greater than the preset minimum operation unit in the operator.

The second case <NUM> is an example where a plurality of weights w<NUM> through w<NUM> and a plurality of activations a<NUM> through a<NUM> are input in the same order to the input registers, respectively. For example, the weight w<NUM> is stored at first and second lower bits of a corresponding input register, the weight w<NUM> is stored at third and fourth lower bits of the input register, the weight w<NUM> is stored at fifth and sixth lower bits of the input register, and the weight w<NUM> is stored at seventh and eighth lower bits of the input register. Similarly, the activations a<NUM> through a<NUM> are stored at respective bits of a corresponding input register. When the operator multiplies values stored in the input registers, an operation result represented as <NUM>n may be obtained as illustrated in a right portion of the second case <NUM> of <FIG>. For example, as illustrated, a coefficient <NUM> of <NUM><NUM> in the operation result may be represented by a sum of products (of multiplications) between the weights and the activations. However, based on that the multiplications in the coefficient <NUM> of <NUM><NUM> are performed on weights and activations that do not correspond to each other, the order in which the weights and activation are arranged in the input registers may change as illustrated in the third case <NUM>.

The third case <NUM> is an example where the order of arranging the weights w<NUM> through w<NUM> in a weight register and the order of arranging the activations a<NUM> through a<NUM> in an activation register differ from each other. For example, the weights w<NUM> through w<NUM> are arranged in order from an upper bit to a lower bit in the weight register, whereas the activations a<NUM> through a<NUM> are arranged in order from a lower bit to an upper bit in the activation register. According to other examples, the weights w<NUM> through w<NUM> may be arranged from the lower bit to the upper bit in the weight register, and the activations a<NUM> through a<NUM> may be arranged from the upper bit to the lower bit in the activation register. Such an operation of varying an arrangement order in an input register may be preprocessed after learning of a neural network, and thus, the overhead may be reduced.

When the operator multiplies the values stored in the input registers, a sum of products (of multiplications) between corresponding weights and activations may be obtained as a coefficient <NUM> of <NUM><NUM> in the operation result. That is, through a scalar multiplication between the values stored in the input registers, a result of a dot product operation which is a vector-vector multiplication may be derived. A sum of products (of multiplications) between weights and activations that are represented by a smaller number of bits than a basic operation unit may be obtained by one-time operation of the operator, and such an operation may thus be referred to as sub-byte parallelism. Such an operation may facilitate the acceleration of a dot product operation between vectors having a smaller number of bits than a minimum operation unit, using a typical, existing operator, without a need for special hardware for an operation with a small number of bits.

The result of the dot product represented by the coefficient <NUM> of <NUM><NUM> may be stored at seventh and eighth lower bits of an output register. When the result of the dot product is greater than <NUM><NUM>, a portion of the result of the dot product may flow to a coefficient of <NUM><NUM>. Thus, preventing such an overflow will be described in detail hereinafter with reference to <FIG>.

<FIG> illustrate an example of first packing-based sub-byte parallelism, which does not fall within the scope of the claims.

As shown in <FIG>, reference numerals <NUM>, <NUM>, and <NUM> illustrate examples of how activations are arranged in a <NUM>-bit register based on first packing. In the example of <FIG>, activations are represented by <NUM> bits that are less than a minimum operation unit of an operator, and the number of activations to be included in one register is represented by depth. For example, in a case in which the number of activations included in one register is <NUM>, it may be represented by <NUM>-depth or depth-<NUM>. The activations may be arranged in the register with the activations being separated from each other at an interval, starting from a lower bit, based on first packing. In an example, the interval may be preset. In the example of <FIG>, empty spaces between the activations may indicate that zeros (<NUM>) are filled therein. Although the following description provided with reference to <FIG> is based on activations for the convenience of description, the following description may also be applicable to weights.

The first case <NUM> is where two activations a<NUM> and a<NUM> are arranged in the <NUM>-bit register. The activation a<NUM> is stored at first through third lower bits of the register, and the activation a<NUM> is stored at ninth through 11th lower bits. The activations a<NUM> and a<NUM> are arranged with them being separated from each other at an interval of <NUM> bits.

The second case <NUM> is where three activations a<NUM>, a<NUM>, and a<NUM> are arranged in the <NUM>-bit register. The activation a<NUM> is stored at first through third lower bits of the register, the activation a<NUM> is stored at sixth through eighth lower bits of the register, and the activation a<NUM> is stored at 11th through 13th lower bits of the register. The activations a<NUM>, a<NUM>, and a<NUM> are arranged with them being separated from each other at an interval of <NUM> bits.

The third case <NUM> is where four activations a<NUM>, a<NUM>, a<NUM>, and a<NUM> are arranged in the <NUM>-bit register. The activation a<NUM> is stored at first through third lower bits of the register, the activation a<NUM> is stored at fifth through seventh lower bits of the register, the activation a<NUM> is stored at ninth through 11th lower bits of the register, and the activation a<NUM> is stored at 13th through 15th lower bits of the register. The activations a<NUM>, a<NUM>, a<NUM>, and a<NUM> are arranged with them being separated from each other at an interval of <NUM> bits.

In an example, by generalizing a preset interval between activations based on first packing, in a case in which activations are arranged in an r-bit register with d-depth, the activations may be arranged in the register at an interval of [r/d] bits.

Referring to <FIG>, weights and activations may be arranged in <NUM>-bit registers, respectively, with <NUM>-depth, and then an operation may be performed accordingly. In the example of <FIG>, each of weights w<NUM>, w<NUM>, and w<NUM> is represented by <NUM> bits smaller than a basic operation unit (e.g., <NUM> bits), and each of activations a<NUM>, a<NUM>, and a<NUM> is represented by <NUM> bit smaller than the basic operation unit. In this example, the weights w<NUM>, w<NUM>, and w<NUM> and the activations a<NUM>, a<NUM>, and a<NUM> are arranged in respective registers <NUM> and <NUM> at an interval of <NUM> bits based on first packing.

A <NUM>-bit operator may perform a multiplication (MUL as illustrated) <NUM> between values stored in the registers <NUM> and <NUM> and store a result therefrom in an output register. The operator may have the same bit number as the registers <NUM> and <NUM>. A value stored in 11th to 15th lower bits in the output register may correspond to a result of a dot product between a weight vector (w = [wo, w<NUM>, w<NUM>]) and an activation vector (a = [a<NUM>, a<NUM>, a<NUM>]). To remove a value of remaining bits, except for the 11th to 15th lower bits, from the output register, an AND operation <NUM> may be performed between values stored in the output register and a <NUM>-bit filter in which the value of the 11th to 15th lower bits is <NUM> and the value of the remaining bits is <NUM> may be performed. In an example, a logical shift right (LSR) operation <NUM> may be performed on the value of the 11th to 15th lower bits remained in the output register to shift it such that the result of the dot product is stored at first to fifth bits of the output register.

In the example of <FIG>, the result of the dot product may be stored in the 11th to 15th bits of the output register. However, when the result of the dot product is greater than a value of <NUM><NUM>-<NUM>, an overflow of a portion of the result of the dot product to a 16th bit of the output register may occur. To prevent such an overflow, a maximum value of the result of the dot product may be less than a maximum value that may be represented by bits allocated to store the result of the dot product, which may be represented by Equation <NUM>.

In Equation <NUM> above, d denotes depth. x denotes the number of bits of a weight, and y denotes the number of bits of an activation. (<NUM>x - <NUM>) · (<NUM>y - <NUM>) denotes a maximum value of a product (of a multiplication) between the weight and the activation. In the case of d-depth, the multiplication between the weight and the activation may be performed d times, and results therefrom may be added. Thus, d · (<NUM>x - <NUM>) · (<NUM>y - <NUM>) may denote the maximum value of the result of the dot product, [r/d] denotes an interval between weights or an interval between activations. The result of the dot product may be extracted from bits corresponding to the corresponding size from the output register, and thus <NUM>[r/d] may denote a maximum value that may be represented by bits allocated to store the result of the dot product.

According to first packing, the interval between the weights and the interval between the activations may be determined to be [r/d], and sub-byte parallelism described above may be performed without an overflow when Equation <NUM> above is satisfied. The result of the dot product may be stored in a preset bit range in the output register. The preset bit range may indicate a range from a jth lower bit to a j+(k-<NUM>)th lower bit. The jth lower bit may indicate a start bit of an uppermost bit group among d bit groups that store therein d weights or activations in an input register, and k denotes a preset interval for the weights or activations.

Referring to <FIG>, there is a maximum depth based on the number of bits of weights and activations to be arranged in <NUM>-bit registers, respectively. In the example of <FIG>, in A1, A2,. , A7 on an x axis, A indicates an activation and an accompanied number indicates the number of bits of the activation. Similarly, in W1, W2,. , W7 on a y axis, W indicates a weight and an accompanied number indicates the number of bits of the weight. The numbers illustrated in a table indicate maximum depths. For example, the <NUM>-bit registers may include therein the weights and activation with maximally <NUM>-depth under the condition that there is not an overflow at W7A1 <NUM>. Equation <NUM> may not be satisfied at W4A4 <NUM> of the <NUM>-bit registers, and thus sub-byte parallelism based on first packing may not be available.

Hereinafter, second packing that may prevent an overflow more effectively than first packing under the same depth condition will be described in detail with reference to <FIG>.

<FIG> illustrate an example of second packing-based sub-byte parallelism.

Reference numerals <NUM>, <NUM>, and <NUM> illustrate example of activations being arranged in a <NUM>-bit register based on second packing that will be described with reference to <FIG>. In the example of <FIG>, activations are represented by <NUM> bits which is smaller than a minimum operation unit (e.g., <NUM> bits) of an operator, and the number of activations included in one register is represented by depth. According to second packing, the activations are arranged in the register at the same interval such that first and last ones among the activations are maximally separated from each other. In the example of <FIG>, empty spaces between the activations indicate that <NUM> is filled therein. Although the example of <FIG> is described based on activations for the convenience of description, the description of the example may also be applicable to weights.

The first case <NUM> is where two activations a<NUM> and a<NUM> are arranged in the <NUM>-bit register. The activation a<NUM> is stored at first to third lower bits of the register, and the activation a<NUM> is stored at 14th to 16th lower bits of the register. The activations a<NUM> and a<NUM> are arranged such that they are separated from each other at an interval of <NUM> bits.

The second case <NUM> is where three activations a<NUM>, a<NUM>, and a<NUM> are arranged in the <NUM>-bit register. The activation a<NUM> is stored at second to fourth lower bits of the register, the activation a<NUM> is stored at lower eighth to tenth bits of the register, and the activation a<NUM> is stored at 14th to 16th lower bits of the register. The activations a<NUM>, a<NUM>, and a<NUM> are arranged such that they are separated from each other at an interval of <NUM> bits.

The third case <NUM> is where four activations a<NUM>, a<NUM>, a<NUM>, and a<NUM> are arranged in the <NUM>-bit register. The activation a<NUM> is stored at second to fourth lower bits of the register, the activation a<NUM> is stored at sixth to eighth lower bits of the register, the activation a<NUM> is stored at 10th to 12th bits lower of the register, and the activation a<NUM> is stored at 14th to 16th lower bits of the register. The activations a<NUM>, a<NUM>, a<NUM>, and a<NUM> are arranged such that they are separated from each other at an interval of <NUM> bits.

By arranging the last activation among the activations such that it is stored at an uppermost bit of the register according to second packing, a greater interval may be achieved under the same depth condition compared to first packing. Thus, it is possible to effectively prevent an occurrence of an overflow. By generalizing a preset interval of activations based on second packing, in a case in which activations having y bits are arranged in an r-bit register with d-depth, the activations may be arranged in the register at an interval of <MAT>.

Referring to <FIG>, weights and activations may be arranged in <NUM>-bit registers, respectively, with <NUM>-depth, and then an operation may be performed accordingly. In the example of <FIG>, each of weights w<NUM>, w<NUM>, and w<NUM> and activations a<NUM>, a<NUM>, and a<NUM> is represented by <NUM> bits which is smaller than a basic operation unit (e.g., <NUM> bits) of an operator. According to second packing, the weights w<NUM>, w<NUM>, and w<NUM> and the activations a<NUM>, a<NUM>, and a<NUM> may be arranged in respective registers <NUM> and <NUM> at an interval of <NUM> bits.

The operator performs a multiplication <NUM> between values stored in the registers <NUM> and <NUM> and store results therefrom in a <NUM>-bit output register. A value stored at 15th to 21st lower bits of the output register may correspond to a result of a dot product between a weight vector (w = [w<NUM>, w<NUM>, w<NUM>]) and an activation vector (a = [a<NUM>, a<NUM>, a<NUM>]). The result of the dot product may be stored at the 15th to 21st lower bits, and thus the output register may have a greater number of bits (e.g., <NUM> bits) than the input registers <NUM> and <NUM>.

To remove a value of remaining bits, except for the 15th to 21st lower bits, from the output register, an AND operation <NUM> may be performed between values stored in the output register and a <NUM>-bit filter in which the value of the 15th to 21st lower bits is <NUM> and the value of the remaining bits is <NUM>. In an example, an LSR operation <NUM> may be performed on the value of the 15th to 21st lower bits remained in the output register to shift it such that the result of the dot product is stored at first to seventh bits of the output register.

In the example of <FIG>, the result of the dot product may be stored at the 15th to 21st lower bits in the output register. However, in a case in which the result of the dot product is greater than <NUM><NUM>-<NUM>, an overflow of a portion of the result of the dot product may flow to a 12th bit of the output register. To prevent such an overflow, a maximum value of the result of the dot product may need to be less than a maximum value that may be represented by bits allocated to store the result of the dot product, which may be represented by Equation <NUM>.

In Equation <NUM> above, d · (<NUM>x - <NUM>) · (<NUM>y - <NUM>) denotes a maximum value of a dot product. <MAT> denotes a maximum value that may be represented by bits allocated to store a result of the dot product.

According to second packing, sub-byte parallelism described above may be performed without an overflow, when Equation <NUM> above is satisfied. The result of the dot product is stored in a preset bit range in the output register. The preset bit range may indicate a range from a jth lower bit to a j+(k-<NUM>)th lower bit. The jth lower bit may indicate a start bit of an uppermost bit group among d bit groups that store therein d weights or activations in an input register, and k denotes a preset interval for the weights or activations.

Referring to <FIG>, there is a maximum depth based on the number of bits of weights and activations to be arranged in <NUM>-bit registers, respectively. In the example of <FIG>, in A1, A2,. , A7 on an x axis, A indicates an activation and an accompanied number indicates the number of bits of the activation. Similarly, in W1, W2,. , W7 on a y axis, W indicates a weight and an accompanied number indicates the number of bits of the weight. The numbers illustrated in a table indicate maximum depths. For example, the <NUM>-bit registers may include therein the weights and activation with <NUM>-depth, maximally, under the condition that there is not an overflow at W3A2 <NUM>. Compared to the example of <FIG> in which maximal <NUM>-depth is available in the case of W3A2 according to first packing, it is possible to effectively increase the maximum depth through second packing. In addition, even at W4A4 <NUM> at which sub-byte parallelism is not available through first packing, sub-byte parallelism may be available with maximal <NUM>-depth through second packing.

<FIG> and <FIG> illustrate an example of local accumulation-based sub-byte parallelism.

<FIG> illustrates an example of an iteration of sub-byte parallelism. For the convenience of description, it is assumed in the example of <FIG> that sub-byte parallelism described above with reference to <FIG> is performed. In a case in which a vector dimension n of a weight vector (w = [w<NUM>, w<NUM>,. , wn-<NUM>]) and an activation vector (a = [a<NUM>, a<NUM>,. , an-<NUM>]) which are targets for a dot product is <NUM>, one-time processing of the sub-byte parallelism may not be sufficient to obtain a result of the dot product, and thus the sub-byte parallelism may need to be performed three times. Even in such a case, a condition that a sum of results of the sub-byte parallelism performed three times is not greater than <NUM><NUM>-<NUM> may need to be satisfied in order to prevent an overflow.

According to an algorithm illustrated in <FIG>, weights w<NUM>, w<NUM>, and w<NUM> and activations a<NUM>, a<NUM>, and a<NUM> may be arranged in input registers, respectively. The multiplication <NUM>, the AND operation <NUM>, and the LSR operation <NUM>, which are described above with reference to <FIG>, may be performed. In an example, weights w<NUM>, w<NUM>, and w<NUM> and activations a<NUM>, a<NUM>, and a<NUM> may be arranged in the input registers, respectively. The multiplication <NUM>, the AND operation <NUM>, and the LSR operation <NUM>, which are described above with reference to <FIG>, may then be performed. Results therefrom may be added to results obtained by performing the sub-byte parallelism for the first time and then stored. In an example, weights w<NUM>, w<NUM>, and w<NUM> and activations a<NUM>, a<NUM>, and as may be arranged in the input registers, respectively. The multiplication <NUM>, the AND operation <NUM>, and the LSR operation <NUM>, which are described above with reference to <FIG>, may then be performed. Results therefrom may be added to results obtained by performing the sub-byte parallelism for the first time and the second time and then stored. In the algorithm of <FIG>, m, which denotes a total length of an array on which a dot product is performed, may be the same as the number of vector dimensions and represented as an m-depth dot product, a depth-m dot product, or an m-dimensional dot product. In addition, mask denotes an AND operation, and shift denotes an LSR operation.

That is, according to the algorithm of <FIG>, for the three-time processing of the sub-byte parallelism, <NUM> instructions represented as (MUL-AND-LSR-ADD)*<NUM> may be executed. In addition, since fused multiply-add (FMA), which is an instruction combined with MUL-ADD cannot be applied, many instruction cycles may be needed.

<FIG> illustrates an example of an iteration of sub-byte parallelism based on local accumulation. An instruction order described above with reference to <FIG> may be changed to effectively reduce an instruction cycle. For example, rather than performing an AND operation, an LSR operation, and ADD operation, each time sub-byte parallelism is performed one time, it may be possible to effectively reduce the instruction cycle by first adding results obtained by performing the sub-byte parallelism several times and then performing once each of the AND operation, the LSR operation, and the ADD operation. When an algorithm of the example of <FIG> is applied to the assumption of the example of <FIG>, ((MUL-ADD)*<NUM>)-AND-LSR-ADD instructions may be executed. Since (MUL-ADD) may be replaced with FMA, the three-time processing of the sub-byte parallelism that is desired to be performed in the example of <FIG> may be completed only with a total of six instructions corresponding to (FMA*<NUM>)-AND-LSR-ADD. By changing the instruction order as described above when performing the same operations, it is possible to efficiently reduce the instruction cycle.

In the algorithm of the example of <FIG>, iter denotes a parameter indicating the number of times a local accumulation is performed. In addition, an inner loop "for j = i * iter to (i + <NUM>) * iter" indicates that the local accumulation is performed as many times as iter and, for this, the for statement may be written in duplicate.

For the convenience of description, it is assumed that a <NUM>-depth dot product is performed based on a total array length of m (m = <NUM>), <NUM>-depth sub-byte parallelism (d = <NUM>), and local accumulation (iter = <NUM>). After the local accumulation is performed iteratively (iter = <NUM>) in the inner loop, a partial result of the dot product may be extracted through mask (that is, AND operation) and shift (that is, LSR operation). Since d-depth sub-byte parallelism is applied, the partial dot product result of iter*d = <NUM>-depth may be extracted. To obtain the final <NUM>-depth dot product result, such a process of extracting the partial dot product result may need to be repeated <NUM> times, which may be represented by an outer loop for i = <NUM> to <MAT>.

<FIG> illustrates an example of a maximum depth and local with respect to the number of bits of weights and activations.

In the example of <FIG>, an x axis indicates the number of bits of activations arranged in a <NUM>-bit register, and a y axis indicates the number of bits of weights arranged in a <NUM>-bit register. The inside of the table may indicate which packing is better from among the first packing and the second packing described above based on the number of bits of each of weights and activations, and a maximum depth and a maximum local in each case may be indicated. The maximum local may indicate the number of times of sub-byte parallelism to which the method described above with reference to <FIG> is applied. For example, the <NUM>-bit registers may include weights and activations with maximal <NUM>-depth based on the first packing under a condition that an overflow does not occur at W5A1 <NUM>, and the sub-byte parallelism may be performed four times iteratively. In addition, the <NUM>-bit registers may include weights and activations with maximal <NUM>-depth based on the second packing under a condition that an overflow does not occur at W5A2 <NUM>, and the sub-byte parallelism may be performed eight times iteratively.

<FIG> illustrates an example of a method of operating a processor. In addition to the description of <FIG> below, the descriptions of <FIG> are also applicable to <FIG>, and are incorporated herein by reference. Thus, the above description may not be repeated here.

An example of how a processor obtains a dot product between vectors using a typical multiplier will be described hereinafter with reference to <FIG>. The processor includes an input register, an operator (e.g., multiplier), and an output register. Although to be described hereinafter, the processor may be embodied as a host processor or an accelerator included in an electronic device.

Referring to <FIG>, in operation <NUM>, the processor arranges, in respective input registers, weights and activations having a smaller number of bits than a minimum operation unit of the operator. The processor arranges the weights in a first input register in a first order, and arrange the activations in a second input register in a second order which is a reverse order of the first order. The number of weights and activations to be arranged in the input registers, respectively, may be determined based on the number of bits of each of the weights, the number of bits of each of the activations, and the number of bits of each of the input registers.

The processor arranges the weights and activations in the input registers at a preset interval. The preset interval may be determined based on the number of bits of each of the input registers and the respective numbers of the weights and activations to be arranged respectively in the input registers.

The processor arranges the weights and activations such that first and last ones of the weights and activations separated from each other at the same interval are maximally separated from each other. The output register has have a greater number of bits than the input registers.

In operation <NUM>, the processor performs a multiplication between values stored in the input registers. The processor may perform a general multiplication between the values stored in the input registers.

In operation <NUM>, the processor outputs, from the output register in which a result of the multiplication is stored, a value in a preset bit range as a result of a dot product between a first vector including the weights and a second vector including the activations. The preset bit range may be determined based on the preset interval between the weights and the activations arranged respectively in the input registers, and a bit position of an activation or weight arranged at an uppermost bit in each of the input registers. The processor may set a remaining bit value in the preset bit range as <NUM>, and shift the value in the preset bit range to a lower bit position.

For example, when not all the weights and activations are arranged respectively in the input registers, the processor may sequentially arrange corresponding portions of the weights and activations in the input registers, respectively. The processor may sequentially perform multiplications between the corresponding portions of the weights and activations sequentially arranged in the respective input registers. The processor may then output a value in a preset bit range as the result of the dot product from the output register in which results of the sequentially performed multiplications are accumulated.

The examples described above may be applied without limitations, if a dot product between vectors is needed to an operation performed in a neural network and even to other application in addition to a neural network-based operation. In such a case, the names of a weight vector and an activation vector described herein may change. In addition, depth may vary depending on the number of bits of weights and/or activations when packing the weights and activations in registers, despite the same number of bits of the registers. Thus, an operation speed of sub-byte parallelism may change depending on the number of bits of weights and/or activations.

<FIG> illustrates an example of a configuration of an electronic device.

Referring to <FIG>, an electronic device <NUM> includes a host processor <NUM>, an off-chip memory <NUM>, a memory controller <NUM>, and an accelerator <NUM>. The host processor <NUM>, the off-chip memory <NUM>, the memory controller <NUM>, and the accelerator <NUM> may communicate with one another through a bus, a network on a chip (NoC), a peripheral component interconnect express (PCIe), and the like.

The host processor <NUM> may be a device configured to control respective operations of the components included in the electronic device <NUM> and include a central processing unit (CPU), a graphics processing unit (GPU), or any of the other devices described below, with reference to the accelerator <NUM>, for example. The host processor <NUM> may control operations performed in the electronic device <NUM>. The host processor <NUM> may receive one or more requests for processing a neural network in the accelerator <NUM>, and generate an instruction that is executable in the accelerator <NUM> in response to the received requests and transfer the generated instruction to the accelerator <NUM>.

The off-chip memory <NUM> may be a memory disposed outside the accelerator <NUM>, for example, a dynamic random-access memory (DRAM) ), a static RAM (SRAM), a thyristor RAM (T-RAM), a zero-capacitor RAM (Z-RAM), a twin-transistor RAM (TTRAM), or a high bandwidth memory (HBM) may be used as a main memory of the electronic device <NUM>. The off-chip memory <NUM> may store inference target data and/or parameters of the neural network to be executed in the accelerator <NUM>, and data stored in the off-chip memory <NUM> may be transferred to the accelerator <NUM> for an inference. In an example, the off-chip memory <NUM> may also be used in a case in which an on-chip memory inside the accelerator <NUM> is not sufficient to execute the neural network in the accelerator <NUM>.

The accelerator <NUM> may be an artificial intelligence (Al) accelerator configured to execute the neural network according to the instruction of the host processor <NUM> and infer data to be input. In an example, the accelerator <NUM> may be a separate processor distinguished from the host processor <NUM>. The accelerator <NUM> may be a microprocessor, single processor, independent processors, parallel processors, single-instruction single-data (SISD) multiprocessing, single-instruction multiple-data (SIMD) multiprocessing, multiple-instruction single-data (MISD) multiprocessing, multiple-instruction multiple-data (MIMD) multiprocessing, a microcomputer, a processor core, a multi-core processor, a multiprocessor, a central processing unit (CPU), neural processing unit (NPU), a graphics processing unit (GPU), a tensor processing unit (TPU), a digital signal processor (DSP), a controller and an arithmetic logic unit (ALU), a field-programmable gate array (FPGA), an application-specific integrated circuit (ASIC), a programmable logic unit (PLU), or an application processor (AP).

The accelerator <NUM> may process a task that is more effectively processed by a separate dedicated processor, for example, the accelerator <NUM>, than by the host processor <NUM> used for general purposes based on the characteristics of operations of the neural network. Here, one or more processing elements (PEs) included in the accelerator <NUM>, and the on-chip memory may be used. The on-chip memory may be a device including a global shared buffer and a local buffer that are included in the accelerator <NUM> and be distinguished from the off-chip memory <NUM> disposed outside the accelerator <NUM>. The on-chip memory may include, for example, a scratchpad memory accessible through an address space, a static random-access memory (SRAM), or the like.

The processor described herein may be embodied as the host processor <NUM> or the accelerator <NUM>. Further description of the processor is provided below.

<FIG> and <FIG> illustrate examples of an electronic device.

Referring to <FIG>, an electronic device may be embodied as a server <NUM>.

The server <NUM> may be a separate device distinguished from a user terminal controlled by a user and may communicate with the user terminal through a wired and/or wireless network. The server <NUM> may receive requests that are simultaneously transmitted from a plurality of users through their terminals. A memory <NUM> included in the server <NUM> may include weights and activations of a requested neural network. The weights and activations may have the number of bits smaller than a minimum operation unit of an operator included in a processor <NUM>. The processor <NUM> may arrange the weights and activations in respective input registers, perform a multiplication between values stored in the input registers, and then output, from an output register in which a result of the multiplication is stored, a value in a preset bit range as a result of a dot product between a first vector including the weights and a second vector including the activations. Inference results obtained through such operations described above may be returned to corresponding user terminals. The user terminals may include, for example, various computing devices such as, smartphones, tablets, laptops, personal computers (PCs), , various wearable devices such as, smartwatches, smart glasses, various home appliances such as, smart speakers, smart televisions (TVs), smart refrigerators, and others such as, smart vehicles, smart kiosks, Internet of things (IoT) devices, drones, and robots.

Referring to <FIG>, an electronic device may be embodied as a user terminal <NUM>. Although the user terminal <NUM> is illustrated as a smartphone in <FIG> for the convenience of description, other devices that are controlled by a user may be applicable without limitations. The user terminal <NUM> may obtain a request from a user. A memory <NUM> included in the user terminal <NUM> may include weights and activations of a requested neural network. A processor <NUM> may arrange the weights and activations in respective input registers, perform a multiplication between values stored in the input registers, and then output, from an output register in which a result of the multiplication is stored, a value in a preset bit range as a result of a dot product between vectors. An inference result obtained through such operations described above may be provided to the user, or be used for the user terminal <NUM> to perform a subsequent operation.

The server <NUM> and the user terminal <NUM> embodied as the electronic device as described above with reference to <FIG> and <FIG>, respectively, may perform the operations described herein, and thus a more detailed and repeated description thereof will be omitted here for brevity. The electronic device described herein may also be referred to as an accelerator system including a host processor and an accelerator.

The electronic device, and other devices, apparatuses, units, modules, and components described herein with respect to <FIG> are implemented by hardware components. Examples of hardware components that may be used to perform the operations described in this application where appropriate include controllers, sensors, generators, drivers, memories, comparators, arithmetic logic units, adders, subtractors, multipliers, dividers, integrators, and any other electronic components configured to perform the operations described in this application. In other examples, one or more of the hardware components that perform the operations described in this application are implemented by computing hardware, for example, by one or more processors or computers. A processor or computer may be implemented by one or more processing elements, such as an array of logic gates, a controller and an arithmetic logic unit, a digital signal processor, a microcomputer, a programmable logic controller, a field-programmable gate array, a programmable logic array, a microprocessor, or any other device or combination of devices that is configured to respond to and execute instructions in a defined manner to achieve a desired result. In one example, a processor or computer includes, or is connected to, one or more memories storing instructions or software that are executed by the processor or computer. Hardware components implemented by a processor or computer may execute instructions or software, such as an operating system (OS) and one or more software applications that run on the OS, to perform the operations described in this application. The hardware components may also access, manipulate, process, create, and store data in response to execution of the instructions or software. For simplicity, the singular term "processor" or "computer" may be used in the description of the examples described in this application, but in other examples multiple processors or computers may be used, or a processor or computer may include multiple processing elements, or multiple types of processing elements, or both. For example, a single hardware component or two or more hardware components may be implemented by a single processor, or two or more processors, or a processor and a controller. One or more hardware components may be implemented by one or more processors, or a processor and a controller, and one or more other hardware components may be implemented by one or more other processors, or another processor and another controller. One or more processors, or a processor and a controller, may implement a single hardware component, or two or more hardware components. A hardware component may have any one or more of different processing configurations, examples of which include a single processor, independent processors, parallel processors, single-instruction single-data (SISD) multiprocessing, single-instruction multiple-data (SIMD) multiprocessing, multiple-instruction single-data (MISD) multiprocessing, multiple-instruction multiple-data (MIMD) multiprocessing, a controller and an arithmetic logic unit (ALU), a DSP, a microcomputer, an application-specific integrated circuit (ASIC), a field programmable gate array (FPGA), a programmable logic unit (PLU), a central processing unit (CPU), a graphics processing unit (GPU), a neural processing unit (NPU), or any other device capable of responding to and executing instructions in a defined manner.

The methods illustrated in <FIG> that perform the operations described in this application are performed by one or more processors implemented as described above executing instructions or software to perform the operations described in this application that are performed by the methods.

Instructions or software to control one or more processors to implement the hardware components and perform the methods as described above may be written as computer programs, code segments, instructions or any combination thereof, for individually or collectively instructing or configuring the one or more processors or computers to operate as a machine or special-purpose computer to perform the operations that are performed by the hardware components and the methods as described above. In an example, the instructions or software includes at least one of an applet, a dynamic link library (DLL), middleware, firmware, a device driver, an application program storing the method of operating a processor.

Claim 1:
A method of operating a processor for computing a dot product between a first vector including a plurality of weights and a second vector including a plurality of activations, comprising:
arranging (<NUM>) the plurality of weights in a first input register (<NUM>) of the processor and the plurality of activations in a second input register (<NUM>) of the processor,
wherein both the first input register (<NUM>) and the second input register (<NUM>) each have a same number of bits and wherein the number of bits used for the representation of each weight in the first input register (<NUM>) and of each activation in the second input register (<NUM>) is the same and is smaller than the number of bits of the first and the second input register (<NUM>, <NUM>),
wherein the weights are arranged in the first input register (<NUM>) in a first order,
wherein the activations are arranged in the second input register (<NUM>) in a second order that is a reverse order of the first order,
wherein a same number of bits separates each pair of two weights in the first input register (<NUM>) that directly follow each other as well as each pair of two activations in the second input register (<NUM>) that directly follow each other,
wherein a first and a last of the weights in the first input register (<NUM>) and a first and a last of the activations in the second input register (<NUM>) are maximally separated from each other in the first input register (<NUM>) and in the second input register (<NUM>), respectively;
performing (<NUM>), by the processor (<NUM>, <NUM>), a multiplication (<NUM>) between values stored in the first input register (<NUM>) and values stored in the second input register (<NUM>);
storing a result of the multiplication (<NUM>) in an output register of the processor (<NUM>, <NUM>), wherein the output register has a greater number of bits than the input registers (<NUM>, <NUM>); and
outputting (<NUM>), from the output register, a value in a preset bit range as a result of the dot product.