Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.arch > #6484 > unrolled thread

Indirect Bit

Back to article view | Back to comp.arch

Contents

  Indirect Bit Mark Thorson <nospam@sonic.net> - 2012-04-10 19:31 -0800
    Re: Indirect Bit Robert Wessel <robertwessel2@yahoo.com> - 2012-04-11 01:29 -0500
      Re: Indirect Bit sarr.blumson@alum.dartmouth.org - 2012-04-11 14:48 +0000
        Re: Indirect Bit mac <acolvin@efunct.com> - 2012-04-12 14:43 +0000
      Re: Indirect Bit Morten Reistad <first@last.name> - 2012-04-22 15:19 +0200
        Re: Indirect Bit "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-04-22 23:24 -0700
    Re: Indirect Bit Terje Mathisen <"terje.mathisen at tmsw.no"> - 2012-04-11 08:32 +0200
      Re: Indirect Bit Michael S <already5chosen@yahoo.com> - 2012-04-11 05:49 -0700
        Re: Indirect Bit "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-04-12 21:22 -0700
          Re: Indirect Bit "Paul A. Clayton" <paaronclayton@gmail.com> - 2012-04-13 08:14 -0700
            Re: Indirect Bit Quadibloc <jsavard@ecn.ab.ca> - 2012-04-13 16:13 -0700
              Re: Indirect Bit "Paul A. Clayton" <paaronclayton@gmail.com> - 2012-04-13 20:01 -0700
                Re: Indirect Bit Andrew Reilly <areilly.---@bigpond.net.au> - 2012-04-14 03:16 +0000
                  Re: Indirect Bit "Paul A. Clayton" <paaronclayton@gmail.com> - 2012-04-14 08:14 -0700
          Re: Indirect Bit Quadibloc <jsavard@ecn.ab.ca> - 2012-04-13 16:05 -0700
            Re: Indirect Bit MitchAlsup <MitchAlsup@aol.com> - 2012-04-13 17:01 -0700
              Re: Indirect Bit Quadibloc <jsavard@ecn.ab.ca> - 2012-04-14 13:49 -0700
            Re: Indirect Bit Anne & Lynn Wheeler <lynn@garlic.com> - 2012-04-13 20:07 -0400
            Re: Indirect Bit Terje Mathisen <"terje.mathisen at tmsw.no"> - 2012-04-14 18:47 +0200
            Re: Indirect Bit Morten Reistad <first@last.name> - 2012-04-22 15:26 +0200
              Re: Indirect Bit "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-04-22 23:25 -0700
                Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-23 09:18 +0100
                  Re: Indirect Bit EricP <ThatWouldBeTelling@thevillage.com> - 2012-04-23 19:35 -0400
                    Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-24 08:37 +0100
                      Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-24 09:42 +0100
                        Re: Indirect Bit Michael S <already5chosen@yahoo.com> - 2012-04-24 01:58 -0700
                          Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-24 11:26 +0100
                            Re: Indirect Bit Michael S <already5chosen@yahoo.com> - 2012-04-24 05:02 -0700
                              Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-24 13:58 +0100
                                Re: Indirect Bit Michael S <already5chosen@yahoo.com> - 2012-04-24 10:07 -0700
                      Re: Indirect Bit Michael S <already5chosen@yahoo.com> - 2012-04-24 04:30 -0700
                        Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-24 13:01 +0100
    Re: Indirect Bit Stefan Monnier <monnier@iro.umontreal.ca> - 2012-04-11 10:03 -0400
    Re: Indirect Bit kenney@cix.compulink.co.uk - 2012-04-11 09:22 -0500
      Re: Indirect Bit Quadibloc <jsavard@ecn.ab.ca> - 2012-04-12 14:11 -0700
        Re: Indirect Bit Stefan Monnier <monnier@iro.umontreal.ca> - 2012-04-12 18:05 -0400
          Re: Indirect Bit "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-04-12 20:13 -0700
        Re: Indirect Bit Mark Thorson <nospam@sonic.net> - 2012-04-12 16:55 -0800
          Re: Indirect Bit Quadibloc <jsavard@ecn.ab.ca> - 2012-04-12 17:25 -0700
            Re: Indirect Bit Robert Wessel <robertwessel2@yahoo.com> - 2012-04-12 20:03 -0500
            Re: Indirect Bit "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-04-12 21:33 -0700
              Re: Indirect Bit Quadibloc <jsavard@ecn.ab.ca> - 2012-04-13 15:57 -0700
                Re: Indirect Bit MitchAlsup <MitchAlsup@aol.com> - 2012-04-13 17:03 -0700
          Re: Indirect Bit "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-04-12 20:14 -0700
    Re: Indirect Bit Anne & Lynn Wheeler <lynn@garlic.com> - 2012-04-11 10:35 -0400
    Re: Indirect Bit MitchAlsup <MitchAlsup@aol.com> - 2012-04-11 08:54 -0700
    Re: Indirect Bit "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-04-12 07:55 -0700
      Re: Indirect Bit MitchAlsup <MitchAlsup@aol.com> - 2012-04-12 10:16 -0700
        Re: Indirect Bit jacko <jackokring@gmail.com> - 2012-04-12 11:07 -0700
          Re: Indirect Bit "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-04-12 21:34 -0700
        Re: Indirect Bit Stephen Fuld <SFuld@alumni.cmu.edu.invalid> - 2012-04-12 11:35 -0700
          Re: Indirect Bit "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-04-12 21:41 -0700
            Re: Indirect Bit jacko <jackokring@gmail.com> - 2012-04-13 14:52 -0700
            Re: Indirect Bit Stephen Fuld <SFuld@alumni.cmu.edu.invalid> - 2012-04-15 09:24 -0700
              Re: Indirect Bit Terje Mathisen <"terje.mathisen at tmsw.no"> - 2012-04-15 22:45 +0200
                Re: Indirect Bit Stephen Fuld <SFuld@alumni.cmu.edu.invalid> - 2012-04-15 18:04 -0700
        Re: Indirect Bit "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-04-12 21:12 -0700
      Re: Indirect Bit timcaffrey@aol.com (Tim McCaffrey) - 2012-04-12 19:23 +0000
      Re: Indirect Bit Terje Mathisen <"terje.mathisen at tmsw.no"> - 2012-04-13 08:54 +0200
        Re: Indirect Bit "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-04-14 14:37 -0700
      Re: Indirect Bit Andrew Reilly <areilly.---@bigpond.net.au> - 2012-04-15 23:42 +0000
        Re: Indirect Bit "Paul A. Clayton" <paaronclayton@gmail.com> - 2012-04-16 08:08 -0700
          Re: Indirect Bit Andrew Reilly <areilly.---@bigpond.net.au> - 2012-04-16 23:38 +0000
            Re: Indirect Bit "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-04-16 21:29 -0700
        Re: Indirect Bit "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-04-16 21:25 -0700
    Re: Indirect Bit Quadibloc <jsavard@ecn.ab.ca> - 2012-04-12 14:05 -0700
      Re: Indirect Bit ChrisQ <blackhole@devnull.com> - 2012-04-14 10:12 +0000
        Re: Indirect Bit "Paul A. Clayton" <paaronclayton@gmail.com> - 2012-04-14 06:25 -0700
          Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-14 14:50 +0100
            Re: Indirect Bit ChrisQ <blackhole@devnull.com> - 2012-04-14 18:01 +0000
              Re: Indirect Bit Quadibloc <jsavard@ecn.ab.ca> - 2012-04-14 14:00 -0700
                Re: Indirect Bit Anne & Lynn Wheeler <lynn@garlic.com> - 2012-04-14 20:58 -0400
              Re: Indirect Bit "Paul A. Clayton" <paaronclayton@gmail.com> - 2012-04-16 09:57 -0700
              Re: Indirect Bit timcaffrey@aol.com (Tim McCaffrey) - 2012-04-20 23:19 +0000
            Re: Indirect Bit "Paul A. Clayton" <paaronclayton@gmail.com> - 2012-04-16 08:50 -0700
              Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-16 18:09 +0100
                Re: Indirect Bit Andrew Reilly <areilly.---@bigpond.net.au> - 2012-04-16 23:19 +0000
                  Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-17 09:20 +0100
                    Re: Indirect Bit Terje Mathisen <"terje.mathisen at tmsw.no"> - 2012-04-17 12:49 +0200
                      Re: Indirect Bit Andrew Reilly <areilly.---@bigpond.net.au> - 2012-04-17 12:40 +0000
                        Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-18 12:01 +0100
                  Re: Indirect Bit anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-17 12:34 +0000
                  Re: Indirect Bit MitchAlsup <MitchAlsup@aol.com> - 2012-04-17 09:10 -0700
                    Re: Indirect Bit Andrew Reilly <areilly.---@bigpond.net.au> - 2012-04-17 22:05 +0000
                    Re: Indirect Bit jgk@panix.com (Joe keane) - 2012-04-19 19:37 +0000
                    Re: Indirect Bit torbenm@diku.dk (Torben Ægidius Mogensen) - 2012-04-20 11:10 +0200
                      Re: Indirect Bit Terje Mathisen <"terje.mathisen at tmsw.no"> - 2012-04-20 11:24 +0200
                        Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-20 15:01 +0100
                        Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-20 15:03 +0100
                          Re: Indirect Bit Michael S <already5chosen@yahoo.com> - 2012-04-20 08:01 -0700
                            Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-20 16:35 +0100
                  Re: Indirect Bit Quadibloc <jsavard@ecn.ab.ca> - 2012-04-18 11:10 -0700
                    Re: Indirect Bit MitchAlsup <MitchAlsup@aol.com> - 2012-04-18 15:37 -0700
            Re: Indirect Bit MitchAlsup <MitchAlsup@aol.com> - 2012-04-16 11:21 -0700
              Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-16 19:36 +0100
                Re: Indirect Bit Quadibloc <jsavard@ecn.ab.ca> - 2012-04-18 11:17 -0700
                  Re: Indirect Bit MitchAlsup <MitchAlsup@aol.com> - 2012-04-18 15:33 -0700
                  Re: Indirect Bit Andreas Eder <andreas_eder@gmx.net> - 2012-04-19 00:29 +0200
                  Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-19 10:50 +0100
                    Re: Indirect Bit MitchAlsup <MitchAlsup@aol.com> - 2012-04-19 11:29 -0700
                      Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-19 21:39 +0100
                      Re: Indirect Bit EricP <ThatWouldBeTelling@thevillage.com> - 2012-04-20 15:14 -0400
                        Re: Indirect Bit "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-04-20 22:43 -0700
                          Re: Indirect Bit EricP <ThatWouldBeTelling@thevillage.com> - 2012-04-21 17:14 -0400
                            Re: Indirect Bit Robert Wessel <robertwessel2@yahoo.com> - 2012-04-21 19:47 -0500
                            Re: Indirect Bit Nomen Nescio <nobody@dizum.com> - 2012-04-22 10:45 +0200
                              Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-22 09:57 +0100
                                Re: Indirect Bit Terje Mathisen <"terje.mathisen at tmsw.no"> - 2012-04-22 12:54 +0200
                                  Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-22 13:00 +0100
                                Re: Indirect Bit Nomen Nescio <nobody@dizum.com> - 2012-04-22 13:28 +0200
                                  Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-22 13:04 +0100
                                    Re: Indirect Bit Fritz Wuehler <fritz@spamexpire-201204.rodent.frell.theremailer.net> - 2012-04-22 23:00 +0200
                                      Re: Indirect Bit Anne & Lynn Wheeler <lynn@garlic.com> - 2012-04-22 18:05 -0400
                                      Re: Indirect Bit glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-04-22 23:20 +0000
                                      Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-23 08:22 +0100
                              Re: Indirect Bit Michael S <already5chosen@yahoo.com> - 2012-04-22 03:56 -0700
                                Re: Indirect Bit EricP <ThatWouldBeTelling@thevillage.com> - 2012-04-22 12:28 -0400
                                  Re: Indirect Bit Robert Wessel <robertwessel2@yahoo.com> - 2012-04-22 12:56 -0500
                                    Re: Indirect Bit Quadibloc <jsavard@ecn.ab.ca> - 2012-04-22 13:15 -0700
                                  Re: Indirect Bit Nomen Nescio <nobody@dizum.com> - 2012-04-22 22:30 +0200
                                    Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-22 21:40 +0100
                                      Re: Indirect Bit Robert Wessel <robertwessel2@yahoo.com> - 2012-04-22 17:15 -0500
                                        Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-23 08:26 +0100
                                          Re: Indirect Bit Stephen Fuld <SFuld@alumni.cmu.edu.invalid> - 2012-04-23 08:02 -0700
                                            Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-23 17:02 +0100
                                            Re: Indirect Bit Fritz Wuehler <fritz@spamexpire-201204.rodent.frell.theremailer.net> - 2012-04-23 20:17 +0200
                                          Re: Indirect Bit Robert Wessel <robertwessel2@yahoo.com> - 2012-04-23 13:07 -0500
                              Re: Indirect Bit Quadibloc <jsavard@ecn.ab.ca> - 2012-04-22 13:16 -0700
                                Re: Indirect Bit MitchAlsup <MitchAlsup@aol.com> - 2012-04-23 13:14 -0700
                                  Re: Indirect Bit Anne & Lynn Wheeler <lynn@garlic.com> - 2012-04-23 16:51 -0400
                                  Re: Indirect Bit Quadibloc <jsavard@ecn.ab.ca> - 2012-04-23 14:22 -0700
                        Re: Indirect Bit MitchAlsup <MitchAlsup@aol.com> - 2012-04-21 11:17 -0700
          Re: Indirect Bit jacko <jackokring@gmail.com> - 2012-04-14 08:02 -0700

