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

#6517

On 4/12/2012 5:25 PM, Quadibloc wrote:
> On Apr 12, 6:55 pm, Mark Thorson<nos...@sonic.net>  wrote:
>
>> Assume you have to write and read
>> each location at least once.  That
>> provides an upper bound on how much
>> memory a von Neumann machine can use.
>
> You haven't seen the quad-core machines turning up at your local
> computer store yet?
>
> That machines will continue to be von Neuman uniprocessor computers,
> rather than some sort of massively parallel architecture... is not a
> physical constraint, and, in fact, appears to be contra-indicated by
> current trends.
>
> So the fact that a machine with 2^80 bytes of RAM might also have 2^40
> processors (or just 2^30 processors) in it... is not necessarily a
> fatal obstacle to the existence of such a machine.
>
> John Savard

OK, what exactly does "Von Neuman architecture" mean to you? Not just 
you, John, but other comp.arch participants.

Uniprocessor - okay, I give, not interesting going forward.

However, I think of a quad core, or even a 2^40 processor system, as 
being a parallel Von Neuman machine.

Wikipedia says "First Draft of a Report on the EDVAC ... a design 
architecture for an electronic digital computer with subdivisions of a 
processing unit consisting of an arithmetic logic unit and processor 
registers, a control unit containing an instruction register and program 
counter, a memory to store both data and instructions, external mass 
storage, and input and output mechanisms."

Many parallel machines are going to look like this, at each node.

A neural net is non-Von, because it doesn't have the pieces: no PC, no 
separate program, the program is the interconnection network.

Thinking of the "von Neuman bottleneck" as a shared instruction and data 
bus that cannort fetch and instruction and do data memory at the same 
time is not interesting.  We have had Harvard cache architectures on von 
Neuman machines for years.  Programs *are* data, but not all the time: 
the data phase and the instruction phase tend to be fairly separate.

My take is that the sequencer, the PC, is the basic von Neuman 
bottleneck.  Somebody has to write a program that gets sequenced. 
Dataflow is between VN and neural nets, because the sequencing is not so 
explicit as in VN, but not as implicit or structured as in neural nets.

Perhaps most interesting is the possiblilty of non-von Neuman 
programming styles running on, whatever, possibly highly parallel von 
Neuman multiprocessors.  Programming, sequencing, is the true von Neuman 
bottleneck.  Logic programming is non-VN.

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

#6526

On Apr 12, 10:33 pm, "Andy (Super) Glew" <a...@SPAM.comp-arch.net>
wrote:

> Uniprocessor - okay, I give, not interesting going forward.
>
> However, I think of a quad core, or even a 2^40 processor system, as
> being a parallel Von Neuman machine.

I don't really claim that multi-processor systems are not von Neumann
machines, although as the number of processors is increased, the von
Neumann bottleneck is avoided.

There are "truly" non-von Neumann architectures, like neural nets, but
I do think that the classic von Neumann architecture is easier to
program and more general-purpose than anything different on a
fundamental level, even so minor a variation as dataflow.

So massively parallel systems are likely as close as we will get to
leaving the von Neumann model behind, at least for some time. So they
will be referred to as non-von Neumann machines, even if that isn't
fully justified, because they will be the standard way of escaping the
bottleneck.

John Savard

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

#6530

On Friday, April 13, 2012 5:57:51 PM UTC-5, Quadibloc wrote:
> So massively parallel systems are likely as close as we will get to
> leaving the von Neumann model behind, at least for some time. So they
> will be referred to as non-von Neumann machines, even if that isn't
> fully justified, because they will be the standard way of escaping the
> bottleneck.

These should be called MIMD machines, instead of non-von-Neumann.

Mitch

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

#6514

On 4/12/2012 5:55 PM, Mark Thorson wrote:
> Quadibloc wrote:
>>
>> 10^23 is about 2^76... and, thus, 80 bits or so is about the limit for
>> macroscopic memory devices storing one bit per atom.
>
> The limit is a lot lower than that.
> Assume you have to write and read
> each location at least once.  That
> provides an upper bound on how much
> memory a von Neumann machine can use.
>
> Even if you could make more memory,
> you wouldn't be able to use it.

But not necessarily on how much address space you can use.

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

#6494

