On 7/6/2021 7:15 AM, Ivan Godard wrote:
> On 7/6/2021 6:06 AM, Stefan Monnier wrote:
>>> There's only one belt at present. Rather than two belts, just configure
>>> a belt twice as big.
>>
>> I think his idea is that with 2 belts (and with control over which
>> results go to which belt) you can arrange to put on belt 1 the
>> results that are only needed very shortly, and on belt 2 the results
>> that are needed in the longer term.  If most results are needed only
>> shortly then belt 1 will move faster and belt 2 will indeed store its
>> result longer.
>>
>> Instead, you use the scratchpad which incurs a higher latency.  IIUC you
>> don't care too much about this latency because it should be reasonably
>> easy to schedule your scratchpad saves&loads in advance, so as long as
>> "save+load" doesn't take more time than the number of cycles results
>> stay on the belt (i.e. the length of the belt measured in cycles), then
>> you can still arrange to have the results "at hand" without delay
>> when you need them.
>>
>>
>>          Stefan
>>
>
> As the belt is just an encoding device, it can be judged on the
> compactness it achieves. Belts don't have a "speed"; things last until
> the more recent set exhausts the capacity. So you could partition the
> belt and decide to put short-life things in one and longer-life things
> in the other, by convention. You'd still need a scratchpad for things
> with still longer lives, but the scratch might be less used (and hence
> smaller) because there would be fewer holes in the slow belt than in a
> double-sized fast belt.
>
> However, this is just a way to selectively preserve longer-life belt
> content. We do preservation now with the rescue() operation, which takes
> a bitmask covering the belt space and renumbers the selected operands to
> the front. It's unclear to me whether a 32-long belt with rescues for
> 33+ drop lives is worse than two 16-long belts with rescues for one of
> them. For space they are the same: choose one of 32 (or 2X16) costs five
> bits. For usage, if the average life is 16-32 drops then the 32-long is
> best because with 2X16 the data falls off the quick belt and overfills
> the slow belt.

I am with Ivan on this, based on general principles. If you have two
classes of things that are similar but different, (in this case, a
"fast" and a "slow" belt) you invariably have cases where you want more
of one and fewer of the other. Similar to the separation of registers
into FP and Int, or data and addresses. The rescue operation is a, IIRC
low cost, fine way of handling that problem.

> Needs some thought.

Sure.

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

> As the belt is just an encoding device, it can be judged on the compactness
> it achieves.

Of course, tho there's also the execution cost of interpreting/executing
the rescue/scratchpad/memory operations when we run out of belt/registers.

> However, this is just a way to selectively preserve longer-life belt content.

At least in theory. In practice if many/most of your values need to be
longer lived, then your "slow belt" will end up moving a fast as (or
faster) than your "fast belt". It's not clear that the concept of
having multiple belts would be a win.

Stefan

> However, this is just a way to selectively preserve longer-life belt
> content. We do preservation now with the rescue() operation, which takes
> a bitmask covering the belt space and renumbers the selected operands to the
> front.

Reminds me: how does the compiler choose between using `rescue` to
extend a value's lifetime in the belt vs putting that value in
the scratchpad?

Stefan

On 7/6/2021 8:46 AM, Stefan Monnier wrote:
>> However, this is just a way to selectively preserve longer-life belt
>> content. We do preservation now with the rescue() operation, which takes
>> a bitmask covering the belt space and renumbers the selected operands to the
>> front.
>
> Reminds me: how does the compiler choose between using `rescue` to
> extend a value's lifetime in the belt vs putting that value in
> the scratchpad?
>
>
> Stefan
>

Some cases are forced. For example, if there is complex control flow
between production and consumption (say produced in a loop prologue and
consumed in the epilogue) then you don't want to be rescuing endlessly
around the loop, and will spill to scratch. Or if the total live exceeds
the fixed belt length then you must spill some, choosing those with the
longest gap before next use.

Otherwise it's just a heuristic: cost of chained rescues, vs. cost of
spill, fill, and scratch space. The specializer looks at the largest gap
(in units of drops, not cycles) between producer and first consumer, or
between pairs of consecutive uses, and if that exceeds a per-member spec
then it spills, otherwise if it's out-of-reach it rescues. But a rescue
rescues everything live at its point of insertion, which alters the gaps
of all of the drops whose life crosses the rescue. Recompute who has the
longest gap, rinse, repeat. It's a natural for a heap-of-ranges data
structure, but it doesn't need to hold gaps that are or become in range
so size tends to be small. I suppose it's nlogn for the out-of-range count.

There's probably a better algorithm for pure rescue insert: given a set
of possibly overlapping ranges, find a set of slices through the set
that reduces all the range fragments to below a fixed length with a
minimal number of slices. Optimal sounds NP to me though - Anton?

Phasing complicates things: "if (A[i+j].p = F(G(a+b, c-d), e^0xf00f00))
{...}" is all one bundle (and one cycle), so you can get intra-bundle
out-of-range or belt overflow too. However, rescue is only possible at
the bundle boundary, while fills are early phase and spills are late
phase, so you may have to bundle bust. (?FILL?, CON, ADD, ADD, SUB,
XOR, CALL, CALL, STORE, BR, ?SPILL?, ?RESCUE?).

