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 4 of 7 — ← Prev page 1 2 3 [4] 5 6 7  Next page →

#6551

Hi Andy,

On Thu, 12 Apr 2012 07:55:02 -0700, Andy (Super) Glew wrote:

> And it's not just scalar operartions.  It is entirely natural to think
> of complex operations on a POD, plain old data, struct, that is
> contiguous and small enough to firt in a memory module.  Hmm, maybe that
> should be the criterion for judging when an operation shiould be
> exported via an instruction packet sent to a remote processing element
> nearer the memory, rather than the memory being fetched to the local
> processor: when the object in question is a small enough POD.
> 
> And then you have the concept of visitor threadlets, instruction packets
> that get sent first to one memopry module, do something there, and then
> to another, and another. Possibly rendezvousing with other threadlets.

I'm confused by the use model where this notion of "sending code" makes 
sense.  Could you elaborate, please?  In my naiive imagination of how 
most processing (particularly HPC) happens at the moment, code is a pre-
execution constant, and so fetching the code to any and all processors 
that will be involved in its execution can be hoisted completely to load-
time.

Are you considering a data-driven, dynamic code compilation environment, 
where pieces of code are newly generated at run-time?  Who (what field) 
is using that model?

Cheers,

-- 
Andrew

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

#6554

On Apr 15, 7:42 pm, Andrew Reilly <areilly....@bigpond.net.au> wrote:
[snip]
> I'm confused by the use model where this notion of "sending code" makes
> sense.  Could you elaborate, please?  In my naiive imagination of how
> most processing (particularly HPC) happens at the moment, code is a pre-
> execution constant, and so fetching the code to any and all processors
> that will be involved in its execution can be hoisted completely to load-
> time.

Rather than seeing this as sending code, one might look at it
as sending work orders.  (If the code size of the work order is
small, sending the code can be cheaper [no cache/TLB misses]
than sending a function pointer.  Likewise, some data might be
more cheaply sent directly rather than sending a pointer.)  If
the data processed by the work order is mostly local to a
different node, transferring the work order can be cheaper than
transferring data to the originating node.

The classic example of this kind of operation is fetch-and-add,
where keeping the cache line holding the value in one place
can have significant benefits (and the additions can even
be coalesced in the network).

(One could also imagine taking advantage of network topology
to minimize traffic.  E.g., rings could work very well for
pipeline operations--and some workloads might be able to
use mostly data rather than functionality localization for
each pipe stage.)

In some sense, this is what memcached does; a request is
received by a generic server and forwarded to a specific
cache server that is likely to have the requested resource.

> Are you considering a data-driven, dynamic code compilation environment,
> where pieces of code are newly generated at run-time?  Who (what field)
> is using that model?
>
> Cheers,
>
> --
> Andrew

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

#6561

On Mon, 16 Apr 2012 08:08:34 -0700, Paul A. Clayton wrote:

> Rather than seeing this as sending code, one might look at it as sending
> work orders.  (If the code size of the work order is small, sending the
> code can be cheaper [no cache/TLB misses]
> than sending a function pointer.  Likewise, some data might be more
> cheaply sent directly rather than sending a pointer.)  If the data
> processed by the work order is mostly local to a different node,
> transferring the work order can be cheaper than transferring data to the
> originating node.
> 
> The classic example of this kind of operation is fetch-and-add,
> where keeping the cache line holding the value in one place can have
> significant benefits (and the additions can even be coalesced in the
> network).

So instead of having a thread on one node do read-add-write of data from 
a remote node, you would have a remote thread that does read-add-write of 
local data with a remote coefficient (or perhaps one in the instruction 
stream).  That sounds like a code structure issue, requiring a higher-
level of compiler optimisation that I think is commonly used.  Perhaps a 
hardware-based "work-order-sending" strategy could work, but it sounds 
more complicated than just optimising the code.  Sounds like a fun 
compiler project, though.  I've often thought that abstracting memory 
operations to higher-level code, at a compiler level, could be an 
interesting exercise.

