JP2004342106A - Modular binary multiplier for signed and unsigned operands of variable width - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To realize a shorter CPI for multiplication instructions with respect to a design of a binary multiplier to be used together with functions shown in a general processor environment in fields of arithmetic techniques and logic techniques in computer and processor architectures. <P>SOLUTION: A concept may be split into two parts, the first of which is multiplication hardware itself and is a compact and less than-full sized multiplier which employs Booth or other type of recording methods upon the multiplier to reduce the number of partial products per scan and is implemented in such a manner that a multiplication operation with large operands may be broken into subgroups of operations that will fill into this mid-sized multiplier whose results, here called modular products, may be knitted back together to form a correct final product. The second part of the concept is supporting hardware used to separate the operands into subgroups and to input data and control signals to the multiplier and the algorithm and apparatus used to align and combine the modular products properly to obtain the final product. <P>COPYRIGHT: (C)2005,JPO&NCIPI

Description

  The present invention relates to the field of arithmetic and logic techniques in computer and processor architectures, and in particular, to the design of binary multipliers for use with features found in common processor environments.

Binary multiplication is a subset of multiplication that deals only with both signed and unsigned integers, so that its operands and results can be completely represented in binary. The simplest way of performing binary multiplication is to imitate a human execution method, in which the multiplicand is processed by the multiplier one digit at a time to produce a partial product, and those partial products are summed to form the final product. Generate a product. An example in which a human multiplication method is applied to a binary number is shown below.
Unsigned multiplication (4 bits x 4 bits-> 8 bits for complete result representation)
1110 Multiplicand 14
0111 Multiplier 07
−−−− −−
1110 pp1 98
1 110 pp200
1 110 pp2 ---
0000 pp3
−−−−−−−−
01100010 Product 98

This method also applies to signed multiplication. However, the use of two's complement negative representation and sign extension eliminates the need for additional processing of the resulting sign.
Signed multiplication (operand sign extension to 8 4 bits x 4 bits-> 8 bits)
1111 1110 Multiplicand -2
0000 0111 Multiplier +7
−−−− −−
1111 1110 pp1 -14
1111 110 pp2
1111 10 pp3
0000 0 pp4
0000 pp5
000 pp6
00 pp7
0 pp8
−−−−−−
1111 0010 Product -14

  This multiplication method is very simple and relatively easy to implement in hardware using shifters, adders, and accumulators, but requires one cycle to process the multiplier bits and generate the partial product. Then, it takes n cycles to complete the operation using the n-bit multiplier. Such a long cycle-per-instruction (CPI) time in the current field of high-speed computing is considered an impediment. The solution to achieve a shorter CPI for multiply instructions is to use additional hardware to group the partial products and compute them at once, and build the adders needed to process them simultaneously It is. This brute force approach to hardware entry reduces the CPI but also increases the chip area dedicated to the multiplication function. In particular, adders are difficult to handle, especially in terms of area and timing constraints usually associated with functional specifications. Therefore, many methods have been formulated to reduce the size of the adder by reducing the partial product by processing multiple bits of the multiplier at one time. One of the more common methods is the Booth recording algorithm.

Booth's recording algorithm is a method of reducing the number of partial products generated from a given n-bit multiplier by scanning multiple bits. This method is based on the idea that a binary 1 string in which the least significant bit of the value "1" has a valid value 2n and one string is z bits long can also be represented as ^{2n + z} - ^2n. I have. For example, the string 0b0111 ^may be expressed as 2 ^3-2 0 = 7, strings 0b1110 can be represented as ² 4 ^-2 1 = 14.

In the above example, the weight of each bit is 2n, where n is the scale value of the corresponding bit. The detection of one string is performed by overlapping the group of scanning multiplier bits by one bit. The application of this counting method to multiplication, where the scan value is a multiplier in a one-bit scan with duplicate bits, requires that the last bit of the string detected by the "1" bit to the right of the duplicate bit be "0" (string Of the string (the least significant bit of the z-bit string) given the value-(2 ⁿ ) * (multiplicand) Bit) is given the value (2 ⁿ ) * (multiplicand) and the bit at the center of the 0 or 1 string is given the value zero. This is summarized in the table below. In this table, the leftmost bit is the bit at position n of the string, and the rightmost bit is the duplicate bit required to detect the string. The column of “adjusted multiplicand value” indicates a multiplicand value. The weight of this value can be implicitly indicated by the position of the corresponding scan bit.

  The key to advantageously implementing Booth's recording method is to increase the number of bits scanned as a group, thereby reducing the overall scan required for the multiplier, as well as the number of partial products and the hardware required to combine the partial products. It is to reduce wear. A typical scan group size is 3 bits, consisting of 2 scan bits and the least significant bit at the bottom. The reason that this is so popular is that the multiplicand multiples required to achieve the recording are simply 0x, ± 1x, and ± 2x, and all possible using shifter, inverter, and two's complement methods Implementing multiples is all relatively easy, while larger scan group sizes require adders that implement higher multiples, such as ± 3x.

  The method of binary multiplication disclosed in one embodiment herein includes the steps of obtaining a multiplicand, obtaining a multiplier, and, if the multiplier exceeds a selected length, dividing the multiplier by a plurality of sub-multiples. Partitioning into groups; partitioning the multiplicand into a plurality of multiplicand subgroups if the multiplicand exceeds a selected length, zeroing unused bits of the multiplicand subgroup; Sign extending a smaller portion of. The method also includes setting a plurality of multiplicand multiples based on at least one of the selected multiplicand subgroup of the plurality of multiplicand subgroups and the multiplicand. Selecting one or more of the plurality of multiplicand multiples based on each of the multiplier subgroups of. And generating a modular product based on the selection method.

  The binary multiplier for a superscalar processor disclosed in another embodiment herein has m bits, where m is the full width of the register of the processor and the maximum width of the operand data of the selected binary multiply instruction. A first register input configured to receive a first operand including multiplicand data of at most m bits, including at least one of the following: a multiplier value; and a portion of the multiplier value of n bits length. And a second register input configured to receive a second operand including one of the multiplier value subgroups, wherein n is less than or equal to a maximum width of operand data of the selected binary multiply instruction. . The multiplicand further comprises: a multiplier configured to select a corresponding bit from the multiplicand data input to generate a valid multiplicand and to set unused bits of the multiplicand data input to zero. A control signal input configured to receive a first control signal indicative of a size of data and a second control signal configured to receive whether the multiplicand operation is signed or unsigned; A second control signal input configured to enable the multiplier to perform sign extension of the effective multiplicand.

  A system for binary multiplication in a superscalar processor, further disclosed herein in yet another embodiment, includes a binary multiplier, and in operable communication with the binary multiplier, multiplier data and multiplicand data. To ensure that the selected subgroup is sent to the binary multiplier and to properly combine the modular product with at least one of the other modular product and the cumulative modular product. A data width shifter for ensuring digit alignment, a register operably communicating with the shifter, and holding the multiplier data and the multiplicand data for input to the shifter; and a register operable with the register. An adder for communicating and accumulating a modular product with at least one of another modular product and an accumulating modular product; and operably communicating with the adder, Includes for the product and 該累 calculation modular product of the input to the adder, and a plurality of registers for holding for the output of 該累 calculation modular product.

  A system for binary multiplication in a superscalar processor, further disclosed herein in yet another embodiment, includes a first register, a second register, a third register, and the first register. , An execution unit including a bit logic unit and a binary adder operably communicating with the second register and a first multiplexer, the first multiplexer operably communicating also with the third register. A first rotator in operable communication with the first register and the execution unit; and a leading zero detection register in operable communication with the execution unit and the second register. Including the pipeline. The system also includes a fourth register, a fifth register, a sixth register, and other bits in operable communication with the fourth register, the fifth register, and the second multiplexer. A second execution unit including a logic unit and another binary adder, wherein the second multiplexer is in operable communication with the sixth register; and A rotator in operable communication with the execution unit, and a second pipeline including a leading zero detect register in operable communication with the second execution unit and the fifth register. The system also includes a third pipe including a seventh register, an eighth register, a ninth register, and a multiplier operably communicating with the seventh register and the eighth register. A general register for storing and retrieving data, an operand buffer for obtaining a first operand and a second operand, the first pipeline, the second pipeline, and the third pipeline. And a communication bus for communication between at least two of the general purpose registers and the operand buffer.

  These and other improvements are described in the detailed description below. For a better understanding of the invention with advantages and features, refer to the description and to the drawings.

  The invention will be described below by way of example and with reference to the accompanying drawings. In some figures, similar elements are indicated by similar numbers.

  Embodiments of the present invention will be described by way of example with reference to the drawings, showing advantages and features.

  As used herein, signed or signed with lossy or lossless results using special superbooth multipliers that are adapted for use with various supporting arithmetic and logic unit (ALU) hardware due to their modularity. Disclosed is a method and system architecture for multiplying various lengths of binary numbers that are none operands. The modularity of this architecture is driven by the need for smaller multipliers that can handle larger operands efficiently. Thus, this architecture is designed to work with arithmetic and logic functions and the resources found in most processor environments. The architecture may include an input of a size less than the full data width as a multiplier operand, and may further include an input of less than a full data width, if not a full data width, as a multiplicand. The architecture also includes a duplicate bit signal that provides a means for combining the subgroups of multiplications together so that they can be finally combined to produce the final correct product. This architecture also controls the incoming multiplicand data to reflect the type of operation, e.g., signed or unsigned, modifies and modulates the output, also referred to as a modular product, with other possible modular products. Some additional signals to combine and create to combine are also used.

  Also, herein, such support hardware for use with the multiplier embodiment is shown, along with the associated algorithms that have been created to implement multiplication in such an environment.

  In one embodiment, a hardware architecture for the multiplier and supporting hardware is disclosed. In another embodiment, a multiplication algorithm for processing using the hardware architecture is disclosed. The architecture of a modular binary multiplier is shown in FIG.

