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

Groups > comp.lang.forth > #41522 > unrolled thread

Registers..

Back to article view | Back to comp.lang.forth

Contents

  Registers.. Mux <Yvo.Zoer@gmail.com> - 2015-08-25 13:35 -0700
    Registers.. Mark Wills <markwills1970@gmail.com> - 2015-08-25 15:20 -0700
      Re: Registers.. Mux <Yvo.Zoer@gmail.com> - 2015-08-25 16:19 -0700
        Re: Registers.. "Elizabeth D. Rather" <erather@forth.com> - 2015-08-25 14:54 -1000
        Re: Registers.. rickman <gnuarm@gmail.com> - 2015-08-26 00:37 -0400
        Re: Registers.. Mat <dambere@web.de> - 2015-08-26 02:35 -0700
        Re: Registers.. hughaguilar96@gmail.com - 2015-08-26 10:24 -0700
          Re: Registers.. rickman <gnuarm@gmail.com> - 2015-08-26 23:56 -0400
      Re: Registers.. rickman <gnuarm@gmail.com> - 2015-08-26 00:35 -0400
    Re: Registers.. "Rod Pemberton" <boo@fasdfrewar.cdm> - 2015-08-25 22:32 -0400
      Re: Registers.. Mux <Yvo.Zoer@gmail.com> - 2015-08-25 19:58 -0700
        Re: Registers.. rickman <gnuarm@gmail.com> - 2015-08-26 00:43 -0400
    Re: Registers.. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-08-26 08:06 +0000
      Re: Registers.. Mux <Yvo.Zoer@gmail.com> - 2015-08-26 07:36 -0700
    Re: Registers.. Mat <dambere@web.de> - 2015-08-26 02:07 -0700
      Re: Registers.. rickman <gnuarm@gmail.com> - 2015-08-26 09:58 -0400
        Re: Registers.. Mat <dambere@web.de> - 2015-08-26 13:50 -0700
          Re: Registers.. rickman <gnuarm@gmail.com> - 2015-08-27 00:13 -0400
            Re: Registers.. Mat <dambere@web.de> - 2015-08-29 02:30 -0700
              Re: Registers.. rickman <gnuarm@gmail.com> - 2015-08-29 09:29 -0400
                Re: Registers.. Mat <dambere@web.de> - 2015-08-29 12:50 -0700
                  Re: Registers.. rickman <gnuarm@gmail.com> - 2015-08-30 11:13 -0400
                    Re: Registers.. Mat <dambere@web.de> - 2015-08-30 09:19 -0700
                      Re: Registers.. rickman <gnuarm@gmail.com> - 2015-08-30 15:44 -0400
                      Re: Registers.. hughaguilar96@gmail.com - 2015-08-30 14:06 -0700
                        Re: Registers.. Greg <abiforth@gmail.com> - 2015-08-30 21:07 -0700
                          Re: Registers.. Mat <dambere@web.de> - 2015-08-31 01:51 -0700
                            Re: Registers.. "Alex McDonald" <blog@rivadpm.com> - 2015-09-01 09:23 +0100
                    Re: Registers.. Mat <dambere@web.de> - 2015-08-30 10:08 -0700
                      Re: Registers.. rickman <gnuarm@gmail.com> - 2015-08-30 16:01 -0400

Page 1 of 2  [1] 2  Next page →

#41522 — Registers..

In sort of a follow up on my previous question (machine-forth != forth?) how do fine people feel about registers? Particularly curious about having one or more address registers.

While it makes things easier in the sense that memory instructions become more atomic, it strays away from the fact that you're now encroaching into the realm of register based machines IMO. It also messes with the fact that interrupts now need to start saving those registers, which isn't all that great.. 

-Y

[toc] | [next] | [standalone]

#41525

I'm currently of the opinion that register machines are superior to stack machines simply due to the fact that certain stack-shuffling sequences can be optimised away by a compiler compiling for a register machine whereas a swap is a swap on a stack machine. Therefore, on the face of it,  a register based machine has the potential to be faster. There may be other factors that I have not taken into account. This is not my area of expertise at all!

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

#41527

On Tuesday, August 25, 2015 at 3:20:38 PM UTC-7, Mark Wills wrote:
> I'm currently of the opinion that register machines are superior to stack machines simply due to the fact that certain stack-shuffling sequences can be optimised away by a compiler compiling for a register machine whereas a swap is a swap on a stack machine. Therefore, on the face of it,  a register based machine has the potential to be faster. There may be other factors that I have not taken into account. This is not my area of expertise at all!