360/67 had optional search-list instruction feature courtesy of lincoln
labs ... and many machines had it installed.

cp67 was changed to use search-list for storage management. blocks of
available storage were ordered on chain by real storage address
... allocation searching possibly avg. of several hundred elements for
allocation (best fit). search-list instruction possibly cut processing
by 2/3rds ... eliminating instruction fetch loop ... but was still
possibly starting to run 20% of processing (under large loads).

cp67 then changed storage management to "subpools" for most common sizes
... push/pop; 14 instructions in&out ... and total processing percentage
in the negligible range ... and everybody forgot about search-list.

original 64bit power/pc did have big argument with rochester that wanted
to move their as/400 cisc to power/risc. They argument was over having
65th bit as part of addresses ... which was used for totally different
purpose in as/400.

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

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

#6498

Since one needs access to the MMU for each loop through the memory access path, at best, you can skip the Address Generate stage of the pipeline, shrinking a 3 (or 4) cycle loop into a 2 (or 3) cycle loop.

I can agree that the upper 4-to-8 address bits in a 64-bit address are unlikely to be used (anytime soon) in the physical space, I am not so sure they are (or should be) available in the logical/virtual space.

But I am convinced more by the argument that most of the time one checks something (p != 0) before indirecting through it that software should be given primatives to do the work and not solutions that don't fit very well.

I do agree that this would be rather easy to implement in the data cache loop; However, it would make it considerably harder to schedule instructions through the address generator.

Mitch

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

#6502

On 4/10/2012 8:31 PM, Mark Thorson wrote:
> The PDP-10 and Nova had an indirect bit, in which a pointer
> had both an address and a bit to indicate whether the object
> being addressed was data or another pointer.

Pointer chasing via an indirect bit is just one example of an operation 
that might ber executed by PIM or LIM (Processing in Memory or Logic in 
Memory) - or, as I prefer to say, PnM (Processing near Memory), since it 
might be in the DRAM itself, or a memory controller, or somewhere in the 
network or a big supercomputer, or ...

http://semipublic.comp-arch.net/wiki/Logic_and_Processing_in_and_near_Memory

I quite like Peter Kogge's http://www.nd.edu/~pim/papers.html

At least you point out that a TLB is needed.

Now, the indirect bit is somewhat non-Von Neuman, in that the 
instruction (the indirect bit, saying "chase this pointer") is actually 
part of the data.  This is convenient for stuff like handles, and 
redirecting objects that are being garbage collected. But of course we 
would want to have instructions that ignore the indirect bit as well.

Further, there are quite a few other operations that might want to be 
executed remotely, at the memory cvontroller or nearer memory.  We of 
course know about atomic RMW operations, such as atomic increment a 
memory location.  But it is not just integer operations: floating point 
atomic RMWs, atomically add to a floating point sum, are commonly 
requested. (Which causes me to think of superaccumulators to avoid 
accuracy problems: atomically add to a superaccumulator).

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.

It's a slippery slope. The indirect bit is packaged with the data.  A 
limited set of atomic RMWs can be made part of the interconnect command 
set.  But at some point you graduate to sending little packets of 
instructions to the remote memory.  And the question is, what is their 
instruction set?

I'll take a swag:

Atomic RMWs, int and FP, are ready to fly now - although this may be a 
case of "tried in the past, and failed", that I am not recognizing as a 
failure.

The indirect bit is not good enough.  Too simplistic.  Definitely need 
to talk about adding offsets, and possibly searches for particular data 
patterns. Since I have never seen or come up with a reasonably 
satisfactory set, I fall down the slipper slope to some simple 
instruction packet.

By the way, in case anyone cares, some of the origonal Sony/Toshiba 
"Cell" patents were interesting along this line - but this nowhere seems 
to be in the current Cell family.

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

#6503

On Thursday, April 12, 2012 9:55:02 AM UTC-5, Andy (Super) Glew wrote:
> The indirect bit is not good enough.  Too simplistic.  Definitely need 
> to talk about adding offsets, and possibly searches for particular data 
> patterns. Since I have never seen or come up with a reasonably 
> satisfactory set, I fall down the slipper slope to some simple 
> instruction packet.

