Patent ID: 12236208

DETAILED DESCRIPTION OF SOME EXAMPLE EMBODIMENTS

FIG.1is a block diagram illustrating an integrated circuit100according to some example embodiments. In more detail, the block diagram ofFIG.1shows a part of the integrated circuit100that performs constant multiplication to generate an output OUT by multiplying an input IN by a constant. The input IN and the output OUT may be or correspond to multi-bit signals, and may be signed or unsigned. Herein, it is assumed that the input IN, the output OUT, and the constant are unsigned values, but example embodiments are not limited thereto. As shown inFIG.1, the integrated circuit100may include a logic circuit120, at least one adder140, and a lookup table160. In some example embodiments, the integrated circuit100may be manufactured/fabricated through a semiconductor process, and the logic circuit120, the at least one adder140, and the lookup table160may be integrated into a single die/single chip or may be respectively integrated into two or more dies/multiple chips. The logic circuit120and the at least one adder140may be collectively referred to as a processing circuitry.

For a more accurate result, the size of the input IN (e.g., the number of bits) may increase. For example, in a machine learning model for identifying a feature from an image, the size of the input image may increase, and/or the number of quantization levels for application to a mobile system may increase for a high accuracy. In order to process the increased size of the input IN, there may be an exponentially increasing cost/exponentially increasing complexity scaling in the multiplier. For example, when the number of bits of the input IN increases 2 times from 8 to 16, four 8-bit multipliers may be required, and/or a multiplier may be required to perform 8-bit multiplications four times. As will be described later with reference to the drawings, the integrated circuit100may have more efficient structures for constant multiplication, thereby providing a high speed and/or low cost multiplication and/or improved scalability. Alternatively or additionally, due to the high performance and high efficiency multiplication, like an inference of a neural network and/or calculations in a proof-of-work based blockchain, both performance and efficiency of operations based on multiple multiplications may be improved. Alternatively or additionally, due to a machine learning model (e.g., a neural network) providing improved performance and efficiency, applications based on machine learning may be widely used in a mobile system. Alternatively or additionally, applications based on a blockchain may be more widely used.

Referring toFIG.1, the logic circuit120may receive the input IN and may access the lookup table160. For example, as shown inFIG.1, the logic circuit120may provide an address ADR to the lookup table160and receive a seed SD from the lookup table160. The logic circuit120may generate a partial product PP based on the seed SD received from the lookup table160. In some example embodiments, as will be described later with reference toFIG.2and the like, the logic circuit120may extract a plurality of parts from the input IN, and provide a plurality of addresses to the lookup table160, thereby receiving a plurality of seeds from the lookup table, and generating a plurality of partial products based on the plurality of seeds. Herein, the parts extracted from the input IN may be referred to as input parts. An example of the logic circuit120will be described later with reference toFIG.2and the like.

The at least one adder140may receive the partial product PP from the logic circuit120and may generate the output OUT based on the partial product PP. For example, as will be described later with reference toFIG.2and the like, the at least one adder140may receive a plurality of partial products from the logic circuit120, and generate the output OUT by summing (adding) the plurality of partial products. Herein, the at least one adder140summing the partial products may be referred to as at least one first adder.

The lookup table memory/the lookup table160may be accessed by the logic circuit120and may store seeds corresponding to multiples of a constant C multiplied by the input IN. The constant C may be an integer, e.g. may be an integer greater than or equal to zero; however, example embodiments are not limited thereto. For example, as shown inFIG.1, when n is an integer, the lookup table160may store ‘n*C’ as a seed. The logic circuit120may generate the address ADR based on a value of the part extracted from the input IN, and may generate/more easily generate a partial product based on a seed corresponding to the address ADR. Accordingly, the product of the input IN and the constant C, for example, the output OUT, may be more efficiently calculated. In some example embodiments, when the integrated circuit100is used in a machine learning model that identifies features from the input image, and the size of the input image increases from, e.g., 513×513 to 4023×3024, the size of the feature map of the neural network increases from 150 MB to 6.2 GB, whereas the size of a weight may increase from about 20 MB to 30 MB. Accordingly, even if the size of the input IN increases, an increase in the size of the lookup table160storing multiples of the weight/multiples of a constant, may be limited. Alternatively or additionally, as will be described later with reference to the drawings, the lookup table160may store only some of all possible values of the partial product, for example, all possible multiples of the constant. For example, the number of seeds stored in the lookup table160may be less than the number of possible values of the partial product, and accordingly, the lookup table160may have a reduced size. For example, the number of seeds stored in the lookup table160may be half the number of possible values of the partial product, or may be less than half the number of possible values of the partial product.

The lookup table160may have any structure storing seeds. For example, the lookup table160may be or may include a volatile memory such as at least one of a static random access memory (SRAM), dynamic random access memory (DRAM), etc., and/or may be or may include a non-volatile memory such as flash memory, resistive random access memory (RRAM), etc., a one-time programmable (OTP) memory, an array of antifuses and/or of fuses, and a storage device such as at least one of a register, a flip-flop, etc.