> (One could also imagine taking advantage of network topology to minimize
> traffic.  E.g., rings could work very well for pipeline operations--and
> some workloads might be able to use mostly data rather than
> functionality localization for each pipe stage.)
> 
> In some sense, this is what memcached does; a request is received by a
> generic server and forwarded to a specific cache server that is likely
> to have the requested resource.

It's the same sort of idea as stored procedures in databases too, isn't 
it?  Or the X-server (back before the host CPU got involved in font 
rendering and 3D ops.)  Or any remote-object (DCOM?) protocol system, 
really.  All of those examples are a much higher level than single-word-
update types of work, but are they not a more realistic approach to 
solving the problem?  Do we really want remote processes stealing 
variable amounts of compute throughput from our local process out of 
sight of the local OS scheduler?  Presumably something like an OS needs 
to get involved if the remote work requires much in the way of state 
resources (registers), effectively managing context switches.  So we 
introduce hardware-level RPC.  Seems klunky to me.

Cheers,

-- 
Andrew

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

#6564

On 4/16/2012 4:38 PM, Andrew Reilly wrote:
> On Mon, 16 Apr 2012 08:08:34 -0700, Paul A. Clayton wrote:
>
>> Rather than seeing this as sending code, one might look at it as sending
>> work orders.  (If the code size of the work order is small, sending the
>> code can be cheaper [no cache/TLB misses]
>> than sending a function pointer.  Likewise, some data might be more
>> cheaply sent directly rather than sending a pointer.)  If the data
>> processed by the work order is mostly local to a different node,
>> transferring the work order can be cheaper than transferring data to the
>> originating node.
>>
>> The classic example of this kind of operation is fetch-and-add,
>> where keeping the cache line holding the value in one place can have
>> significant benefits (and the additions can even be coalesced in the
>> network).
>
> So instead of having a thread on one node do read-add-write of data from
> a remote node, you would have a remote thread that does read-add-write of
> local data with a remote coefficient (or perhaps one in the instruction
> stream).  That sounds like a code structure issue, requiring a higher-
> level of compiler optimisation that I think is commonly used.  Perhaps a
> hardware-based "work-order-sending" strategy could work, but it sounds
> more complicated than just optimising the code.  Sounds like a fun
> compiler project, though.  I've often thought that abstracting memory
> operations to higher-level code, at a compiler level, could be an
> interesting exercise.
>
> It's the same sort of idea as stored procedures in databases too, isn't
> it?

Some of my thinking here is inspired by David Dewitt's database class at 
Wisconsin.

One day he asked "Which is better, shipping the code to data or shipping 
the data to the code?"

Now, hardware always ships the data to the code.

But Dewitt said that it is a truism, nearly always the case, that in 
databases one ships the code to the data.  Function shipping.

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

#6563

On 4/15/2012 4:42 PM, Andrew Reilly wrote:
> I'm confused by the use model where this notion of "sending code" makes
> sense.  Could you elaborate, please?  In my naiive imagination of how
> most processing (particularly HPC) happens at the moment, code is a pre-
> execution constant, and so fetching the code to any and all processors

Thanks, I meant to say something about this.  The last time we talked 
about this, a few months ago, Mitch said something like "sending code 
makes no sense, just send an instruction pointer and rely on the cache 
coherency model".  So, a few items:

(0) I do not necessarily assume a shared memory computer at all. Not 
necessarily just a message passing cluster - so called "web services", 
where you send a packet of code across a network like TCP/IP to be 
executed at a remote processor on whatever data it has locally - and 
then possibly forwarded on to some other remote node.

(1) You may have shared memory, but not necessarily cache coherent 
shared memory.

By the way, with the proper mindset code is never a pre-execution 
constant pre-loaded into all processors.  All the processors are doing 
something - in reset, finishing some previous job - and a new piece of 
code starts executing and slowly, slowly, parts of that code get 
propagated to the nodes that are executing them.