Thanks for the comment, although I wasn't really trying to start a comparison between stack machines and register based machines. In fact, this has been put to rest when superscalar architectures came out. 

That said, stack machines DO have the ability to make up for their lack of performance by just stamping a LOT of them out on a single die and interconnecting them. The GA144 is a great example of that although somewhat botched in execution. 

Anyway, my question was whether or not you're treading into register machine territory by adding registers to the otherwise 'pure' stack machine architecture, which is, that everything uses the stack, including memory operations. The introduction of one or more registers seems to imply a shift from the core stack machine philosophy.

Just thinking out loud.. :-)

-Y

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

#41531

On 8/25/15 1:19 PM, Mux wrote:
> On Tuesday, August 25, 2015 at 3:20:38 PM UTC-7, Mark Wills wrote:
>> I'm currently of the opinion that register machines are superior to stack machines simply due to the fact that certain stack-shuffling sequences can be optimised away by a compiler compiling for a register machine whereas a swap is a swap on a stack machine. Therefore, on the face of it,  a register based machine has the potential to be faster. There may be other factors that I have not taken into account. This is not my area of expertise at all!
>
> Thanks for the comment, although I wasn't really trying to start a comparison between stack machines and register based machines. In fact, this has been put to rest when superscalar architectures came out.
>
> That said, stack machines DO have the ability to make up for their lack of performance by just stamping a LOT of them out on a single die and interconnecting them. The GA144 is a great example of that although somewhat botched in execution.
>
> Anyway, my question was whether or not you're treading into register machine territory by adding registers to the otherwise 'pure' stack machine architecture, which is, that everything uses the stack, including memory operations. The introduction of one or more registers seems to imply a shift from the core stack machine philosophy.
>
> Just thinking out loud.. :-)

Most of the Forth processors have had one or two registers. For example 
(from Greenarrays.com): "Each F18A contains 128 words of memory
(up to 512 instructions) plus 20 words of stacks and registers; no 
memory bottlenecks. 18-bit registers are S and T, the top two elements 
of the data stack; R, the top element of the return stack; and A, a 
read/write register. Address register B has 9 bits, and the
program counter P has 10."

Cheers,
Elizabeth

-- 
==================================================
Elizabeth D. Rather   (US & Canada)   800-55-FORTH
FORTH Inc.                         +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
==================================================

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

#41538

On 8/25/2015 7:19 PM, Mux wrote:
> On Tuesday, August 25, 2015 at 3:20:38 PM UTC-7, Mark Wills wrote:
>> I'm currently of the opinion that register machines are superior to stack machines simply due to the fact that certain stack-shuffling sequences can be optimised away by a compiler compiling for a register machine whereas a swap is a swap on a stack machine. Therefore, on the face of it,  a register based machine has the potential to be faster. There may be other factors that I have not taken into account. This is not my area of expertise at all!
>
> Thanks for the comment, although I wasn't really trying to start a comparison between stack machines and register based machines. In fact, this has been put to rest when superscalar architectures came out.
>
> That said, stack machines DO have the ability to make up for their lack of performance by just stamping a LOT of them out on a single die and interconnecting them. The GA144 is a great example of that although somewhat botched in execution.
>
> Anyway, my question was whether or not you're treading into register machine territory by adding registers to the otherwise 'pure' stack machine architecture, which is, that everything uses the stack, including memory operations. The introduction of one or more registers seems to imply a shift from the core stack machine philosophy.

You already have two stacks in the Forth model.  In my CPU designs I 
take advantage of that by using the return stack to hold the address for 
any memory operations.  I even give it some arithmetic capability to 
help with address and loop calculations.

-- 

Rick

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

#41551

Am Mittwoch, 26. August 2015 01:19:54 UTC+2 schrieb Mux:
> That said, stack machines DO have the ability to make up for their lack of performance by just stamping a LOT of them out on a single die and interconnecting them. The GA144 is a great example of that although somewhat botched in execution...

This strategy is limited by the increase of needed core management (or routing) specially for accessing shared, internal or external resources (which do not mean that it can not be done in an efficient way). Unfortunately, this implies increased complexity for optimizing compilers and because the demand for such tools increase with the inability for machine-oriented programming, this is a serious market? disadvantage if such compiler does not exist or the existing ones are to limited (well, in my subjective opinion of course)