FIG.2is a block diagram illustrating an example of an integrated circuit200according to some example embodiments. In more detail, the block diagram ofFIG.2shows the integrated circuit200that generates the output OUT by multiplying a 16-bit input IN[16:1] by a constant. Similar to the integrated circuit100ofFIG.1, the integrated circuit200ofFIG.2may include a logic circuit220, at least one adder240, and a lookup table260.

The logic circuit220may include an address generator222and an arithmetic logic224. The address generator222may receive the 16-bit input IN[16:1] and may generate the address ADR and a control signal CTR. The address generator222may extract a plurality of parts from the 16-bit input IN[16:1]. For example, as shown inFIG.2, the address generator222may extract first to fourth parts P1to P4from the 16-bit input IN[16:1], and each of the first to fourth parts P1to P4may have a length of four (4) bits. In some example embodiments, as will be described later with reference toFIG.9, the address generator222may extract a part that shares at least one bit with another part from the 16-bit input IN[16:1]. AlthoughFIG.2illustrates that the input IN[16:1] is divided into four (4) equal parts of four (4) bits in length each, example embodiments are not limited thereto. For example, the input IN[16:1] may be divided into unequal parts, and/or may be divided into less than four (4) or more than four (4) parts.

The address generator222may generate a plurality of addresses ADRs and the control signal CTR based on the first to fourth parts P1to P4extracted from the 16-bit input IN [16:1]. In some example embodiments, the address generator222may generate at least one address from one part. In some example embodiments, the address generator222may not generate an address when the part extracted from the 16-bit input IN [16:1] is zero. The lookup table260may provide a plurality of seeds SDs respectively corresponding to the plurality of addresses ADRs to the logic circuit220. In some example embodiments, the plurality of addresses ADRs may be simultaneously provided to the lookup table260in parallel, and the plurality of seeds SDs may also be provided to the logic circuit220in parallel and simultaneously. In addition, in some example embodiments, the plurality of addresses ADRs may be sequentially provided to the lookup table260, and the plurality of seeds SDs may also be sequentially provided to the logic circuit220.

The arithmetic logic224may receive the control signal CTR from the address generator222and may receive the plurality of seeds SDs from the lookup table260. The arithmetic logic224may be referred to as or may correspond to an arithmetic logic unit (ALU), and may perform an arithmetic operation and/or a bit shift operation based on the control signal CTR, thereby generating first to fourth partial products PP1to PP4from the plurality of seeds SDs. Herein, the arithmetic operation and the bit shift operation may be collectively referred to as an operation. Also, the bit shift operation may simply be referred to as a shift, and may refer to a shift left. In some example embodiments, the first to fourth partial products PP1to PP4may respectively correspond to values obtained by multiplying the first to fourth parts P1to P4extracted from the 16-bit input IN[16:1] by a constant, e.g. by the same constant. Examples of the arithmetic logic224will be described later with reference toFIGS.3,5,7, and9and the like.

The at least one adder240may generate the output OUT by summing the first to fourth partial products PP1to PP4. In some example embodiments, the arithmetic logic224may sequentially output the first to fourth partial products PP1to PP4, and the at least one adder240may generate the output OUT by sequentially accumulating the first to fourth partial products PP1to PP4. The at least one adder240may have an arbitrary structure for summing the first to fourth partial products PP1to PP4, and may include three adders, e.g. three adders comprising half-adder circuitry and/or full-adder circuitry in some example embodiments. Hereinafter, as shown inFIG.2, an example of processing the 16-bit input IN[16:1] will be mainly described, but it will be understood that example embodiments are not limited thereto.

FIG.3is a block diagram illustrating an integrated circuit300according to some example embodiments.FIG.4is a diagram illustrating a table400including partial products generated by the integrated circuit300ofFIG.3according to some example embodiments. Specifically, the block diagram ofFIG.3shows a logic circuit320generating one partial product PP, and the table400ofFIG.4shows how all possible values of the partial product PP are generated by the integrated circuit300ofFIG.3.

Referring toFIG.3, the integrated circuit300may include a logic circuit320and a lookup table360. The lookup table360may store seeds corresponding to odd multiples of the constant C, and may not store seeds corresponding to even multiples of the constant C. For example, as shown inFIG.3, the lookup table360may store eight seeds ‘C, 3C, . . . , 15C’. Accordingly, the lookup table360may not store all of the possible values of the partial product PP, and may store only half of 16 possible values of the partial product PP. As will be described later, when a part IN[k+3:k] is an odd number, the seed provided by the lookup table360in response to the address ADR may be output as the partial product PP, while when the part IN[k+3:k] is an even number, a value obtained by shifting the seed provided by the lookup table360at least one time in response to the address ADR may be output as the partial product PP.

The logic circuit320may receive the part IN[k+3:k] (k=1, 5, 9 or 13) of a certain length, e.g. a 4-bit length extracted from the input IN, and may generate the partial product PP. As shown inFIG.3, the integrated circuit300may include an address generator322and arithmetic logic324. The address generator322may generate the address ADR and the control signal CTR based on the part IN[k+3:k]. When the part IN[k+3:k] is an odd number, the address generator322may generate the address ADR indicating a location where a seed corresponding to the product of the part IN[k+3:k] and the constant C is stored. Alternatively, when the part IN[k+3:k] is an even number, the address generator322may generate the address ADR indicating a location where a seed capable of generating the partial product PP by a shift is stored.

