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 2 of 2 — ← Prev page 1 [2]

#41609

Am Samstag, 29. August 2015 15:29:54 UTC+2 schrieb rickman:
> 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

STACK:
a b c d = TOS

CODE:
OR    (a b c d - a b n)
-ROT  (a b n   - n a b)
AND   (n a b   - n m)
SWAP  (n m     - m n)

we try to execute AND and OR parallel:

1st possibility:

STACK: a b c d
-ROT     (a b c d - a d b c)
SWAP     (a d b c - a d c b)
OR | AND (a d c b - a d n - a m)

m n != a m (false stack order)

2st possibility:

STACK: a b c d
-ROT     (a b c d - a d b c)
OR | AND (a d b c - a d n - a m
SWAP     (a m - m a)

m n != m a (false stack order)

...
(I think to overview every possible combination with the conclusion that all computations lead to an incorrect stack order)
...

really bad is in addition, that the right order 'm n' isn't otherwise reconstructible because either 'm' or 'n' is consumed!

The only possibility I see is to combine the previous stack-shuffling instruction with the following logic operation:

OR  | -ROT
AND | SWAP

However because the stack-shuffling instructions '-ROT' and 'SWAP' change the order of input values for the next logic instruction both combined logic and stack addressing instructions can not executed parallel (there can be processed as instruction bundle of course) !

If you think otherwise, please give me a hint (possibly a link of an existing design), thanks.

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

#41611

On 8/29/2015 3:50 PM, Mat wrote:
> Am Samstag, 29. August 2015 15:29:54 UTC+2 schrieb rickman:
>> 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
>
> STACK:
> a b c d = TOS
>
> CODE:
> OR    (a b c d - a b n)
> -ROT  (a b n   - n a b)
> AND   (n a b   - n m)
> SWAP  (n m     - m n)
>
> we try to execute AND and OR parallel:
>
> 1st possibility:
>
> STACK: a b c d
> -ROT     (a b c d - a d b c)
> SWAP     (a d b c - a d c b)
> OR | AND (a d c b - a d n - a m)
>
> m n != a m (false stack order)
>
> 2st possibility:
>
> STACK: a b c d
> -ROT     (a b c d - a d b c)
> OR | AND (a d b c - a d n - a m
> SWAP     (a m - m a)
>
> m n != m a (false stack order)
>
> ...
> (I think to overview every possible combination with the conclusion that all computations lead to an incorrect stack order)
> ...
>
> really bad is in addition, that the right order 'm n' isn't otherwise reconstructible because either 'm' or 'n' is consumed!
>
> The only possibility I see is to combine the previous stack-shuffling instruction with the following logic operation:
>
> OR  | -ROT
> AND | SWAP
>
> However because the stack-shuffling instructions '-ROT' and 'SWAP' change the order of input values for the next logic instruction both combined logic and stack addressing instructions can not executed parallel (there can be processed as instruction bundle of course) !
>
> If you think otherwise, please give me a hint (possibly a link of an existing design), thanks.

Really?  You can't figure this out?  I don't know what your code above 
is trying to do.  You seem to want to execute all the instructions in 
different orders.  The stack juggling is there to bring the right items 
to the top of the stack so they can be operated on.  To optimize this 
you need hardware that can operate on data in other locations.

Processing in parallel means you have two things doing the processing. 
One does the operation on the two items at the top of the stack the 
other works on the two items below.

AND-ab | OR-cd

-- 

Rick

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

#41612

Am Sonntag, 30. August 2015 17:13:51 UTC+2 schrieb rickman:
> On 8/29/2015 3:50 PM, Mat wrote:
> > Am Samstag, 29. August 2015 15:29:54 UTC+2 schrieb rickman:
> >> 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
> >
> > STACK:
> > a b c d = TOS
> >
> > CODE:
> > OR    (a b c d - a b n)
> > -ROT  (a b n   - n a b)
> > AND   (n a b   - n m)
> > SWAP  (n m     - m n)
> >
> > we try to execute AND and OR parallel:
> >
> > 1st possibility:
> >
> > STACK: a b c d
> > -ROT     (a b c d - a d b c)
> > SWAP     (a d b c - a d c b)
> > OR | AND (a d c b - a d n - a m)
> >
> > m n != a m (false stack order)
> >
> > 2st possibility:
> >
> > STACK: a b c d
> > -ROT     (a b c d - a d b c)
> > OR | AND (a d b c - a d n - a m
> > SWAP     (a m - m a)
> >
> > m n != m a (false stack order)
> >
> > ...
> > (I think to overview every possible combination with the conclusion that all computations lead to an incorrect stack order)
> > ...
> >
> > really bad is in addition, that the right order 'm n' isn't otherwise reconstructible because either 'm' or 'n' is consumed!
> >
> > The only possibility I see is to combine the previous stack-shuffling instruction with the following logic operation:
> >
> > OR  | -ROT
> > AND | SWAP
> >
> > However because the stack-shuffling instructions '-ROT' and 'SWAP' change the order of input values for the next logic instruction both combined logic and stack addressing instructions can not executed parallel (there can be processed as instruction bundle of course) !
> >
> > If you think otherwise, please give me a hint (possibly a link of an existing design), thanks.
> 
> Really?  You can't figure this out?  I don't know what your code above 
> is trying to do.  You seem to want to execute all the instructions in 
> different orders.  The stack juggling is there to bring the right items 
> to the top of the stack so they can be operated on.  To optimize this 
> you need hardware that can operate on data in other locations.
> 
> Processing in parallel means you have two things doing the processing. 
> One does the operation on the two items at the top of the stack the 
> other works on the two items below.
> 
> AND-ab | OR-cd
> 
> -- 
> 
> Rick

Your imaginary stack processor can't process both logic instructions in parallel because there input depend on stack shuffling which need to be executed before these instructions are processed (this is what my example shows). As you have written yourself "The stack juggling is there to bring the right items  to the top of the stack so they can be operated on". Because "to optimize this you need hardware that can operate on data in other locations" the stack processor must be able to fetch data-stack values independent of the actual top-of-stack position otherwise both instructions process anything but the right values. This is however not a classic stack design I've had referenced to in my example so we both talked past each other here.

Beside the enormous effort for implementing such feature I can't see any advantage against a register ISA in this case (that was my entry point of view).

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

#41615

On 8/30/2015 12:19 PM, Mat wrote:
> Am Sonntag, 30. August 2015 17:13:51 UTC+2 schrieb rickman:
>> On 8/29/2015 3:50 PM, Mat wrote:
>>> Am Samstag, 29. August 2015 15:29:54 UTC+2 schrieb rickman:
>>>> 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
>>>
>>> STACK: a b c d = TOS
>>>
>>> CODE: OR    (a b c d - a b n) -ROT  (a b n   - n a b) AND   (n a
>>> b   - n m) SWAP  (n m     - m n)
>>>
>>> we try to execute AND and OR parallel:
>>>
>>> 1st possibility:
>>>
>>> STACK: a b c d -ROT     (a b c d - a d b c) SWAP     (a d b c - a
>>> d c b) OR | AND (a d c b - a d n - a m)
>>>
>>> m n != a m (false stack order)
>>>
>>> 2st possibility:
>>>
>>> STACK: a b c d -ROT     (a b c d - a d b c) OR | AND (a d b c - a
>>> d n - a m SWAP     (a m - m a)
>>>
>>> m n != m a (false stack order)
>>>
>>> ... (I think to overview every possible combination with the
>>> conclusion that all computations lead to an incorrect stack
>>> order) ...
>>>
>>> really bad is in addition, that the right order 'm n' isn't
>>> otherwise reconstructible because either 'm' or 'n' is consumed!
>>>
>>> The only possibility I see is to combine the previous
>>> stack-shuffling instruction with the following logic operation:
>>>
>>> OR  | -ROT AND | SWAP
>>>
>>> However because the stack-shuffling instructions '-ROT' and
>>> 'SWAP' change the order of input values for the next logic
>>> instruction both combined logic and stack addressing instructions
>>> can not executed parallel (there can be processed as instruction
>>> bundle of course) !
>>>
>>> If you think otherwise, please give me a hint (possibly a link of
>>> an existing design), thanks.
>>
>> Really?  You can't figure this out?  I don't know what your code
>> above is trying to do.  You seem to want to execute all the
>> instructions in different orders.  The stack juggling is there to
>> bring the right items to the top of the stack so they can be
>> operated on.  To optimize this you need hardware that can operate
>> on data in other locations.
>>
>> Processing in parallel means you have two things doing the
>> processing. One does the operation on the two items at the top of
>> the stack the other works on the two items below.
>>
>> AND-ab | OR-cd
>>
>> --
>>
>> Rick
>
> Your imaginary stack processor can't process both logic instructions
> in parallel because there input depend on stack shuffling which need
> to be executed before these instructions are processed (this is what
> my example shows). As you have written yourself "The stack juggling
> is there to bring the right items  to the top of the stack so they
> can be operated on". Because "to optimize this you need hardware that
> can operate on data in other locations" the stack processor must be
> able to fetch data-stack values independent of the actual
> top-of-stack position otherwise both instructions process anything
> but the right values. This is however not a classic stack design I've
> had referenced to in my example so we both talked past each other
> here.
>
> Beside the enormous effort for implementing such feature I can't see
> any advantage against a register ISA in this case (that was my entry
> point of view).

I think you are making a big deal out of something that is fairly 
trivial.  The line I was responding to was, "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".  I am simply trying to show 
it is not *harder* to do this with stack processors running a language 
like Forth.  I have never said it is significantly *eaiser* to implement 
parallelism with a stack machine.

*All* parallel processing requires extra hardware.  There have to be 
multiple execution units along with extra hardware to fetch and store 
multiple operands.  I have a very simple dual stack processor which 
performs parallel processing for some operations with very little extra 
hardware by fully utilizing the inherent parallelism of both stacks.  It 
can do a fetch/store operation using the data stack for data while 
updating the address (increment/decrement) using the return stack. 
Likewise it can do an operation on the data stack while updating a loop 
counter on the return stack.

You seem to think that to perform more complex operations in parallel 
requires gargantuan efforts by the hardware designer of stack machines 
because you can't think past the instruction written by the coder. 
Compilers can generate the code required to control parallel operations 
rather than requiring the hardware to do this.

I will also reply to your other post, but given that you claim it is 
your "final" post on this, I don't expect any further discussion. 
That's a shame as I feel you aren't understanding what I am saying and I 
would like for you to understand.

-- 

Rick

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

#41617

On Sunday, August 30, 2015 at 9:19:28 AM UTC-7, Mat wrote:
> Your imaginary stack processor can't process both logic instructions in parallel because there input depend on stack shuffling which need to be executed before these instructions are processed (this is what my example shows). As you have written yourself "The stack juggling is there to bring the right items  to the top of the stack so they can be operated on". Because "to optimize this you need hardware that can operate on data in other locations" the stack processor must be able to fetch data-stack values independent of the actual top-of-stack position otherwise both instructions process anything but the right values. This is however not a classic stack design I've had referenced to in my example so we both talked past each other here.
> 
> Beside the enormous effort for implementing such feature I can't see any advantage against a register ISA in this case (that was my entry point of view).

Mat is right about this --- Rickman is wrong.

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

#41624

These guys conclude, it seems, that ILP has not been investigated enough for stack machines, not that it is not possible or that is somewhat inferior to register machines. http://www-users.cs.york.ac.uk/~chrisb/main-pages/stack-machines/stack-machines-research-page.html

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

#41626

Am Montag, 31. August 2015 06:07:43 UTC+2 schrieb Greg:
> These guys conclude, it seems, that ILP has not been investigated enough for stack machines, not that it is not possible or that is somewhat inferior to register machines. http://www-users.cs.york.ac.uk/~chrisb/main-pages/stack-machines/stack-machines-research-page.html

Hello,
there exist some ongoing though exceptional research on this topic. These two publications overview and discuss related ILP approaches to stack processors in detail:

http://fpgacpu.ca/stack/Second-Generation_Stack_Computer_Architecture.pdf

http://www-users.cs.york.ac.uk/~chrisb/main-pages/publications/Shi_Huibin_PhD_thesis.pdf.1

The first publication compare two implementation approaches for stack processors with a register-based architecture (MIPS32, in-order pipelined): A common stack architecture with packed encoding and combined execution states and a pipelined in-order version. His conclusions from these comparisons up page 92 was worth reading in detail for me as I can conclude with the author though own experiences that a two-stage pipelined in-order stack architecture *can* have more or less the same cycle count as a five-stage in-order pipelined register architecture (RISC style).

However early in his publication, the author notes on page 28, 3.4.2:
"Computers from the second generation keep their stacks separate from main memory and usually on-chip. This has the advantage of causing no memory traffic,  but typically limits access to the topmost two to four elements  since the stack is no longer  addressable. This limitation requires that the topmost elements be permuted to bring a value to the top of the stack (Section 7.3.3). The  original overhead of memory traffic is thus transformed into the overhead of extra operations to manipulate the stack. This problem can be  mitigated by using more deeply-accessible stacks or more complex stack manipulation operations. This random access comes at the price of increased system complexity, culminating in a conventional multiparty register file."

That's to the point also my own conviction. Both class of architectures depend on comparable logic, accessing an multiparted register file for ILP, except that in case of a stack ISA additional logic effort must be considered in one way or another implementing the stack access. This effort is not much as is. To be precise it does not have anything to do with implementation details like needed multiplexing but it have aftereffects for the entire implementation and should have consequences for the ISA design. As the instruction execution (not unit functionality) is a part with should process and thus can't be simply switched off without complex effort to save power in consideration to the somewhat higher logic complexity for *such* ILP capable stack architecture, there aren't really an alternative to a conventional register-based approach (in my opinion.

Mat.

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

#41633

on 31/08/2015 09:51:33, Mat wrote:
> Am Montag, 31. August 2015 06:07:43 UTC+2 schrieb Greg:
>> These guys conclude, it seems, that ILP has not been investigated enough
> for stack machines, not that it is not possible or that is somewhat
> inferio r to register machines.
> http://www-users.cs.york.ac.uk/~chrisb/main-pages/stack-machines/stack-machines-research-page.html
> 
> Hello,
> there exist some ongoing though exceptional research on this topic.
> These t wo publications overview and discuss related ILP approaches to
> stack proces sors in detail:
> 
> http://fpgacpu.ca/stack/Second-Generation_Stack_Computer_Architecture.pdf
> http://www-users.cs.york.ac.uk/~chrisb/main-pages/publications/Shi_Huibin_PhD_thesis.pdf.1
> 
> The first publication compare two implementation approaches for stack
> proce ssors with a register-based architecture (MIPS32, in-order
> pipelined): A co mmon stack architecture with packed encoding and
> combined execution states and a pipelined in-order version. His
> conclusions from these comparisons up page 92 was worth reading in
> detail for me as I can conclude with the auth or though own
> experiences that a two-stage pipelined in-order stack archite cture
> *can* have more or less the same cycle count as a five-stage in-order
> pipelined register architecture (RISC style).
> 
> However early in his publication, the author notes on page 28, 3.4.2:
> "Computers from the second generation keep their stacks separate from
> main memory and usually on-chip. This has the advantage of causing no
> memory tra ffic, but typically limits access to the topmost two to
> four elements sin ce the stack is no longer addressable. This
> limitation requires that the t opmost elements be permuted to bring a
> value to the top of the stack (Secti on 7.3.3). The original overhead
> of memory traffic is thus transformed int o the overhead of extra
> operations to manipulate the stack. This problem ca n be mitigated by
> using more deeply-accessible stacks or more complex stac k
> manipulation operations. This random access comes at the price of
> increas ed system complexity, culminating in a conventional multiparty
> register fil e."
> 
> That's to the point also my own conviction. Both class of
> architectures dep end on comparable logic, accessing an multiparted
> register file for ILP, ex cept that in case of a stack ISA additional
> logic effort must be considered in one way or another implementing the
> stack access. This effort is not mu ch as is. To be precise it does
> not have anything to do with implementation details like needed
> multiplexing but it have aftereffects for the entire i mplementation
> and should have consequences for the ISA design. As the instr uction
> execution (not unit functionality) is a part with should process and
> thus can't be simply switched off without complex effort to save power
> in consideration to the somewhat higher logic complexity for *such*
> ILP capabl e stack architecture, there aren't really an alternative to
> a conventional register-based approach (in my opinion.
> 
> Mat.
> 

https://en.wikipedia.org/wiki/Belt_machine

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

#41613

To cut an endless discussion I want to final clarifier my argumentation:

1. A stack as organization for a register file have two disadvantages. First most instructions operate on two or one input sources and because the next instruction depends on a SINGLE storage location (stack file, TOS) this lead to large dependency chains (WHICH DON'T MEAN THAT PARALLELIZATION IS NOT POSSIBLE). Second for A CLASSICAL STACK DESIGN (AND ONLY IN THIS CASE) it is impossible to execute these DEPENDENT instructions FOR MOST INSTRUCTION SEQUENCES parallel because there exist ONLY ONE STORAGE LOCATION (TOS) WHICH IS ALSO THE MOST FREQUENT AND MORE IMPORTANT ONLY INPUT SOURCE.

1A. So to exploit instruction level parallelism THERE MUST exist ADDITIONAL LOGIC for accessing stack elements independent of the top-of-stack position.

2. I had give you examples for tree implementation architectures which are able (albeit more or less inefficient in terms of logic effort and energy usage) to process an register based ISA efficient by exploiting instruction-level parallelism. I also discuss (to shortly maybe) why these architectures would be way less efficient processing a stack based ISA (probably excluding the case of the VLIW architecture with multiple, independent data stacks).

4. My main argument is that the effort for parallelization of stack code is also otherwise likewise higher (all related to instruction-level parallelization, single core) than for comparable implementation of a register based ISA. The advantage of stack architectures are the the chance FOR A MORE COMPACT ENCODING and MINIMAL OVERHEAD FOR SUBROUTINE CALLS.

5. Stack based multi-core architectures tend to burden the overhead for routing to the programmer or compiler. In the case of a bus driven architecture, where different SHARED memories are program source for the local cores, the stack architecture limit parallel usage because of the increased cost for parallelization (see above). In the first case, the marked? disadvantage lays in ongoing research for implementing optimizing compilers for such architectures (which is demanded). In the second one, there is no advantage against an register based ISA implementation in my opinion because even a simple one can be implement with lesser effort (however the stack design may be more energy efficient).

6. Stack code can be efficient compiled for an register based ISA.

Thanks, for reading and understanding,
Mat.

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

#41616

On 8/30/2015 1:08 PM, Mat wrote:
> To cut an endless discussion I want to final clarifier my
> argumentation:
>
> 1. A stack as organization for a register file have two
> disadvantages. First most instructions operate on two or one input
> sources and because the next instruction depends on a SINGLE storage
> location (stack file, TOS) this lead to large dependency chains
> (WHICH DON'T MEAN THAT PARALLELIZATION IS NOT POSSIBLE). Second for A
> CLASSICAL STACK DESIGN (AND ONLY IN THIS CASE) it is impossible to
> execute these DEPENDENT instructions FOR MOST INSTRUCTION SEQUENCES
> parallel because there exist ONLY ONE STORAGE LOCATION (TOS) WHICH IS
> ALSO THE MOST FREQUENT AND MORE IMPORTANT ONLY INPUT SOURCE.
>
> 1A. So to exploit instruction level parallelism THERE MUST exist
> ADDITIONAL LOGIC for accessing stack elements independent of the
> top-of-stack position.

Yes, this is the same as register based machines.  In a register machine 
multiplexors are used to select the register for each arithmetic 
operation unless the instruction format is accumulator based where you 
need instructions to load the accumulator (even further from 
parallelism).  In a stack machine you have direct paths from the TOS and 
NOS to the ALU with no extra multiplexors.

To implement parallelism a register machine needs to add multiplexors to 
allow the fetching of more operands at the same time which is exactly 
like a stack machine which needs to add multiplexors to fetch multiple 
stack items at the same time.

I'm not sure what "A CLASSICAL STACK DESIGN" is but in any event this is 
an arbitrary limitation.  It is like saying a CPU without parallel 
execution cant implement parallel operations.  Yes, that is true.


> 2. I had give you examples for tree implementation architectures
> which are able (albeit more or less inefficient in terms of logic
> effort and energy usage) to process an register based ISA efficient
> by exploiting instruction-level parallelism. I also discuss (to
> shortly maybe) why these architectures would be way less efficient
> processing a stack based ISA (probably excluding the case of the VLIW
> architecture with multiple, independent data stacks).

To be honest, I didn't read that fully as I didn't see how it is 
relevant to the issue we are discussing.  Isn't that just a way of 
analyzing the instructions and has no effect on the actual hardware used 
or in any way impact how much parallelism is possible?


> 4. My main argument is that the effort for parallelization of stack
> code is also otherwise likewise higher (all related to
> instruction-level parallelization, single core) than for comparable
> implementation of a register based ISA. The advantage of stack
> architectures are the the chance FOR A MORE COMPACT ENCODING and
> MINIMAL OVERHEAD FOR SUBROUTINE CALLS.

Uh, what?  I don't follow your conclusions at all.  I think you are 
stuck thinking that stack machines have to be a certain way, which if 
you accept that, then yes, parallelism isn't possible... just like 
register machines which don't implement parallelism.

Just open your mind to the possibilities and look to see how it *can* be 
done and you will find parallelism to be easy with stack based designs.


> 5. Stack based multi-core architectures tend to burden the overhead
> for routing to the programmer or compiler. In the case of a bus
> driven architecture, where different SHARED memories are program
> source for the local cores, the stack architecture limit parallel
> usage because of the increased cost for parallelization (see above).

Now you are assuming that your previous statements are correct, but even 
so how does this impact the use of a shared memory bus???


> In the first case, the marked? disadvantage lays in ongoing research
> for implementing optimizing compilers for such architectures (which
> is demanded). In the second one, there is no advantage against an
> register based ISA implementation in my opinion because even a simple
> one can be implement with lesser effort (however the stack design may
> be more energy efficient).

I think you just don't understand the underlying hardware very well. 
The "energy savings" of stack designs come from the reduction of data 
path multiplexors for the ALU inputs (a small delta).  Otherwise there 
is not a lot of difference.  In reality there aren't many stack 
processor designs out there and I don't see power advantages to them 
other than the focus that was placed on low power design rather than 
being inherent in the stack architecture.


> 6. Stack code can be efficient compiled for an register based ISA.

Ok...

-- 

Rick

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

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

csiph-web