Page 5 of 7 — ← Prev page 1 2 3 4 [5] 6 7  Next page →

#6571

In article <9v56mlF1l7U1@mid.individual.net>,
Andrew Reilly  <areilly.---@bigpond.net.au> wrote:
>On Tue, 17 Apr 2012 12:49:53 +0200, Terje Mathisen wrote:
>
>> That one is dead simple if you have both N*N->2N multiply and
>> 2N/N->(N,N)
>> division, if you don't, then things become "slightly" more complicated.
>
>To be fair to Nick, N*N->2N multiply and division (of any sort) were 
>indeed weak points of most of the early RISC parts that I knew of.  Some 
>could only do multiplies in the FPU (if there was one), which gave you 
>about 56 bits of product: not quite enough.  Many had no integer 
>multiply, or only multiply-step instructions, and almost none had 
>division instructions.  There are still quite a lot of procecessors that 
>don't have integer division.  Even when there is a multiply, there 
>sometimes wasn't a full set of signed.unsigned or unsigned.unsigned 
>variants, so extended precision could indeed be messy.

The messiness was my point, not that it needed multiple instructions.
Quite often, it needed a lot of conditional branches, and sometimes
needed integer overflow traps disabling.


Regards,
Nick Maclaren.

[toc] | [prev] | [next] | [standalone]