The arithmetic logic324may include at least one shifter324_2and a multiplexer (MUX)324_4. The at least one shifter324_2may generate a shifted seed SD′ by shifting the seed SD received from the lookup table360based on the control signal CTR received from the address generator322. The address generator322may determine the number of times to shift the seed SD when the part IN[k+3:k] is an even number, and may generate the control signal CTR based on the determined number of shifts.

The MUX324_4may select and output, as the partial product PP, either the seed SD provided from the lookup table360or the shifted seed SD′ received from the at least one shifter324_2based on the control signal CTR received from the address generator322. The address generator322may generate the control signal CTR for selecting the seed SD when the part IN[k+3:k] is an odd number, while when the part IN[k+3:k] is an even number, the address generator322may generate the control signal CTR for selecting the shifted seed SD′.

Referring toFIG.4, the table400represents an operation for generating the partial product PP from the part IN[k+3:k], for example, an arithmetic operation and/or a bit shift operation. As described above with reference toFIG.3, the lookup table360may store odd multiples of the constant C and may not store even multiples of the constant C, and accordingly, the partial product PP corresponding to the part IN[k+3:k] of the odd value may be same as the seed SD.

The partial product PP corresponding to the part IN[k+3:k] of the even value may be generated by shifting the seed SD at least one time. As used herein, the operation “<<” may be or may correspond to a shift operation, e.g. a bit shift operation. For example, a partial product ‘2C’ may be generated by shifting/bit shifting the seed ‘C’ one time (C<<1), a partial product ‘12C’ may be generated by shifting/bit shifting the seed ‘3C’ twice (3C<<2), and a partial product ‘8C’ may be generated by shifting/bit shifting the seed ‘C’ 3 times (C<<3). Accordingly, all 16 values of the partial product PP may be generated.

FIG.5is a block diagram illustrating an integrated circuit500according to some example embodiments.FIG.6is a diagram illustrating a table600including partial products generated by the integrated circuit500ofFIG.5according to some example embodiments. In more detail, the block diagram ofFIG.5shows a logic circuit520that generates one partial product PP, and the table600ofFIG.6shows how all possible values of the partial product PP are generated by the integrated circuit500.

Referring toFIG.5, the integrated circuit500may include a logic circuit520and a lookup table560. The lookup table560may store two or more seeds, and the partial product PP may be generated based on one or more operations on at least one seed. For example, as shown inFIG.5, the lookup table560may store the two seeds ‘C, 3C’, and as will be described later, the partial product PP may be generated based on operation of at least one of the two seeds ‘C, 3C’. The lookup table560ofFIG.5may store a smaller number of seeds as compared to the lookup table360ofFIG.3, while the arithmetic logic524ofFIG.5to be described later may further include at least one adder524_4when compared to the arithmetic logic324ofFIG.3. In some example embodiments, the lookup table560may store a small, e.g. a minimum number, of seeds such that the partial product PP is generated by one addition and/or at least one shift from at least one seed, as described below with reference toFIG.6.

The logic circuit520may receive the part IN[k+3:k] having a 4-bit length extracted from the input IN, and may generate the partial product PP. As shown inFIG.5, the logic circuit520may include an address generator522and arithmetic logic524. The address generator522may generate the address ADR and the control signal CTR based on the part IN[k+3:k]. For example, the address generator522may generate the address ADR corresponding to one of the two seeds ‘C, 3C’ and may generate addresses corresponding to the one of two seeds ‘C, 3C’ (in parallel and/or sequentially), based on the part IN[k+3:k], as described later with reference toFIG.6.

The arithmetic logic524may include at least one shifter524_2and at least one adder524_4. The at least one shifter524_2may receive the seed SD provided from the lookup table560and/or may receive an output of the at least one adder524_4based on the control signal CTR, and may shift a received value. In addition, the at least one adder524_4may receive the seed SD provided from the lookup table560and/or may receive the output of the at least one shifter524_2based on the control signal CTR, and may add or subtract received values based on the control signal CTR. Herein, the at least one adder524_4included in the arithmetic logic524may be referred to as at least one second adder.

Referring toFIG.6, the table600represents an operation for generating the partial product PP from the part IN[k+3:k], for example, an arithmetic operation and/or a bit shift operation. As described above with reference toFIG.5, the lookup table560may store, e.g. may only store, the two seeds ‘C, 3C’, and accordingly, the partial product PP corresponding to the part IN[k+3:k], which is 1 or 3, may be same with the seed SD.

Some values of the partial product PP may be generated by shifting the seed SD. For example, as shown inFIG.6, the four partial products ‘2C, 4C, 8C, 12C’ may be generated by shifting one of the two seeds ‘C, 3C’, and no additional operation may be used to generate such partial products. Some values of the partial product PP may be generated by adding the seed SD and/or the shifted seed with the seed SD and/or the shifted seed. For example, a partial product ‘10C’ may be generated by adding a value obtained by shifting the seed ‘3C’ one time and a value obtained by shifting the seed ‘C’ twice. Some values of the partial product PP may be generated by subtracting the seed SD and/or the shifted seed from the seed SD and/or the shifted seed. For example, a partial product ‘15C’ may be generated by subtracting the seed ‘C’ from a value obtained by shifting the seed ‘C’ four times. In some example embodiments, some values of partial product PP may be generated in a different manner from that shown inFIG.6. For example, a partial product ‘9C’ may be generated by adding a value obtained by shifting the seed ‘3C’ one time and the seed ‘3C’, differently from that shown inFIG.6.