> Anyway, my question was whether or not you're treading into register machine territory by adding registers to the otherwise 'pure' stack machine architecture, which is, that everything uses the stack, including memory operations. The introduction of one or more registers seems to imply a shift from the core stack machine philosophy. 

Indeed. This tendency can lead probably to accumulator-store architectures with implicit stack addressing.

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

#41565

On Tuesday, August 25, 2015 at 4:19:54 PM UTC-7, Mux wrote:
> Anyway, my question was whether or not you're treading into register machine territory by adding registers to the otherwise 'pure' stack machine architecture, which is, that everything uses the stack, including memory operations. The introduction of one or more registers seems to imply a shift from the core stack machine philosophy.

You may be interested in my FMITE design: http://www.forth.org/FMITE.txt

I have either one or two stack items in registers. At one time I had three, but that bloated out the instruction set too much, and I didn't expect the third register to be used very much because not many instructions (OVER and ROT etc.) actually used it.

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

#41573

On 8/26/2015 1:24 PM, hughaguilar96@gmail.com wrote:
> On Tuesday, August 25, 2015 at 4:19:54 PM UTC-7, Mux wrote:
>> Anyway, my question was whether or not you're treading into
>> register machine territory by adding registers to the otherwise
>> 'pure' stack machine architecture, which is, that everything uses
>> the stack, including memory operations. The introduction of one or
>> more registers seems to imply a shift from the core stack machine
>> philosophy.
>
> You may be interested in my FMITE design:
> http://www.forth.org/FMITE.txt

I can't seem to load that page.  I'd like to take a look.


> I have either one or two stack items in registers. At one time I had
> three, but that bloated out the instruction set too much, and I
> didn't expect the third register to be used very much because not
> many instructions (OVER and ROT etc.) actually used it.

Not sure why registers are significant.  If your design is implemented 
in an ASIC I guess that is the way to do it.  In an FPGA a stack would 
most likely be in memory where you can have two ports and read any two 
levels on each access.  Unless you want to use one of the two ports for 
some other function, no reason to use FF based registers.

Is it your intent the FMITE would be implemented in an ASIC or is it 
technology agnostic?

-- 

Rick

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

#41537

On 8/25/2015 6:20 PM, Mark Wills wrote:
> I'm currently of the opinion that register machines are superior to
> stack machines simply due to the fact that certain stack-shuffling
> sequences can be optimised away by a compiler compiling for a
> register machine whereas a swap is a swap on a stack machine.

I know when I was writing code for the GA144 I learned many techniques 
that would not only work, but would end up being faster than the obvious 
blunt method.  For example rather than subtracting by inverting the 
subtrahend and then adding a 1 before doing the add, the operands can be 
subtracted by inverting the minuend and the difference completely 
eliminating the addition of 1 saving several instructions. 
Interestingly enough, I found that every time I used this, the operands 
were already in the correct order saving a swap operation (which the 
GA144 doesn't even have) that would be needed with the obvious approach.

My point is that I think a compiler can do just as good a job of 
optimizing the stack code to eliminate the shuffling as it can optimize 
register usage.  It just has to be done with the same degree of effort.


> Therefore, on the face of it,  a register based machine has the
> potential to be faster. There may be other factors that I have not
> taken into account. This is not my area of expertise at all!

In the real world I'm not often concerned with highly optimized code.  I 
am not a compiler writer, but I can write very efficient stack code if I 
try.  Moderate optimization is pretty easy.

-- 

Rick

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

#41532

On Tue, 25 Aug 2015 16:35:43 -0400, Mux <Yvo.Zoer@gmail.com> wrote:

> In sort of a follow up on my previous question (machine-forth
> != forth?) how do fine people feel about registers?

I've programmed a few assembly languages and many high level
languages.  So, I feel fine with them.  How about you?  ...

> Particularly curious about having one or more address registers.

Oh, you meant registers in Forth ...  We'll call you "Mr. Vague."
:-)

Charles Moore used a temporary register in his Machine Forth called
the 'a' register.  The ability to move one stack or one return
stack item out of the way of a stack sequence or stack operation
can be useful, especially when implementing Forth system words
and using an interpreted Forth.

Some Forths keep the first and sometimes the second stack item in
registers.  These were known as TOS as top-of-stack and NOS as
next-on-stack, or somesuch ...  Someone with more in-depth Forth
history should be able to clarify.

