Scheduling multiple operations in a divider unit

A multiplier unit that may be configured to concurrently perform multiple division and square operations is disclosed. The multiplier unit may include multiple stages. Each stage may be configured to perform a corresponding arithmetic operation. Control circuitry coupled to the multiplier unit may be configured to schedule in a given cycle of the plurality of cycles, a respective tasks of a plurality of tasks included in a first operation for execution on a respective stage of the multiple stages. The control circuitry may be further configured to schedule execution of each tasks of a second plurality of tasks included in a second operation during a respective cycle on an unused stage of the multiple stages.

BACKGROUND

Technical Field

Embodiments described herein relate to integrated circuits, and more particularly, to techniques for performing arithmetic operations within integrated circuits.

Description of the Related Art

Computing systems typically include one or more processors or processing cores which are configured to execute program instructions. The program instructions may be stored in one of various locations within a computing system, such as, e.g., main memory, a hard drive, a CD-ROM, and the like.

Processors include various functional blocks, each with a dedicated task. For example, a processor may include an instruction fetch unit, a memory management unit, and an arithmetic logic unit (ALU). An instruction fetch unit may prepare program instruction for execution by decoding the program instructions and checking for scheduling hazards, while arithmetic operations such as addition, subtraction, and Boolean operations (e.g., AND, OR, etc.) may be performed by an ALU. Some processors include high-speed memory (commonly referred to as “cache memories” or “caches”) used for storing frequently used instructions or data

Some arithmetic operations may not have dedicated hardware within an ALU. Such arithmetic operations, such as, e.g., division, may be implemented as a series of program instructions making use of functional blocks within the ALU. In some cases, additional circuitry may be added to an ALU to implement one of various algorithms for performing such arithmetic operations.

SUMMARY OF THE EMBODIMENTS

Various embodiments of a multiplier unit are disclosed. Broadly speaking, a circuit and a method are contemplated in which a multiplier unit includes a plurality of stages. Each stage may be configured to perform a corresponding arithmetic operation. Control circuitry may be configured to schedule for a given cycle a given task of a first plurality of tasks associated with a first operation. The control circuitry may be further configured to schedule execution of a second plurality of tasks associated with a second operation on unused stages in the multiplier unit.

In one embodiment, the first and second operations each include one of an integer divide operation, a floating point single precision divide operation, a floating point double precision divide operation, a floating point single precision square root operation, or a floating point double precision divide operation. In a non-limiting embodiments, the first plurality of tasks includes a first plurality of steps included in a first iterative division operation, and the second plurality of tasks includes a second plurality of steps included in a second iterative division operation.

In a further embodiment, the first plurality of tasks includes a first plurality of steps included in a first iterative square root operation, and the second plurality of tasks includes a second plurality of steps include in a second iterative square root operation.

DETAILED DESCRIPTION OF EMBODIMENTS

In a computing system, arithmetic operations may be performed by an arithmetic logic unit (ALU) of a processor. The ALU may contain dedicated logic circuits, such as, e.g., an adder or multiplier, that are designed to perform the desired arithmetic function. Some arithmetic operations, however, may be infrequently used, or may be costly, in terms of silicon area, to implement in logic circuits, may be implemented using multiple program instructions. In other cases, other logic circuits, (e.g., a multiplier) may be reused, with additional logic circuits, in an iterative fashion to perform the desired arithmetic operation.

Some operations, such as, e.g., division or square root, although infrequently used may have high latencies. Such latencies may adversely affect system performance. To remediate high latency for some operations, dedicated logic circuits may employed increasing area usage and power consumption. Using existing circuits within an ALU to perform other arithmetic operations may necessitate modifications to the existing circuits that may increase their size and power consumption. The embodiments illustrated in the drawings and described below may provide techniques for improving latency of some arithmetic operations while limiting increases in area usage and power consumption.

A block diagram illustrating one embodiment of a distributed computing unit (DCU)100is shown inFIG. 1. In the illustrated embodiment, DCU100includes a service processor110, coupled to a plurality of processors120a-cthrough bus170. It is noted that in some embodiments, system processor110may additionally be coupled to system memory130through bus170. Processors120a-care, in turn, coupled to system memory130, and peripheral storage device140. Processors120a-care further coupled to each other through bus180(also referred to herein as “coherent interconnect180”). DCU100is coupled to a network150, which is, in turn coupled to a computer system160. In various embodiments, DCU100may be configured as a rack-mountable server system, a standalone system, or in any suitable form factor. In some embodiments, DCU100may be configured as a client system rather than a server system.

