NetNews Usenet Archive 1992 #27/NN_1992_27.iso/spool/comp/arch/10816

Internet Message Format | 1992-11-17 | 7.8 KB

Xref: sparky comp.arch:10816 comp.lang.misc:3729
Newsgroups: comp.arch,comp.lang.misc
Path: sparky!uunet!zaphod.mps.ohio-state.edu!cs.utexas.edu!usc!sol.ctr.columbia.edu!ira.uka.de!math.fu-berlin.de!unidui!rrz.uni-koeln.de!Germany.EU.net!Urmel.Informatik.RWTH-Aachen.DE!martin
From: [e-mail] (  Martin Schoenert)
Subject: Re: how to advocate new software/hardware features (Re: Hardware Support for Numeric Algorithms)
Message-ID: <martin.721995695@bert>
Sender: [e-mail] (Newsfiles Owner)
Nntp-Posting-Host: bert.math.rwth-aachen.de
Organization: Rechnerbetrieb Informatik  /  RWTH Aachen
References: <[e-mail]> <[e-mail]> <[e-mail]> <[e-mail]>
Date: 17 Nov 92 10:21:35 GMT
Lines: 168

Bob Silverman wrote in his article:

   Quite a few modern microprocessors have hardware to do 32 x 32 bit
   multiplies and 64 bit / 32 bit divides.  I know of no HLL that will
   allow me to write code to access these instructions. For example,
   suppose I want to compute A*B/C exactly, where A,B, C are 32 bit
   ints and C > A and C > B.  How do I do this in a HLL ?

Alan Watson responded in his article:

    Not that I wish to defend C, but a good compiler should be able to
    eliminate unnecessary casts and use mixed 32/64-bit arithmetic in the
    following expressions:

    long l, n, m;
    int i, j, k;

    l = (long) i * (long) j;    /* emit 32x32 -> 64 */
    n = m / i;            /* emit 64/32 -> 64 */

    by use of the `as if' rule.  Perhaps there is a subtlety I have
    missed.  I agree that the casts are a nuisance, and one can argue that
    C's default promotions are perhaps not the best choice, but in these
    cases the language does provide the degree of control that Silverman
    requires.

This of course assumes that 'long' is 64  bits  wide.  On most commercial
systems this just isn't  the case.  If  'sizeof(long) = sizeof(int)  = 4'
you only get the lower  half of the product this way (and the upper  half
is much more difficult to get).

Besides,  I  have collected some  information  about  the  multiplication
instructions of modern micro processors.  From this it appears to me that
on those systems where 'sizeof(long)'  might be 8 (64 bits) you also have
a 64x64 -> 128 instruction (or short sequence of instructions).  And then
you loose  again because you  cannot get at the upper half  of such a 128
bit product.

Thomas Breuel responded in his article:

    Well, then you simply haven't looked very far. Many implementations
    of HLL let you access those instructions in a variety of ways.

    (1) Implementations like GNU C/C++ and implementations of CommonLisp
        and Scheme often have very sophisticated and efficient assembly
        language interfaces. Of course, those interfaces are not portable,
        but neither is the assembly language (I myself would like to see
        vendors standardize on the GNU C/C++ assembly language interface).

Yes  that is  true, and I know of  at  least one large integer arithmetic
which  uses  GNU C to  get at the  powerful  multiplication instructions.
However, the assembler  interface  is  not  part of the  definition of  C
(neither ANSI  or K&R say something  about  it).  So it is true that  the
*language*   does  allow  you   to   do   this   (even   though   special
*implementations* might).

Thomas Breuel continues:

    (3) Many programming languages let you declare 32 and 64bit
        integers explicitly and good compilers will select the right
        instruction to go with the types (Ada and CommonLisp are
        among those languages).

        Even the C language has provisions for just the case that you are
        concerned with in the case of 16bit integers, 32bit longs:

        int a = ...;
            int b = ...;
            int c = ...;
        long product = a*b;
        int result = product/c;

        In fact, on some machines, int is 32bit and long is 64bit,
        so this code will do what you want.

Ahh, but the 16x16->32 bit multiplication is not as good.  Suppose that I
want to multiply two large integers, each 32 bytes long.  Using 16x16->32
bit multiplication I  need 256 such  instructions.   Using 32x32->64  bit
multiplication I  only need 64 such instructions.  Since on  most  modern
processors both  instructions take  about  the same  amount  of  time the
latter is about 4 times as fast.  (If you have an application  that  runs
for MIPS years, a factor of 4 is quite a big deal ;-)

Thomas Breuel continues:

        Furthermore, C is being extended to allow access to 64bit types,
        so that you can write:

        int a = ...;
        int b = ...;
        long long product = a*b;
        int result = product/c;

This  may  be  so,  but it  isn't  really  relevant.   Bob  talked  about
*languages*,  you  talk about  *implementation* or  possible *extension*.
This is not the same thing.

Herman Rubin writes in his article:

   In addition, this has architectural implications.  Hardware
   designers seem to avoid asking users what instructions they want in
   hardware, but look at the current HLLs.  Having nxn ->2n [32bit x
   32bit multiplication yielding a 64bit result] in the language, and
   2n/n in the language, is far more likely to keep it in the
   architecture than Bob using it in his programs.

Well  I  don't  know.   From  my  information  about  the  multiplication
instructions it appears  that  almost all modern  processors have nxn->2n
instructions, even though they *cannot* be used from C (which seems to be
the HLL that architects are most concerned with).

Herman Rubin writes in another article:

    >(3) Many programming languages let you declare 32 and 64bit
    >    integers explicitly and good compilers will select the right
    >    instruction to go with the types (Ada and CommonLisp are
    >    among those languages).

    >    Even the C language has provisions for just the case that you are
    >    concerned with in the case of 16bit integers, 32bit longs:

    >    int a = ...;
    >    int b = ...;
    >    int c = ...;
    >    long product = a*b;
    >    int result = product/c;

    As I read the language description, types are cast either before
    or after the operation.  I know of no operations in the C language
    which explicitly allow for different types of arguments/results
    except for comparisons, with Boolean results.  And those Booleans
    are not very flexible.  As Bob Silverman wrote, he would like to
    use a different operation symbol for the situation.

Let us use a slightly different example (so  that we avoid the  issues of
overflow and sign handling).

    unsigned short a, b;        /* assume 16 bits */
    unsigned long  c;           /* assume 32 bits */
    c = (unsigned long) a * (unsigned long) b;

The ANSI definition specifies that the  result (c) shall be the value one
gets when one does the following

    extend a to 32 bits
    extend b to 32 bits
    multiply a and b to give a 64 bit result with a 32x32->64 instruction
    shorten the result to 32 bits

However,  ANSI does  *not* specify how  the produced  object  code  shall
obtain this result.  (As far as ANSI is concerned it  would be all  right
to e-mail the operands to another machine, have the other machine compute
the result and e-mail it back ;-) So because the following sequence would
give the same result as the one above, it would be absolutly legal for an
ANSI compiler to produce this code

    multiply a and b to give a 32 bit result with a 16x16->32 instruction

And yes, I have seen compilers produce such code.  (It doesn't help us of
course, because we  really want  to use the 32x32->64 bit instruction and
are usually missing the 64 bit integer type to hold the result).

Martin.

-- .- .-. - .. -.  .-.. --- ...- . ...  .- -. -. .. -.- .-
Martin Sch"onert,   [e-mail],  [phone]
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, D 51 Aachen, Germany