FIG.7is a block diagram illustrating an integrated circuit700according to some example embodiments andFIG.8is a diagram illustrating an example of an operation of the integrated circuit700ofFIG.7according to some example embodiments. In more detail, the block diagram ofFIG.7shows a logic circuit720for generating one partial product PP, andFIG.8shows an operation of updating a lookup table760by the logic circuit720.

Referring toFIG.7, the integrated circuit700may include the logic circuit720and the lookup table760. The lookup table760may store not only seeds but also valid bits respectively corresponding to the seeds. An activated valid bit VB may indicate that the seed SD corresponding to the valid bit VB is valid, while an inactivated valid bit VB may indicate that the seed SD corresponding to the valid bit VB is invalid. For example, as shown inFIG.7, in the lookup table760, the activated valid bit VB corresponding to the constant C may be ‘1’, while the inactivated valid bit VB corresponding to an invalid value X may be ‘0’. As used herein an activated valid bit VB may have a value of ‘1’, while an inactivated valid bit VB may have a value of ‘0’; however, example embodiments are not limited thereto. For example, an activated valid bit VB may have a value of ‘O’, while an inactivated valid bit VB may have a value of ‘1’. In some example embodiments, the seed SD may be generated in a process of generating the partial product PP, and the generated seed SD may be stored in the lookup table760, and thus, the valid bit VB may be activated. Referring toFIG.8, when a part ‘0110’ is received while the lookup table760stores the constant C, as shown inFIG.8, ‘3C’ may be generated by summing a value shifted from the seed ‘C’ and the seed ‘C’, and a partial product ‘6C’ may be generated by shifting ‘3C’. For example ‘3C’ generated in the process of generating the partial product PP may be used later as a seed, and accordingly, as shown inFIG.8, an updated lookup table760′ may store the seed ‘3C’ and ‘1’ indicating the activated valid bit.

Referring back toFIG.7, the logic circuit720may receive the part IN[k+3:k] having a 4-bit length extracted from the input IN, and calculate the partial product PP. As shown inFIG.7, the logic circuit720may include an address generator722, and arithmetic logic724. The address generator722may generate the address ADR and the control signal CTR based on the part IN[k+3:k]. The address generator722may receive the valid bit VB corresponding to the address ADR, and may identify whether the seed SD is valid based on the valid bit VB. For example, when the valid bit VB is activated (e.g., has a value of ‘1’), the address generator722may identify that the seed SD received by the arithmetic logic724together with the valid bit VB is valid. Meanwhile, when the valid bit VB is inactivated (e.g., has a value of ‘0’), the address generator722may identify that the seed SD received by the arithmetic logic724together with the valid bit VB is invalid.

The address generator722may generate the control signal CTR such that the seed SD required for/used for generation of the partial product PP is generated by the arithmetic logic724in response to the inactivated valid bit VB. As shown inFIG.7, the arithmetic logic724may provide the generated seed SD to the lookup table760, and the address generator722may provide the address ADR and an activated write enable signal WE to the lookup table760. Accordingly, the seed SD generated by the arithmetic logic724may be stored in the lookup table760. Alternatively or additionally, the address generator722may provide not only the address ADR and the activated write enable signal WE, but also the activated valid bit VB to the lookup table760, and accordingly, the seed SD stored in the lookup table760may be used later to generate the partial product PP from the part IN[k+3:k]. As a result, the seed SD may be generated and stored in the lookup table760when first used, and the stored seed SD may be used when generating the partial product PP later.

The arithmetic logic724may include at least one bit shifter724_2and at least one adder724_4. The at least one shifter724_2may receive the seed SD provided from the lookup table760and/or an output of the at least one adder724_4based on the control signal CTR, and may shift a received value. In addition, the at least one adder724_4may receive the seed SD provided from the lookup table760and/or an output of the at least one shifter724_2based on the control signal CTR, and may add or subtract received values based on the control signal CTR. As described above, the at least one shifter724_2and the at least one adder724_4may be used to generate not only the partial product PP but also the seed SD that is first used.

FIG.9is a block diagram illustrating an integrated circuit900according to some example embodiments. Specifically, the block diagram ofFIG.9shows a logic circuit920that generates the first to fourth partial products PP1to PP4from the input IN. As shown inFIG.9, the integrated circuit900may include the logic circuit920and a lookup table960.

In some example embodiments, a partial product may be generated based on a Booth algorithm. The Booth algorithm may refer to a multiplication algorithm that provides a reduced amount of computations by encoding a multiplicand based on part of the multiplier and summing encoded multiplicands. The integrated circuit900may generate the first to fourth partial products PP1to PP4by encoding the constant C based on parts extracted from the input IN, as described later. The Booth algorithm may be based on a two's complement of the multiplicands.

