5
$\begingroup$

I am currently writing a program where a lot of adding 0 to numbers and multiplying by 1 and 0 occurs and it got me to wondering if the CPU 'shortcuts' (drops), these operations. I'm a CS student and this hasn't been brought up ever.

Can a CPU do this? What are the trade-offs in designing a CPU that detects +1, *1 and *0 and executes them faster?

$\endgroup$

migrated from electronics.stackexchange.com Feb 26 '17 at 22:44

This question came from our site for electronics and electrical engineering professionals, students, and enthusiasts.

  • 8
    $\begingroup$ Generally if these are constants, a halfway decent compiler will optimize them out, generating non-wasteful code. Most CPUs do not alter execution time depending on operands within a given width/type category, but all sorts of hardware runtime optimizations have been proposed on paper, and a smaller set implemented in silicon. $\endgroup$ – Chris Stratton Feb 24 '17 at 22:29
  • $\begingroup$ For floating point numbers, multiplying by zero is a special case (as it cannot be "renormalised") $\endgroup$ – TEMLIB Feb 24 '17 at 22:33
  • 1
    $\begingroup$ This is too broad, as you could definitively find one that does, and others that don't. What about CPUs without dedicated multipliers? So these count as shortcutting if the software multiplication stops if all set bits in either operand have been processed? $\endgroup$ – Marcus Müller Feb 24 '17 at 22:40
  • 1
    $\begingroup$ In many cases, the logic to detect and "shortcut" such cases would actually be slower than just doing the operation. As Chris said, it is the compiler's responsibility to minimize instructions, but for non-constant operands it may not be available. $\endgroup$ – uint128_t Feb 24 '17 at 23:03
  • 1
    $\begingroup$ Could you specify the type of variables (int, long, float etc)? I assume that in your case the compiler cannot determine that at compile time, right? $\endgroup$ – Evil Feb 26 '17 at 22:55
3
$\begingroup$

Yes, there are processors which detect some kind of do-nothing operations, handle them specially so that they take less time than what they would take if they were handled naïvely. In some cases, there are even recommended instructions to use for NOP (NOP are sometimes useful to align the code with a memory boundary, having NOP of various lengths available help the relieve the decoding part), the wikipedia page for NOP has a list which gives the normal meaning for some of them.

But

  • what you think as a do-nothing operation may not be one if you take into account things like resetting flags or the side effects of memory accesses -- and a processor should behave correctly in such matter;

  • I'd not rely on this as an optimization; more as an encoding trick or as a way to reduce the op-code pressure; they are working when the operands are statically known to have no effect and in such cases, the code writer -- human or compiler -- should avoid the operation if possible;

  • detecting dynamically that the value has no effect is probably more costly than what would be gained by doing so. That said, some relatively simple processors have operations which take a time which depend on the arguments (for arithmetic operations, don't think I've seen this for something else than integer multiplication and division, or for floating point operations)

$\endgroup$
3
$\begingroup$

Doing this in the processor is less trivial than you think - for example, if you want to handle multiplication by 1 as a special case, you'd want to handle both x * 1 and 1 * x, which means checking two numbers, and then you still have to produce the right result, taking either the first or the second operand. x * 0 is harder; again you have to check two numbers for being zero, plus you need to handle that inf * 0 = NaN and NaN * 0 = NaN, and that a negative number times 0 is -0, not 0. That's an awful lot of checking for a rare case.

There's the problem that it takes time to decide that there's no special case. It will take time to stop the processor from proceeding with the multiplication. This may be difficult if a multiplication is designed to take all of the available time.

Now let's say a multiplication takes 3 cycles usually and you could cut it short to 1 cycle. This means you now need the ability that data goes through the processor on two different paths, one single cycle and one three cycle path.

Where it is done is during division, which is usually implemented in a slow and iterative way, for example producing two bits per cycle. Since this is slow and iterative anyway, it is easier to cut the calculation short when the dividend becomes zero, for example dividing 255 / 5 needs only six bits of the result. That can and does lead to a shorter execution time on modern processors.

$\endgroup$
2
$\begingroup$