Modular Binary Multiplier This modular binary multiplier 10 includes, but is not limited to, six primary inputs. That is, the first operand is 64-bit data used as a multiplicand shown as 1 and the second operand is 15-bit data used as a multiplier or multiplier subgroup shown as 2. . The overlap bits between multiplier subgroups, denoted as 3 and also referred to as Z_BIT, provide continuity from one multiplier subgroup to the next and are used for string detection as required when using Booth's recording algorithm. Is done. 4, also referred to as MCAND_64, indicates to the binary multiplier 10 whether to use a 32-bit or 64-bit multiplicand 1 in the operation, and an “unsigned” control signal 5, also referred to as UNSIGNED, The MTERM_SHIFT signal 6 is used to prepare the binary multiplier 10 for signed or unsigned operations, and an additional MTERM_SHIFT signal 6 is provided to properly align the modular product output of the binary multiplier 10 with other modular products. Used to shift so that no cycle is needed. Table 2 shows an outline of the decode logic of the two control signals MCAND_644 and UNSIGNED5.

表２において、

In Table 2,

  [0,0] indicates a signed operation using a 32-bit multiplicand. Bits 32-63 of the operand data, the low word, remain unchanged, while bits 0-31, the high word, are sign-extended from the 32-bit multiplicand data.

  [0,1] indicates an unsigned 32-bit operation. When the garbage data is input together with the corresponding low word, the low word of the multiplicand data is retained, while the high word is set to zero.

  [1,0] indicates a signed 64-bit operation. This is treated as an invalid configuration in this hardware architecture of the binary multiplier 10. The reason is that the input of the multiplicand 1 and the data width of the adder are 64 bits, sign extension is not possible, and therefore, the modular product may be inappropriately expressed.

  [1,1] indicates an unsigned 64-bit operand, so the high word of the operand data will be used as the high word of the multiplicand.

  The decode and logic of MCAND_64 and UNSIGNED and the necessary changes to make to the high word of the multiplicand 1 are shown in the multiplicand high word conversion module 11. The result of the multiplicand high word conversion module is merged with the unmodified low word of the operand data in a merge 12 to generate the arithmetic multiplicand data indicated by 1A for use in the binary multiplier 10. In one embodiment, a radix-4 Booth algorithm is used, using a 3-bit scan consisting of 2 scan bits and overlapping bits between groups. This type of Booth algorithm is used because the required multiplicand multiples 0x, ± 1x, and ± 2x are relatively easy to form. It should be understood that if the required multiplier is + 1x, no changes to the multiplicand data to generate the product are necessary. Therefore, when the operation multiplicand data 1A is + 1x, it is shown to be directly supplied to the selection logic 17.

  Continuing with the description of FIG. 1, the left shifter 13 receives the upper 63 bits of the multiplicand data as input, adds "0" b to the right, shifts the data left by one bit, or is commonly known. As a result, a + 2x multiple of the multiplicand data is generated, which is also sent to the selection logic 17. The output of shifter 13 is also provided to one's complement module 15 to perform a bit flip, thereby forming a one's complement + 2x multiplier of arithmetic multiplicand data 1A, and a "hot one" in select logic 17. To complete the generation of the −2 × multiplier of the operation multiplicand 1A. The addition of this "hot 1" is handled by the selection logic 17, along with the selection of which multiple of the multiplicand 1A to use based on the recording of bits in the effective multiplier group. Similarly, by bitwise inversion, the 1's complement of the calculated multiplicand data 1A is formed using all 64 bits of the calculated multiplicand data 1A, and binary 1 is added to add the binary 1 to the 2's complement of the calculated multiplicand data 1A, or It is only necessary to form a -1x multiplier. Also in this case, the selection logic 17 adds “hot 1”.

  Continuing with FIG. 1, the radix-4 booth recording logic function 16 performs eight simultaneous, overlapping 3-bit scans using a 16-bit multiplier at a time to generate eight partial products. Table 3 shows an exploded view, divided into two groups and stacked, to show the configuration of the 16 scans required to completely process the 32-bit multiplier. In this table, Z indicates the above-mentioned duplicate bit 3 (also referred to as Z_BIT) that completes the 17-bit sequence required for this scanning algorithm and allows for multiples greater than 16 bits. By setting Z_BIT3 appropriately, the hardware can treat any group of 16 bits in the same way, whether it includes the whole or part of the multiplier 2.

  As a result of each 3-bit scan, a 3-bit internal signal is generated. Two variables, SX and S2X, determined by Booth decoding indicate the absolute coefficients of each multiplier. That is, when SX is active, a 1x multiplier is used and no special action is required. When S2X is active, the arithmetic multiplicand 1A is shifted left by one digit and zeros are inserted to fill the LSB. It should be understood that SX and S2X cannot be active at the same time. Furthermore, a state where both SX and S2X are not active at the same time indicates a 0x multiplier of the selection logic 17. The third internal control signal SINV is equal to a multiple sign determined by Booth decode for each scan. If a positive multiple is generated, SINV is set to zero and no special action is required. In the case of a negative multiple, SINV is set to "1" and 1's and 2x multiples in the one's complement form of the multiplicand 1A are selected. To complete the two's complement, the active SINV is placed into the next partial product of the same column or bit position (ie, the next row in the partial product array) as the LSB of the current partial product, as described above. Used as Table 4 shows a truth table of Booth decoding. It should be understood that this embodiment does not implement negative zero. That is, a 3-bit scan of "111" b produces the same true zero decode of "000" b. The effect of a true zero is that the partial product results in a sequence of zeros, which, of course, clears the "hot one" of the intent.

  Table 5 shows the input from the multiplicand multiple generation logic (eg, 12, 13, 14, and 15) and the rightmost dot representation of the partial product array generated by selection logic function 17 using Booth recording logic 16. Show. From this table, it can be seen that no columns use a compression structure that requires more than 15 inputs (inputs with partial product bits plus carry). Furthermore, with only eight scans, there are basically at most eight partial products, except for column 49 of row 9 (partial product 9, ie pp9) consisting of "hot 1" from eight scans. Please note. Conveniently, the right hand column has only seven product terms, indicating that there is one less carry carried from column 50 to column 49. Thus, using adder 18 using an 8: 2 compression structure with seven carry-ins from the bottom, hot 1 of pp9 is used as the ninth instead of as a carry to adder 18. , It is possible to easily form a 9: 2 compression structure with six carry. In other words, both of the above structures require a partial product bit and exactly 15 inputs that are carry-over, and produce exactly 9 outputs that are total bits and carry-out. I do.

  In one embodiment, the resulting sum and carry results are optionally latched in registers 19 and 20 and then combined in carry propagate adder 21 to produce one final modular product. This modular product and its 16-bit left-shifted form are sent to multiplexer 22. Multiplexer 22 is controlled by input signal MTERM_SHIFT to determine whether the modular product needs to be left shifted for alignment according to the algorithm of the current operation. The final product output of binary multiplier 10 is denoted herein as MP_OUT.