Referring toFIG.9, the logic circuit920may include an address generator922and an arithmetic logic924. The address generator922may extract a plurality of parts from the input IN, and each of the plurality of parts may share at least one bit with another part for Booth encoding. For example, as shown inFIG.9, the address generator922may extract the first to fourth parts P1to P4from the input IN based on a radix-10 Booth multiplication. The first part P1may share a fourth bit IN[4] of the input IN with the second part P2, the second part P2may share an eighth bit IN[8] of the input IN with the third part P3, and the third part P3may share a 12th bit IN[12] of the input IN with the fourth part P4. Alternatively or additionally, the first part P1may additionally include one bit IN[0] that is not included in the input IN. The address generator922may provide the first to fourth parts P1to P4to the arithmetic logic924, and may generate a plurality of addresses ADRs based on a value of each of the first to fourth parts P1to P4. As described above with reference toFIG.2and the like, the plurality of addresses ADRs may be simultaneously provided to the lookup table960in parallel or may be sequentially provided to the lookup table960. As shown inFIG.9, the lookup table960may store three seeds ‘C, 3C, 5C’, and, in response to each of the plurality of addresses ADRs, may output one of the three seeds ‘C, 3C, 5C’.

The arithmetic logic924may include first to fourth Booth encoders924_1to924_4, and the first to fourth Booth encoders924_1to924_4may respectively receive the first to fourth parts P1to P4from the address generator922. Each of the first to fourth Booth encoders924_1to924_4may receive the seed SD from the lookup table960, and may respectively generate the first to fourth partial products PP1to PP4from the first to fourth parts P1to P4based on the seed SD. According to the radix-10 Booth algorithm, the second Booth encoder924_2receiving the second part P2may generate the second partial product PP2by shifting the encoded value three times, the third Booth encoder924_3receiving the third part P3may generate the third partial product PP3by shifting the encoded value seven times, and the fourth Booth encoder924_4receiving the fourth part P4may generate the fourth partial product PP4by shifting the encoded value eleven times.

FIG.10is a flowchart illustrating a method for constant multiplication according to some example embodiments. As shown inFIG.10, the method for constant multiplication may include a plurality of operations S10, S30, S50, S70, and S90. In some example embodiments, the method ofFIG.10may be performed by the integrated circuit200ofFIG.2, andFIG.10will be described below with reference toFIG.2.

Referring toFIG.10, in operation S10, a plurality of parts may be extracted from the input IN. For example, the address generator222may receive the input IN having a 16-bit length and extract the first to fourth portions P1to P4from the input IN. The plurality of parts may be the same size, or may be different sizes.

In operation S30, the plurality of addresses ADRs may be generated. For example, the address generator222may generate the plurality of addresses ADRs based on the first to fourth parts P1to P4. The address generator222may generate at least one address based on a part extracted from the input IN. Alternatively or additionally, the address generator222may generate the control signal CTR based on the first to fourth parts P1to P4. In some example embodiments, the address generator222may not generate an address when the part extracted from the input IN is zero, and may generate the control signal CTR so that a corresponding partial product is zero.

In operation S50, a plurality of seeds SDs may be obtained from the lookup table260. For example, the lookup table260may store seeds, and may concurrently or sequentially output the plurality of seeds SDs in response to the plurality of addresses ADRs received in parallel or sequentially from the address generator222.

In operation S70, a plurality of partial products may be generated. For example, the arithmetic logic224may generate the plurality of partial products from the plurality of seeds SDs, for example, the first to fourth partial products PP1to PP4, based on the control signal CTR provided from the address generator222. The first to fourth partial products PP1to PP4may respectively correspond to values obtained by multiplying the first to fourth parts P1to P4by a constant. Due to the plurality of seeds SDs provided in operation S50, the first to fourth partial products PP1to PP4may be more easily generated based on a reduced amount of computations.

In operation S90, the plurality of partial products may be summed, e.g. may be accumulated. For example, the at least one adder240may receive the first to fourth partial products PP1to PP4from the arithmetic logic224and generate the output OUT by summing the first to fourth partial products PP1to PP4.

FIG.11is a flowchart illustrating a method for constant multiplication according to some example embodiments. Specifically, the flowchart ofFIG.11shows an example of operation S70ofFIG.10. As described above with reference toFIG.10, a plurality of partial products may be generated in operation S70′ ofFIG.11. As shown inFIG.11, operation S70′ may include a plurality of operations S71, S72, and S73. In some example embodiments, operation S70′ may be performed by the integrated circuit300ofFIG.3, andFIG.11will be described below with reference toFIG.3.

Referring toFIG.11, in operation S71, a part extracted from the input IN may be determined to be an even number. For example, the address generator322may receive the part IN[k+3:k] having a 4-bit length extracted from the input IN, and may determine whether a least significant bit (LSB) of the part IN[k+3:k], e.g., a k-th bit IN[k] of the input IN, is zero. As described above with reference toFIGS.3and4, the lookup table360may store odd multiples of the constant C, and the arithmetic logic324may receive the seed SD corresponding to odd multiples of the constant C from the lookup table360. As shown inFIG.11, when the part IN[k+3:k] is an odd number, e.g. has a least significant bit of ‘1’, operation S70′ may end, and the seed SD received from the lookup table360may be output as the partial product PP.