(2) By the way^2, if you say "Who the heck is building a non-cache 
coherent processor in this day and age?", well, (a) Lots of the 
supercomputer guys I was working with a few years ago were against cache 
consistency, and (b) it gets more interesting when you consider simple 
processing elements.  Such as the Processing In Memory (PIM) logic this 
thread has discussed - things that aren't a full fledged cache coherent 
processor, but just enough logic to follow a pointer (the indirect bit 
of the title) or to do a fetch-and-add, etc.  You can imagine a system 
that has both big cache coherent processors and such small PIM 
processing elements.  Now, I think it might be ugly to give up cache 
coherency for the PIM logic - but I can imagine a system where the PIM 
logic has no coherency hardware, but where the "instruction packets" 
that I have mentioned are just commands that flow along with the 
coherency messages.  E.g. there have been, and perhaps still are, 
systems where "increment memory location" is part of the cache coherence 
protocol, a bus command not unlike read-line or write-line that flows to 
wherever the data lives, and gets done there. Where "there" may be 
memory, but may also be some L1, L2, or Ln cache level, or a switch, or ....

(3) I'm also not averse to using this "instruction packet" concept in a 
cache coherent multiprocessor, where you may just be sending a PC 
around, and relying on cache coherency, as Mitch stated.  Well, of 
course, you will also be sending thread context around - privilege 
domain, address space, register contents - although it is also 
interesting to imagine relying on cache coherency to pick those up.

But, because I am also thinking of (0) non-shared memory and (1) and (2) 
non cache coherent shared memory, I am interested in the possibility 
that shared memory may be just an optimization.  Just as one often 
builds message passing supercomputers out of nodes that are individually 
shared memory.

(4) I guess that on the fly code generation is of some interest, but its 
not really necessary for what I was talking about.

(5) Finally, because I am a capability type of guy, I am interested in 
the possibility that these instruction packets or threadlets may not 
necessarily be in the same privilege domain as program that created them.

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

#6507

On Apr 10, 9:31 pm, Mark Thorson <nos...@sonic.net> wrote:

> Now, with 64-bit architectures, there's a bunch of address
> bits nobody needs.  How about taking A63 and using it as
> an indirect bit?

> So why isn't this already being implemented?

RISC is fashionable. CISC is unfashionable. Indirect addressing is
considered just about beyond the pale.

Actually, there are legitimate reasons for this.

Today's architectures, RISC or CISC, are being implemented in ways
which provide very fast cycle times, and which support rapid
instruction execution. The Pentium was the first microprocessor to
incorporate the basic implementation features that were found in the
IBM System/360 Model 195 - cache plus superpipelining plus advanced
division algorithm.

That kind of implementation does *not* mix well with a mode bit in an
instruction that necessarily makes it take significantly more cycles.

Add to this the motive behind CISC - memory accesses (when out of
cache) are painfully slow - and the last thing one wants is to
increase the role of memory in programs.

Note, of course, the number of cycles a memory-reference instruction
takes is changed, unpredictably, by cache misses - this one special
case is dealt with in hardware - but no more of that is wanted if it
can be at all avoided.

One can load pointer registers and so on to do indirect addressing in
software for the few algorithms where it's needed, but it is a poor
fit to current implementations, so its unfashionability has sound
reasons behind it.

John Savard

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

#6534

On 04/12/12 21:05, Quadibloc wrote:

>
> RISC is fashionable. CISC is unfashionable. Indirect addressing is
> considered just about beyond the pale.
>

Perhaps you could define "indirect" ?. afaics, most risc designs use
register indirect for just about all memory accesses and older cisc
designs like 68k even had a set of registers dedicated to holding
memory addresses.

Just because something is "unfashionable", doesn't mean that it isn't
an appropriate solution. Fashion changes with the wind and usually
bears no relation to any technical considerations, good or bad. 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...

Regards,

Chris

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

#6535

ChrisQ wrote:
[snip]
> Just because something is "unfashionable", doesn't mean that it isn't
> an appropriate solution. Fashion changes with the wind and usually
> bears no relation to any technical considerations, good or bad.

I doubt that technical considerations play no role in this area.  The
importance of different tradeoffs may have been misunderstood, but
I am guessing that few production ISAs were designed just based
on what everyone else was doing.  More common, I think, is the
lack of reevaluating tradeoffs.