I believe that the S.E.L (n.e. Gould) 32 architecture supports indirection.
In this case, the data loaded from memory contains not just an indirect bit
but also another base register, and an offset so one could "do clever things".

But I agree with Andy, and as long as we have vonNeumann architectures, we
might as well have each instruction make a quantifiable amount of forward 
progress on behalf of the program running. Data marked with indirection 
does not qualify.

Mitch

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

#6504

An indirect chase read or write instruction pair, with indirection count, and offset literals (one for each count).

Such as 'load 0(r1), 3(r2), 6, 7, 3' may be very useful. But would be microcoded I suppose. With the 0 count being register direct.

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

#6518

On 4/12/2012 11:07 AM, jacko wrote:
> An indirect chase read or write instruction pair, with indirection count, and offset literals (one for each count).
>
> Such as 'load 0(r1), 3(r2), 6, 7, 3' may be very useful. But would be microcoded I suppose. With the 0 count being register direct.

Microcoded if you execute it at the CPU.

If executed outsiede the processor, well, each state transition may be 
executed at a memory node, and then the operation may have to be 
forwarded to the memory node where the next piece of data lives.

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

#6505

On 4/12/2012 10:16 AM, MitchAlsup wrote:
> On Thursday, April 12, 2012 9:55:02 AM UTC-5, Andy (Super) Glew wrote:
>> The indirect bit is not good enough.  Too simplistic.  Definitely need
>> to talk about adding offsets, and possibly searches for particular data
>> patterns. Since I have never seen or come up with a reasonably
>> satisfactory set, I fall down the slipper slope to some simple
>> instruction packet.
>
> I believe that the S.E.L (n.e. Gould) 32 architecture supports indirection.
> In this case, the data loaded from memory contains not just an indirect bit
> but also another base register, and an offset so one could "do clever things".

The Univac 1108 and its successors have an indirect bit in each 
instruction that has a memory address and the indirection includes not 
only the address and another indirect bit, but an index register and 
even a bit that indicates index register incrementation.  So you could 
really could "do clever things", especially once you realize that 
control instructions such as jump to the address given in the 
instruction could be indirected as well.  This allowed for some *really* 
clever things.

Interrupts were locked out during an indirect reference set and there 
was a hardware timer to prevent infinite loops.  The cleverness allowed 
was overwhelmed by the problems and this was deprecated in newer 
systems.  In fact, the "extended mode", which is used for most new 
software, redefined that instruction bit to something else thus 
eliminating the possibility of using this stuff except for legacy type 
software.  Almost certainly a good thing to do.



-- 
  - Stephen Fuld
(e-mail address disguised to prevent spam)

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

#6519

On 4/12/2012 11:35 AM, Stephen Fuld wrote:
> On 4/12/2012 10:16 AM, MitchAlsup wrote:
>> On Thursday, April 12, 2012 9:55:02 AM UTC-5, Andy (Super) Glew wrote:
>>> The indirect bit is not good enough. Too simplistic. Definitely need
>>> to talk about adding offsets, and possibly searches for particular data
>>> patterns. Since I have never seen or come up with a reasonably
>>> satisfactory set, I fall down the slipper slope to some simple
>>> instruction packet.
>>
>> I believe that the S.E.L (n.e. Gould) 32 architecture supports
>> indirection.
>> In this case, the data loaded from memory contains not just an
>> indirect bit
>> but also another base register, and an offset so one could "do clever
>> things".
>
> The Univac 1108 and its successors have an indirect bit in each
> instruction that has a memory address and the indirection includes not
> only the address and another indirect bit, but an index register and
> even a bit that indicates index register incrementation. So you could
> really could "do clever things", especially once you realize that
> control instructions such as jump to the address given in the
> instruction could be indirected as well. This allowed for some *really*
> clever things.

This is cool - I had forgotten about the SEL indirection, which really 
was not an indirection, more like an "execute instruction at this memory 
location".  Heck, I've still forgotten - I remember "execute instruction 
in register", and maybe in memory. Perhaps execute instruction in memory 
could be another execute instruction in memory, and so on.

(By the way, note: execute-instruction-in-memory is a special 
instruction, not just a load-word that looks for the indirect bit.)

But it also reveals the problem: execute-instruction-in-memory is easy 
if the memory location is fetched to the procewssor, and then executed 
by the processor, where it has access to all the processor state.