#6568

Andrew Reilly <areilly.---@bigpond.net.au> writes:
>Eh?  Your experience and mine clearly differ.  The (early) RISC machines 
>that I remember suffered more (but not much) from a slavish adherence to 
>the semantics of C (such as that was generally understood, at the time), 
>leaving out seemingly useful features of earlier architectures, like post-
>increment addressing modes and condition codes.

Post-increment addressing modes look like a good fit for C with it's
*p++ idiom to me, at least for a simple code generator.  But AFAIK the
benchmarks used for early MIPS work were written in Pascal, and a PL/I
subset was used for IBM 801; not sure about Berkeley RISC, but that
was less compiler-oriented anyway.

My guess is that they were left away for (one or more of) several
reasons:

* It requires an additional register write port or the instruction
  requires as many cycles as the load/store and the increment.

* Such addressing modes do not fit well with some instruction
  selection techniques (in particular, tree parsing), so a code
  generator using such a technique may generate code without these
  addressing modes, or code where they are not utilized well.

* Induction variable elimination can reduce the number of increments,
  so the potential benefit of these addressing modes may be less than
  it might appear at first even for C programs.

Condition codes also fit reasonably well in with the short-circuit
evaluation used in C.  They don't fit so well into Pascal, though.
Moreover, if you have just one condition code register, that restricts
the code generator quite a bit (e.g., wrt instruction scheduling,
which was important for early (and also later) RISCs); so MIPS put the
results of comparisons into a general-purpose register, and Power (ok,
not an early RISC) had several CC registers.