When the part IN[k+3:k] is an even number, e.g. has a ‘0’ in the least significant bit, the seed SD may be shifted in operation S72. For example, when the part IN[k+3:k] is an even number, the address generator322may generate the control signal CTR so that the seed SD is shifted by the at least one shifter324_2of the arithmetic logic324. The at least one shifter324_2may shift the seed SD in response to the control signal CTR.

In operation S73, an index k may be increased by 1, and operation S71may be subsequently performed based on the increased index k. As described above with reference toFIG.4, when the part IN[k+3:k] has a value corresponding to a multiple of 4 (e.g., 4C, 12C), the seed SD may be or be required to shift twice, and when the part IN[k+3:k] has a value corresponding to a multiple of 8 (e.g., 8C), the seed SD may be or be required to shift three times. Accordingly, as illustrated inFIG.11, the seed SD may be shifted by the number of consecutive zeros from the LSB of the part IN[k+3:k]. For convenience of illustration, an example in which the seed SD is sequentially shifted is illustrated inFIG.11, but in some example embodiments, the address generator322may identify the number of consecutive zeros from the LSB of the part IN[k+3:k] and generate the control signal CTR based on the identified number, and the at least one shifter324_2may shift the seed SD one or more times based on the control signal CTR.

FIG.12is a flowchart illustrating a method for constant multiplication according to some example embodiments. Specifically, the flowchart ofFIG.12shows the method of generating a partial product based on operation of two or more seeds. As shown inFIG.12, the method for constant multiplication may include operation S37, operation S55, and operation S77, and operation S37, operation S57, and operation S77may be included in operation S30, operation S50, and operation S70ofFIG.9, respectively. In some example embodiments, the method ofFIG.12may be performed by the integrated circuit500ofFIG.5, andFIG.12will be described below with reference toFIG.5.

Referring toFIG.12, at least two addresses may be generated in operation S37. For example, the address generator522may generate the at least two addresses based on a value of the part IN[k+3:k] extracted from the input IN. As described above with reference toFIG.5, the lookup table560may store the seed ‘C’ and also the seed ‘3C’, and the address generator522may generate the at least two addresses respectively corresponding to at least two seeds required to generate the partial product PP. For example, as described above with reference toFIG.6, when the part ‘0101’ is received, the address generator522may generate two addresses respectively corresponding to the seed ‘C’ and the seed ‘3C’.

In operation S57, the at least two seeds may be obtained from the lookup table560. For example, the lookup table560may output the at least two seeds in response to the at least two addresses provided in operation S37, and the arithmetic logic524may receive the at least two seeds from the lookup table560.

In operation S77, the partial product PP may be generated based on operation of the at least two seeds. For example, in operation S37, the address generator522may generate not only the at least two addresses but also the control signal CTR, and the arithmetic logic524may generate the partial product PP based on operation of the at least two seeds based on the control signal CTR provided from the address generator522. The arithmetic logic524may include the at least one shifter524_2and the at least one adder524_4, and as described above with reference toFIG.6, may generate the partial product PP from the at least two seeds based on addition, subtraction, and/or shift.

FIG.13is a flowchart illustrating a method for constant multiplication according to some example embodiments. Specifically, the flowchart ofFIG.13shows an example of operation S50ofFIG.10. As described above with reference toFIG.10, a plurality of seeds may be obtained from a lookup table in operation S50′ ofFIG.13. As shown inFIG.13, operation S50′ may include a plurality of operations S51to S56. In some example embodiments, operation S50′ may be performed by the integrated circuit700ofFIG.7, andFIG.13will be described below with reference toFIG.7.

Referring toFIG.13, in operation S51, the valid bit VB corresponding to the address ADR may be obtained. For example, the lookup table760may store seeds and valid bits respectively corresponding to the seeds, and each of the valid bits may indicate whether a seed corresponding to a valid bit is valid. The address generator722may receive the valid bit VB by providing the address ADR to the lookup table760.

In operation S52, the valid bit VB may be determined whether to be activated. For example, the address generator722may determine that the valid bit VB is activated when a value of the valid bit VB received from the lookup table760is ‘1’, while the address generator722may determine that the valid bit VB is inactivated when the value of the valid bit VB is ‘0’. As shown inFIG.13, when the valid bit VB is activated, the seed SD corresponding to the address ADR may be provided for generation of the partial product PP in operation S56.

When the valid bit VB is inactivated, the seed SD may be calculated in operation S53. For example, as described above with reference toFIG.8, the arithmetic logic724may generate the seed SD in a process of generating the partial product PP based on the control signal CTR provided from the address generator722. Then, the seed SD calculated in operation S53may be provided for the generation of the partial product PP in operation S54.

In operation S55, the calculated seed SD and the activated valid bit VB may be stored in the lookup table760. For example, the arithmetic logic724may provide the seed SD calculated in operation S53to the lookup table760, and the address generator722may provide the activated valid bit VB and the activated write enable signal WE to the lookup table760. The lookup table760may store the activated valid bit VB received from the address generator722and the seed SD received from the arithmetic logic724in response to the activated write enable signal WE.