Currently the algorithm does not consider scratchpad pressure, though
having to spill to memory instead of scratch is real expensive. Some day
there will be an intern or grad stewey who will have fun with that.

Brett <ggtgp@yahoo.com> schrieb:

> I have used architectures with scratchpads or that could configure half the
> cache as scratchpad, yuck.
> And I have the talent to use such, for the average programer the idea is a
> joke.

That should be a question for the compiler writer, not the
application programmer.

Thomas Koenig [2021-07-07 13:47:55] wrote:
> Brett <ggtgp@yahoo.com> schrieb:
>> I have used architectures with scratchpads or that could configure half the
>> cache as scratchpad, yuck.
>> And I have the talent to use such, for the average programer the idea is a
>> joke.
> That should be a question for the compiler writer, not the
> application programmer.

The kind of scratchpad he's referring to is "out of reach" of most
compilers: they're not up to the task of deciding what to put into it
and what not, so the problem becomes the responsability of the
"application programmer".

The Mill's scratchpad share the same name but are a different concept.

Stefan

Stefan Monnier wrote:
> Thomas Koenig [2021-07-07 13:47:55] wrote:
>> Brett <ggtgp@yahoo.com> schrieb:
>>> I have used architectures with scratchpads or that could configure half the
>>> cache as scratchpad, yuck.
>>> And I have the talent to use such, for the average programer the idea is a
>>> joke.
>> That should be a question for the compiler writer, not the
>> application programmer.
>
> The kind of scratchpad he's referring to is "out of reach" of most
> compilers: they're not up to the task of deciding what to put into it
> and what not, so the problem becomes the responsability of the
> "application programmer".
>
> The Mill's scratchpad share the same name but are a different concept.
>
>
> Stefan

Seems to me that it is similar to the register allocator with an
extra level, in that there is a non-uniform cost between belt rescue,
scratchpad and stack memory. So it should be a cost minimization problem,
also taking into account the lifetime of values (most are single read),
and that temp values across subroutine calls must live in scratchpad
or stack memory (no non-arg belt slots live across calls).

Its reminiscent of VLIW in that belt values are "in flight" forwarded
values, scratchpad is a "large register set" and stack as usual.

EricP [2021-07-07 12:00:53] wrote:
> Stefan Monnier wrote:
>> Thomas Koenig [2021-07-07 13:47:55] wrote:
>>> Brett <ggtgp@yahoo.com> schrieb:
>>>> I have used architectures with scratchpads or that could configure half the
>>>> cache as scratchpad, yuck.
>>>> And I have the talent to use such, for the average programer the idea is a
>>>> joke.
>>> That should be a question for the compiler writer, not the
>>> application programmer.
>> The kind of scratchpad he's referring to is "out of reach" of most
>> compilers: they're not up to the task of deciding what to put into it
>> and what not, so the problem becomes the responsability of the
>> "application programmer".
>> The Mill's scratchpad share the same name but are a different concept.
> Seems to me that it is similar to the register allocator with an
> extra level, in that there is a non-uniform cost between belt rescue,
> scratchpad and stack memory.

Indeed, using `rescue` could be called "belt allocation" in that it's
a similar problem to register allocation, yet it's a bit different, so
it's not immediately obvious what algorithm to use to approximate the
optimal solution.

Ivan's answer suggests that they currently use a bunch of heuristics
that are hoped to work well but without having a clear model of a
global optimum.

> and that temp values across subroutine calls must live in scratchpad
> or stack memory (no non-arg belt slots live across calls).

That's not my understanding. According to the slides of the "belt
talk", the caller's belt is automatically preserved during a function
call, and the function call just "drops" its result(s) onto the caller's
belt exactly like a normal op would do.
So temp values can definitely live on the belt across calls.

Stefan

Stefan Monnier <monnier@iro.umontreal.ca> schrieb:
> Thomas Koenig [2021-07-07 13:47:55] wrote:
>> Brett <ggtgp@yahoo.com> schrieb:
>>> I have used architectures with scratchpads or that could configure half the
>>> cache as scratchpad, yuck.
>>> And I have the talent to use such, for the average programer the idea is a
>>> joke.
>> That should be a question for the compiler writer, not the
>> application programmer.
>
> The kind of scratchpad he's referring to is "out of reach" of most
> compilers: they're not up to the task of deciding what to put into it
> and what not, so the problem becomes the responsability of the
> "application programmer".

There are only two options, then: Either compiler technology is
improved so this works, or the concept is dead.

How do we know that compilers are not up to it? Did anybody try to
throw a relevant machine description at one of the major compilers?
I would suspect that putting registers which do nothing, but which
have low-cost register moves to registers which do something,
could already provide something reasonable (iff that scratchpad
is cheaper than using a cache).

Of course, there should be an API to determine when could use what.

> The Mill's scratchpad share the same name but are a different concept.

So I gathered.