- anton
-- 
M. Anton Ertl                    Some things have to be seen to be believed
anton@mips.complang.tuwien.ac.at Most things have to be believed to be seen
http://www.complang.tuwien.ac.at/anton/home.html

[toc] | [prev] | [next] | [standalone]

#6569

On Monday, April 16, 2012 6:19:47 PM UTC-5, Andrew Reilly wrote:
> What's non-orthogonal about a general 3-register instruction structure?

Stuff like:

     x = 356/i
     y = 413-j

So the compiler has easy access to "reg op constant" but almost no access
to "constant op reg". Some instruction sets gave access with additional 
instructions such as ReverseSubtract (and similar). This only maters when
the op is not commutitive.

Comment on pre/post increment/decrement:

The register port required for the write back of the data on a small machine
it quite horrible while the register port on any great-big-Out-of-Order
machine is inconsequential.

But that is not why it was "left out". It was left out because there are so
many occurances where p++ was still "alive" when another p++ is encountered.
The compiler was happy to merge both (many) increments into a single add
and decorate the p++ accesses into p[0], p[1], p[2] accesses. This reduces
the number of computations required. So not doing these increases performance.

Mitch

[toc] | [prev] | [next] | [standalone]

#6570

On Tue, 17 Apr 2012 09:10:46 -0700, MitchAlsup wrote:

> On Monday, April 16, 2012 6:19:47 PM UTC-5, Andrew Reilly wrote:
>> What's non-orthogonal about a general 3-register instruction structure?
> 
> Stuff like:
> 
>      x = 356/i y = 413-j
> 
> So the compiler has easy access to "reg op constant" but almost no
> access to "constant op reg". Some instruction sets gave access with
> additional instructions such as ReverseSubtract (and similar). This only
> maters when the op is not commutitive.

Those are only non-orthogonal when the 3-register instruction actually 
has a two-register-and-constant form, which many did have.  There were a 
few pure 3-reigster archs though, so you always had to load the constant 
separately: no "extra" effort.

Is it fair to complain that a generally applicable shortcut isn't 
universally applicable?  Maybe it is, but it seems like a reasonable 
tradeoff to me.

> Comment on pre/post increment/decrement:
> 
> The register port required for the write back of the data on a small
> machine it quite horrible while the register port on any
> great-big-Out-of-Order machine is inconsequential.
> 
> But that is not why it was "left out". It was left out because there are
> so many occurances where p++ was still "alive" when another p++ is
> encountered. The compiler was happy to merge both (many) increments into
> a single add and decorate the p++ accesses into p[0], p[1], p[2]
> accesses. This reduces the number of computations required. So not doing
> these increases performance.

Oh, I understand that.  Also the condition code thing.  Both perfectly 
reasonable.  I was just clutching at architecture diminutions that were 
commented on at the time.  Couldn't think of anything that actually 
supported my original argument of missing non-C support.  Maybe Pascal-
call convention return operations (auto-pop)?

Cheers,

-- 
Andrew

[toc] | [prev] | [next] | [standalone]

#6578

In article <21570746.2123.1334679046583.JavaMail.geo-discussion-forums@ynaz34>,
MitchAlsup  <MitchAlsup@aol.com> wrote:
>Stuff like:
>
>     x = 356/i
>     y = 413-j

IIRC a lot of RISCs had a 'reverse subtract'.

Of course PDP-11 doesn't need it.

The divide example i don't believe (for integer).

[toc] | [prev] | [next] | [standalone]

#6581

MitchAlsup <MitchAlsup@aol.com> writes:

> On Monday, April 16, 2012 6:19:47 PM UTC-5, Andrew Reilly wrote:
>> What's non-orthogonal about a general 3-register instruction structure?
>
> Stuff like:
>
>      x = 356/i
>      y = 413-j
>
> So the compiler has easy access to "reg op constant" but almost no access
> to "constant op reg". Some instruction sets gave access with additional 
> instructions such as ReverseSubtract (and similar). This only maters when
> the op is not commutitive.

For commutative operations, it is a waste of opcode space to have
constants as both 1st and 2nd operand, so it makes much more sense to
keep the position of the immediate argument fixed and provide two
instructions for non-commutative operations (like reverse subtract).  In
fact, if you have signed immediates, it makes more sense to have a
revers-subtract-immediate instruction than a subtract-immediate
instruction, since the latter is just an add-immediate with opposite
sign.  So you don't really need both.  This, obviously, won't work for
reverse-division-immediate, but IIRC, few RISC processors even have
divide-immediate instructions in the first place, so there is no lack of
symmetry.  Apart from 1/x, there are few interesting cases of k/x
anyway, so I see little need for a reverse-division-immediate
instruction.

	Torben