The problem with stack items in registers is that the stack
implementation is split between a register or two and an actual
stack.  So, stack operations can be become more complicated
to implement, i.e., longer, slower.  E.g., think SWAP with one
item in register and the next on the stack.  Compare with both
items in register and both items on stack.  Even if two items
are in registers, this split-stack can affect other stack
operations that cross the boundary, e.g., ROT, ROLL, or which
add or remove stack items, e.g., DROP, DUP.  However, having
one or two stack items in register can allow for faster
fetch @ and store ! operations.  Since Forth uses many of these
to perform it's tasks, this may be advantageous enough to be
worthwhile even with the extra overhead added to stack
manipulation words.  I don't recall seeing any specific timing
data on one method versus the other.  If you trace your Forth
words, you could simply perform a count of how many @ and !
there are versus other stack words, DROP DUP SWAP OVER R> >R .
If @ and ! vastly outnumber the other words, then having TOS
and NOS in register would be advantageous.

You can also look at Rob Chapman's Stack Quarks for more insight
into this issue.


Rod Pemberton

--
Scientists now say we'll experience a mini-ice age in 2030.
So, I guess we need more global warming today ...

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

#41534

Considering this is comp.lang.forth I would have kinda assumed people would make the connection, alas.. :) 

And yes, I'm familiar with internal registers in forth cpu's. The difference between the TOS, NOS, PC and the instruction register is that they are transparent to the outside whereas the A (and B) register(s) are visible and, in case of an interrupt, would need to be saved. It also feels a bit like a hack to be honest, which is why I posed the question from a more philosophical point of view. Stack CPU's have a relatively consistent interface to the programmer which I feel is getting somewhat muddled when you start bolting on registers. Then again, it makes things more efficient, so I guess it's a bit of a trade off..

-mr. Vague

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

#41539

On 8/25/2015 10:58 PM, Mux wrote:
> Considering this is comp.lang.forth I would have kinda assumed people
> would make the connection, alas.. :)
>
> And yes, I'm familiar with internal registers in forth cpu's. The
> difference between the TOS, NOS, PC and the instruction register is
> that they are transparent to the outside whereas the A (and B)
> register(s) are visible and, in case of an interrupt, would need to
> be saved. It also feels a bit like a hack to be honest, which is why
> I posed the question from a more philosophical point of view. Stack
> CPU's have a relatively consistent interface to the programmer which
> I feel is getting somewhat muddled when you start bolting on
> registers. Then again, it makes things more efficient, so I guess
> it's a bit of a trade off..

The use of a stack in the programming model doesn't automatically deal 
with context switching for interrupts.  If an interrupt routine needs 
data between invocations, it has to use memory storage regardless of 
having registers or a stack.  Otherwise a register machine only needs to 
save the registers to be used in the interrupt which can be few.

You will notice that in the F18A and similar stack machines there are no 
interrupts resolving any issues with having registers.  Interrupts are 
considered an abomination by many CPU designers.  They do play hell with 
the architecture.

-- 

Rick

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

#41546

Mux <Yvo.Zoer@gmail.com> writes:
>In sort of a follow up on my previous question (machine-forth !=3D forth?) =
>how do fine people feel about registers? Particularly curious about having =
>one or more address registers.

With registers, you always have to worry about whether they are
caller-saved, callee-saved, used as parameters or return values.  The
stack provides a nice abstraction from these worries nonsense; if the
stack is too limited (requires too much stack juggling), then locals
are a solution that does not have the problems of registers and are
therefore preferable.

That's the programming POV.  From a hardware POV, the address
registers of Chuck Moore's recent chips allow to write stuff like MOVE
efficiently at little hardware cost that would be written in CODE in
Forths on other hardware, so implementing it in hardware is ok.  But I
think exposing it as a feature for higher-level programming makes
programming harder.

Hmm, if we want address thingies for the programmers, we could turn
the address registers into address stacks; the return stack is already
a stack, so only the A register would be turned into a stack.  That
would solve the saving issues; for parameters one could have the
convention that addresses are passed on the A stack.  One would
probably need to add ADUP ASWAP etc.  Are the benefits worth the
costs, or should we better stick with the data stack for passing
addresses around?

The A stack and D stack would be the stack machine equivalence of the
68000's A and D registers: a generalization of the 6800's index (X)
and accumulator (A); in contrast, standard Forth's data stack is the
stack equialent of the general-purpose registers of the PDP-11.

>While it makes things easier in the sense that memory instructions become m=
>ore atomic, it strays away from the fact that you're now encroaching into t=
>he realm of register based machines IMO.

So what?  Purity is for gurus.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2015: http://www.rigwit.co.uk/EuroForth2015/

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