Thomas Koenig [2021-07-07 17:08:04] wrote:
> Stefan Monnier <monnier@iro.umontreal.ca> schrieb:
>> Thomas Koenig [2021-07-07 13:47:55] wrote:
>>> Brett <ggtgp@yahoo.com> schrieb:
>>>> I have used architectures with scratchpads or that could configure half the
>>>> cache as scratchpad, yuck.
>>>> And I have the talent to use such, for the average programer the idea is a
>>>> joke.
>>> That should be a question for the compiler writer, not the
>>> application programmer.
>> The kind of scratchpad he's referring to is "out of reach" of most
>> compilers: they're not up to the task of deciding what to put into it
>> and what not, so the problem becomes the responsability of the
>> "application programmer".
> There are only two options, then: Either compiler technology is
> improved so this works, or the concept is dead.

And yet, the concept has existed and keeps existing.
It's typically used in two circumstances:
- Boot time, before the external memory can be used because it hasn't
yet been configured.
- Embedded systems, where the "application programmer" does the job of
optimizing placement, and in return gets more predictable memory
access times.

> I would suspect that putting registers which do nothing, but which
> have low-cost register moves to registers which do something,
> could already provide something reasonable (iff that scratchpad
> is cheaper than using a cache).

AFAIK it usually has the same latency when used as a scratchpad as when
used as a cache.

Stefan

Stefan Monnier <monnier@iro.umontreal.ca> schrieb:
> Thomas Koenig [2021-07-07 17:08:04] wrote:

>> I would suspect that putting registers which do nothing, but which
>> have low-cost register moves to registers which do something,
>> could already provide something reasonable (iff that scratchpad
>> is cheaper than using a cache).
>
> AFAIK it usually has the same latency when used as a scratchpad as when
> used as a cache.

Then it is not interesting. Values spilled to the stack will end
up in the L1 cache anyway, and if there is no latency advantage,
there is no point. You just lose adressing modes and flexibility.

I could understand some architecture putting in a larger number of
registers that can be accessed at register speeds (single-cycle
latency), but that is apparently not what is being discussed.

On 7/7/2021 11:45 AM, Thomas Koenig wrote:
> Stefan Monnier <monnier@iro.umontreal.ca> schrieb:
>> Thomas Koenig [2021-07-07 17:08:04] wrote:
>
>>> I would suspect that putting registers which do nothing, but which
>>> have low-cost register moves to registers which do something,
>>> could already provide something reasonable (iff that scratchpad
>>> is cheaper than using a cache).
>>
>> AFAIK it usually has the same latency when used as a scratchpad as when
>> used as a cache.
>
> Then it is not interesting. Values spilled to the stack will end
> up in the L1 cache anyway, and if there is no latency advantage,
> there is no point. You just lose adressing modes and flexibility.

There are embedded applications that have a required response time to
some event. That is, when that event occurs, you must respond within a
specified amount of time. By having a fixed amount of storage that you
know will respond within that time, you can guarantee meeting the
timing. If you put it in a cache, you risk getting a cache miss on that
data, and thus missing timing.

> I could understand some architecture putting in a larger number of
> registers that can be accessed at register speeds (single-cycle
> latency), but that is apparently not what is being discussed.

Right.

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