Supported Hardware FIG. 2 shows a simplified block diagram and data flow of a three-pipeline superscaler fixed-point processor architecture 200 according to one embodiment. The three pipelines 50 are also called an X pipe 50a, a Y pipe 50b, and a Z pipe 50c, respectively. Each of the three pipes 50a, 50b, and 50c interfaces with a bus and includes at least two 64-bit operand registers. A1 and B1 (51 and 52) as operand registers of X pipe 50a, A2 and B2 (53 and 54) as operand registers of Y pipe 50b, and A3 and B3 (55 and 56) as operand registers of Z pipe 50c. Indicated by Both X-pipe 50a and Y-pipe 50b each have an output C register to which data is supplied via multiplexers 60 and 62, and are designated C157 and C258, respectively. The two output registers C157 and C258 are used to write data to the general-purpose register file 90, respectively. The general purpose register file 90 supplies data to the operand registers via the REGISTER_DATA bus. The operand registers can also be supplied with data from memory via the operand buffer 92 via the STORAGE_DATA bus. Two values can be written and four values can be read from the register file in one cycle. Additional logic (not shown) may be incorporated to perform data processing, such as detecting leading zeros and checking for valid data. Multiplexers 60 and 62 are respectively supplied with data from the binary adder units denoted Bin 164 and Bin 266 and the bit logic units denoted Blu 172 and Blu 274 of the X50a and Y50b pipes, respectively. Data is supplied to the bit logic units Blu172 and Blu274 from rotators indicated by rot176 and rot278, respectively. Rotators rot 176 and rot 278 are used with bit logic units Blu 172 and Blu 274 to effectively use masking and are also used for shift operations. For simplicity and simplicity, in this specification, a bit logic unit or Blu172 or Blu274 may be regarded as including the rotators rot176 and rot278 and the bit logic units Blu172 and Blu274. The contents of registers B152 and B254 also interface with leading zero detect logic 82 and 84 of X-pipe 50a and Y-pipe 50b, respectively, for some terminations implemented in hardware architecture 200 of this embodiment for early termination. Used in instructions.

  Z-pipe 50c includes a third working register, designated E59, that some instructions use to hold information for later use. In one embodiment, the binary multiplier 10, shown in detail in FIG. 1, resides in the Z-pipe 50c of the fixed-point superscaler architecture 200. The input to the binary multiplier 10 is from the complete 64-bit register indicated by A355, and also from the least significant 16 bits of the B3 register 56. The output of the multiplier, denoted MP_OUT, is tri-stated in buffer 86, and the output of binary adder Bin 164 of X pipe 50a eliminates the need for an additional input to the multiplexer that feeds the C157 register.

  The A and B registers 51-56 receive data retrieved, in part, by the register file 90 via the REGISTER_DATA bus, by the operand buffer 92 via the STORAGE_DATA bus, and from the immediate field of the instruction text. The input is obtained from a bus network fed by the data contained in the instruction itself via the bus. Understand that STORAGE_DATA and IMMEDIATE_DATA are pre-aligned so that after the operands arrive at work registers A and B (51-56), they are all treated the same regardless of the source of the data. This is very important.

  It should be understood that this specification describes one embodiment of a processor architecture 200 that operates with the multiplier 10. Other configurations are possible as long as they have some important functions. One such function is the ability to rotate the multiplier 2 and the multiplicand 1, although not necessarily simultaneously, to place the appropriate subgroups in the proper locations for proper subgroup processing. It is. Another feature is the ability to accumulate modular products into one final term.