These optimizations occur in compilation time (statically) rather than in execution time (dynamically). The code generation part of the compiler will convert addition by the constant 1 to an increment operation, if such an operation is available and faster. Multiplication by 1 will be cut out at an even earlier stage, as is multiplication by 0, which will be replaced by the constant 0, and further optimized. These simplifications are similar to constant folding, in which constant arithmetic expressions are evaluated in compile time.

Another question you could ask is whether addition or multiplication of two non-constant numbers is faster if some of the operands are trivial. I doubt that it does for modern CPUs, but in general it could depend on the processor, especially if a certain expensive operation like division is performed sequentially.

$\endgroup$
  • 1
    $\begingroup$ Let's not discount JITs, which fall somewhere in between. $\endgroup$ – Raphael Mar 1 '17 at 19:21
1
$\begingroup$

In general, processors do not detect and special case identity elements (zero addends, zero shifts, one multiplicants, one divisors) or zero multiplicands.

Addition is typically extremely inexpensive; a processor complex enough to handle the identity special case would typically have enough execution width that skipping an occasional addition would not improve performance much. The latency benefit is also low (e.g., zero cycles versus one cycle). The frequency with which such occurs would also be low, so the net benefit would be small at best.

With the noteworthy exception of zeroing idioms, a zero result would be detected near the end of the execution cycle. At that point, the decision to execute the dependent operation has already been made and, in a traditional out-of-order design, the expectation of a result of the dependent operation in one cycle has been used by the scheduler to schedule dependent operations. Dynamically converting the addition to a copy at execution might save a little energy, but detecting the special case of an addition and making the decision for many operations (the common case) would probably use more energy overall.

Zeroing idioms are recognized in decode and handled in register renaming. This removes most of the added cost of zero detection and provides the information early enough that instruction scheduling can be adjusted. As mentioned in this Real World Technologies forum post, Intel does exploit this special case to provide lower latency for some indexed addressing cases where the index has been zeroed using a zeroing idiom.

Because no-page-crossing speculation (and its misprediction recovery mechanism) is broadly useful, adding this special case may have been very inexpensive. Even though such zero-indexed loads would be somewhat rare (e.g., the first load in a loop), the extra cost would be small and load latency is often critical. (While a compiler could convert the first iteration of such loops into direct base + offset addressing, the code bloat effect is obvious and the optimization rather microarchitecture specific. Similarly, function calls with explicit zero operands could be handled specially by the compiler with longer compile times and possible code bloat.)

Special casing addition by an explicitly zeroed operand could be handled in rename, but as noted above the benefit would be modest because additions are cheap in latency and issue width. (Multiplication by an explicitly zeroed operand would be similar, though the benefit would be greater.)

Multiplication is a different; multiplication generally has high enough latency that early output of the result would be easier to implement in terms of scheduling. With a fully pipelined multiplier, throughput would not be improved with early output, but latency would be improved. (In theory, throughput could be improved in a fully pipelined multiplier if two short multiplications were executed in parallel, a kind of dynamic SIMD. Since such would also involve more operands, the extra complexity would not be likely to be justified.)

Motorola's (now Freescale) PowerPC 750 had an unpipelined multiplier and supported early out when a specific operand was small (not just one or zero). This improved both latency and throughput.

While some ISAs have detection of zero results at no additional cost (setting flags on many operations) and this would also make detection of small positivie numbers easy (the most significant bits being zero is part of the specific zero detection), if the potentially special value has a short life (the common case), the opportunity for exploiting such special cases would be small.

If the special value is recognized earlier than other operands are available (or a structural hazard delays start of execution), this extra delay could in theory be exploited to strength reduce the operation before it starts execution. When the special value is recognized and the scheduler has decided not to execute the operation (data or structural hazard preventing execution or even energy management throttling execution), the operation could be strength reduced before the next scheduling opportunity. This does not seem likely to be low hanging (nor high value) fruit.

Other tricks might be used to hide the scheduling loop latency to facilitate such dynamic strength reductions, but professional hardware designers have not yet chosen to perform such strength reductions so the cost and benefit tradeoffs are presumably not favorable (under expected conditions).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.