>                                  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.  For a RISC instruction selection is usually
somewhat trivial (there are relatively few cases in which there is
a choice [integer doubling, register zeroing, and nop are the only
ones I can think of off hand].  Likewise, the load-store architecture
should make choosing whether to keep a value in a register
substantially simpler.  Having a larger number of of orthogonal
registers makes register allocation easier.  Even the fixed
instruction size should simplify optimization for code size, fetch
alignment, or cache line crossing.  RISC simplifies tradeoffs
by removing choice.

In a CISC, the writer of an optimizing compiler must make
decisions about the cost of using a complex instruction or a
series of simpler instructions.  Even if it is guaranteed that
for all implementations the complex instruction will be faster
in all circumstances relative to the same semantic expressed
as a sequence of simpler instructions (and this was often not
the case), there can still be cases in which fewer simple
instructions might be needed for the desired semantic effect
but the complex instruction is more space efficient (which
can be significant for performance) or even have better
isolated performance.

If the CISC is not orthogonal (which can be desirable for
targeting code density), then further complexity is added to
the compiler.  In addition, traditional CISCs have relatively
few registers, which makes register allocation choices
more difficult even if the ISA does not have special
registers (even if the special register operations have
alternate encodings without the register restrictions, the
compiler must make a choice about whether to use the
presumably shorter, possibly preferred form--and have
more complex register handling--or the more generic form--
and sacrifice the size and other possible benefits of the
restricted-register format).

Most CISCs (like RISCs designed for code density) also
use destructive operations.  If non-destructive formats
are not provided, then register allocation (and the choice
of when to use register-register move operations) becomes
more complex.

CISCs also have the issue of "semantic clash" where a
complex instruction does not fit the semantic of the
language/compiler/programmer.

CISC also makes instruction scheduling more complex
and more limited.  Even if complex instructions are
optimized for every implementation (which historically
has not been the case), using simple instructions allows
operations to be interleaved outside of the larger units
covered by complex instructions.

In general, a CISC can be emulated by providing macros
that translate a complex pseudo-instruction into a fixed
sequence of simple instructions.

My guess is that CISCs were successful more from
code density (and microcode implementation techniques--
which I think involved tradeoffs in design complexity and
ROM vs. logic [and RAM] cost) than from compiler
complexity.  (Virtual memory also modestly complicates
the implementation of a non-load-store ISA.)

For a compiler performing minimal optimizations, a CISC
compiler might be easier to implement if the CISC
instructions match well to the programming language
primitives.  Such a compiler would tend to have difficulty
supporting multiple languages (and perhaps even language
extensions) and multiple ISAs (if the chosen instructions
are different).  Translating source code into primitive
operations seems to be standard practice now (and I
suspect such is not just "fashion").

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

#6536

In article <6799b00c-7c9e-4f0c-9a97-3994c3d81b5f@x17g2000vba.googlegroups.com>,
Paul A. Clayton <paaronclayton@gmail.com> 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.


Regards,
Nick Maclaren.

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

#6542

On 04/14/12 13:50, nmm1@cam.ac.uk wrote:

>
> 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.
>

Saying that risc is easier for compiler writers makes virtue of the 
necessity
that there is less to choose from, whereas a better solution might be more
machine fluent compiler writers ?. Perhaps the lines have become blurred, in
that features considered cisc like are now found in risc devices. The 
arm cortex
m3, for example, has conditional execution and also the ability to select
if flags are set on some instructions, In comparison to 68k, the only things
missing are a few addressing modes. The orthoganality and elegance from a
programming point of view are retained.

Imo, the real problem is more fundamental, in that once code is 
compiled, there
is a disconnect between the programmers intent, in terms of algorithm, 
optimisation
opportunity etc and the machine. For most desktop apps, the speed 
problem was solved
10 years ago, so perhaps it's time to put more intelligence / high level 
language
awareness into the silicon. Not a new idea, as pdp11 had a commercial 
instruction
set option in a 40 pin package decades ago. Primitive, yes, but no doubt 
usefull.
No idea how this could be done now, but perhaps something like downloadable
microcode reflecting language characteristics, written by the compiler 
vendor,
would get it started...

Regards,

Chris

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

#6544

On Apr 14, 12:01 pm, ChrisQ <blackh...@devnull.com> wrote:
> For most desktop apps, the speed
> problem was solved
> 10 years ago, so perhaps it's time to put more intelligence / high level
> language
> awareness into the silicon. Not a new idea, as pdp11 had a commercial
> instruction
> set option in a 40 pin package decades ago. Primitive, yes, but no doubt
> usefull.

That's actually not the same thing as making the silicon more aware of
a higher-level language. The 360 also had decimal and string
instructions for business work; this is simply a specialized datatype,
like floating point for scientific work.

There certainly were machines that implemented higher-level languages
more directly, though. There were stack machines, like the Burroughs
machines and the KDF9. There was an experimental 360/40 or 360/30 that
was used to run APL directly with custom microcode.

But the speed problem is "solved" on today's chips because they're
hardwired, _not_ microcoded. Using known approaches to shift the
instruction set towards the HLL would mean one would have to use much
smaller and slower processor designs as the basis.

John Savard

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

#6546

Quadibloc <jsavard@ecn.ab.ca> writes:
> There certainly were machines that implemented higher-level languages
> more directly, though. There were stack machines, like the Burroughs
> machines and the KDF9. There was an experimental 360/40 or 360/30 that
> was used to run APL directly with custom microcode.

there was 360/50 that had specialized micrcode for CPS
... conversational programing system for pli and basic. CPS was done by
IBM Boston Programming Center on 3rd flr of 545 tech sq (IBM science
center was on 4th flr, and multics was on 5th flr) ... some amount
subcontracted to allen-babcock:
http://www.bitsavers.org/pdf/allen-babcock/cps/CPS_Progress_Report_may66.pdf

IBM cambridge science center did port of apl\360 to cp67/cms for
cms\apl.  IBM palo alto science center then did apl\cms for vm370/cms
... as well as the corresponding apl microcode assist for the 370/145.

some amount of 360 emulation was done for PALM (earlier had been SCAMP)
... used to run apl\360 for the 5100 ... done at the IBM palo alto
science center.
http://www.brouhaha.com/~eric/retrocomputing/ibm/5100/
http://en.wikipedia.org/wiki/IBM_5100
http://www.classiccmp.org/dunfield/ibm5100/index.htm

-- 
virtualization experience starting Jan1968, online at home since Mar1970

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

#6556

On Apr 14, 2:01 pm, ChrisQ <blackh...@devnull.com> wrote:
[snip]
> Saying that risc is easier for compiler writers makes
> virtue of the necessity that there is less to choose from,
> whereas a better solution might be more  machine fluent
> compiler writers ?.

I took your statement "Raw hardware performance is of little
use if there are not enough competent programmers to write
decent compilers for them" to indicate that the limit was
compiler writers time and ability and that CISC made the
task of writing a decent compiler easier.

Since a CISC more closely links instruction selection with
scheduling, register allocation, and code layout (i.e.,
is less orthogonal to the compiler writer), it makes
optimization more difficult.

Since successful ISAs have multiple implementations, the
tradeoffs in instruction selection are more likely to
change for a CISC.  (Instruction selection can change for
RISCs as well--e.g., transformations that do more work
but reduce path length in a superscalar implementation--,
but such will be less common.)  Forcing implementers to
maintain performance compatibility (in terms of
instruction selection), places an artificial limit on
the implementation.

> Perhaps the lines have become blurred, in that features
> considered cisc like are now found in risc devices. The
> arm cortex m3, for example, has conditional execution

Predication is not a particular CISC feature.  In fact,
VLIWs are known for using predication and being motivated
by taking RISC philosophy of moving work to the compiler
even further.

Complete predication is more orthogonal than limiting
predication to register select (and conditional store
and a few other variations); but high performance
implementation of predication is more difficult.

> and also the ability to select if flags are set on some
> instructions, In comparison to 68k, the only things
> missing are a few addressing modes. The orthoganality
> and elegance from a programming point of view are
> retained.
>
> Imo, the real problem is more fundamental, in that
> once code is compiled, there is a disconnect between
> the programmers intent, in terms of algorithm,
> optimisation opportunity etc and the machine. For
> most desktop apps, the speed problem was solved 10
> years ago, so perhaps it's time to put more
> intelligence / high level language awareness into
> the silicon.

One problem with closing the semantic gap is that
translating intent into direct actions is not trivial.
While providing a "sort" instruction communicates
more intent (facilitating microarchitectural and
dynamic data-dependent optimizations), implementing
such an instruction in hardware would be complex.

In addition, one would want the ability to add to
the library of supported operations.  Requiring
every implementation of an ISA to include all the
libraries of operations that are useful to someone
would be impractical.  Even software has found it
useful to change interfaces to operations as well
as change the implementation.

It is also not trivial to predict what information
future hardware might be able to use effectively.

One could conceive of a system that integrated
compilation (somewhat like Transmeta's Code
Morphing Software) with different degrees of
caching persistence to exploit different degrees
of locality of usage pattern where the software
distribution format was more "expressive" than
a traditional ISA.  Some of the 'cache' might
even be on the network, allowing new 'instructions'
and new optimizations to be provided.

Such a system-level design would have advantages,
but the cooperation required seems unlikely given
the current environment.  Such cooperation also
tends to lead to artificial pricing (e.g., through
lock-in).

[This was a longer post than intended.  I hope
I have not wasted "too much" of others time.]

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

#6588

In article <jmce1u$i6n$1@speranza.aioe.org>, blackhole@devnull.com says...
>
>On 04/14/12 13:50, nmm1@cam.ac.uk wrote:
>
>>
>> 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.
>>
>
>Saying that risc is easier for compiler writers makes virtue of the 
>necessity
>that there is less to choose from, whereas a better solution might be more
>machine fluent compiler writers ?. Perhaps the lines have become blurred, in
>that features considered cisc like are now found in risc devices. The 
>arm cortex
>m3, for example, has conditional execution and also the ability to select
>if flags are set on some instructions, In comparison to 68k, the only things
>missing are a few addressing modes. The orthoganality and elegance from a
>programming point of view are retained.
>
>Imo, the real problem is more fundamental, in that once code is 
>compiled, there
>is a disconnect between the programmers intent, in terms of algorithm, 
>optimisation
>opportunity etc and the machine. For most desktop apps, the speed 
>problem was solved
>10 years ago, so perhaps it's time to put more intelligence / high level 
>language
>awareness into the silicon. Not a new idea, as pdp11 had a commercial 
>instruction
>set option in a 40 pin package decades ago. Primitive, yes, but no doubt 
>usefull.
>No idea how this could be done now, but perhaps something like downloadable
>microcode reflecting language characteristics, written by the compiler 
>vendor,
>would get it started...
>

You mean like what the Burroughs Small Systems did 25-30 years ago?

		- Tim

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

#6555

On Apr 14, 9:50 am, n...@cam.ac.uk wrote:
> In article <6799b00c-7c9e-4f0c-9a97-3994c3d81...@x17g2000vba.googlegroups.com>,
> Paul A. Clayton <paaronclay...@gmail.com> wrote:
[snip]
> >It is probably more difficult to write an _optimizing_ compiler for
> >CISC than for RISC.  ...
>
> He did say "orthogonal", and is probably right there.

Could you unpack that statement.  It seems to me that a CISC
would include all the instructions in a RISC plus instructions
which are semantically just sequences of RISC instructions
(with the potential--not necessarily guaranteed--difference of
being atomic with respect to interrupts).

An optimizing compiler for a CISC (even ignoring register
count differences) must make a decision of when to use a
complex instruction versus using simple instructions that
can be scheduled independently (and might do less work
than the complex instruction).  At worst, the RISC
compiler can use macros to implement CISC instructions,
and just as the provider of a CISC implementation provides
the implementation of the complex instructions, the
provider of a RISC implementation could provide a
reference set of macros.

A source code sequence that translates trivially to
three complex instructions might translate into nine
simple instructions (which can be independently
scheduled for the pipeline) or three less complex
instructions and three simple instructions.  An
optimizing compiler would have to evaluate all three
possibilities; for a RISC the compiler only needs to
evaluate one.

Furthermore, CISC is usually not a load-store ISA.  This
necessarily complicates register allocation and
instruction selection decisions by fusing the two concerns.

Variable length (or variable work) instructions also ties
instruction selection with code layout.

> 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.

Other than delayed branches (and for Alpha, lack of smaller
memory operations--both of which were performance hacks),
to what constraints, semantics, and idiosyncrasies are you
referring?  (A number of early RISCs handled multiplication
poorly as well--even MIPS with its HI and LO result
registers is non-orthogonal.)

(Note that I like some of the semantic content--which in
some cases can reduce the amount of physical work necessary
or facilitate other microarchitectural optimizations--and
code density features of CISC.  I just do not see how an
optimizing CISC compiler would be easier to write--but I
am not even a programmer, so my ignorance is vast.)

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

#6557

In article <5623c8b4-715e-4ee3-8440-ed4331416aee@z3g2000vbk.googlegroups.com>,
Paul A. Clayton <paaronclayton@gmail.com> wrote:
>[snip]
>> >It is probably more difficult to write an _optimizing_ compiler for
>> >CISC than for RISC. =A0...
>>
>> He did say "orthogonal", and is probably right there.
>
>Could you unpack that statement.  It seems to me that a CISC
>would include all the instructions in a RISC plus instructions
>which are semantically just sequences of RISC instructions
>(with the potential--not necessarily guaranteed--difference of
>being atomic with respect to interrupts).

I am afraid that's far too simplistic and even naive.  The problem
with the so-called RISC designs wasn't the fact that they often
had more instructions than CISC ones, but that the semantics of
the instructions they did have were often highly unsuitable for
programming with and with extremely non-orthogonal semantics.

Such delights as not being allowed an instruction of type X within
3 executed instructions of one of type Y, when the former updated
register A and the latter used register A for address calculations.
That's invented, but was the sort of thing that did get specified.


Regards,
Nick Maclaren.

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

#6560

On Mon, 16 Apr 2012 18:09:00 +0100, nmm1 wrote:

> In article
> <5623c8b4-715e-4ee3-8440-ed4331416aee@z3g2000vbk.googlegroups.com>,
> Paul A. Clayton <paaronclayton@gmail.com> wrote:
>>[snip]
>>> >It is probably more difficult to write an _optimizing_ compiler for
>>> >CISC than for RISC. =A0...
>>>
>>> He did say "orthogonal", and is probably right there.
>>
>>Could you unpack that statement.  It seems to me that a CISC would
>>include all the instructions in a RISC plus instructions which are
>>semantically just sequences of RISC instructions (with the
>>potential--not necessarily guaranteed--difference of being atomic with
>>respect to interrupts).
> 
> I am afraid that's far too simplistic and even naive.  The problem with
> the so-called RISC designs wasn't the fact that they often had more
> instructions than CISC ones, but that the semantics of the instructions
> they did have were often highly unsuitable for programming with and with
> extremely non-orthogonal semantics.

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.

What's non-orthogonal about a general 3-register instruction structure?

> Such delights as not being allowed an instruction of type X within 3
> executed instructions of one of type Y, when the former updated register
> A and the latter used register A for address calculations.
> That's invented, but was the sort of thing that did get specified.

Yes, some of the earlier RISCs didn't have full (or any) pipeline 
interlocks, which was unusual, but (IMO) a worthwhile experiment to see 
how much advantage for pipelining that could give you in return.  The 
most egregious example was probably the i860, but it was the fastest 
thing going for a significant chunk of time.  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.

In terms of actual instruction semantics (particularly arithmetic and 
logic instructions), you couldn't ask for more consistency or suitability 
for programming with...

Cheers,

-- 
Andrew

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

#6565

In article <9v3noiFchsU1@mid.individual.net>,
Andrew Reilly  <areilly.---@bigpond.net.au> wrote:
>>
>>>> >It is probably more difficult to write an _optimizing_ compiler for
>>>> >CISC than for RISC. =A0...
>>>>
>>>> He did say "orthogonal", and is probably right there.
>>>
>>>Could you unpack that statement.  It seems to me that a CISC would
>>>include all the instructions in a RISC plus instructions which are
>>>semantically just sequences of RISC instructions (with the
>>>potential--not necessarily guaranteed--difference of being atomic with
>>>respect to interrupts).
>> 
>> I am afraid that's far too simplistic and even naive.  The problem with
>> the so-called RISC designs wasn't the fact that they often had more
>> instructions than CISC ones, but that the semantics of the instructions
>> they did have were often highly unsuitable for programming with and with
>> extremely non-orthogonal semantics.
>
>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.

A lot of CISCs didn't have the former, and anyone with any Clue
knows that the latter or equivalent are almost essential for
compiler support.  However, I wasn't really talking about such
things, but about the general uncleanliness of most of their
designs when it came to boundary conditions and support for the
extended precisions often needed by languages.

I tried to code several important primitives on some and, in my
usual fashion, tried to get them right for all cases.  Ugh.  And
optimising compilers have serious problems producing good code
when its tricky to do so even by hand.  This was for things like
(A*B)/C->(quot,rem) with reliable overflow detection and no spurious
overflow.

>What's non-orthogonal about a general 3-register instruction structure?

You are STILL thinking solely in terms of the syntax!  It never
was that that was the problem - it was the semantics.  Compilers
have no trouble fixing up syntax oddities.


Regards,
Nick Maclaren.

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

#6566

nmm1@cam.ac.uk wrote:
> I tried to code several important primitives on some and, in my
> usual fashion, tried to get them right for all cases.  Ugh.  And
> optimising compilers have serious problems producing good code
> when its tricky to do so even by hand.  This was for things like
> (A*B)/C->(quot,rem) with reliable overflow detection and no spurious
> overflow.

:-)

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.