Multiplication Method It will be appreciated that, due to the modular nature of multiplication described above, many algorithms can be envisaged to perform selected operations in a particular architecture and environment. Described herein are methods relating to operations performed in the context of the aforementioned fixed-point superscalar processor. This method clearly illustrates the particular advantages of using multiplier 10 and the features available in the support hardware shown in FIG.

  Referring to FIG. 3, a high-level schematic diagram of a multiplication process 200 according to one embodiment is shown. The process receives as input instruction information indicating which particular multiplication is to be performed, and two-operand data used as the multiplicand and multiplier for the operation. This instruction information is sent to a group of logic, referred to herein as control logic, which controls the dataflow hardware based on the algorithm used to implement the different types of multiply instructions, and Route the data where it is needed to perform the required functions and find the final product. In this embodiment, MCAND_64, UNSIGNED, and MTERM_SHIFT control signals are generated. The instruction information controls the process 210 to rotate or shift the operand data appropriately to obtain the appropriate multiplicand 1 and / or multiplier 2 subgroups by cycle or by instruction, as well as one string. Obtain the appropriate Z_BIT used with the multiplier to provide continuity needed for detection. This particular implementation also provides a leading zero and leading one detection function for use with multiplier data 2 to provide early termination information to the control logic for some multiply instructions.

  The multiplier 10 in FIG. 3 receives multiplicand data 1 and multiplier data 2 as inputs. Multiplier data 2 is partitioned into scan groups at process block 214, with the input duplicate bits indicated by Z_BIT3. In this embodiment, the 16-bit multiplier data along with Z_BIT is partitioned into eight 3-bit overlap scan groups, but appropriate support, ie, setting the multiplicand multiple, recording, selection logic for the multiple, etc. Other multipliers and scan group widths are possible using. At process block 218, multiplier data 2 is recorded according to a radix-4 Booth algorithm. Turning now to multiplicand 1, at process block 212, control signals MCAND_644 and UNSIGNED5 are decoded to determine whether the binary multiplication is signed or unsigned, or, in this embodiment, It is determined whether the multiplicand 1 is 32 bits or 64 bits. At process block 214, selected multiples of the multiplicand 1 are generated, for example, 0x, ± 1x, and ± 2x.

  Continuing with FIG. 3, at process block 220, the result of the booth recording at process block 218 of multiplier 2 and Z_BIT3, partitioned into eight groups of SX, S2X, and SINV as described above, Based on this, select the desired multiple of multiplicand 1 from process block 218 and add zeros to the right as appropriate to generate the partial product. At process block 222, these partial products are summed to produce one modular product. Finally, in process block 224, the modular product output is shifted, if necessary / possible, based on the control signal MTERM_SHIFT6, thereby combining the modular product output with other modular products in process block 250. Eliminates the need for proper digit alignment. This block uses summing hardware, shift / rotation hardware, hold paths, feedback paths, and working registers and is controlled by control logic block 210 to properly combine modular products to produce the final correct product. Generate. In this way, different configurations of this block may be used to handle modular products.

  Some of the multiply instructions implemented in this embodiment of the present invention are detailed below. Referring to FIGS. 4, 5 and 6, there is shown a schematic diagram illustrating the multiplication operation and associated execution algorithm using the hardware described above, the execution process 200, and the multiplier hardware 10 shown in FIG. ing. The multiplication algorithm is configured to handle various types of multiplication involving operands of different sizes.

Operation with Multiplicands of Different Sizes Referring to FIG. 4, an example is shown illustrating one embodiment using multiplicands 1 of various sizes. In one embodiment, multiplier 10 is configured to process a 16-bit by 64-bit lossy binary multiplication to generate the lower 80 bits of the possible 80 bits. This allows the hardware architecture 200 to perform the 16-bit × 32-bit operation in which the lower 32 bits of the product are generated and the 16-bit × 64-bit operation in which the lower 64 bits of the product are generated in the same number of cycles. Can be processed. By setting MCAND_64 to zero for 32-bit operations and to 1 for 64-bit operations, both types of multiplication operations can be easily performed using the same algorithm. The only additional change required is to remember the results. Control is set to a 32-bit word for the first operation, e.g., a 16-bit x 32-bit multiply, and set to full length for the subsequent operation, e.g.

  For example, in FIG. 4, a group of instructions for one processor, such as MH, MHI, and MGHI used for multiplication of a multiplicand by a halfword, take full advantage of the foregoing features. Instructions MH and MHI both produce a 32-bit product, each of which obtains its multiplicand from general purpose register (GPR) 90. However, the MHI obtains its multiplier data as an immediate field that is part of the instruction text, while the MH obtains its multiplier from the GPR 90. Similarly, instruction MGHI receives its 64-bit multiplicand data from GPR 90 and its multiplier data from the immediate field of the instruction text. The multiply halfword immediate family is a set of lossy instructions that take a 16-bit field of instruction text that holds immediate data as a multiplier input. In the figure, the multiplier can be included in one subgroup, and the multiplicand can also be included in one subgroup because the result is lossy, so that one iteration with multiplication hardware Is shown. Table 6 below shows an example of a one-cycle process for multiplier data 2 and multiplicand data 1 and the interaction with X pipe 50A, Y pipe 50B, Z pipe 50c, and multiplier 10. In cycle 1, multiplier data 2 indicated by M1 in the table and multiplicand data 1 indicated by m1 in the table are input to the A355 and B356 registers of the Z pipe 50c, respectively. After one cycle of latency, the modular product, mp1, which is also the final product in this example, is shown as the output of multiplier MP_OUT in the second cycle, which is considered the last cycle of this operation, and is stored in storage in the next cycle. Can be put in. Note the syntax used in the table. If a register receives "mcand" or "mplier" values that specify the multiplicand 1 and multiplier 2 operand values, respectively, it means that these values come from the data bus. Also in this embodiment, the multiplier input is input from the least significant 16 bits of the register B356. To obtain the appropriate multiplier subgroup, it is only necessary to rotate or shift the multiplier data so that the required subgroup is at the least significant halfword position.

  At cycle e1, the operand data (mcand and mplier, respectively) latched in registers A355 and B356 are passed to binary multiplier 10 and data from A3 register 55 is used to generate multiplicand data 1; The multiplier data 2 is generated using the data from the B3 register 56. Data from the A3 register 55, shown as M1, is modified according to the control signals MCAND_64 and unsigned5 to generate a valid multiplicand. The effective multiplicand is then shifted and complemented and processed to generate ± 1x and ± 2x multiplicand multiples, as described above for FIG. On the other hand, in this embodiment, some processing is also performed on the first subgroup including the multiplier data 1 from the rightmost 16 bits of the B3 register 56 and the duplicate bit Z_BIT3 added to the right. The duplicate bit is zero in this case because it is the lowest (and only) subgroup. This 17-bit string is decomposed into eight 3-bit groups (2 bits + 1 duplicate bits) by the Booth recording logic of FIG. 1 to select either a 1x or 2x multiple of the multiplicand for each 3-bit scan group. Are generated, indicating whether or not to select a negative multiple for the partial product of the group, and in the case of a negative multiple, the multiplicand In order to complete the two's complement process (including the process of complementing the number and the process of adding "1") used to generate a negative multiple of Another group of eight 1-bit SINV signals is generated that feeds the partial products of the scan groups. In the same cycle, the eight partial products and one "Hot 1" input from the eighth group as a result of the booth recording of the eight 3-bit scan groups are added at adder 18 (FIG. 1). Combined and compressed into two redundant 64-bit sum and carry terms and latched into the sum and carry registers, structures 20 and 19 of FIG.

  In cycle 2, the respective data from the sum and carry registers 20 and 19 are combined by adder 21. This output and its 16-bit left shifted form are input to the multiplexer 22 of FIG. 1 and one of two is selected using the input control signal MTERM_SHIFT6. The output MP_OUT of the multiplier, which is the first modular product mp1 of this cycle, is selected as the output of the tri-state buffer 86 at the output of the binary adder 64 of FIG. This is considered the last execution cycle of this instruction, since the final result of the operation has been reached.

  By implementing the multiplication hardware to handle multi-width multiplicands, it is possible to use substantially the same algorithm with minor control changes, without having to preformat the incoming operand data. Multiplications of different multiplicand widths are processed. The format of the multiplicand data 1 is appropriately processed inside the binary multiplier 10 and is controlled by only two signals. One of the signals is a signal indicating the length of the multiplicand, for example, MCAND_64, and the other is a signal indicating whether the operand is signed or unsigned, for example, UNSIGNED5. The signal was shown.

