By: NoSpammer (no.delete@this.spam.com), August 8, 2022 9:31 am
Room: Moderated Discussions
Adrian (a.delete@this.acm.org) on August 4, 2022 4:56 am wrote:
> NoSpammer (no.delete@this.spam.com) on August 4, 2022 3:18 am wrote:
> >
> > I guess, apart from stack housekeeping, the primary reason is many instructions have high or variable
> > latency, which means that you will not be able to reuse the top of stack immediately. So you either
> > need to shuffle or you continue with dependent instruction anyways and let OOO handle that. But still,
> > for optimal execution it's more optimal to put instructions closer to the order of execution, to release
> > resources earlier. Even if you use stacks the optimal number of addressable sources will be close to
> > what the register requirements studies have found, so you will have to address about 16-32 somehow,
> > if not directly then you will be shuffling like x87. So I see no advantage for stacks.
>
>
> What you say is correct when there is a single operand stack, like in Intel 8087.
>
> In an ISA with multiple operand stacks, the reason of having more of them is
> to dedicate each stack to a distinct chain of *dependent* instructions.
I don't remember the exact number of times when I needed to use multiple stacks for algorithmic optimization, maybe 5 times max, including coding competitions. It doesn't strike me as a natural idea to represent the majority of computing problems.
> So you always want to reuse immediately the top-of-the-stack and all instructions that
> target the same stack will be executed at the pace determined by their latencies.
Reusing the top of stack reminds me very much of some initial attempts at optimizing compilers which could remember the symbolic contents of a small handful of registers and reuse them.
> The latencies are hidden by not using the same stack in instructions
> that are adjacent in the instruction stream.
>
>
> Of course an OoO implementation can relax the requirement of always alternating between
> stacks, because it can reorder the instructions itself, but you still need to have
> multiple chains of dependent instructions anyway, otherwise even OoO cannot do miracles,
> and when there is a single chain it would still be limited by latencies.
It will be limited by the latencies AND the number of buffered instructions.
> Even when the compiler does not have to be careful with the scheduling, the correct code generation
> for such an ISA would be to always use a stack per chain of dependent instructions, as that
> could enable hardware optimizations for the placement of intermediate results.
>
>
> With multiple stacks, it is likely that many cases when shuffling was required
> in a single stack can better be done with copying/moving the top of one stack
> to another stack, at appropriate times, instead of using shuffling.
You are arguing totally the wrong way to convince me. The way to go is to collect relevant register and temp var reusage stats from a decent compiler on a decent number of tests. Then you can look at some entropy data and argue about how best to represent that optimally or even in compressed form, maybe it's not a stack at all.
To give you one point of support I remember reading a paper about some proposed arch that used a handful of clusters with a smaller number of registers and a compiler optimizing reuse inside each cluster. They cited some possible power gains. I think in spirit this would be somewhat similar to your multiple stacks idea, at least as a collection of some relevant data points.
Can stacks be space efficient? Yes, just use PUSHAD and POPAD for entry/exit of every function on x86 instead of loading/storing particular registers. Is a compiler likely to guess where this is a good idea without some relevant runtime information? I doubt so. Do lazy programmers use that at points where it will not matter? Yes, we do.
As for recent and new archs, I think load pair / store pair is a fantastic code condensing idea, covering a bunch of use cases, including stack implementations. As for priorities I would go for methods to learn something more from the fact that a misprediction happened (deep history buffers but also new ways of prediction), trying to predict multiple future branches, and which instructions are on the critical line, before even thinking of stacks and condensing code.
> NoSpammer (no.delete@this.spam.com) on August 4, 2022 3:18 am wrote:
> >
> > I guess, apart from stack housekeeping, the primary reason is many instructions have high or variable
> > latency, which means that you will not be able to reuse the top of stack immediately. So you either
> > need to shuffle or you continue with dependent instruction anyways and let OOO handle that. But still,
> > for optimal execution it's more optimal to put instructions closer to the order of execution, to release
> > resources earlier. Even if you use stacks the optimal number of addressable sources will be close to
> > what the register requirements studies have found, so you will have to address about 16-32 somehow,
> > if not directly then you will be shuffling like x87. So I see no advantage for stacks.
>
>
> What you say is correct when there is a single operand stack, like in Intel 8087.
>
> In an ISA with multiple operand stacks, the reason of having more of them is
> to dedicate each stack to a distinct chain of *dependent* instructions.
I don't remember the exact number of times when I needed to use multiple stacks for algorithmic optimization, maybe 5 times max, including coding competitions. It doesn't strike me as a natural idea to represent the majority of computing problems.
> So you always want to reuse immediately the top-of-the-stack and all instructions that
> target the same stack will be executed at the pace determined by their latencies.
Reusing the top of stack reminds me very much of some initial attempts at optimizing compilers which could remember the symbolic contents of a small handful of registers and reuse them.
> The latencies are hidden by not using the same stack in instructions
> that are adjacent in the instruction stream.
>
>
> Of course an OoO implementation can relax the requirement of always alternating between
> stacks, because it can reorder the instructions itself, but you still need to have
> multiple chains of dependent instructions anyway, otherwise even OoO cannot do miracles,
> and when there is a single chain it would still be limited by latencies.
It will be limited by the latencies AND the number of buffered instructions.
> Even when the compiler does not have to be careful with the scheduling, the correct code generation
> for such an ISA would be to always use a stack per chain of dependent instructions, as that
> could enable hardware optimizations for the placement of intermediate results.
>
>
> With multiple stacks, it is likely that many cases when shuffling was required
> in a single stack can better be done with copying/moving the top of one stack
> to another stack, at appropriate times, instead of using shuffling.
You are arguing totally the wrong way to convince me. The way to go is to collect relevant register and temp var reusage stats from a decent compiler on a decent number of tests. Then you can look at some entropy data and argue about how best to represent that optimally or even in compressed form, maybe it's not a stack at all.
To give you one point of support I remember reading a paper about some proposed arch that used a handful of clusters with a smaller number of registers and a compiler optimizing reuse inside each cluster. They cited some possible power gains. I think in spirit this would be somewhat similar to your multiple stacks idea, at least as a collection of some relevant data points.
Can stacks be space efficient? Yes, just use PUSHAD and POPAD for entry/exit of every function on x86 instead of loading/storing particular registers. Is a compiler likely to guess where this is a good idea without some relevant runtime information? I doubt so. Do lazy programmers use that at points where it will not matter? Yes, we do.
As for recent and new archs, I think load pair / store pair is a fantastic code condensing idea, covering a bunch of use cases, including stack implementations. As for priorities I would go for methods to learn something more from the fact that a misprediction happened (deep history buffers but also new ways of prediction), trying to predict multiple future branches, and which instructions are on the critical line, before even thinking of stacks and condensing code.