System memory130may include any suitable type of memory, such as Fully Buffered Dual Inline Memory Module (FB-DIMM), Double Data Rate, Double Data Rate 2, Double Data Rate 3, or Double Data Rate 4 Synchronous Dynamic Random Access Memory (DDR/DDR2/DDR3/DDR4 SDRAM), or Rambus® DRAM (RDRAM®), for example. It is noted that although one system memory is shown, in various embodiments, any suitable number of system memories may be employed.

Peripheral storage device140may, in some embodiments, include magnetic, optical, or solid-state storage media such as hard drives, optical disks, non-volatile random-access memory devices, etc. In other embodiments, peripheral storage device140may include more complex storage devices such as disk arrays or storage area networks (SANs), which may be coupled to processors120a-cvia a standard Small Computer System Interface (SCSI), a Fiber Channel interface, a Firewire® (IEEE 1394) interface, or another suitable interface. Additionally, it is contemplated that in other embodiments, any other suitable peripheral devices may be coupled to processors120a-c, such as multi-media devices, graphics/display devices, standard input/output devices, etc.

In one embodiment, service processor110may include a field programmable gate array (FPGA) or an application specific integrated circuit (ASIC) configured to coordinate initialization and boot of processors120a-c, such as from a power-on reset state. Additionally, in some embodiments, service processor110may include a programmable read-only memory (PROM) that may store instructions to perform a power-on self-test (POST). In various embodiments, service processor110may be configured to allow access to administrative functions such as test and debug modes of processors120a-c, such as testing cache memories in processors120a-c, or providing test code to processors120a-csuch that each of processors120a-cmay test their respective cache memories, for example.

As described in greater detail below, each of processors120a-cmay include one or more processor cores and cache memories. In some embodiments, each of processors120a-cmay be coupled to a corresponding system memory, while in other embodiments, processors120a-cmay share a common system memory. Processors120a-cmay be configured to work concurrently on a single computing task and may communicate with each other through coherent interconnect180to coordinate processing on that task. For example, a computing task may be divided into three parts and each part may be assigned to one of processors120a-c. Alternatively, processors120a-cmay be configured to concurrently perform independent tasks that require little or no coordination among processors120a-c.

The embodiment of the distributed computing system illustrated inFIG. 1is one of several examples. In other embodiments, different numbers and configurations of components are possible and contemplated. It is noted that althoughFIG. 1depicts a multi-processor system, the embodiments described herein may be employed with any number of processors, including a single processor core