Ivan Godard <ivan@millcomputing.com> wrote:
> On 7/6/2021 1:04 AM, Brett wrote:
>> Ivan Godard <ivan@millcomputing.com> wrote:
>>> On 7/5/2021 12:15 AM, Brett wrote:
>>>> Brett <ggtgp@yahoo.com> wrote:
>>>>> Thomas Koenig <tkoenig@netcologne.de> wrote:
>>>>>> Brett <ggtgp@yahoo.com> schrieb:
>>>>>>> Thomas Koenig <tkoenig@netcologne.de> wrote:
>>>>>>>> Ivan Godard <ivan@millcomputing.com> schrieb:
>>>>>>>>> On 6/26/2021 2:32 AM, Thomas Koenig wrote:
>>>>>>>>
>>>>>>>>> See the Texas Instruments C64
>>>>>>>>
>>>>>>>> That's rather interesting, thanks!
>>>>>>>>
>>>>>>>> Looks rather similar to what I had in mind, except that they allow
>>>>>>>> at least some cross-operation between the different register files,
>>>>>>>> and they had 16 registers (later 32) per register file.
>>>>>>>>
>>>>>>>
>>>>>>> I like it, however I would burn two instruction bits for the two banks.
>>>>>>> So you can say bank 0, bank 1, both banks, sequential load to both, etc.
>>>>>>
>>>>>> What would you appy them to? Assuming a three-register instruction,
>>>>>> (and assuming that r0-15 are in the first bank and r16-r31 in the
>>>>>> second) would you then be able to write
>>>>>>
>>>>>> add r2,r17,r22
>>>>>
>>>>> Add.12 r2,r17,r22 ; both banks run same instruction.
>>>>>
>>>>> A loop unroll of one is just tagging the opcode to run on both banks.
>>>>> Which gives good code density.
>>>>>
>>>>> Add.1s r2,r17,r22 ; add bank 1 but splat result to both banks.
>>>>>
>>>>> Also would do load pair splat, so banks get sequential items for loop
>>>>> unroll use, which saves an address register in the second bank from having
>>>>> to be a clone plus 1 and other grief. The saved register could then be your
>>>>> loop index, etc.
>>>>>
>>>>> You get loop unrolling without doubling your rename width or ports, both of
>>>>> which are critical limits to scaling.
>>>>>
>>>>>> (so the bank 1 ALU presumably does the calculation and sends over
>>>>>> the result to bank 0)?
>>>>>>
>>>>>> Also, this would use one bit only if you have two banks. I was
>>>>>> envisioning more than two, then the advantage in encoding bits
>>>>>> starts to disappear.
>>>>>
>>>>> You can use 2 bank bits and 1 splat or other bit, cheaper than three 6 bit
>>>>> register specifiers. 2+1+(3*4) = 15, verses 3*6 = 18.
>>>>>
>>>>> With four banks the four common choices are; bank 1, all, alternate primary
>>>>> bank, and all but primary bank. Which is better than my 2 bank mask bits in
>>>>> the same opcode space.
>>>>>
>>>>> You can expand this to 3 bits, or the full 4 bit mask each bank which is
>>>>> wasteful. There is also the issue of splat variants if any, which may
>>>>> better be handled by other opcodes. There will be a copy bank register
>>>>> instruction that handles all the tough cases.
>>>>
>>>> I have thought about this some more and how it overlaps vector registers
>>>> but with more flexibility and have decided that 5 banks of 16 registers is
>>>> best so that one can do away with vector registers since you have that
>>>> functionality.
>>>>
>>>> All addressing is done in the first two banks, and the other banks are for
>>>> unrolling and long calculations that need more than 16 registers. Only the
>>>> last four banks support floating point and vector type operations. All
>>>> registers are 64 bits.
>>>>
>>>> Basically a sort of super upgraded RISC 68000, without the crap instruction
>>>> set arch and limits. You can’t do addressing in vector registers, but can
>>>> with this arch.
>>>>
>>>> You could also do a Mill variant of this arch, and with 5 belts you can
>>>> dump the evil kluge visible scratchpad resulting in a nicer cleaner
>>>> architecture.
>>>
>>> Code can have unbounded numbers of concurrently live operands that have
>>> to be put somewhere. If you don't have a scratchpad then you have to be
>>> prepared to stash to memory. Even if you do have a scratchpad you have
>>> to be prepared fo it to overflow and need stashing to memory too.
>>> Scratchpad, like registers, is just an optimization of memory for
>>> certain common special cases.
>>
>> I have used architectures with scratchpads or that could configure half the
>> cache as scratchpad, yuck.
>> And I have the talent to use such, for the average programer the idea is a
>> joke.
>>
>> The age of two way caches that suffer aliasing issues is over, use the
>> cache as God intended.
>>
>> Of course in your case the compiler is using the scratchpad, and it may
>> give you more bandwidth, and that bandwidth costs less power than the
>> cache.
>>
>> But I still think a scratchpad is an over complicated kludge and thus you
>> are living in the past. More importantly it will scare off mediocre
>> programers. The belt is scary enough as is.
>>
>> On an OS call the scratchpad can leak information unless cleared, a small
>> performance liability.
>
> Calls, to the OS or otherwise, get a whole new scratchpad (or so it
> appears), courtesy the hardware spiller.
>
>> The real problem is that you only have one virtual belt, as that makes
>> opcodes smaller and seemingly makes things simpler. But not all problems
>> fit in one belt, fat code blows apart a single belt. Thus a scratchpad to
>> shoehorn more code with good performance. Fat code purely from cache would
>> perform badly.
>
> Yes; hence the scratchpad.
>
>> You also have compiler issues, which makes handling more belts difficult.
>> It is easy to say that one bank should be used for globals and thus rarely
>> rotate, another for addressing and others for compute, but convincing a
>> compiler to do something intelligent is really hard.
>
> There's only one belt at present. Rather than two belts, just configure
> a belt twice as big.
>
>> A loop has a limited number of dependent compute chains, it should be
>> possible to just randomly assign opcode chains to belts. Filling belts
>> roughly evenly over time.
>
> Too much fanout in open code, although FP codes are better; you would
> wind up doing a lot of inter-belt transfers because the dataflow is
> tree-like rather than linear.

Integer trees are so short they are forks. No arch can help such junk.
Addressing is linear and makes up a third of the ops.

>> You have some secrete sauce still I bet to get to 32 ops a cycle, how you
>> handle vector support spreading across units? Etc. Maybe you have lots of
>> belts hiding under the virtual belt, and thus are doing what I am
>> suggesting.
>
> Nope. Remember, the belt is a naming device, not a shift register.

It can be hard to wrap ones brain around doing 32 ops a cycle when you have
16 belt registers.

An 8 way unroll with lots of ALU’s can pull this off.