However, if you want to export it so that it is done outside the 
processor, how much state do you send?  The entire register set?  :-(
A bitmask indicating what registers to send? :-(

By now we are almost at an instruction packet - because if we send 
multiple registers, surely we would want to do multiple instructions? 
If only to build large constants on a RISC machine (not on a variable 
width ISA with full width constants.)

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

#6525

4 register is state. I shall say it no more.

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

#6549

On 4/12/2012 9:41 PM, Andy (Super) Glew wrote:

snip


> This is cool - I had forgotten about the SEL indirection, which really
> was not an indirection, more like an "execute instruction at this memory
> location". Heck, I've still forgotten - I remember "execute instruction
> in register", and maybe in memory. Perhaps execute instruction in memory
> could be another execute instruction in memory, and so on.
>
> (By the way, note: execute-instruction-in-memory is a special
> instruction, not just a load-word that looks for the indirect bit.)

Yes, but they are logically related in a sense.  The big difference is 
that with indirection, the op code comes from the original instruction 
whereas with with execute remote, the op code comes from the target 
instruction.  You do have many of the same issues - do you allow the 
target of an execute instruction to be an execute instruction, what 
about infinite loops, etc.?

BTW, there have been variants on the "simple" execute instruction.

The IBM S/360 and successors' execute instruction can optionally "or" 
some bits in a register specified in the execute instruction with 
certain bits in the instruction being executed (the instruction being 
executed is not modified in memory - only within the CPU and only for 
the duration of the executed instruction).

Also, extended mode on the Unisys 2200 series adds an execute repeat 
instruction.  This is sort of like the repeat prefix in X86 land.  The 
target instruction is executed multiple times.  When combined with index 
register incrementation in the target instruction, this can be very 
useful.  I guess it can also save some power, as the executed 
instruction need not be decoded multiple times, and the loop test and 
branch back is "built in" and thus doesn't require another instruction.

I would guess that there are others here who are familiar other 
variants, and urge them to chime in.

Note also that there can be interaction between indirection and and a 
remote execute instruction.  That is, within the execute instruction, 
the address of the instruction to be executed could be allowed to be 
specified as indirect. And the target instruction of an execute could 
also specify indirection.  This could all get "exciting"  :-)


-- 
  - Stephen Fuld
(e-mail address disguised to prevent spam)

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

#6550

Stephen Fuld wrote:
> Note also that there can be interaction between indirection and and a
> remote execute instruction. That is, within the execute instruction, the
> address of the instruction to be executed could be allowed to be
> specified as indirect. And the target instruction of an execute could
> also specify indirection. This could all get "exciting" :-)

I think the word you (or the cpu architects) are looking for is 
"interesting", as in "May you live in interesting times."

Terje

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

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

#6552

On 4/15/2012 1:45 PM, Terje Mathisen wrote:
> Stephen Fuld wrote:
>> Note also that there can be interaction between indirection and and a
>> remote execute instruction. That is, within the execute instruction, the
>> address of the instruction to be executed could be allowed to be
>> specified as indirect. And the target instruction of an execute could
>> also specify indirection. This could all get "exciting" :-)
>
> I think the word you (or the cpu architects) are looking for is
> "interesting", as in "May you live in interesting times."

Fair enough  :-)



-- 
  - Stephen Fuld
(e-mail address disguised to prevent spam)

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

#6515

On 4/12/2012 10:16 AM, MitchAlsup wrote:
> On Thursday, April 12, 2012 9:55:02 AM UTC-5, Andy (Super) Glew wrote:
>> The indirect bit is not good enough.  Too simplistic.  Definitely need
>> to talk about adding offsets, and possibly searches for particular data
>> patterns. Since I have never seen or come up with a reasonably
>> satisfactory set, I fall down the slipper slope to some simple
>> instruction packet.
>
> I believe that the S.E.L (n.e. Gould) 32 architecture supports indirection.
> In this case, the data loaded from memory contains not just an indirect bit
> but also another base register, and an offset so one could "do clever things".
>
> But I agree with Andy, and as long as we have vonNeumann architectures, we
> might as well have each instruction make a quantifiable amount of forward
> progress on behalf of the program running. Data marked with indirection
> does not qualify.
>
> Mitch