FIG.14is a flowchart illustrating a method for constant multiplication according to some example embodiments. Specifically, the flowchart ofFIG.14shows a method of performing constant multiplication based on a Booth algorithm. As shown inFIG.14, the method for constant multiplication may include operation S18, operation S38, operation S58and operation S78, and operation S18, operation S38, operation S58and operation S78may be respectively included in operation S10, operation S30, operation S50, and operation S70ofFIG.10. In some example embodiments, the method ofFIG.14may be performed by the integrated circuit900ofFIG.9, andFIG.14will be described below with reference toFIG.9.

Referring toFIG.14, in operation S18, a part that shares at least one bit with another part may be extracted from the input IN. For example, the address generator922may extract the first to fourth parts P1to P4from the input IN, based on a radix-10 Booth multiplication, and each of the first to fourth parts P1to P4may share the at least one bit with another part.

In operation S38, at least one address may be generated. For example, the address generator922may generate the at least one address, in order to receive, from the lookup table960, at least one seed required to generate a partial product based on the Booth multiplication from the part extracted in operation S18.

In operation S58, the at least one seed may be obtained from the lookup table960. For example, the address generator922may provide the at least one address generated in operation S38to the lookup table960, and the lookup table960may provide the at least one seed to the arithmetic logic924in response to the at least one address.

In operation S78, a Booth encoded partial product may be generated. For example, the arithmetic logic924may include the first to fourth Booth encoders924_1to924_4, and the first to fourth Booth encoders924_1to924_4may respectively generate the first to fourth partial products PP1to PP4from the first to fourth parts P1to P4based on the at least one seed provided in operation S58.

FIG.15is a diagram illustrating an example of an operation of storing seeds in the lookup table12_2according to some example embodiments. Specifically, the left side ofFIG.15shows operations S1, S3, S5, S7, and S9of mounting a machine learning model on a processing device10designed to execute the machine learning model, and the right side ofFIG.15shows an example of operation S9in detail.

The machine learning model may be or may refer to a model such as an arbitrary model trained by a plurality of samples. For example, the machine learning model may be a model based on at least one of an artificial neural network (ANN), a decision tree, a support vector machine, a regression analysis, a Bayesian network, a genetic algorithm, etc. In some example embodiments, when the machine learning model is based on an ANN (or simply a neural network), the ANN may include, as a non-limiting example, at least one of a convolution neural network (CNN), a region with convolution neural network (R-CNN), a region proposal network (RPN), a recurrent neural network (RNN), a stacking-based deep neural network (S-DNN), a state-space dynamic neural network (S-SDNN), a deconvolution Network, a deep belief network (DBN), restricted Boltzmann machine (RBM), a fully convolutional network, a long short-term memory (LSTM) network, and a classification network.

The processing device10may execute the machine learning model. For example, the processing device10may include dedicated hardware designed to execute a machine learning model, such as a neural processing unit (NPU), and may also include hardware for various purposes that may execute a machine learning model such as a central processing unit (CPU), a mining accelerator, a graphics processing unit (GPU), etc. Further, in some example embodiments, a processing device10may include a processor in memory (PIM) such as computational RAM. As shown inFIG.15, the processing device10may include an integrated circuit12and a nonvolatile memory (NVM)14, and the integrated circuit12may include a lookup table12_2, a logic circuit12_4, and at least one adder12_6. In some example embodiments, the processing device10may include a plurality of cells, such as a plurality of standard cells, that in parallel generate products of inputs and weights included in a feature map, and each of the plurality of cells may include the lookup table12_2, the logic circuit12_4, and the at least one adder12_6. Herein, the processing device10may be simply referred to as a device.

Referring to the left side ofFIG.15, a floating point model may be prepared in operation S1. For a more accurate result, a floating point model trained through floating point arithmetic instead of fixed point arithmetic may be prepared.

In operation S3, quantization may be performed. For example, the processing device10designed to execute the machine learning model may be included in a mobile system and may include limited resources. Accordingly, a floating point model may be quantized, and the quantized model may be installed on the processing device10. As described above with reference toFIG.1, the number of quantization levels may increase for a more accurate result.

In operation S5, a seed calculation may be performed. The floating point model that is completely trained in operation S1may include floating point weights, and in operation S3, the floating point weights may be quantized. Seeds stored beforehand in the lookup table12_2may be used for multiplication of inputs and weights included in the feature map, as described above with reference to the drawings, and seeds to be stored in the lookup table12_2in operation S5may be calculated. Because the weights are determined in operation S3, the seeds may be calculated a priori, e.g. beforehand in operation S5, independent of inference performed by executing the machine learning model by the processing device10.

In operation S7, compilation may be performed. For example, a compiler executed by a computing system may convert the model quantized in operation S3and the seeds calculated in operation S5into a form executable by the processing device10.

In operation S9, provisioning may be performed. For example, as shown on the right side ofFIG.15, data DAT compiled in operation S7may be provisioned to the processing device10. As described above, the data DAT may include the seeds calculated in operation S5. The data DAT provided to the processing device10may be programmed to the NVM14, and the lookup table12_2may load seeds SDs from the NVM14. As a result, some of operations required/used when a machine learning model is executed may be performed in advance, and inference of the machine learning model may be more efficiently performed.