#41559

On Wednesday, August 26, 2015 at 1:50:14 AM UTC-7, Anton Ertl wrote:
>
> >In sort of a follow up on my previous question (machine-forth !=3D forth?) =
> >how do fine people feel about registers? Particularly curious about having =
> >one or more address registers.
> 
> With registers, you always have to worry about whether they are
> caller-saved, callee-saved, used as parameters or return values.  The
> stack provides a nice abstraction from these worries nonsense; if the
> stack is too limited (requires too much stack juggling), then locals
> are a solution that does not have the problems of registers and are
> therefore preferable.
> 
> That's the programming POV.  From a hardware POV, the address
> registers of Chuck Moore's recent chips allow to write stuff like MOVE
> efficiently at little hardware cost that would be written in CODE in
> Forths on other hardware, so implementing it in hardware is ok.  But I
> think exposing it as a feature for higher-level programming makes
> programming harder.
> 
> Hmm, if we want address thingies for the programmers, we could turn
> the address registers into address stacks; the return stack is already
> a stack, so only the A register would be turned into a stack.  That
> would solve the saving issues; for parameters one could have the
> convention that addresses are passed on the A stack.  One would
> probably need to add ADUP ASWAP etc.  Are the benefits worth the
> costs, or should we better stick with the data stack for passing
> addresses around?
> 
> The A stack and D stack would be the stack machine equivalence of the
> 68000's A and D registers: a generalization of the 6800's index (X)
> and accumulator (A); in contrast, standard Forth's data stack is the
> stack equialent of the general-purpose registers of the PDP-11.
> 
> >While it makes things easier in the sense that memory instructions become m=
> >ore atomic, it strays away from the fact that you're now encroaching into t=
> >he realm of register based machines IMO.
> 
> So what?  Purity is for gurus.
> 
> - anton
> -- 
> M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
> comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
>      New standard: http://www.forth200x.org/forth200x.html
>    EuroForth 2015: http://www.rigwit.co.uk/EuroForth2015/

I think you kinda hit the nail on the head there. From a hardware (and performance) pov it does make sense to have an address register. What Anton pointed out as well is that you now have to deal with saving the state of that register if you have interrupts. That in itself leads to an interesting discussion as to whether you should actually have interrupts or not, especially if you're going multicore like the GA144 where you basically stall and therefore don't really care about the state.

The idea of an 'address stack' is an interesting one btw.. It wouldn't need to be very deep either. Maybe a few entries?

To Rickman's comment (can I call you Rick?) I wasn't talking about complete context switching, just interrupts. As a result the interrupt becomes nothing more than a subroutine call.

Chuck's / GA's solution to communication across CPU's seems to follow his usual KISS approach where CPU's just stall. XMOS on the other hand uses a dedicated switch to reduce CPU overhead.

Anyway, fun to argue the sides of purism -vs- implementation. Thanks!

-Y

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

#41549

Am Dienstag, 25. August 2015 22:35:45 UTC+2 schrieb Mux:
> In sort of a follow up on my previous question (machine-forth != forth?) how do fine people feel about registers? Particularly curious about having one or more address registers...

Hello,
In terms of code flexibility, disadvantages of stack versus register files surely depends on frequent code patterns, parameter usage and the specific subroutine-branch overhead. In terms of design, the implicit addressing of stack files can lead to very compact opcode formats in comparison to designs which are based on explicit register addressing because of the additional needed code-space for register assignment (an exception of this may are accumulator-store architectures). As one recent bottleneck (both in terms of implementation effort and energy efficiency which both can be related together) of recent processors is (more or less) the access-time decrease to external memory, where a compact code format help reducing implementation complexity and can lead to higher cache efficiency. This affect performance and energy usage directly.

However, the main disadvantage of stack architectures is the inevitable serial nature of program code which increases complexity if not make it impossible to exploit parallelism at instruction level - at least with conventional established methods.

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

#41558