Turning now toFIG. 2, a block diagram of an embodiment of a processor200is shown. Processor200may, in some embodiments, correspond to one of processors120a-cof DCU100as illustrated inFIG. 1. In the illustrated embodiment, the processor200includes a fetch control unit201, an instruction cache202, a decode unit204, a mapper209, a scheduler206, a register file207, an execution core208, an interface unit211, and a floating point/graphics unit (FGU)212. The fetch control unit201is coupled to provide a program counter address (PC) for fetching from the instruction cache202. The instruction cache202is coupled to provide instructions (with PCs) to the decode unit204, which is coupled to provide decoded instruction operations (ops, again with PCs) to the mapper205. The instruction cache202is further configured to provide a hit indication and an ICache PC to the fetch control unit201. The mapper205is coupled to provide ops, a scheduler number (SCH#), source operand numbers (SO#s), one or more dependency vectors, and PCs to the scheduler206. The scheduler206is coupled to receive replay, mispredict, and exception indications from the execution core208, is coupled to provide a redirect indication and redirect PC to the fetch control unit201and the mapper205, is coupled to the register file207, and is coupled to provide ops for execution to the execution core208. The register file is coupled to provide operands to the execution core208, and is coupled to receive results to be written to the register file207from the execution core208. The execution core208is coupled to the interface unit211, which is further coupled to an external interface of the processor200.

Fetch control unit201may be configured to generate fetch PCs for instruction cache202. In some embodiments, fetch control unit201may include one or more types of branch predictors212. For example, fetch control unit202may include indirect branch target predictors configured to predict the target address for indirect branch instructions, conditional branch predictors configured to predict the outcome of conditional branches, and/or any other suitable type of branch predictor. During operation, fetch control unit201may generate a fetch PC based on the output of a selected branch predictor. If the prediction later turns out to be incorrect, fetch control unit201may be redirected to fetch from a different address. When generating a fetch PC, in the absence of a nonsequential branch target (i.e., a branch or other redirection to a nonsequential address, whether speculative or non-speculative), fetch control unit201may generate a fetch PC as a sequential function of a current PC value. For example, depending on how many bytes are fetched from instruction cache202at a given time, fetch control unit201may generate a sequential fetch PC by adding a known offset to a current PC value.

The instruction cache202may be a cache memory for storing instructions to be executed by the processor200. The instruction cache202may have any capacity and construction (e.g. direct mapped, set associative, fully associative, etc.). The instruction cache202may have any cache line size. For example, 64 byte cache lines may be implemented in an embodiment. Other embodiments may use larger or smaller cache line sizes. In response to a given PC from the fetch control unit201, the instruction cache202may output up to a maximum number of instructions. It is contemplated that processor200may implement any suitable instruction set architecture (ISA), such as, e.g., the ARM™, PowerPC™, or x86 ISAs, or combinations thereof.

In some embodiments, processor200may implement an address translation scheme in which one or more virtual address spaces are made visible to executing software. Memory accesses within the virtual address space are translated to a physical address space corresponding to the actual physical memory available to the system, for example using a set of page tables, segments, or other virtual memory translation schemes. In embodiments that employ address translation, the instruction cache202may be partially or completely addressed using physical address bits rather than virtual address bits. For example, instruction cache202may use virtual address bits for cache indexing and physical address bits for cache tags.

In order to avoid the cost of performing a full memory translation when performing a cache access, processor200may store a set of recent and/or frequently-used virtual-to-physical address translations in a translation lookaside buffer (TLB), such as Instruction TLB (ITLB)203. During operation, ITLB203(which may be implemented as a cache, as a content addressable memory (CAM), or using any other suitable circuit structure) may receive virtual address information and determine whether a valid translation is present. If so, ITLB203may provide the corresponding physical address bits to instruction cache202. If not, ITLB203may cause the translation to be determined, for example by raising a virtual memory exception.

The decode unit204may generally be configured to decode the instructions into instruction operations (ops). Generally, an instruction operation may be an operation that the hardware included in the execution core208is capable of executing. Each instruction may translate to one or more instruction operations which, when executed, result in the operation(s) defined for that instruction being performed according to the instruction set architecture implemented by the processor200. In some embodiments, each instruction may decode into a single instruction operation. The decode unit204may be configured to identify the type of instruction, source operands, etc., and the decoded instruction operation may include the instruction along with some of the decode information. In other embodiments in which each instruction translates to a single op, each op may simply be the corresponding instruction or a portion thereof (e.g. the opcode field or fields of the instruction). In some embodiments in which there is a one-to-one correspondence between instructions and ops, the decode unit204and mapper205may be combined and/or the decode and mapping operations may occur in one clock cycle. In other embodiments, some instructions may decode into multiple instruction operations. In some embodiments, the decode unit16may include any combination of circuitry and/or microcoding in order to generate ops for instructions. For example, relatively simple op generations (e.g. one or two ops per instruction) may be handled in hardware while more extensive op generations (e.g. more than three ops for an instruction) may be handled in microcode.

Ops generated by the decode unit204may be provided to the mapper205. The mapper205may implement register renaming to map source register addresses from the ops to the source operand numbers (SO#s) identifying the renamed source registers. Additionally, the mapper205may be configured to assign a scheduler entry to store each op, identified by the SCH#. In an embodiment, the SCH# may also be configured to identify the rename register assigned to the destination of the op. In other embodiments, the mapper205may be configured to assign a separate destination register number. Additionally, the mapper205may be configured to generate dependency vectors for the op. The dependency vectors may identify the ops on which a given op is dependent. In an embodiment, dependencies are indicated by the SCH# of the corresponding ops, and the dependency vector bit positions may correspond to SCH#s. In other embodiments, dependencies may be recorded based on register numbers and the dependency vector bit positions may correspond to the register numbers.

The mapper205may provide the ops, along with SCH#, SO#s, PCs, and dependency vectors for each op to the scheduler206. The scheduler206may be configured to store the ops in the scheduler entries identified by the respective SCH#s, along with the SO#s and PCs. The scheduler may be configured to store the dependency vectors in dependency arrays that evaluate which ops are eligible for scheduling. The scheduler206may be configured to schedule the ops for execution in the execution core208. When an op is scheduled, the scheduler206may be configured to read its source operands from the register file207and the source operands may be provided to the execution core208. The execution core208may be configured to return the results of ops that update registers to the register file207. In some cases, the execution core208may forward a result that is to be written to the register file207in place of the value read from the register file207(e.g. in the case of back to back scheduling of dependent ops).

The execution core208may also be configured to detect various events during execution of ops that may be reported to the scheduler. Branch ops may be mispredicted, and some load/store ops may be replayed (e.g. for address-based conflicts of data being written/read). Various exceptions may be detected (e.g. protection exceptions for memory accesses or for privileged instructions being executed in non-privileged mode, exceptions for no address translation, etc.). The exceptions may cause a corresponding exception handling routine to be executed.

The execution core208may be configured to execute predicted branch ops, and may receive the predicted target address that was originally provided to the fetch control unit201. The execution core208may be configured to calculate the target address from the operands of the branch op, and to compare the calculated target address to the predicted target address to detect correct prediction or misprediction. The execution core208may also evaluate any other prediction made with respect to the branch op, such as a prediction of the branch op's direction. If a misprediction is detected, execution core208may signal that fetch control unit201should be redirected to the correct fetch target. Other units, such as the scheduler206, the mapper205, and the decode unit204may flush pending ops/instructions from the speculative instruction stream that are subsequent to or dependent upon the mispredicted branch.

Execution unit208may also be configured to execute and provide results for certain types of fetched instructions. In one embodiment, execution unit208may be configured to execute certain integer-type instructions defined in the implemented ISA, such as arithmetic, logical, and shift instructions. It is noted that in the illustrated embodiment instructions destined for floating point/graphics unit (FGU)212pass through execution unit208. However, in alternative embodiments it is contemplated that such instructions may be issued directly to their respective units without passing through execution unit208.

The execution core may include a data cache209, which may be a cache memory for storing data to be processed by the processor200. Like the instruction cache202, the data cache209may have any suitable capacity, construction, or line size (e.g. direct mapped, set associative, fully associative, etc.). Moreover, the data cache209may differ from the instruction cache202in any of these details. As with instruction cache202, in some embodiments, data cache209may be partially or entirely addressed using physical address bits. Correspondingly, a data TLB (DTLB)210may be provided to cache virtual-to-physical address translations for use in accessing the data cache209in a manner similar to that described above with respect to ITLB203. It is noted that although ITLB203and DTLB210may perform similar functions, in various embodiments they may be implemented differently. For example, they may store different numbers of translations and/or different translation information.

Floating point unit (FPU)212may be configured to execute and provide results for certain floating-point and graphics-oriented instructions defined in the implemented ISA. For example, in one embodiment FGU212may implement single- and double-precision floating-point arithmetic instructions compliant with a version of the Institute of Electrical and Electronics Engineers (IEEE) 754 Standard for Binary Floating-Point Arithmetic (more simply referred to as the IEEE 754 standard), such as add, subtract, multiply, divide, and certain transcendental functions. Depending on the implementation of FGU212, may include multiplier unit213. As described below in more detail, multiplier unit213may be employed in an iterative fashion to approximate values for multiple arithmetic operations, such as, e.g., division and square root, in parallel.

The register file207may generally include any set of registers usable to store operands and results of ops executed in the processor200. In some embodiments, the register file207may include a set of physical registers and the mapper205may be configured to map the logical registers to the physical registers. The logical registers may include both architected registers specified by the instruction set architecture implemented by the processor200and temporary registers that may be used as destinations of ops for temporary results (and sources of subsequent ops as well). In other embodiments, the register file207may include an architected register set containing the committed state of the logical registers and a speculative register set containing speculative register state.

The interface unit211may generally include the circuitry for interfacing the processor200to other devices on the external interface. The external interface may include any type of interconnect (e.g. bus, packet, etc.). The external interface may be an on-chip interconnect, if the processor200is integrated with one or more other components (e.g. a system on a chip configuration). The external interface may be on off-chip interconnect to external circuitry, if the processor200is not integrated with other components. In various embodiments, the processor200may implement any instruction set architecture.

It is noted that the embodiment of a processing device illustrated inFIG. 2is merely an example. In other embodiments, different functional block or configurations of functional blocks are possible and contemplated.

Computing systems, such as, e.g., DCU100as illustrated inFIG. 1, may be limited in area due to manufacturing cost or form factor considerations. To keep within area targets, circuit and logic designers may elect to implement certain functions as a set of software instructions, thereby trading processing efficiency for area. In other cases, some functions may re-use other hardware in a different fashion to perform the desired function. Examples of such re-use include division and square root operations that make use of multiplier unit hardware to implement the desired operation without creating dedicated hardware. In such cases, additional logic circuits may be added to a multiplier unit to allow one of various division or square root algorithms to be performed, such as, a Goldschmidt algorithm, for example.

As shown in equation 1, a quotient Q may be written as a product of a dividend a and a reciprocal of a divisor b. In the case of the Goldschmidt algorithm, an initial approximation of the reciprocal of the divisor is refined through multiple iterations, until a desired level of accuracy is achieved. In various embodiments, a final value of the divisor may be rounded. The final quotient may then be realized through a multiplication of the dividend by the estimated divisor.
Q=a/b=a(1/b)  (1)

As shown in equation 2, during each iteration, a next value of the numerator, Ni+1, is dependent upon a multiplication of a current value of the numerator, Ni, a current scaling value Ri, and a next value of the denominator, Di+1, is dependent upon a multiplication of a current value of the denominator, Di, and Ri. The next value of the scaling factor, Ri+1, is derived from the current value of the scaling factor. By employing independent multiplications, the multiplication may, in various embodiments be pipelined through a multiplier, allowing for higher throughput.
Ni+1=NiRi
Di+1=DiRi
Ri+1=2−Ri(2)

It is noted that although the above discussion is generally directed towards division, in other embodiments, similar techniques may be applied to other arithmetic operations. For example, square root may be performed by using the function 1/√{square root over (x)} instead of merely a reciprocal of a divisor as is the case with a division operation.

Turning toFIG. 3, an embodiment of multiplier unit is illustrated. In the illustrated embodiment, multiplier unit300includes bypass stage302, mul1 stage303, mul2 stage303, add stage304, and circuitry305. Multiplier unit300may, in some embodiments, be used to implement one of various algorithms, such as Newton-Raphson or Goldschmidt, for example. In various embodiments, multiplier unit300may be configured to produce an approximation of a quotient of two floating point numbers, a quotient of two integer numbers, or an approximation of a square root of a floating point number.

Each of bypass stage302, mul1 stage303, mul2 stage304, and add stage305may be configured to multiply at least two operands, and may be designed in accordance with one of various multiplier architectures. For example, any of the aforementioned stages may employ Wallace tree, or other suitable multiplier algorithm. In various embodiments, multiplier may be configured to allow operands of any suitable length, such as, e.g., integer or floating point operands.

During operation when multiplier unit300is used to perform a first iterative operation such as, e.g., floating point division, integer division, or square root, input operands307are received by bypass stage302, which, in turn, performs a first calculation of the iterative operation during a first processing cycle. For example, bypass stage302may calculate a value for a denominator according to equation 2. During a second processing cycle, bypass stage302may pass its results to mul1 stage303and calculate a value for a numerator according to equation 2. Mull stage303may calculate an updated value for the denominator during the second processing cycle. The process may continue, as described below in more detail in regard toFIG. 4, in a pipelined fashion, over a suitable number of processing cycles, until final values for numerator, denominator, and remainder are calculated. A final answer may then be sent to output308.

While the first iterative operation is being executed, circuitry306may schedule a second iterative operation for execution. In various embodiments, circuitry306may schedule a particular calculation of the second iterative operation to be executed on an unused stage. For example, after bypass stage302completed the calculation of the numerator of the first iterative operation in cycle2, it may not be used for two subsequent processing cycles. Circuitry306may schedule the calculation of an initial value of a numerator of the second iterative operation for execution on bypass stage302during a third processing cycle. Other calculations included in the second iterative operation may be schedule for execution in a similar fashion.

When scheduling the execution of the calculations included in the second iterative operation, circuitry306may use patterns of usage of the various stages by each of the first and second iterative operations do determine when a particular stage is unused during a given processing cycle. In some embodiments, circuitry306may employ predetermined usage patterns which may be selected dependent upon the type of operation, such as, floating point division, for example.

In some embodiments, circuitry306may determine cycles in which there are unused stages while two iterative operations are being performed. In such cases, circuitry306may schedule single cycle operations, such as, e.g., integer multiplication, for execution on the unused stages during a given processing cycle. By allowing a single cycle operation to be included with the two iterative operations, multiplier300may, in various embodiments, improving utilization and reduce latency.

In situations where a calculation included in the second iterative operation is schedule for execution on a stage at the same time a calculation from the first iterative operation is schedule, circuitry306may stall execution of the calculation from the second iterative operation until the calculation from the first iterative operation has completed.

It is noted that the embodiment illustrated inFIG. 3is merely an example. In other embodiments, different numbers of stages and different configurations of functional stages are possible and contemplated.

Turning toFIG. 4, a chart depicting multiplier stage usage during a floating point divide, integer divide, or square root operation is illustrated. In the present illustration, the usage pattern of a floating point divide, integer divide, or square root operation using the Goldschmidt algorithm is depicted. In the chart depicted inFIG. 4, the variables a and b represent floating point numbers. Additionally, x0 represents an initial approximation of 1/b or 1/sqrt(b), q0 represents the quotient of a and b, and r0, r1, and r2, represent remainders from a given iteration. In the first processing cycle, a bypass stage, such as, e.g., bypass stage302of multiplier300as illustrated inFIG. 3, begins the calculation of an initial value for a denominator in accordance with the Goldschmidt algorithm. The other stages, mul1, mul2, and add, are idle.

In the second processing cycle, the mul1 stage receives results from the bypass stage, and continues the calculation of the initial value of the denominator. The bypass stage then begins the calculation of an initial value of a numerator in accordance with the Goldschmidt algorithm. The stages mul2 and add remain idle during the second processing cycle.

Moving to the third processing cycle, the bypass stage becomes idle, while the mul1 stage continues the calculation of the initial value of the numerator. The mul2 stage becomes active and continues the calculation of the initial value of the denominator, while the add stage remains idle. In the fourth processing cycle, both the bypass and mul1 stages are idle. The mul2 stage continues the calculation of the initial value of the numerator value, while the add stage becomes active and completes the calculation of the initial value of the denominator.

In the fifth processing cycle, the bypass stage can begin the calculation of a second value of the denominator since the add stage completed the calculation of the initial value of the denominator. The mul1 stage and the mul2 stage are idle, while the add stage completes the calculation of the initial value of the numerator.

In a similar fashion, each subsequent value of both the denominator and numerator are calculated by the various stages in a pipelined fashion. As final results for a given iteration become available, a new iteration may begin in the bypass stage. It this present example, four iterations are performed, each generating a new result for the numerator and denominator. The values from the final iteration may then be used to calculate values for the desired quotient and remainder.

It is noted that the chart depicted inFIG. 4is merely an example. In other embodiments, the use of different algorithms may result in different calculations being performed in different cycles and on different stages.

As evident in the chart ofFIG. 4, not all stages within a multiplier unit are in use each cycle during an iterative operation, such as, a floating point divide operation, for example. To take advantage of the unused stages, new operations may be started when the bypass stage is idle. Turning toFIG. 5, a chart illustrating bypass stage utilization during a floating point divide operation is depicted.

In the first and second processing cycles, the bypass stage is active. The values to start the next iteration of the calculation for the denominator are not available unit the fifth cycles. As a result, the next iteration of calculation of the denominator and numerator values cannot be started until the fifth processing cycle, leaving the bypass stage idle for processing cycles three and four. In a similar fashion, the bypass stage is idle for processing cycles 7, 8, 11, 12, 13, 15, 16, 17, and 19-24, resulting the multiplier being utilized 36% of the time.

It is noted that bypass stage utilization depicted inFIG. 5is merely an example. In other embodiments, different number of pipe stages within a multiplier unit may result in different bypass stage utilization.

The unused stages may be used, in various embodiments, to perform a second iterative operation. A chart depicting the scheduling of two iterative operations in a single pipelined multiplier unit is illustrated inFIG. 6. As with the chart depicted inFIG. 5, a first iterative operation is started in processing cycle one, which results in the bypass stage being active for processing cycles one and two.

In processing cycle3, however, instead of having the bypass stage be idle while it waits for results from the first iteration of the first iterative operation, a second iterative operation is started. The bypass stage is not active beginning the calculation for initial values for the denominator and numerator for the second iterative operation in processing cycles 3 and 4.

In processing cycles 5 and 6, the bypass stage begins the calculation of values for the next iteration of the first operation. At processing cycle7, the results from the first iteration of the second operation are available for use in starting the second iteration of the second operation. The bypass stage may then spend processing cycles 7 and 8 beginning the calculation of values for the denominator and numerator for the second iteration of the second operation. In a similar fashion, the two operations continue to make sure of the bypass stage throughout the rest of the processing cycles. It is noted that the two operations are both being executed at the full speed of the processing, and that, once started, the control for the second operation is identical to the control for the first operation.

With two iterative operations running within the multiplier unit, 33% of the cycles are still available to perform work. In some embodiments, a third iterative operation may be scheduled to take advantage remaining free processing cycles. Alternatively or additionally, the free processing cycles may be used to execute single cycle instructions, further increasing the utilization of the multiplier unit.

It is noted that the scheduling depicted in the chart ofFIG. 6is merely an example. In other embodiments, the second iterative operation may be initiated at any suitable cycle where the bypass stage is unused and does not result in conflicts with multiple calculations schedule for a given stage at a same time.

Turning toFIG. 7a flow diagram illustrating an embodiment of concurrently performing two operations using a multiplier operation is depicted. The method begins in block701. A multiplier unit, such as, e.g., multiplier unit300as illustrated inFIG. 3may then receive a first operation (block702). In various embodiments, the first operation may be a single or double floating point precision division operation, an integer division operation, or a single or double precision floating point square root operation. The multiplier unit may be configured to implement an iterative algorithm, such as, e.g., the Goldschmidt operation, to perform the division of square root operation using a series of multiplication operations.

The execution of the first operation may then begin (block703). In various embodiments, control circuitry, such as, e.g., control circuitry303as depicted inFIG. 3, may schedule different iterations of the iterative operation on different stages within the multiplier unit. Each iteration may be executed during a different cycle, allowing pipeline operation of the multiplier unit.

A second operation may then be received (block704). In various embodiments, the second operation may also be a single or double precision floating point division operation, an integer division operation, or a single or double precision floating point square root operation. It is noted that although the flow diagram depicts the second operation as being received after the start of execution of the first operation, it other embodiments, the second operation may be received concurrently with the first operations, or at any other suitable time. The operation may then depend on if the second operation may be scheduled concurrently with the first operation (block705).

If the second operation may be scheduled concurrently, then the control circuitry may schedule the second operation to start at a determined cycle (block707). In some embodiments, control circuitry may determine a number of cycles to wait after the start of the first operation to allow iterations of the second operation to be performed on stages of the multiplier unit that are not currently being used for the first operation. Once the second operation has been started, the method may conclude in block708.

Alternatively, if the second operation cannot be scheduled concurrently, one cycle of the first operation may be performed (block706). Once the cycle has been completed, the method may then proceed from block705as described above.

It is noted that the embodiment illustrated is merely an example. In other embodiments, different operations and different orders of operations may be employed.

A flow diagram depicting an embodiment of a method for determining if a second operation may be executed concurrently with a first operation in a multiplier unit is illustrated inFIG. 8. In various embodiments, the method illustrated inFIG. 8may correspond to block705of the flow diagram depicted inFIG. 7. The method begins in block801.

Remaining cycles that have that include multiplier stages unused by the first operation may then be determined (block802). As illustrated inFIG. 5, not all of the stages of a multiplier will be active for a single or double precision floating point division, integer division, or single or double precision square root operation. In such cases, cycles that have an unused multiplier stage will be identified. A pattern of multiplier stage usage per cycle may then be determined for the second operation (block803). In some embodiments, the second operation may a single or double precision floating point division operation, an integer division operation, or a single or double precision floating point square root operation. In other embodiments, the second operation may be any suitable operation. The method may then depend on if the usage pattern of the second operation matches the pattern of remaining unused stages in the multiplier while executing the first operation (block804).

If the usage pattern of the second operation does not match the pattern of unused stages, then the method concludes in block806. In various embodiments, if an iteration of the second operation would be scheduled to be executed by a given multiplier stage that is already schedule for executing an iteration of the first operation, the second operation may stall for a processing cycle and, as described above in regard toFIG. 7, circuitry may re-check for conflict after the processing cycle has completed.

If, however, the usage pattern of the second operation matches the pattern of unused stages, then a starting cycle for the second operation may be determined (block805). In some embodiments, the second operation may be started at the first available free processing cycle, while in other embodiments, any suitable free processing cycle may be selected to start the second operation.

It is noted that the method depicted in the flow diagram illustrated inFIG. 8is merely an example. In other embodiments, different operations, and different orders of operations may be employed.