Reducing Cycles per Instruction Another example that illustrates the flexibility of embodiments of the present disclosure is based on implementations of the MSG and MSGR algorithms. Both are 64 × 64 operations that generate a 64-bit lossy product, with the difference that MSGR obtains its multiplier data 2 from a general purpose register, eg, register file 90, while MSG obtains its data. In this embodiment, it is obtained from the memory via the operand buffer 92. Control signal MCAND_644 is set to 1 to obtain a lossy 64-bit result. The operation of this algorithm for each cycle is shown in Table 7 below, and the instruction subgroup processing order is shown in FIG. This figure shows that the multiplier is divided into four multiplier subgroups. Since this operation is a lossy operation, the complete first operand is held as 64-bit multiplicand data.

  Referring again to FIGS. 1 and 2, in cycle 1 (denoted by e1), the MSG / MSGR is a 64-bit × 64-bit instruction, so complete multiplicand data 1 is the only group in this case, the valid group. Form a multiplicand subgroup M1. The multiplier data input 2 to the binary multiplier 10 is shorter than the multiplicand 1 and again obtains the 16-bit least significant data from the B3 register 56 and defines the first multiplier subgroup, also referred to herein as m1. Generate. The multiplicand "subgroup" M1 and the multiplier subgroup m1 are processed by the binary multiplier 10 in the same manner as in the previous example, and at the end of this cycle the redundant sum and carry terms are summed by the sum register 20 and the carry register 19. Respectively. At the same time, in X pipe 50A, the complete multiplier previously entered in the A1 register is placed in bit logic unit 72 and rotated to a second multiplier subgroup (hereinafter m2), for example, the original multiplier. Are placed in the rightmost position (bits 48 to 63) of the data field. Next, the output of BLU 172 is latched into registers A253 and B354 at the end of this cycle for use in the next cycle.

  In cycle 2, the sum register 20 and the carry register 19, which hold the result of the multiplication of M1 and m1 in the previous cycle, are combined to produce the modular product mp1 as the first output of the binary multiplier 10. . This modular product mp1 is also latched as an input into the B2 register 54 at the end of this cycle for use in the next cycle. On the other hand, the multiplier is processing the subgroup M1 * m2 and puts the result in the sum register 20 and the carry register 19 as well. In the Y pipe 50B, the m2 multiplier held in the A2 register 53 is also rotated, and the third multiplier subgroup m3 is placed at the lowest position of the data path. Again, this new multiplier subgroup m3 is input to the B3 register 56 for use in the next cycle.

  In cycle 3, the sum register 20 and carry register 19, each holding the result of the multiplication of M1 and m2 in the previous cycle, are combined to generate the next modular product (hereinafter referred to as mp2), which is 16 bits left Shifted and digitized in preparation for combination with the modular product mp1. The shifted modular product mp2 is latched in register A2 for use in the next cycle. On the other hand, the binary multiplier 10 processes the subgroup M1 * m3 and puts the resulting product into the sum register 20 and the carry register 19. In the Y pipe 50B, the m2 multiplier input from the B3 register 56 in the previous cycle is set to the fourth multiplier subgroup indicated by m4 (for example, bits 0 to 15 of the original multiplier value), and the least significant 16 bit position of the data is set. It is rotated to come. The result is input to the B3 register 56 for use in the next cycle.

  In cycle 4, the sum register 20 and carry register 19 holding the result of the multiplication of M1 and M3 in the previous cycle are combined, and the modular product mp3 is generated as the third output of the binary multiplier 10 and shifted. Without being passed through multiplexer 22 and latched in B2 register 54 for use in the next cycle. On the other hand, A2 register 53 and B2 register 54, which hold modular products mp1 and mp2, respectively, are added at BIN 266 to produce an accumulated modular product mp1: 2, which is input to E register 59 for later use. Will be retained.

  In cycle 5, the sum register 20 and carry register 19 holding the result of the multiplication of M1 and m4 in the previous cycle are combined to form a fourth and final modular product of these instructions, denoted by mp4. One modular product is generated and left shifted and output from multiplexer 22 for digit alignment in combination with modular product mp3. The shifted modular product mp4 is input to the input of the A2 register 53 for use in the next cycle.

  In cycle 6, mp3 and left-shifted mp4, which are the contents of the A2 register 53 and the B2 register 54, are added by the binary adder Bin266 of the Y pipe 50B to generate an accumulated mp3: 4 term. You. This is then input to A2 register 53 for use in the next cycle. On the other hand, the mp1: 2 term held in the E register 59 is input to the B2 register 54 for later use.

  In cycle 7, the contents of the A2 register, e.g., the accumulated modular product mp3: 4, are shifted 32 bits to the left and aligned as shown in FIG. 4 in preparation for addition with the mp1: 2 term. This alignment is performed in bit logic unit BLU 274, where mp3: 4 is shifted through BLU 274 and the shifted result (mp3: 4) is fed back to A2 register 53 for use in the next cycle. Is done.

  Finally, in cycle 8, the 32-bit shifted accumulated modular product (mp3: 4) and mp1: 2, the contents of A2 register 53 and B2 register 54, respectively, are combined in a binary adder BIN266, The final product mp1: 4 in this last execution cycle is generated. The product of this final result is input to the C258 register to save for the next cycle.

  Specifically, in the case of a pair of modular products shown as (mp1, mp2) and (mp3, mp4), the modular product is shifted left by 16 bits using the multiplexer 22 and the shifter 6 at the end of the multiplier 10 in FIG. Table 7 readily shows that this is advantageous because it saves processing cycles. Otherwise, the unshifted modular product (mp2 or mp4) returns to X pipe 50A or Y pipe 80B, shifts, and then combines it with the other modular products (mp1 and mp3, respectively). This results in the use of two processing cycles instead of one required for the shift.

  The use of the existing features of this particular embodiment of the support hardware shown in FIG. 2 in conjunction with the multiplier hardware 10 and the process 200 saves processing cycles and, in particular, the existing leading zero detection. The functions, for example, 82 and 84 (FIG. 2) need not be used. To fully support early termination logic for multiplications that use large operands but have small actual multiplier values, minor changes have been made to leading zero detection functions 82 and 84 to support leading one detection. Can be added.

  Returning to a single multiply (64 bit) instruction as an example, it will be readily apparent that this instruction pair is optimal for early termination with respect to multiplier size. Since the multiplier data is processed from right to left, the algorithm can be terminated at an advantageous point corresponding to the size of the multiplier data. For example, if the multiplier data is in the range (0x000 to 0x7fff), or (0xFFFFffffFFFF8000) to (0xFFFFffffFFFFffffff), the multiplier data can be essentially represented by m1, and execution may be terminated after cycle e3. At that point, the modular product mp1 held in the B2 register 54 can be routed as a final output to the C2 register 58, thereby completing the multiplication with 3 valid cycles instead of the full 8 cycles shown. be able to. Similarly, such a quick method can be easily implemented using multiplier data of different effective lengths, and the effective length 15, 31, 32, 47, and 48 bit multipliers (ie, the absolute value Can be completely represented by these numbers of bits), allowing 3, 4, 5, 6, and 7 execution cycles, respectively. The execution tables for the first two early terminations are shown in Tables 8 and 9, respectively. Here, the contents of the register for each multiplier processing cycle are shown.

  When performing unsigned multiplication using the Booth algorithm, a correction term, referred to herein as a modular product correction (mpc) term, which must be added because the method of reducing partial products is based on string detection. There may be. Coming to the end of the string (most significant bit) does not mean the end of the computation. In unsigned multiplication, there will always be one or more implicit bits of the "0" b value that exceed the MSB. If the MSB of the multiplier is 0, such implicit bits to the left of the MSB indicate a continuous string of zeros and no action is taken. However, the MSB of "1" b with zeros added to the left indicates that the end of the string has been reached, and for a 3-bit scan these bits are "001" b and the LSB of the correction is the multiplier LSB. Represents a + 1x multiplicand multiple that must be added to the result and aligned to be one bit to the left of the MSB (see FIG. 6). This is why an operation with a multiplier that can be completely represented by 32 bits requires one cycle more than an operation with a multiplier that can be completely represented by 31 bits because it is necessary to incorporate correction into the final product. Depending on the embodiment and resources of the instruction, this additional mpc term may or may not be incorporated into the algorithm.

  Another example of the benefits and flexibility of the embodiment is based on the use of a logical 64-bit x 64-bit lossless (eg, taking into account and taking into account carry) multiply instruction that produces a 128-bit result. Referring to FIG. 6, for lossless product, the control signal MCAND_644 must be set to zero so that all generated modular products are also set as lossless. In FIG. 6, the multiplier is divided into four multiplier subgroups, but the 64-bit multiplicand data is divided into two subgroups and a 16-bit × 32-bit multiplication is created to avoid lossy results Is illustrated. Table 10 shows the use of hardware in an MLG / MLGR implementation in one embodiment of the present invention. Table 10 shows the contents of the registers for each multiplier processing cycle.

  At cycle e1, binary multiplier 10 processes subgroup M1 * m1 while in X pipe 50A, and bit logic unit BLU 172 rotates multiplier data 2 to generate a second multiplier subgroup m2. . This multiplier subgroup m2 is latched in A2 register 53 and B3 register 54 for use in the next cycle.

  In cycle 2, the binary multiplier 10 processes the multiplier subgroup M1 * m2, compresses the result of M1 * m1 into a modular product term mp1, and inputs it to the B2 register 54 for use in the next cycle. At Y pipe 50B, the contents m2 of A2 register 53 (from the previous cycle) are rotated at BLU 274 to produce multiplier subgroup m4, which is latched into E register 59 for later use. Register A253 receives multiplicand data mand from the bus for use in the next cycle.

  At cycle 3, the binary multiplier 10 finishes compressing the result of M1 * m2, shifts the result 16 bits to the left, and aligns the modular product term mp2 for later combining with mp1, and Input to the A2 register 53 for use in the next cycle. Register B 356 holds the m2 data for later use. On the other hand, in Y pipe 50B, bit logic unit BLU 274 rotates the multiplicand data to generate a second multiplicand subgroup M2, which is input to register A355 for use in the next cycle.

  In cycle 4, the binary multiplier 10 processes the subgroup M2 * m2. The contents m4 of E register 59 are provided to B3 register 56 for use in the next cycle, and A3 register 55 gets the multiplicand data from the bus and creates subgroup M1 for use by the multiplexer in the next cycle. I do.

  At cycle 5, binary multiplier 10 processes subgroup M1 * m4, finishes compressing the result of M2 * m2, shifts it 16 bits to the left to generate modular product mp3, which is Input to the B2 register 53 for use. In the Y pipe 50B, the contents of the registers A253 and B254 are added to generate a combined modular product mp1: 2, which is input to the E register 59 of the Z pipe 50C for later use.

  At cycle 6, binary multiplier 10 finishes compressing the result of M1 * m4, shifts the result left 16 bits to generate modular product mp4, and uses the result for use in the next cycle. Input to register A253. Register A151 of X pipe 50A inputs the multiplicand from the bus for use in the next cycle.

  At cycle 7, BIN 266 adds the mp4 data previously input to register A253 and the mp3 data previously stored in B254 to generate a combined modular product mp3: 4, which is input to A253 for later use. I do. On the other hand, at X pipe 50A, BLU 172 obtains mcand data from register A151, rotates it to generate a second multiplicand subgroup M2, and inputs it to A355 for use in the next cycle. Register A 151 receives a multiplier from the bus for use in the next cycle. Register B356 also latches a multiplier value from the bus to use the first subgroup m1 in the next cycle.

  At cycle 8, the multiplier processes the subgroup M2 * m1 and latches the multiplicand into the A3 register 55 for using the first multiplicand subgroup M1 in the next cycle. The multiplier held in A1 register 51 is rotated by X pipe 50A to generate a third multiplier subgroup m3, which is latched in register B356 for use in the next cycle.

  At cycle 9, the multiplier processes the subgroup M1 * m3, finishes processing the result of M2 * m1, generates a modular product mp5, and latches it in the B2 register 54 for use in the next cycle. Register B 356 holds that m3 value for later use.

  At cycle 10, the multiplier finishes processing M1 * m3 to generate a modular product mp6, which is latched in B2 register 54 for use in the next cycle. On the other hand, in the Y pipe 50B, the binary adder BIN 266 adds mp3: 4 and mp5, which are the contents of the A2 register 53 and the B2 register 54, to generate a combined modular product 3: 5. At X pipe 50A, A1 register 51 latches the multiplicand from the bus for use in the next cycle.

  In cycle 11, in Y pipe 50B, BIN 266 adds the contents of register A 253 and register B 254 to generate a combined modular product 3: 6. In X pipe 50A, BLU 172 processes the multiplier data in register A151 to generate a second multiplicand subgroup M2, which is input to register A355 for later use.

  In cycle 12, in the Z pipe 50C, the values M2 and m3 are held in the A3 register 55 and the B3 register 56 for use in the next cycle. On the other hand, in the Y pipe 50B, the mp3: 6 data in the register A 253 input from the BIN 266 in the previous cycle is rotated by the BLU 274, whereby the low 32-bit word is exchanged for the high 32-bit word, and another modular product is used. To produce the rotational modular product rmp3: 6 needed to produce the 128-bit final result. The B2 register 54 latches the mp1: 2 data from the E register 59 for use in the next cycle. In the X pipe 50A, the multiplicand is input to the A1 register 53 in preparation for the possibility of being used in the next cycle.

  At cycle 13, the multiplier processes subgroup M2 * m3. In the Y-pipe 50B, the rotated modular product rmp3: 6 is combined with mp1: 2, with its lowwords set to zero, to produce the least significant doubleword of the resulting quadword. This is latched into register C258 to save for the next cycle. Register A253 inputs multiplier data from the bus for use in the next cycle. On the other hand, in the X pipe 50A, the multiplicand data is added to the rotated modular product rmp3: 6 low word, with the condition that the most significant bit of the multiplier data happens to be “1” bit, and the corrected modular product is added. cmp3: 6 is generated. This result is input to the B2 register 54 for later use.

  At cycle 14, binary multiplier 10 finishes compressing the result of M2 * m3 to produce modular product mp7, which is input to register B254 for use in the next cycle. A3 register 55 of Z pipe 50C holds its M2 value for use in the next cycle. The multiplier data in register A253 is passed through BLU 274 to generate a fourth multiplier subgroup m4, which is latched in register B356 for use in the next cycle.

  At cycle 15, binary multiplier 10 processes subgroup M2 * m4. At Y pipe 50B, BIN 266 combines the modular product mp7 in A2 register 53 with the corrected modular product cmp3: 6 to produce mp3: 7, which is A2 for use in the next cycle. It is latched by the register 53.

  At cycle 16, binary multiplier 10 finishes compressing the result of M2 * m4, shifts the result 16 bits to the left, and generates modular product mp8, which is stored in register A151 for use in the next cycle. Is input to The mp3: 7 data in register A 252 is passed through BIN 266 and input to register B 254 for use in the next cycle.

  At cycle 17, the last cycle of execution, the data in register A 151 and the data in register B 152 are combined to produce the most significant doubleword of the final result with corrections already applied. This is latched in register C157 to save for the next cycle.

  The above example has shown how hardware can be used in lossless multiplication.

  Advantageously, the above embodiment using lossless instructions allows the multiplier 10 of the embodiment to process data where the multiplier 2 and the multiplicand 1 are much larger than the actual hardware data path. This indicates that it can be easily set. FIG. 6 shows that the modular products can also be calculated in different combinations. It will be appreciated that the particular order shown is only one of many ways to perform these operations. For example, if the hardware supports immediate shift out and the ability to store the final product as soon as it is calculated, the order of mp5: mp6 could be exchanged with mp3: mp4 to do so. Alternatively, as in the embodiments described above for the implementation of instructions such as MSG / MSGR, to support early termination of certain operations, the order can be adjusted to process multiplier 2 from right to left. Such "out-of-order" processing of the multiplication subgroup ultimately results in, for example, flexible, high-performance, medium-scale multiplication hardware.

  The invention of this disclosure may be embodied in the form of a computer, a controller, or a method of implementing processor 100 and an apparatus for performing such method. The present invention also relates to a computer program code comprising instructions embodied on a tangible medium 102, such as a floppy diskette, CD-ROM, hard drive, or any other computer-readable storage medium. When the computer program code is loaded and executed on a computer, a control device, or the processor 100, the computer, the control device, or the processor 100 may execute the present invention. It becomes. Also, the present invention may be stored in a storage medium and loaded or executed on a computer, a controller, or the processor 100, or via any transmission medium, such as electronic wiring or cables, optical fibers, electromagnetic radiation, etc. It can also be implemented in the form of computer program code as a data signal 103, whether transmitted or not, in which case, when the computer program code is loaded and executed on a computer, the computer An apparatus for implementing the present invention. When implemented on general-purpose processor 100, the computer program code segments configure the processor to build specific logic circuits.

  It should be understood that first, second, or other similar designations for indicating similar elements do not define or imply a particular order, unless explicitly stated otherwise.

  As described above, the present invention has been described with reference to the embodiments. However, various modifications can be made without departing from the scope of the present invention, and equivalents can be used instead of the respective elements. Those skilled in the art will understand. In addition, many modifications may be made to adapt a particular situation or material to the teachings of the invention without departing from the essential scope thereof. Accordingly, the invention is not limited to the specific embodiments disclosed as the best mode contemplated for carrying out the invention, but the invention includes all embodiments falling within the scope of the appended claims.