FIGS.16A and16Bare block diagrams illustrating examples of an operation of storing seeds in lookup tables22_2aand22_2baccording to embodiments. Unlike the example ofFIG.15, data compiled by a compiler may not include seeds, and seeds may be calculated by processing devices20aand20bofFIGS.16A and16B. Hereinafter, descriptions ofFIGS.16A and16Bredundant with that ofFIG.15are omitted.

Referring toFIG.16A, the processing device20amay include an integrated circuit22a, an NVM24a, and a seed calculator26a, and the integrated circuit22amay include the lookup table22_2a, a logic circuit22_4a, and at least one adder22_6a. As described above with reference toFIG.15, in order to provision a machine learning model to the processing device20a, the data DAT may be programmed in the NVM24a.

The seed calculator26amay receive a plurality of weights WTs from among the data DAT programmed in the NVM24a, and generate the plurality of seeds SDs from the plurality of weights WTs. As shown inFIG.16A, the seed calculator26amay provide the plurality of seeds SDs to the NVM24a, and the plurality of seeds SDs may be programmed to the NVM24atogether with the data DAT. Accordingly, the plurality of seeds SDs may be calculated when the machine learning model is provided, and the lookup table22_2amay load the plurality of seeds SDs from the NVM24a.

Referring toFIG.16B, the processing device20bmay include an integrated circuit22b, an NVM24b, and a seed calculator26b, and the integrated circuit22bmay include the lookup table22_2b, a logic circuit22_4b, and at least one adder22_6b. As described above with reference toFIG.15, in order to provision the machine learning model to the processing device20b, the data DAT may be programmed in the NVM24b.

The seed calculator26bmay receive the weight WT from the NVM24b, and may calculate the seed SD from the weight WT to provide the seed SD to the lookup table12_2b. Accordingly, different from the examples ofFIGS.15and16A, the seed SD may not be stored in the NVM24band the seed SD may be calculated from the weight WT by the seed calculator26band provided to the lookup table12_2bbefore multiplication of an input by the weight WT is performed.

FIG.17is a block diagram illustrating a system30according to some example embodiments. In some example embodiments, the system30may be a system-on-chip in which elements are integrated in one chip (or die), and may be referred to as an application processor (AP). As shown inFIG.17, the system30may include a CPU31, a GPU32, an NPU33, a modem34, a memory35, an accelerator36, an interface37, and at least one sensor38, and the CPU31, the GPU32, the NPU33, the modem34, the memory35, the accelerator36, the interface37and the at least one sensor38may communicate with each other via a bus39.

The CPU31may execute a series of instructions and control the system30. In some example embodiments, the CPU31may execute an operating system (OS) and may execute a plurality of applications on the OS. The CPU31may include a plurality of cores capable of executing the instructions independently from each other, and may include a cache memory accessed by the plurality of cores. In some example embodiments, the CPU31may include circuitry such as an integrated circuit for constant multiplication described above with reference to the drawings.

The GPU32may refer to dedicated hardware designed to process graphic data, and the NPU33may refer to dedicated hardware designed to execute a machine learning model. In some example embodiments, the GPU32and/or the NPU33may include a plurality of cells operating in parallel with each other, and each of the plurality of cells may include an integrated circuit for constant multiplication described above with reference to the drawings.

The modem34may extract information by demodulating and/or decoding a signal received through a wired channel and/or a wireless channel. Further, the modem34may generate a signal to be transmitted over the wired channel or the wireless channel by encoding and/or modulating the information. The memory35may be accessed by other elements via the bus39and may include a volatile memory and/or an NVM. In some example embodiments, the memory35may store seeds to be loaded into a lookup table described above with reference to the drawings. The accelerator36may refer to hardware designed to perform a specific function at a high speed. The interface37may provide an interface with external devices of the system30, for example, input/output devices. The at least one sensor38may sense or detect a physical quantity such as at least one of a temperature, voltage, current, etc.

As used herein variously described example embodiments are not necessarily mutually exclusive. For example, some example embodiments may include features described with reference to one figure, and may also include features described with reference to another figure.

Furthermore each of, or at least some of, the elements described above may be implemented as processing circuitry, e.g. may be implemented with logic gates such as standard cells comprising various transistors such as CMOS transistors. Elements may be designed as or implemented as standard cells such as full adders, half adders, multiplexers, decoders, encoders, etc.

Any of the elements and/or functional blocks disclosed above may include or be implemented in processing circuitry such as hardware including logic circuits; a hardware/software combination such as a processor executing software; or a combination thereof. For example, the processing circuitry more specifically may include, but is not limited to, a central processing unit (CPU), an arithmetic logic unit (ALU), a digital signal processor, a microcomputer, a field programmable gate array (FPGA), a System-on-Chip (SoC), a programmable logic unit, a microprocessor, application-specific integrated circuit (ASIC), etc. The processing circuitry may include electrical components such as at least one of transistors, resistors, capacitors, etc. The processing circuitry may include electrical components such as logic gates including at least one of AND gates, OR gates, NAND gates, NOT gates, etc.

While inventive concepts have been particularly shown and described with reference to various example embodiments thereof, it will be understood that various changes in form and details may be made therein without departing from the spirit and/or the scope of the following claims.