Which means that after your virtual belt get translated to operations you
have lots of little independent chains which are little belts. Most call
this OoO, but you can order the opcodes sequentially, but doing so is not
belt friendly as each data step is 8 opcodes away on a 8 way unroll.

You need a form of OoO somewhere when the ops hit the hardware, and this is
what is confusing me.

>> It’s been years since I read your docs, I apologize for any
>> mischaracterizations I have made. My mental model of your architecture is
>> undoubtedly wrong.
>>
>> I thank you for your posts, they are enlightening.

On 7/7/2021 9:00 AM, EricP wrote:
> Stefan Monnier wrote:
>> Thomas Koenig [2021-07-07 13:47:55] wrote:
>>> Brett <ggtgp@yahoo.com> schrieb:
>>>> I have used architectures with scratchpads or that could configure
>>>> half the
>>>> cache as scratchpad, yuck.
>>>> And I have the talent to use such, for the average programer the
>>>> idea is a
>>>> joke.
>>> That should be a question for the compiler writer, not the
>>> application programmer.
>>
>> The kind of scratchpad he's referring to is "out of reach" of most
>> compilers: they're not up to the task of deciding what to put into it
>> and what not, so the problem becomes the responsability of the
>> "application programmer".
>>
>> The Mill's scratchpad share the same name but are a different concept.
>>
>>
>>         Stefan
>
> Seems to me that it is similar to the register allocator with an
> extra  level, in that there is a non-uniform cost between belt rescue,
> scratchpad and stack memory. So it should be a cost minimization problem,
> also taking into account the lifetime of values (most are single read),
> and that temp values across subroutine calls must live in scratchpad
> or stack memory (no non-arg belt slots live across calls).
>
> Its reminiscent of VLIW in that belt values are "in flight" forwarded
> values, scratchpad is a "large register set" and stack as usual.

Close but no cigar :-)

Belt values *do* persist across calls, they just don't persist *into*
calls except for explicit arguments (which are reordered to signature
order). Scratch is the same, except no called arguments are passed in
scratch.

Yes, the task is very like a register allocator for a non-uniform
register set. For example, do you put a value in one register or a
different one, and decide based on whether the one register will be need
for an upcoming instruction that needs a register pair including that one?

And yes, it's a cost minimization problem.

On 7/7/2021 9:35 AM, Stefan Monnier wrote:
> EricP [2021-07-07 12:00:53] wrote:
>> Stefan Monnier wrote:
>>> Thomas Koenig [2021-07-07 13:47:55] wrote:
>>>> Brett <ggtgp@yahoo.com> schrieb:
>>>>> I have used architectures with scratchpads or that could configure half the
>>>>> cache as scratchpad, yuck.
>>>>> And I have the talent to use such, for the average programer the idea is a
>>>>> joke.
>>>> That should be a question for the compiler writer, not the
>>>> application programmer.
>>> The kind of scratchpad he's referring to is "out of reach" of most
>>> compilers: they're not up to the task of deciding what to put into it
>>> and what not, so the problem becomes the responsability of the
>>> "application programmer".
>>> The Mill's scratchpad share the same name but are a different concept.
>> Seems to me that it is similar to the register allocator with an
>> extra level, in that there is a non-uniform cost between belt rescue,
>> scratchpad and stack memory.
>
> Indeed, using `rescue` could be called "belt allocation" in that it's
> a similar problem to register allocation, yet it's a bit different, so
> it's not immediately obvious what algorithm to use to approximate the
> optimal solution.
>
> Ivan's answer suggests that they currently use a bunch of heuristics
> that are hoped to work well but without having a clear model of a
> global optimum.

It's pretty clear that optimum is bin-packing and hence NP. The
specializer is intended to be used as a very fast install-time tool, and
can't afford NP, no more than a JIT (with a similar place in the
process) can afford it. Hence, heuristics for both.

We do not have a compile-time batch version of the specializer intended
for when NP algorithms are desirable to get optimum. If market demands,
we will.

>> and that temp values across subroutine calls must live in scratchpad
>> or stack memory (no non-arg belt slots live across calls).
>
> That's not my understanding. According to the slides of the "belt
> talk", the caller's belt is automatically preserved during a function
> call, and the function call just "drops" its result(s) onto the caller's
> belt exactly like a normal op would do.
> So temp values can definitely live on the belt across calls.

Yes

On 7/7/2021 4:14 PM, Brett wrote:
> Ivan Godard <ivan@millcomputing.com> wrote:
>> On 7/6/2021 1:04 AM, Brett wrote:

<snip>

>>> You also have compiler issues, which makes handling more belts difficult.
>>> It is easy to say that one bank should be used for globals and thus rarely
>>> rotate, another for addressing and others for compute, but convincing a
>>> compiler to do something intelligent is really hard.
>>
>> There's only one belt at present. Rather than two belts, just configure
>> a belt twice as big.
>>
>>> A loop has a limited number of dependent compute chains, it should be
>>> possible to just randomly assign opcode chains to belts. Filling belts
>>> roughly evenly over time.
>>
>> Too much fanout in open code, although FP codes are better; you would
>> wind up doing a lot of inter-belt transfers because the dataflow is
>> tree-like rather than linear.
>
> Integer trees are so short they are forks. No arch can help such junk.
> Addressing is linear and makes up a third of the ops.