FIG. 3 is a diagram illustrating an example of a data flow of a binary multiplier architecture. FIG. 3 is a schematic block diagram of a three-pipe superscaler fixed-point processor and a diagram showing a data flow according to an embodiment. FIG. 4 is a diagram illustrating a flowchart of a multiplication method according to the embodiment. FIG. 4 illustrates a lossy binary multiply instruction. FIG. 4 illustrates two instructions in a one-time multiplication family of binary multiplication instructions. FIG. 4 is a diagram illustrating a pair of instructions in a multiplication logic group of binary multiplication.

Explanation of reference numerals

DESCRIPTION OF SYMBOLS 1 Multiplicand 2 Multiplier 3 Duplicate bit 4 MCAND_64 control signal 5 UNSIGNED control signal 6 MTERM_SHIFT control signal 10 Multiplier 11 Multiplicand high word conversion 12 Multiplicand input merge (logic for generating multiplicand multiple)
13 Left shifter (multiplicand multiple generation logic)
14 1's complement module (multiplicand multiple generation logic)
15 One's complement module (multiplicand multiple generation logic)
12 Multiplicand multiple generation logic 13 Multiplicand multiple generation logic 14 Multiplicand multiple generation logic 15 Multiplicand multiple generation logic 16 Booth recording logic 17 Selection logic 18 Adder 19 Carry register 20 Total register 21 Carry propagation adder 22 Multiplexer 50a Pipeline 50b Pipe Line 50c pipeline 51 operand register 52 operand register 53 operand register 54 operand register 55 operand register 56 operand register 57 output register 58 output register 59 working register 60 multiplexer 62 multiplexer 64 binary adder unit 66 2 Hex adder unit 72 bit logic unit 74 bit logic unit 76 rotator 78 rotator 82 leading zero detection logic 84 Leading zero detection logic 86 Buffer 90 General purpose register file 92 Operand buffer 100 Processor 102 Medium 103 Data signal 200 3 Pipeline superscaler Fixed point processor

