8

In the BESM-6 technical manuals — for example, in the ALU description, page 4 — there is a table specifying min/max/average instruction latencies in clock cycles (the last 3 columns; the clock rate was 9 MHz): Latencies of arithmetic operations

The rows are:

    1. Addition, {ACC, Y} := ACC + OP
    1. Subtraction, {ACC, Y} := ACC - OP
    1. Reverse subtraction, {ACC, Y} := OP - ACC
    1. Subtraction of absolute values, {ACC, Y} := abs(ACC) - abs(OP)
    1. Negation, ACC := OP < 0 ? -ACC : ACC
    1. Division, ACC := ACC / OP, requires OP to be normalized, otherwise traps.
    1. Multiplication, {ACC, Y} := ACC * OP

The ACCumulator and the OPerand are in the "simplistic" floating point format: 7 base-2 exponent bits, a sign bit, 40 mantissa bits in 2's complement format. All arithmetic instruction except division and negation produce a result with 80 bits of mantissa: the upper bits in the accumulator, the lower bits in the separate Y register.

The question is, how come the additive operations can take up to 280 clock ticks? Unlike multiplication and division, addition requires equalizing the exponents by shifting the mantissa of one of the operands to the right, 1 bit per cycle; if there was no circuit terminating the equalization early as soon as all significant mantissa bits of the operand with the smaller exponent were shifted away, the process might take up to 127 cycles; but then the actual addition, performed as parallel bitwise 3-to-2 reductions, until no carries are left to reduce, should not have anything left to do. Then, normalization to the left might take up to 128 cycles, for at most 256 plus a handful, when zero with the lowest exponent is added to zero with the highest exponent. Still, quite far from 280.

My experiments implementing the algorithm deduced from the documentation show the following statistics, out of 100 million trials each:

Integer addition (equal exponents in the operands, final normalization to the left is disabled):

min = 5, max = 31, avg = 9.66, median = 9

Obviously, the theoretical maximum would be a shade greater than 40, when adding -1 and 1.

Completely random floating point addition (arbitrary exponents, arbitrary potentially denormalized mantissas):

min = 5, max = 169, avg = 51.30, median = 46

Requiring mantissas of the operands to be normalized:

min = 5, max = 151, avg = 50.28, median = 45

Further clamping operands to be within approx. 6 decimal orders of magnitude (absolute difference of exponents no more than 21) of each other, quasi-normally distributed:

min = 5, max = 63, avg = 13.66, median = 13

Thus, the claim of the average (or, more likely, median) latency being 11 cycles, given an equal mix of integer and floating point additions, is substantiated, but the maximum of 280 cycles is a mystery.

  • 2
    @Wilson it means 11. Old typewriters didn't allways have a 1 key, so capital i (or lowercase L) were used instead. – UncleBod Jan 9 at 9:47
  • 3
    maybe the extra cycles are to normalize the result, which requires shifting in the opposite direction. – Ken Gober Jan 9 at 15:04
  • 1
    @Raffzahn No, that's the time the instruction takes just in the ALU, after all fetches. – Leo B. Jan 9 at 15:57
  • 1
    @dirkt shifting takes one cycle per bit, that is known. – Leo B. Jan 9 at 16:01
  • 2
    Further below, the document says that exponent addition/subtraction/etc takes a minimum of 3, an average of 5, and a maximum of 133(!) cycles. Do you know what it's doing in the maximum case there? Handling traps? I can't imagine it's doing the exponent addition for so many cycles, or else the average would've been much larger. Although thinking about, it could be doing optional normalization there, too. In which case, this doesn't help. (But I'm keeping the comment in case it helps after all) – secondperson Jan 10 at 1:26
4

Compiling details pointed to in the comments by @secondperson and my own findings:

It appears that the documentation is inaccurate. There are apparent typos and/or transcription errors. For example, the max. latency of the negation operation cannot be 25, as the operation involves negating a 40-bit 2's-complement value, which requires up to 40 clock cycles for carry propagation, and, as well as in all other arithmetic operations, there is an optional normalization of the result, which could take up to 127 clock cycles.

The greatest latency of approx. 259, is achieved by adding two numbers with zero mantissas, one with the exponent field set to 0177 (corresponding to 263), the other with the exponent field set to zero (corresponding to 2-64). Equalizing the exponents and attempting normalization take ~127 clock cycles each.

It is notable that in all cases of non-trivial operands, requiring actual multi-cycle carry propagation, the latency of the addition instruction as a whole will be substantially less than 260.

Thus it is likely that the max. latency intended to be printed was 260, which is close enough graphically to 280, and the difference was inconsequential for no one to notice. A more glaring case of the max. latency of the negation instruction was not taken care about either.

A curious case had been observed: adding 0 with the max. exponent 63 and -1 with the min. exponent -64 (-1*2-64 == -5.42⏨-20) takes 211 cycles, and produces, after replicating the sign bit to all 80 mantissa bits during the 127 steps of exponent equalization and subsequent normalization of these 80 bits, the value of -1*263-80 == -7.63⏨-6.

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.