To simplify an example:
source: a+b+c+d
breadth-first: (a+b)+(c+d) 2 cycles, max belt live load 2
depth-first: (a+(b+(c+d))) 3 cycles, max belt live load 1

constraints:
belt live load cannot exceed belt length;
belt delta (distance in drops between producer and consumer) cannot
exceed belt length without rescue or spill/fill
no NP

BTW, a graph-coloring register allocator is also NP.

>>> You have some secrete sauce still I bet to get to 32 ops a cycle, how you
>>> handle vector support spreading across units? Etc. Maybe you have lots of
>>> belts hiding under the virtual belt, and thus are doing what I am
>>> suggesting.
>>
>> Nope. Remember, the belt is a naming device, not a shift register.
>
> It can be hard to wrap ones brain around doing 32 ops a cycle when you have
> 16 belt registers.

Not possible, unless the op arguments were shared from 16 available and
all had 16 or fewer drops total (neglecting phasing). As a rule of
thumb, a Mill member is configured such that <slot count> == <belt
length>. The larger members (Gold has 32 belt length) rarely need to
rescue, although they may have occasional obligatory spills, while
smaller ones (Copper has 8 belt length) are replete with rescues on the
same code.

> An 8 way unroll with lots of ALU’s can pull this off.

Nope.

> Which means that after your virtual belt get translated to operations you
> have lots of little independent chains which are little belts. Most call
> this OoO, but you can order the opcodes sequentially, but doing so is not
> belt friendly as each data step is 8 opcodes away on a 8 way unroll.

Software pipelining rather than unroll, but yes: the belt must be long
enough to hold the un-piped placement times the piping.In practical
configs the constraint to piping limiting factor is the number of FUs
you have of whatever is the most constraining kind. If your loop body
has a multiply and you have two multipliers you can't pipe it into a
single 3-pipe bundle.

On 2021-07-06, Stefan Monnier wrote:
>> I have used architectures with scratchpads or that could configure half the
>> cache as scratchpad, yuck.
>
> I don't think these scratchpads are very much like the Mill's scratchpad.
>
> I suspect the "yuck" above refers to the problems you end up having of
> administering this scratchpad, sharing it between unrelated functions.
>
> Mill's scratchpad is more like a CPU-supported notion of frame
> activation record. Every time you enter a function you get a fresh new
> scratchpad and when you return from a function, the scratchpad is thrown
> away and the caller recovers instead the scratchpad it had before the
> call (scrachpads get "pushed on/popped off the stack" behind the scene).
>
> So it's easy for programmers and compilers to use it as a kind of "slow
> register file with register-windows".

I've been toying with the idea of having a small scratchpad at a fixed
memory location in the MRISC32 for the sake of doing things like vector
register permutations (a la POWER vperm): Since the machine has
scatter/gather it is trivial to do permutations via memory in just two
instructions (a linear store + a gather load), and since the idea is
that the vector registers should be long enough to hide any pipeline
latencies the permutation operation basically has the same cost as two
back-to-back ALU operations, /provided/ that there are no cache misses.

The size of a vector register is 64+ bytes (implementation dependent),
so the memory requirement for a single register is typically more than
one cache line.

So, what do you people think? Would a HW scratchpad have a performance
advantage over, say, using the local stack as scratchpad area for the
purpose of doing vector permutations and similar?

One obvious advantage would be that the DCache is not polluted.

/Marcus

On 7/7/2021 11:20 PM, Marcus wrote:
> On 2021-07-06, Stefan Monnier wrote:
>>> I have used architectures with scratchpads or that could configure
>>> half the
>>> cache as scratchpad, yuck.
>>
>> I don't think these scratchpads are very much like the Mill's scratchpad.
>>
>> I suspect the "yuck" above refers to the problems you end up having of
>> administering this scratchpad, sharing it between unrelated functions.
>>
>> Mill's scratchpad is more like a CPU-supported notion of frame
>> activation record.  Every time you enter a function you get a fresh new
>> scratchpad and when you return from a function, the scratchpad is thrown
>> away and the caller recovers instead the scratchpad it had before the
>> call (scrachpads get "pushed on/popped off the stack" behind the scene).
>>
>> So it's easy for programmers and compilers to use it as a kind of "slow
>> register file with register-windows".
>
> I've been toying with the idea of having a small scratchpad at a fixed
> memory location in the MRISC32 for the sake of doing things like vector
> register permutations (a la POWER vperm): Since the machine has
> scatter/gather it is trivial to do permutations via memory in just two
> instructions (a linear store + a gather load), and since the idea is
> that the vector registers should be long enough to hide any pipeline
> latencies the permutation operation basically has the same cost as two
> back-to-back ALU operations, /provided/ that there are no cache misses.
>
> The size of a vector register is 64+ bytes (implementation dependent),
> so the memory requirement for a single register is typically more than
> one cache line.
>
> So, what do you people think?