[toc] | [prev] | [next] | [standalone]

#6582

Torben Ægidius Mogensen wrote:
> For commutative operations, it is a waste of opcode space to have
> constants as both 1st and 2nd operand, so it makes much more sense to
> keep the position of the immediate argument fixed and provide two
> instructions for non-commutative operations (like reverse subtract).  In
> fact, if you have signed immediates, it makes more sense to have a
> revers-subtract-immediate instruction than a subtract-immediate
> instruction, since the latter is just an add-immediate with opposite
> sign.  So you don't really need both.  This, obviously, won't work for

I agree, I've often wished x86 had reverse subtract. :-)

> reverse-division-immediate, but IIRC, few RISC processors even have
> divide-immediate instructions in the first place, so there is no lack of
> symmetry.  Apart from 1/x, there are few interesting cases of k/x
> anyway, so I see little need for a reverse-division-immediate
> instruction.

1/x otoh is so interesting that hw tweaks for it tends to turn up, like 
the ~12 bit reciprocal lookup opcode in SSE.

BTW, if I can only get a single lookup opcode I'd prefer inverse square 
root, since I can use that to trivially get the plain reciprocal value.

Terje
-- 
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

[toc] | [prev] | [next] | [standalone]

#6583

In article <8km769-fa22.ln1@ntp6.tmsw.no>,
Terje Mathisen  <"terje.mathisen at tmsw.no"> wrote:
>Torben Ægidius Mogensen wrote:
>> For commutative operations, it is a waste of opcode space to have
>> constants as both 1st and 2nd operand, so it makes much more sense to
>> keep the position of the immediate argument fixed and provide two
>> instructions for non-commutative operations (like reverse subtract).  In
>> fact, if you have signed immediates, it makes more sense to have a
>> revers-subtract-immediate instruction than a subtract-immediate
>> instruction, since the latter is just an add-immediate with opposite
>> sign.  So you don't really need both.  This, obviously, won't work for
>
>I agree, I've often wished x86 had reverse subtract. :-)
>
>> reverse-division-immediate, but IIRC, few RISC processors even have
>> divide-immediate instructions in the first place, so there is no lack of
>> symmetry.  Apart from 1/x, there are few interesting cases of k/x
>> anyway, so I see little need for a reverse-division-immediate
>> instruction.
>
>1/x otoh is so interesting that hw tweaks for it tends to turn up, like 
>the ~12 bit reciprocal lookup opcode in SSE.
>
>BTW, if I can only get a single lookup opcode I'd prefer inverse square 
>root, since I can use that to trivially get the plain reciprocal value.
>
>Terje
>-- 
>- <Terje.Mathisen at tmsw.no>
>"almost all programming can be viewed as an exercise in caching"

[toc] | [prev] | [next] | [standalone]

#6584

In article <8km769-fa22.ln1@ntp6.tmsw.no>,
Terje Mathisen  <"terje.mathisen at tmsw.no"> wrote:
>
>BTW, if I can only get a single lookup opcode I'd prefer inverse square 
>root, since I can use that to trivially get the plain reciprocal value.

Hmm.  That previous aberration was the result of a bus error in
Pnews!  I meant to send this:

It has several advantages, too, such as never overflowing - and
being marginally faster to calculate if using Newton-Raphson.


Regards,
Nick Maclaren.

[toc] | [prev] | [next] | [standalone]

#6585

On Apr 20, 5:03 pm, n...@cam.ac.uk wrote:
> In article <8km769-fa22....@ntp6.tmsw.no>,
> Terje Mathisen  <"terje.mathisen at tmsw.no"> wrote:
>
>
>
> >BTW, if I can only get a single lookup opcode I'd prefer inverse square
> >root, since I can use that to trivially get the plain reciprocal value.
>
> Hmm.  That previous aberration was the result of a bus error in
> Pnews!  I meant to send this:
>
> It has several advantages, too, such as never overflowing - and
> being marginally faster to calculate if using Newton-Raphson.
>
> Regards,
> Nick Maclaren.