Actually, I think the indirect bit does make forward progress - modulo 
infinite loops.

Just not useful enough.  The simple indirect bit is only good enough for 
forwarding. I think more than that is necessary, or at least desirable.

The best argument that can be made for the indirect bit is that there is 
ample experience with it.

In http://semipublic.comp-arch.net/wiki/PIM_search_operations I mention 
some slightly more general operations that can do more general searches. 
  Probably something you would want to wrap in an instruction, but still 
less than the fairly full instruction set that Kogge's group proposes. 
things like search-linked-list, search-B-tree -- basically, searches on 
linked data structures *(LDT).

(By the way, in case anyone asks: LDTs, but NOT hash tables.  A single 
level of hash table seems to have little advantage PIM versus processor: 
after all, its O(1).  You can thing of these LDTs as searching in the 
hash bins or collision data structures, and/or doing ordered searches.)

We already mentioned atomics, as in 
http://semipublic.comp-arch.net/wiki/List_of_possible_atomic_RMW_operations

Q: what other classes of operations are suitable for remote access?

Ah, here's something obvious: block memory operations, copies, fills.

The problem is that so many operations require more than one memory 
location.  Unary vector is okay for PIM.  Vector op scalar is okay. 
Vector op vector starts getting challenging.  Certainly not impossible - 
certainly still a candidate for exporting from the processor.  E.g. to 
take advantage of David Shaw et al's result: the best place to do a 
computation is at the centroid of the data locations.  But now we are 
getting more into PII (Processing In Interconnect) and POOP (Processing 
Outside Of Processor), than PIM.

(Humor wise, that's bad even for me.)

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

#6506

In article <4F86ECC6.4060405@SPAM.comp-arch.net>, andy@SPAM.comp-arch.net 
says...
>

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

And I think you are well on your way to a dataflow architecture here...

		- Tim

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

#6520

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.

My possibly naive approach here would be to require a POD (program 
packet) to be smaller than the amount of data otherwise transported, 
with a few caveats:

a) The smallest relevant size is a single cache line.

b) If the POD don't need to send any results back, then it could be 
twice as large as the data (i.e. data must normally be both read and 
written back).

c) If the POD can be sent off _before_ the corresponding data could have 
have been loaded (I can't see how this is possible, but assuming it is), 
then we can exchange bandwidth for latency by sending a larger 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.

Same as above: The program needs to be smaller than the amount of data 
touched between each program movement.

> I'll take a swag:
>
> Atomic RMWs, int and FP, are ready to fly now - although this may be a
> case of "tried in the past, and failed", that I am not recognizing as a
> failure.

LOCK XADD is sort of doing most of this, IBMs version which adds basic 
logical operations as well is closer.

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

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

#6545

On 4/12/2012 11:54 PM, Terje Mathisen wrote:
> Andy (Super) Glew wrote:
> My possibly naive approach here would be to require a POD (program
> packet) to be smaller than the amount of data otherwise transported,
> with a few caveats:
>
> a) The smallest relevant size is a single cache line.
>
> b) If the POD don't need to send any results back, then it could be
> twice as large as the data (i.e. data must normally be both read and
> written back).
>
> c) If the POD can be sent off _before_ the corresponding data could have
> have been loaded (I can't see how this is possible, but assuming it is),
> then we can exchange bandwidth for latency by sending a larger 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.
>
> Same as above: The program needs to be smaller than the amount of data
> touched between each program movement.

These sound like good rules.  Trying to reduce the total amount of data 
traffic, i.e. bandwidth, roughly correlating to power.

But

(1) Needs to take into account the initial address request(s) as well as 
the data transferred.

(2) Latency is an extra consideration: if I have to send an address, 
wait to get the data, and then do the operation at the processor, I have 
had two of what we used to call "bus crossings". (What should we call 
them now, network traversals?  Fabric crossings?  There must be a pun 
there...)  More if the data then has to be sent to the next guy who 
wants to operate on the memory location.

Whereas is a send even a fairly large packet to wherever the data 
currently lives to do it remotely, I only have one bus crossing.  (Plus 
return traffic, certainly for fetch-and-op that returns the old value, 
as well as error reporting to the requester.)

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

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

Back to top | Article view | comp.arch

csiph-web