What happens if you take an interrupt and want to do a context switch
between the store and the gather load?

> Would a HW scratchpad have a performance
> advantage over, say, using the local stack as scratchpad area for the
> purpose of doing vector permutations and similar?

Probably, but I suspect there are better ways of accomplishing this
functionality.

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

Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:
>There are embedded applications that have a required response time to
>some event. That is, when that event occurs, you must respond within a
>specified amount of time. By having a fixed amount of storage that you
>know will respond within that time, you can guarantee meeting the
>timing. If you put it in a cache, you risk getting a cache miss on that
>data, and thus missing timing.

There exists hardware where you can lock cache lines (they cannot be
evicted) for that purpose. AFAIK some PowerPC CPUs have this, and I
expect that ARM Cortex-R CPUs have this, too.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

On 2021-07-08, Stephen Fuld wrote:
> On 7/7/2021 11:20 PM, Marcus wrote:
>> On 2021-07-06, Stefan Monnier wrote:
>>>> I have used architectures with scratchpads or that could configure
>>>> half the
>>>> cache as scratchpad, yuck.
>>>
>>> I don't think these scratchpads are very much like the Mill's
>>> scratchpad.
>>>
>>> I suspect the "yuck" above refers to the problems you end up having of
>>> administering this scratchpad, sharing it between unrelated functions.
>>>
>>> Mill's scratchpad is more like a CPU-supported notion of frame
>>> activation record.  Every time you enter a function you get a fresh new
>>> scratchpad and when you return from a function, the scratchpad is thrown
>>> away and the caller recovers instead the scratchpad it had before the
>>> call (scrachpads get "pushed on/popped off the stack" behind the scene).
>>>
>>> So it's easy for programmers and compilers to use it as a kind of "slow
>>> register file with register-windows".
>>
>> I've been toying with the idea of having a small scratchpad at a fixed
>> memory location in the MRISC32 for the sake of doing things like vector
>> register permutations (a la POWER vperm): Since the machine has
>> scatter/gather it is trivial to do permutations via memory in just two
>> instructions (a linear store + a gather load), and since the idea is
>> that the vector registers should be long enough to hide any pipeline
>> latencies the permutation operation basically has the same cost as two
>> back-to-back ALU operations, /provided/ that there are no cache misses.
>>
>> The size of a vector register is 64+ bytes (implementation dependent),
>> so the memory requirement for a single register is typically more than
>> one cache line.
>>
>> So, what do you people think?
>
> What happens if you take an interrupt and want to do a context switch
> between the store and the gather load?
>

Interrupts and exceptions are generally problematic for vector loads and
stores and need sufficient support for handling things like a mid-vector
page fault. I have not implemented any solutions for that yet (but there
*are* solutions).

Specifically for a scratchpad you'd have to define the semantics, of
course. I have not come that far yet but you would typically want it to
behave like a register file that is managed during context switches (one
option is to have many small areas - one for each thread, until you run
out of hard areas and need to do software switching).

>> Would a HW scratchpad have a performance
>> advantage over, say, using the local stack as scratchpad area for the
>> purpose of doing vector permutations and similar?
>
> Probably, but I suspect there are better ways of accomplishing this
> functionality.

The best (as in most performant) way is to have a dedicated vector
permutation unit, so that you do not have to do the cache/scratchpad
roundtrip, but such a thing is usually quite costly (and it adds
requirements on how the VRF must work).

Hmm... I guess you could code up a "macro instruction" that acts like
a combined store + load but against an internal memory that is hidden
from the programmer. If the instruction is guaranteed to be atomic (i.e.
no interrupts are allowed mid instruction), there would be no need to
ever care about the contents of the memory (e.g. during context
switches). I do not have any similar instructions ATM, though.

/Marcus

On 7/8/2021 12:12 AM, Anton Ertl wrote:
> Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:
>> There are embedded applications that have a required response time to
>> some event. That is, when that event occurs, you must respond within a
>> specified amount of time. By having a fixed amount of storage that you
>> know will respond within that time, you can guarantee meeting the
>> timing. If you put it in a cache, you risk getting a cache miss on that
>> data, and thus missing timing.
>
> There exists hardware where you can lock cache lines (they cannot be
> evicted) for that purpose. AFAIK some PowerPC CPUs have this, and I
> expect that ARM Cortex-R CPUs have this, too.

Yes, another solution to the problem. It has the advantage of not
requiring the HW to have a specific hardware defined amount of dedicated
memory. It's disadvantage is that you are "wasting" some amount of HW
(the tags, etc. for the locked lines), which could be significant if you
need a relatively large amount of locked space.

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

Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:
>On 7/8/2021 12:12 AM, Anton Ertl wrote:
>> There exists hardware where you can lock cache lines (they cannot be
>> evicted) for that purpose. AFAIK some PowerPC CPUs have this, and I
>> expect that ARM Cortex-R CPUs have this, too.
>
>Yes, another solution to the problem. It has the advantage of not
>requiring the HW to have a specific hardware defined amount of dedicated
>memory. It's disadvantage is that you are "wasting" some amount of HW
>(the tags, etc. for the locked lines)