But there ain't no such thing as a free lunch.
For any given precision of result 1/sqrt(x) lookup table has to be
twice bigger than 1/x table. So, in a space required for 12b-precise 1/
sqrt(x) lookup table one can store 12b-precise 1/(x) lookup table
*plus* 11b-precise 1/sqrt(x) lookup table!
As to you first argument - yes,  1/(x) overflows on most denormal
inputs while 1/sqrt(x) does not. But 1/sqrt(x) has similar, if not
worse, problem with negative inputs.
So, at the end, the only real unequivocal advantage of  1/sqrt(x)
approximation hardware over 1/x [assuming strange hypothetical
conditions in which you're allowed to have only one of the two] is the
one mentioned by Terje - you can easily synthesize the later out of
the former, but not the other way around.

[toc] | [prev] | [next] | [standalone]

#6586

In article <dad316d6-761d-4b22-a42b-7c5df34d379b@r13g2000vbg.googlegroups.com>,
Michael S  <already5chosen@yahoo.com> wrote:
>
>But there ain't no such thing as a free lunch.

That is true.

>For any given precision of result 1/sqrt(x) lookup table has to be
>twice bigger than 1/x table. So, in a space required for 12b-precise 1/
>sqrt(x) lookup table one can store 12b-precise 1/(x) lookup table
>*plus* 11b-precise 1/sqrt(x) lookup table!

Er, that isn't quite how it should be implemented ....

>As to you first argument - yes,  1/(x) overflows on most denormal
>inputs while 1/sqrt(x) does not. But 1/sqrt(x) has similar, if not
>worse, problem with negative inputs.

Not at all.  It's a simple condition, and is either easy and clean
to test for, or can trivially be kludged up.  The problem about
overflow in inversion is that it is difficult to describe, and
needs implementation-dependent magic numbers to test for.

>So, at the end, the only real unequivocal advantage of  1/sqrt(x)
>approximation hardware over 1/x [assuming strange hypothetical
>conditions in which you're allowed to have only one of the two] is the
>one mentioned by Terje - you can easily synthesize the later out of
>the former, but not the other way around.

There are very few unequivocal advantages in this world, and even
that is not one.


Regards,
Nick Maclaren.

[toc] | [prev] | [next] | [standalone]

#6572

On Apr 16, 5:19 pm, Andrew Reilly <areilly....@bigpond.net.au> wrote:
> Most of the CISCs of the
> day (excluding IBM, of which I have no personal experience) didn't have
> those problems because they just didn't do pipelining.

IBM didn't _like_ pipelining, thanks to their bad experience with the
STRETCH, and the fact that for them, unlike Control Data, scientific
computing was not their core business. So they dumped the 370/195 like
a hot potato. Instead, the microcoded IBM 360/85 architecture got used
as the basis of the 370/165 and the 3033.

But _for_ the 360/91, ancestor of the 360/95, the 360/195, and the
370/195, IBM invented the Tomasulo algorithm, part of the basis of how
a properly designed computer with a pipeline should work.

John Savard

[toc] | [prev] | [next] | [standalone]

#6575

On Wednesday, April 18, 2012 1:10:16 PM UTC-5, Quadibloc wrote:
> On Apr 16, 5:19 pm, Andrew Reilly <areilly....@bigpond.net.au> wrote:
> > Most of the CISCs of the
> > day (excluding IBM, of which I have no personal experience) didn't have
> > those problems because they just didn't do pipelining.
> 
> IBM didn't _like_ pipelining, thanks to their bad experience with the
> STRETCH, and the fact that for them, unlike Control Data, scientific
> computing was not their core business.

I want to disagree with this!

IBM loved pipelining! What IBM refused to do again (until recently) was
out-of-order. The 360/65 WAS pipelined, and so were most of the higher
end big mainframes. Memory was both pipelined and banked.

>                                        So they dumped the 370/195 like
> a hot potato. Instead, the microcoded IBM 360/85 architecture got used
> as the basis of the 370/165 and the 3033.

Which were pipelined in any classical sense of the word pipelined!

> But _for_ the 360/91, ancestor of the 360/95, the 360/195, and the
> 370/195, IBM invented the Tomasulo algorithm, part of the basis of how
> a properly designed computer with a pipeline should work.

Confusing the word pipeline--which measn a series of steps that perform
a unit of work--with the word out-of-order--which means that the steps of 
the pipeline can transpire in different order based on other things
going on at the time.

Mitch

[toc] | [prev] | [next] | [standalone]

#6558

On Saturday, April 14, 2012 8:50:48 AM UTC-5, nm...@cam.ac.uk wrote:
> In article <6799b00c-7c9e-4f0c-9a97-3994c3d81b5f@x17g2000vba.googlegroups.com>,
> Paul A. Clayton 
>  wrote:
> >ChrisQ wrote:
> >
> >>                                  There's
> >> a good reason why orthoganal, cisc architectures were successfull,
> >> even if a little was lost in absolute performance terms. Raw hardware
> >> performance is of little use if there are not enough competent
> >> programmers to write decent compilers for them...
> >
> >It is probably more difficult to write an _optimizing_ compiler for
> >CISC than for RISC.  ...
> 
> He did say "orthogonal", and is probably right there.
> 
> The reason that it was so hard to write optimising compilers
> for so-called RISC systems is that the instruction constraints,
> semantics and idiosyncracies are so complicated and non-orthogonal.
> Of course, that doesn't apply to a well-designed and simple true
> RISC system, but most weren't.

I think the whole notion of optimization is misconstrued. At best
an "optimizing" simply does a less poor job of translating the 
semantics of the HLL inot machine code than does a less "optimizing"
compiler.

But moreover, It never ceased to amaze me that compiler people were 
loathe to read the machine code output from their compilers!!! This
is akin to a person creating fonts to never bother to print the fonts 
out and look at them.

Having written code generators for RICS (2) and CISC (3) machines;
I further thnk that more is made over the headches of one versus
the other than is warrented. Afterall, a code generator is a great
big pattern matchin problem. Clever compiler writers get down into
it and figure out which constructs are working and which are not. 
Then leverage this knowledge over the rest of the instructioni set.
In fact, I would not let a computer architect design an instruction
set UNTIL they ad successfully constructed a code generator that works
rather well.

As Gordon Bell stated in his seminal work: the instruction set should
contain primatives, not solutions. So, while PDP-11 orthogonality and
addressing modes were an adequate fit for the days of expensive memory
they are not such a good fit in more modern times. What with pipe-
lining, out-of-order execution, breaking CISC instructions into multiple 
RICS primitives,...

Then reading Kahan's work on the dangers of allowing compilers to do
anything with floating point optimizations sends chills down ones
spine.

Similar work has been done by others on the merits and dangers of 
optimizing (reordering) memory transfer instructions (or side effects)
with similar dire consequences (mainly in C land).

Mitch

[toc] | [prev] | [next] | [standalone]

#6559

In article <1454560.470.1334600502251.JavaMail.geo-discussion-forums@ynbi17>,
MitchAlsup  <MitchAlsup@aol.com> wrote:
>
>Then reading Kahan's work on the dangers of allowing compilers to do
>anything with floating point optimizations sends chills down ones
>spine.

I belong to a different, and more traditional, sect - Fortran does
precisely that, and 50+ years of experience has shown how well it
works.  You MUST NOT think of floating-point results as points,
but as representatives of sets/intervals/distributions/fuzzes/....

>Similar work has been done by others on the merits and dangers of 
>optimizing (reordering) memory transfer instructions (or side effects)
>with similar dire consequences (mainly in C land).

Quite.  Abandon the extreme sequential von Neumann model favoured
by WG14 and the associated people, move to a higher-level, and there
isn't a problem.  Even OpenMP gets THAT right!

My point here is that modern 'computer scientists' have regressed
from the days when computing was dominated by mathematicians and
engineers.  Thinking in terms of such very machine-code concepts
as bit-pattern to bit-pattern operations and a deterministic,
sequential order of actions is just SO 1950s :-)

There always were such people, but they have come to dominate the
world of computer design, both theoretically and practically, and
in almost all areas.  That's sad, and very harmful.


Regards,
Nick Maclaren.

[toc] | [prev] | [next] | [standalone]

#6573

On Apr 16, 12:36 pm, n...@cam.ac.uk wrote:
> In article <1454560.470.1334600502251.JavaMail.geo-discussion-forums@ynbi17>,
> MitchAlsup  <MitchAl...@aol.com> wrote:
>
> >Then reading Kahan's work on the dangers of allowing compilers to do
> >anything with floating point optimizations sends chills down ones
> >spine.
>
> I belong to a different, and more traditional, sect - Fortran does
> precisely that, and 50+ years of experience has shown how well it
> works.  You MUST NOT think of floating-point results as points,
> but as representatives of sets/intervals/distributions/fuzzes/....

Certain floating-point optimizations are legitimate; others are not,
because they would result in massive loss of precision under some
circumstances. In general, compiler writers do know which is which,
and only perform legitimate optimizations when working with floating-
point.

It should be noted, though, that the IEEE 754 standard has been useful
in improving the quality of computer floating-point arithmetic - and
it is founded on the premise that we should start thinking of floating
point numbers as having exact values, and aiming for the closest
possible result in a computation.

The cost of doing this, though, even just for division, can be
inordinate. For transcendental functions (except square root), the
standard forbears to ask for the impossible.

John Savard

[toc] | [prev] | [next] | [standalone]

#6574

On Wednesday, April 18, 2012 1:17:08 PM UTC-5, Quadibloc wrote:
> On Apr 16, 12:36 pm, n...@cam.ac.uk wrote:
> > In article <1454560.470.1334600502251.JavaMail.geo-discussion-forums@ynbi17>,
> > MitchAlsup  <MitchAl...@aol.com> wrote:
> >
> > >Then reading Kahan's work on the dangers of allowing compilers to do
> > >anything with floating point optimizations sends chills down ones
> > >spine.
> >
> > I belong to a different, and more traditional, sect - Fortran does
> > precisely that, and 50+ years of experience has shown how well it
> > works.  You MUST NOT think of floating-point results as points,
> > but as representatives of sets/intervals/distributions/fuzzes/....
> 
> Certain floating-point optimizations are legitimate; others are not,
> because they would result in massive loss of precision under some
> circumstances. In general, compiler writers do know which is which,
> and only perform legitimate optimizations when working with floating-
> point.

It is MUCH worse than this. Subtle rearrangements can cause a rounding
error that then propogates up to the point where all accuracy is lost.
Much of the time, the programmer will be completely unaware until a
particular set of data presents the problem to the user; EVEN if that
programmer is COMPLETELY aware of the dangers and inadequacies of 754
floating point.

What is even worse, is that subtle optimization of floating point codes
can render the "additions" of 754 inadequate to deal with the problems
at hand. Those additions are qradual underflow, default results from
invalid operations/operands, and NANs which basically no compiler writer
understands sufficiently to attemp proper optimization of FP codes.

For example: one cannot take:

     IF( x < Y ) THEN Q = Z ELSE Q = F

and convert it into:

     IF( x >= Y ) THEN Q = F ELSE Q = Z

Beacuse of the mere existence of NANs. The presence of a NAN will render
different assignments to Q ! This is because NANs cannot be compared! 
The first example, a NAN will cause Q = F while in the second a NAN will
cause Q = Z !!!

{I've been boning up on old Kahan literature in the last couple of days}
 
> It should be noted, though, that the IEEE 754 standard has been useful
> in improving the quality of computer floating-point arithmetic - and
> it is founded on the premise that we should start thinking of floating
> point numbers as having exact values, and aiming for the closest
> possible result in a computation.

It is this higher quality of arithmetic that has made programmers overly
comfortable with the quality so as to assume that FP has become benign
and rather useable. Yet various stories return time and time again as to
how this is not so (ususlly bad stories--USS Yorktown, Ariane 5,...)

> The cost of doing this, though, even just for division, can be
> inordinate. For transcendental functions (except square root), the
> standard forbears to ask for the impossible.

Au contraire: Rather easy to do with a CORDIC unit (which also solves 
the REM problem of 754).

But CORDIC is too slow, they say! Compared to computing SINE with a
polynomial--not so much. Compared to DIV with CORDIC yes definately.
So the moral should have been--do in hardware what should be done in
hardware, and do in software what shold be done in software. That is
one has a FP ADDER that does add, sub, compare, move,... : one has
a multiplier that does mult (and possibly DIV, or a SRT divider that 
does DIV, REM). But this aleviates no-one from having a CORDIC unit
somewhere in the FP mass of logic.

I remember the Athlon/Opteron FP x87/SSE multiplier. That unit had 
the requisite amount of adders and multiplexers to do CORDIC functions 
so all that was missing were the tables to drive the CORDIC algorithms.
Note, those adders were 131-bits long, BTW.

Mitch

[toc] | [prev] | [next] | [standalone]

#6576

>>>>> "Quadibloc" == Quadibloc  <jsavard@ecn.ab.ca> writes:

    Quadibloc> The cost of doing this, though, even just for division, can be
    Quadibloc> inordinate. For transcendental functions (except square root), the
    Quadibloc> standard forbears to ask for the impossible.

square root is obviously not a transcendental function but an algebraic
one.

'Andreas

-- 
ceterum censeo redmondinem esse delendam.

[toc] | [prev] | [next] | [standalone]

#6577

In article <b992445b-d51c-4c5b-acb2-2ffcd5b4e7db@t7g2000pbp.googlegroups.com>,
Quadibloc  <jsavard@ecn.ab.ca> wrote:
>>
>> >Then reading Kahan's work on the dangers of allowing compilers to do
>> >anything with floating point optimizations sends chills down ones
>> >spine.
>>
>> I belong to a different, and more traditional, sect - Fortran does
>> precisely that, and 50+ years of experience has shown how well it
>> works. =A0You MUST NOT think of floating-point results as points,
>> but as representatives of sets/intervals/distributions/fuzzes/....
>
>Certain floating-point optimizations are legitimate; others are not,
>because they would result in massive loss of precision under some
>circumstances. In general, compiler writers do know which is which,
>and only perform legitimate optimizations when working with floating-
>point.

Absolutely NOT!  Mitch has pointed out some of the issues, but the
problem is well-known to be insoluble in theory and practice; the
compiler is almost the worst place to make such decisions.   For
example, there is no sense in which a decision can be legitimate
or illegitimate, except in the context of an accuracy analysis of
the context (which, as far as the compiler can tell, is the whole
program).

>It should be noted, though, that the IEEE 754 standard has been useful
>in improving the quality of computer floating-point arithmetic - and
>it is founded on the premise that we should start thinking of floating
>point numbers as having exact values, and aiming for the closest
>possible result in a computation.

Grrk.  Has it?  Some evidence of that, rather than merely repeating
the polemic, would strengthen your argument.  It certainly brought
order to a chaotic area, and helped to kill some of the more extreme
idiocies (like System/360 floating-point), but has it caused more
good than harm or more harm than good?  It's a moot point.

In particular, it is well-known that thinking of floating-point as
exact makes debugging easier, but does NOT improve accuracy or
reliability, in general.  Indeed, whether it improves it on average
is another moot point - one of the many tasks on my stack is to
do some investigation of that, and the people who have done some
have generally found that it made little difference.


Regards,
Nick Maclaren.

[toc] | [prev] | [next] | [standalone]

#6579

On Thursday, April 19, 2012 4:50:17 AM UTC-5, nm...@cam.ac.uk wrote:
> >Certain floating-point optimizations are legitimate; others are not,
> >because they would result in massive loss of precision under some
> >circumstances. In general, compiler writers do know which is which,
> >and only perform legitimate optimizations when working with floating-
> >point.
> 
> Absolutely NOT!  Mitch has pointed out some of the issues, but the
> problem is well-known to be insoluble in theory and practice; the
> compiler is almost the worst place to make such decisions.

For todays lesson in FP optimizations: consider the following::

     x = 3.0/7.0
     if( x == 3.0/7.0 ) blah();

A) Is it legal for the optimizer to compute the 3.0/7.0 for the 
assignment statement at compile time?
B) is it legal for the optimizer to compile the 3.0/7.0 for the
if-statement at compile time?
C) is it legal for the optimizer to dead-code-eliminate the if-
statement leaving only the call to blah() ?

{Leaving out the falacy of EVER comparing FP numbers for exactness}

Answers:
A) yes
B) no
C) no

This snippet of code is designed to determine if arithmetic operations
are carried out with more precision in registers than is store in memory.
For machines that have more precision in regsiters than in memory, blah
is never called.

Mitch

[toc] | [prev] | [next] | [standalone]

Page 5 of 7 — ← Prev page 1 2 3 4 [5] 6 7  Next page →

Back to top | Article view | comp.arch

csiph-web