On 8/26/2015 5:07 AM, Mat wrote:
> Am Dienstag, 25. August 2015 22:35:45 UTC+2 schrieb Mux:
>> In sort of a follow up on my previous question (machine-forth !=
>> forth?) how do fine people feel about registers? Particularly
>> curious about having one or more address registers...
>
> Hello, In terms of code flexibility, disadvantages of stack versus
> register files surely depends on frequent code patterns, parameter
> usage and the specific subroutine-branch overhead. In terms of
> design, the implicit addressing of stack files can lead to very
> compact opcode formats in comparison to designs which are based on
> explicit register addressing because of the additional needed
> code-space for register assignment (an exception of this may are
> accumulator-store architectures). As one recent bottleneck (both in
> terms of implementation effort and energy efficiency which both can
> be related together) of recent processors is (more or less) the
> access-time decrease to external memory, where a compact code format
> help reducing implementation complexity and can lead to higher cache
> efficiency. This affect performance and energy usage directly.
>
> However, the main disadvantage of stack architectures is the
> inevitable serial nature of program code which increases complexity
> if not make it impossible to exploit parallelism at instruction level
> - at least with conventional established methods.

I don't think that is true.  If I can figure out what can be done in 
parallel by looking at machine code, why can't a compiler.  Stack 
architectures are no more inherently serial than register designs.

-- 

Rick

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

#41569

Am Mittwoch, 26. August 2015 15:58:45 UTC+2 schrieb rickman:
> On 8/26/2015 5:07 AM, Mat wrote:
> > Am Dienstag, 25. August 2015 22:35:45 UTC+2 schrieb Mux:
> >> In sort of a follow up on my previous question (machine-forth !=
> >> forth?) how do fine people feel about registers? Particularly
> >> curious about having one or more address registers...
> >
> > Hello, In terms of code flexibility, disadvantages of stack versus
> > register files surely depends on frequent code patterns, parameter
> > usage and the specific subroutine-branch overhead. In terms of
> > design, the implicit addressing of stack files can lead to very
> > compact opcode formats in comparison to designs which are based on
> > explicit register addressing because of the additional needed
> > code-space for register assignment (an exception of this may are
> > accumulator-store architectures). As one recent bottleneck (both in
> > terms of implementation effort and energy efficiency which both can
> > be related together) of recent processors is (more or less) the
> > access-time decrease to external memory, where a compact code format
> > help reducing implementation complexity and can lead to higher cache
> > efficiency. This affect performance and energy usage directly.
> >
> > However, the main disadvantage of stack architectures is the
> > inevitable serial nature of program code which increases complexity
> > if not make it impossible to exploit parallelism at instruction level
> > - at least with conventional established methods.
> 
> I don't think that is true.  If I can figure out what can be done in 
> parallel by looking at machine code, why can't a compiler.  Stack 
> architectures are no more inherently serial than register designs.
> 
> -- 
> 
> Rick

Probably we have different definitions of instruction level parallelism in mind. If you take a look at stack code you can recognize that most instructions depend on the finished execution of the previous one simply because there exist one possible destination for computed results, the actual top-of-stack element. Exceptions from this are only either direct memory locations or probably some additional registers available.

With a register based architectures however (specially a tree operand ISA) direct register scheduling is possible because the storage destination is not fixed. Whether this is exploited then depends on the processor implementation whereby common approaches are super scalar pipelined out-of-order and in-order pipelined designs (beside VLIW oriented architectures).

Let's discuss the processing of each execution strategy (shortly):

With respect to some simplifications, in the first case instructions are probably rearranged to avoid RAW, WAR and RAR stalls, finally decoded and corresponding control codes of INDEPENDENT instructions distributed to shared internal buffers in which execution is done for each execution pipeline (or pool of different pipelines) out-of-order by 'choosing' one buffered 'instruction' dependent of the internal pipeline states which do not need to be related to the instruction dependencies of the actual processed code sequence. The calculated results are there after resorted and in-order written to the specific destination locations whereby in the worst case pipelines need to be stalled (external memory accesses are handled differently, there are often prefetched dependent of heuristic algorithms).

For a register based ISA this is efficient although energy-intense because instruction sequences tend to have short data dependencies (alias dependency paths). For a stack based architecture however it is common that data dependencies consist until the next independent subroutine call. This lead to the situation that typical code sequences are often simply to large to be effective scheduled to the units.

In-order pipelined implementations:

Here instructions are decoded and executed dependent of there code position. For super scalar designs that means that instructions are decoded and control codes buffered in order of there position in the instruction sequence.