Claims (30)

A binary multiplier for a superscalar processor, comprising:
m bits include at least one of a full width of the processor's register and a maximum width of operand data of a selected binary multiply instruction, and receive a first operand including a maximum m-bit long multiplicand data. A first register input configured as
A second operand comprising one of a multiplier value and a multiplier value subgroup comprising a section of the multiplier value having a length of n bits, wherein n is the operand of the selected binary multiply instruction. A second register input that is less than or equal to the maximum width of the data;
A first indication of the size of the multiplicand data, wherein the multiplier selects a corresponding bit from the multiplicand data input to generate a valid multiplicand and allows unused bits of the multiplicand data input to be set to zero; A control signal input configured to receive a control signal of
A second control signal configured to receive a second control signal indicating whether the multiplicand operation is signed or unsigned, the second control signal configured to enable the multiplier to perform sign extension of the effective multiplicand; And a control signal input.   The multiplier of claim 1, wherein the multiplier further comprises a third control signal input configured to shift the modular product and allow it to be aligned with another modular product for combination. Multiplier.   The multiplier of claim 1, wherein the first control signal facilitates interpretation of a length of the multiplicand data.   The second control signal controls whether the multiplication is recognized as a signed operation or an unsigned operation, and uses a two's complement format as a negative expression so that the multiplicand data is signed and signed. The multiplier according to claim 1, wherein the multiplier controls which of the two is treated as none.   The first control signal cooperates with the second control signal to characterize and modify the multiplicand data to avoid lossy results without additional processing to obtain the appropriate code. The multiplier of claim 1, wherein the multiplier produces a loss result.   2. The apparatus of claim 1, further comprising an input configured to receive continuity bits between the two multiplier value subgroups, thereby allowing multiplication by multipliers of length greater than n bits. The multiplier as described.   The multiplier of claim 1, further comprising recording logic for use on the one of the multiplier value and the multiplier value subgroup to generate a reduced number of partial products.   The multiplier of claim 7, wherein the recording logic includes, but is not limited to, a radix-4 Booth algorithm.   Recording logic generates a multi-bit signal for each scan group, using at least one bit to indicate which multiple of the multiplicand data is to be selected, and using another one bit to determine whether the multiplicand data is positive or negative. The multiplier of claim 7, wherein the multiplier indicates a negative multiple.   For each scan group, the recording logic generates a 3-bit signal, with 2 bits indicating whether to select at least one of ± 1x multiple and ± 2x multiple of the multiplicand data, with the third bit being positive or negative. The multiplier of claim 7, wherein the multiplier indicates a negative multiple.   The third bit is used as a "hot one" that is input to a subsequent partial product at the same column or bit position as the least significant bit of the current partial product to complete a two's complement, The multiplier of claim 10, further comprising implementing a negative multiple.   The multiplier of claim 1, wherein a plurality of partial products are processed using an adder, and the plurality of partial products are compressed into two product terms.   The modular product is operably connected to the output of the adder and shifts the modular product left by n bits based on the size of each of the multiplier value and one of the multiplier value subgroups, based on the alignment of the modular product. 2. The multiplier of claim 1, further comprising a combination of a shifter and a multiplexer to facilitate coupling with other modular products. A system for binary multiplication in a superscalar processor, comprising:
A binary multiplier;
It is in operable communication with the binary multiplier to shift multiplier data and multiplicand data to ensure that selected subgroups are sent to the binary multiplier and to combine the modular product with another one. A data width shifter that ensures that the digit is aligned to properly combine with at least one of the modular product and the cumulative modular product;
A register operably communicating with the shifter and holding the multiplier data and the multiplicand data for input to the shifter;
An adder operatively communicating with the register and accumulating a modular product with at least one of another modular product and an accumulating modular product;
A system operatively communicating with the adder and including a plurality of registers for holding the modular product and the accumulated modular product for input to the adder and for output of the accumulated modular product. .   Further including leading zero detection logic to detect small operand absolute values of the unsigned multiplier data to control possible early termination logic for longer operations using relatively wide data multiplier data; The system according to claim 14.   In order to control possible early termination logic for longer term operations using relatively wide data multiplier data, the leading one detection logic further detects the small operand absolute value of the negative signed multiplier data. The system of claim 14, comprising:   15. The system of claim 14, further comprising another data width shifter for shifting the multiplier data and the multiplicand data.   15. The system of claim 14, further comprising another adder combining the redundant terms into one modular product.   If the multiplier output is in a redundant form, further comprising another register, wherein two registers hold redundant terms that are input to the adder and combined as one modular product, and wherein the other register is the accumulator. 15. The system of claim 14, wherein the system retains a modular product.   15. The multiplier configured to switch between multiplicand data of different lengths using a control signal for multiplication using equal size multipliers and different size multiplicands. System.   The multiplier and the multiplicand subgroup are optional, in order to accommodate large operands and large results, or to accommodate early termination logic, taking into account constraints in available support hardware. 15. The system of claim 14, wherein the system is configured to be processed in order. A system for binary multiplication in a superscalar processor, comprising:
A first register, a second register, a third register, a bit logic unit and a binary adder operably communicating with the first register, the second register, and the first multiplexer. An execution unit, wherein the first multiplexer is in operative communication with the third register; a first rotator is in operable communication with the first register and the execution unit; A first pipeline including an execution unit and a leading zero detect register in operable communication with the second register;
A fourth register, a fifth register, a sixth register, another bit logic unit and another two operably communicating with the fourth register, the fifth register, and the second multiplexer. A second execution unit including a binary adder, wherein the second multiplexer is in operable communication with the sixth register, and is operable with the fourth register and the execution unit. A second pipeline including a rotator communicating with the second execution unit and a leading zero detection register operably communicating with the second execution unit and the fifth register;
A third pipeline including a seventh register, an eighth register, a ninth register, and a multiplier operably communicating with the seventh register and the second register;
General purpose registers for storing and retrieving data,
An operand buffer for obtaining a first operand and a second operand;
A system including a communication bus for communication between at least two of the first pipeline, the second pipeline, the third pipeline, the general purpose register, and the operand buffer. A method of binary multiplication,
Obtaining a multiplicand;
Obtaining a multiplier;
Partitioning the multiplier into a plurality of multiplier subgroups if the multiplier exceeds a selected length;
If the multiplicand exceeds a selected length, partition the multiplicand into a plurality of multiplicand subgroups, zero out unsigned bits in the multiplicand subgroup, and sign extend a smaller part of the multiplicand subgroup. Doing at least one of
Setting a plurality of multiplicand multiples based on at least one of the selected multiplicand subgroup of the plurality of multiplicand subgroups and the multiplicand;
Selecting one or more of the multiplicands of the plurality of multiplicands based on each of the multiplier subgroups of the plurality of multipliers subgroups;
Generating a modular product based on the selection method. Generating another modular product based on the selection method;
24. The method of claim 23, further comprising: matching and combining the modular product with the other modular product to produce a resulting product. Recording the plurality of multiplier subgroups using a recording algorithm;
Selecting one or more multiplicand multiples of the plurality of multiplicand multiples based on the record.
24. The method of claim 23, wherein the multiplicand multiple is also based on the record.   26. The method of claim 25, wherein the recording algorithm is a radix-4 Booth algorithm.   The recording step includes the steps of generating a multi-bit signal for each scan group, using at least one bit to indicate which multiple of the multiplicand is to be selected, and using another one bit to calculate the multiplicand. Indicating a positive multiple or a negative multiple.   The multi-bit signal is a 3-bit signal, two bits are used to select one of 0x, ± 1x, and ± 2x multiples of the multiplicand, and a third bit is a positive or negative of the multiplicand. 24. The method of claim 23, used to indicate a negative multiple.   The method of claim 1, further comprising using the other one bit as a "hot one" input to a subsequent product to complete a two's complement required to implement a negative multiple of the multiplicand data. 28. The method according to 28.   24. The method of claim 23, wherein the step of partitioning the multiplicand segments the multiplicand data to avoid lossy results.

Images