If you want to lock lines that are not in a hardware-defined subset of
the address space, the tags are not wasted.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

On 7/8/2021 10:20 AM, Anton Ertl wrote:
> Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:
>> On 7/8/2021 12:12 AM, Anton Ertl wrote:
>>> There exists hardware where you can lock cache lines (they cannot be
>>> evicted) for that purpose. AFAIK some PowerPC CPUs have this, and I
>>> expect that ARM Cortex-R CPUs have this, too.
>>
>> Yes, another solution to the problem. It has the advantage of not
>> requiring the HW to have a specific hardware defined amount of dedicated
>> memory. It's disadvantage is that you are "wasting" some amount of HW
>> (the tags, etc. for the locked lines)
>
> If you want to lock lines that are not in a hardware-defined subset of
> the address space, the tags are not wasted.

I probably wasn't clear. I know that you need the tags for the locked
lines, but if you used dedicated memory instead of a cache, then you
don't need tags, etc. for the dedicated memory.

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

On Thursday, July 8, 2021 at 12:03:39 PM UTC-6, Stephen Fuld wrote:
> On 7/8/2021 10:20 AM, Anton Ertl wrote:

> > If you want to lock lines that are not in a hardware-defined subset of
> > the address space, the tags are not wasted.

> I probably wasn't clear. I know that you need the tags for the locked
> lines, but if you used dedicated memory instead of a cache, then you
> don't need tags, etc. for the dedicated memory.

You still don't need to waste the tags.

If it happens that a cache line is 64 bits, since a tag is a 64-bit address,
you could simply use the tags too and thus have to lock only half as many
cache entries to get your buffer.

Of course, a cache line is more likely to be something like 512 bits.

John Savard

On 7/8/2021 5:00 AM, Marcus wrote:
> On 2021-07-08, Stephen Fuld wrote:
>> On 7/7/2021 11:20 PM, Marcus wrote:
>>> On 2021-07-06, Stefan Monnier wrote:
>>>>> I have used architectures with scratchpads or that could configure
>>>>> half the
>>>>> cache as scratchpad, yuck.
>>>>
>>>> I don't think these scratchpads are very much like the Mill's
>>>> scratchpad.
>>>>
>>>> I suspect the "yuck" above refers to the problems you end up having of
>>>> administering this scratchpad, sharing it between unrelated functions.
>>>>
>>>> Mill's scratchpad is more like a CPU-supported notion of frame
>>>> activation record.  Every time you enter a function you get a fresh new
>>>> scratchpad and when you return from a function, the scratchpad is
>>>> thrown
>>>> away and the caller recovers instead the scratchpad it had before the
>>>> call (scrachpads get "pushed on/popped off the stack" behind the
>>>> scene).
>>>>
>>>> So it's easy for programmers and compilers to use it as a kind of "slow
>>>> register file with register-windows".
>>>
>>> I've been toying with the idea of having a small scratchpad at a fixed
>>> memory location in the MRISC32 for the sake of doing things like vector
>>> register permutations (a la POWER vperm): Since the machine has
>>> scatter/gather it is trivial to do permutations via memory in just two
>>> instructions (a linear store + a gather load), and since the idea is
>>> that the vector registers should be long enough to hide any pipeline
>>> latencies the permutation operation basically has the same cost as two
>>> back-to-back ALU operations, /provided/ that there are no cache misses.
>>>
>>> The size of a vector register is 64+ bytes (implementation dependent),
>>> so the memory requirement for a single register is typically more than
>>> one cache line.
>>>
>>> So, what do you people think?
>>
>> What happens if you take an interrupt and want to do a context switch
>> between the store and the gather load?
>>
>
> Interrupts and exceptions are generally problematic for vector loads and
> stores and need sufficient support for handling things like a mid-vector
> page fault. I have not implemented any solutions for that yet (but there
> *are* solutions).
>
> Specifically for a scratchpad you'd have to define the semantics, of
> course. I have not come that far yet but you would typically want it to
> behave like a register file that is managed during context switches (one
> option is to have many small areas - one for each thread, until you run
> out of hard areas and need to do software switching).

Ugh!

>>> Would a HW scratchpad have a performance
>>> advantage over, say, using the local stack as scratchpad area for the
>>> purpose of doing vector permutations and similar?
>>
>> Probably, but I suspect there are better ways of accomplishing this
>> functionality.
>
> The best (as in most performant) way is to have a dedicated vector
> permutation unit, so that you do not have to do the cache/scratchpad
> roundtrip, but such a thing is usually quite costly (and it adds
> requirements on how the VRF must work).
>
> Hmm... I guess you could code up a "macro instruction" that acts like
> a combined store + load but against an internal memory that is hidden
> from the programmer. If the instruction is guaranteed to be atomic (i.e.
> no interrupts are allowed mid instruction), there would be no need to
> ever care about the contents of the memory (e.g. during context
> switches). I do not have any similar instructions ATM, though.

That was along the lines of what I was thinking.

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