Using just portable 32-bit C, and unsigned only, you'll still need quite 
a bit of code...

uint32_t muldiv(uint32_t a, uint32_t b, uint32_t c, uint32_t *rem)
{
   uint32_t abl, abm1, abm2, abh;

   // None of the following operations can overflow

   // Do the 4 16*16->32 multiplications:
   abl = (a & 0xffff) * (b & 0xffff);
   abm1 = (a & 0xffff) * (b >> 16);
   abm2 = (a >> 16) * (b & 0xffff);
   abh = (a >> 16) *(b >> 16);

   // Merge into low/high result:
   abh += (abm1 >> 16) + (abm2 >> 16);
   abm1 = (abm1 & 0xffff) + (abm2 & 0xffff) + (abl >> 16);

   // Generate final abh:abl result:
   abh += abm1 >> 16;
   abl = (abl & 0xffff) | (abm1 << 16);

   // Now for the division part:

   // The division will overflow if C <= ABH, this includes the C==0 case
   // Return (0,C) if so:
   if (c <= abh) {
     *rem = c;
     return 0;
   }

   // At this point the fastest approach depends on the magnitude of C:
   // C < 64K: Use repeated 32/16 -> 16 divisions
   // C >= 64K: Do trial divisions using the top 16 bits of C
   // Fast fp? Calculate reciprocal and approximate answer,
   // adjust with a final loop.

}

The amount of code required does blow up pretty quickly when you don't 
have those N-2N operations!

Compare with x86 asm:
uint32_t muldiv(uint32_t a, uint32_t b, uint32_t c, uint32_t *rem)
{
   __asm {
     mov eax,[a]
     mul [b]
     div [c]  // Can trap here!
     mov ebx,[rem]
     mov [ebx],edx
   }
}

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

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

#6567

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.

Also, most 64-bit operations were/are library calls.

It's true.  I had my "all-the-world's 32-bit" tinted glasses on when I 
said that things were rosy.

Cheers,

-- 
Andrew

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

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

Back to top | Article view | comp.arch

csiph-web