For such architectures (such as early ATOM CPU's from Intel) a register based design is of advantage because instructions tend to have short dependencies ... as the storage destination is not fixed whereby stack based code would execute instruction for instruction successively although pipelined for there whole (long) dependency path.

VLIW architectures:

Because these implementation strategy delegate instruction-level parallelism completely to a compiler (or assembler programmer) there is no hope that stack based code can be efficient encoded for such architectures as long as there do not exist several independent stacks for which independent instruction sequences can be encoded. Anyhow, the chance for high unit utilization is questionable again because of the longer dependency paths (again).

Finally, if you look at unencoded stack architectures (probably what you mean with instruction-level parallelism) these code formats just encode the unit control explicitly (load TOS, increment an index register and the data-stack pointer for example). The code format nevertheless encode single instructions.

-Mat.

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

#41574

On 8/26/2015 4:50 PM, Mat wrote:
> Am Mittwoch, 26. August 2015 15:58:45 UTC+2 schrieb rickman:
>> On 8/26/2015 5:07 AM, Mat wrote:
>>> Am Dienstag, 25. August 2015 22:35:45 UTC+2 schrieb Mux:
>>>> In sort of a follow up on my previous question (machine-forth
>>>> != forth?) how do fine people feel about registers?
>>>> Particularly curious about having one or more address
>>>> registers...
>>>
>>> Hello, In terms of code flexibility, disadvantages of stack
>>> versus register files surely depends on frequent code patterns,
>>> parameter usage and the specific subroutine-branch overhead. In
>>> terms of design, the implicit addressing of stack files can lead
>>> to very compact opcode formats in comparison to designs which are
>>> based on explicit register addressing because of the additional
>>> needed code-space for register assignment (an exception of this
>>> may are accumulator-store architectures). As one recent
>>> bottleneck (both in terms of implementation effort and energy
>>> efficiency which both can be related together) of recent
>>> processors is (more or less) the access-time decrease to external
>>> memory, where a compact code format help reducing implementation
>>> complexity and can lead to higher cache efficiency. This affect
>>> performance and energy usage directly.
>>>
>>> However, the main disadvantage of stack architectures is the
>>> inevitable serial nature of program code which increases
>>> complexity if not make it impossible to exploit parallelism at
>>> instruction level - at least with conventional established
>>> methods.
>>
>> I don't think that is true.  If I can figure out what can be done
>> in parallel by looking at machine code, why can't a compiler.
>> Stack architectures are no more inherently serial than register
>> designs.
>>
>> --
>>
>> Rick
>
> Probably we have different definitions of instruction level
> parallelism in mind. If you take a look at stack code you can
> recognize that most instructions depend on the finished execution of
> the previous one simply because there exist one possible destination
> for computed results, the actual top-of-stack element. Exceptions
> from this are only either direct memory locations or probably some
> additional registers available.

Not sure what you mean by all this.  Whether or not two operations can 
be paralleled or not has to do with whether the results of one operation 
are needed as inputs to the other.  Where the results are stored is not 
relevant.

-- 

Rick

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

#41604

Am Donnerstag, 27. August 2015 06:13:18 UTC+2 schrieb rickman:
> On 8/26/2015 4:50 PM, Mat wrote:
> > Am Mittwoch, 26. August 2015 15:58:45 UTC+2 schrieb rickman:
> >> On 8/26/2015 5:07 AM, Mat wrote:
> >>> Am Dienstag, 25. August 2015 22:35:45 UTC+2 schrieb Mux:
> >>>> In sort of a follow up on my previous question (machine-forth
> >>>> != forth?) how do fine people feel about registers?
> >>>> Particularly curious about having one or more address
> >>>> registers...
> >>>
> >>> Hello, In terms of code flexibility, disadvantages of stack
> >>> versus register files surely depends on frequent code patterns,
> >>> parameter usage and the specific subroutine-branch overhead. In
> >>> terms of design, the implicit addressing of stack files can lead
> >>> to very compact opcode formats in comparison to designs which are
> >>> based on explicit register addressing because of the additional
> >>> needed code-space for register assignment (an exception of this
> >>> may are accumulator-store architectures). As one recent
> >>> bottleneck (both in terms of implementation effort and energy
> >>> efficiency which both can be related together) of recent
> >>> processors is (more or less) the access-time decrease to external
> >>> memory, where a compact code format help reducing implementation
> >>> complexity and can lead to higher cache efficiency. This affect
> >>> performance and energy usage directly.
> >>>
> >>> However, the main disadvantage of stack architectures is the
> >>> inevitable serial nature of program code which increases
> >>> complexity if not make it impossible to exploit parallelism at
> >>> instruction level - at least with conventional established
> >>> methods.
> >>
> >> I don't think that is true.  If I can figure out what can be done
> >> in parallel by looking at machine code, why can't a compiler.
> >> Stack architectures are no more inherently serial than register
> >> designs.
> >>
> >> --
> >>
> >> Rick
> >
> > Probably we have different definitions of instruction level
> > parallelism in mind. If you take a look at stack code you can
> > recognize that most instructions depend on the finished execution of
> > the previous one simply because there exist one possible destination
> > for computed results, the actual top-of-stack element. Exceptions
> > from this are only either direct memory locations or probably some
> > additional registers available.
> 
> Not sure what you mean by all this.  Whether or not two operations can 
> be paralleled or not has to do with whether the results of one operation 
> are needed as inputs to the other.  Where the results are stored is not 
> relevant.
> 
> -- 
> 
> Rick

because the actual top-of-stack position is both source and destination for processed values, the (immediate) storage location matters. A general-purpose microprocessor has to check if the later instructions need outputs from earlier instructions. If each instruction depends on the result of the preceding instruction (that's the case for stack based code), then there are no instruction level opportunities for out-of-order execution, at least for conventional processor designs.

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

#41606

On 8/29/2015 5:30 AM, Mat wrote:
> Am Donnerstag, 27. August 2015 06:13:18 UTC+2 schrieb rickman:
>> On 8/26/2015 4:50 PM, Mat wrote:
>>> Am Mittwoch, 26. August 2015 15:58:45 UTC+2 schrieb rickman:
>>>> On 8/26/2015 5:07 AM, Mat wrote:
>>>>> Am Dienstag, 25. August 2015 22:35:45 UTC+2 schrieb Mux:
>>>>>> In sort of a follow up on my previous question
>>>>>> (machine-forth != forth?) how do fine people feel about
>>>>>> registers? Particularly curious about having one or more
>>>>>> address registers...
>>>>>
>>>>> Hello, In terms of code flexibility, disadvantages of stack
>>>>> versus register files surely depends on frequent code
>>>>> patterns, parameter usage and the specific subroutine-branch
>>>>> overhead. In terms of design, the implicit addressing of
>>>>> stack files can lead to very compact opcode formats in
>>>>> comparison to designs which are based on explicit register
>>>>> addressing because of the additional needed code-space for
>>>>> register assignment (an exception of this may are
>>>>> accumulator-store architectures). As one recent bottleneck
>>>>> (both in terms of implementation effort and energy efficiency
>>>>> which both can be related together) of recent processors is
>>>>> (more or less) the access-time decrease to external memory,
>>>>> where a compact code format help reducing implementation
>>>>> complexity and can lead to higher cache efficiency. This
>>>>> affect performance and energy usage directly.
>>>>>
>>>>> However, the main disadvantage of stack architectures is the
>>>>> inevitable serial nature of program code which increases
>>>>> complexity if not make it impossible to exploit parallelism
>>>>> at instruction level - at least with conventional
>>>>> established methods.
>>>>
>>>> I don't think that is true.  If I can figure out what can be
>>>> done in parallel by looking at machine code, why can't a
>>>> compiler. Stack architectures are no more inherently serial
>>>> than register designs.
>>>>
>>>> --
>>>>
>>>> Rick
>>>
>>> Probably we have different definitions of instruction level
>>> parallelism in mind. If you take a look at stack code you can
>>> recognize that most instructions depend on the finished execution
>>> of the previous one simply because there exist one possible
>>> destination for computed results, the actual top-of-stack
>>> element. Exceptions from this are only either direct memory
>>> locations or probably some additional registers available.
>>
>> Not sure what you mean by all this.  Whether or not two operations
>> can be paralleled or not has to do with whether the results of one
>> operation are needed as inputs to the other.  Where the results are
>> stored is not relevant.
>>
>> --
>>
>> Rick
>
> because the actual top-of-stack position is both source and
> destination for processed values, the (immediate) storage location
> matters. A general-purpose microprocessor has to check if the later
> instructions need outputs from earlier instructions. If each
> instruction depends on the result of the preceding instruction
> (that's the case for stack based code), then there are no instruction
> level opportunities for out-of-order execution, at least for
> conventional processor designs.

That is your mistake, assuming that stack based code has automatic 
dependencies.  If a, b, c, d are on the stack and the code is OR -rot 
AND swap, the values c and d do not have any impact on the calculation 
of AND while the result of OR has no impact on the calculation of AND. 
So there is no dependency and the two operations can be run in parallel.

You are thinking that because the operands of a calculation depend on 
their position in the stack, this creates dependencies between the 
various operations.  As shown above this is not correct.

-- 

Rick

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

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.forth

csiph-web