On 1/15/2022 2:01 AM, Thomas Koenig wrote:
> Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
>> Thomas Koenig wrote:
>>> Ivan Godard <ivan@millcomputing.com> schrieb:
>>>
>>>> Where ISAs really fall down is parsing a bit stream: grab a dynamic
>>>> number of bits off the front of a bit stream, advancing the stream; word
>>>> boundaries are not significant. The problem is that HW provides word
>>>> streams (loop/load) and mapping that to a bit stream is nasty. The logic
>>>> is the same as mapping a line stream into a (VL) instruction stream in
>>>> the decoder's instruction buffer, but how to represent that in an ISA?
>>>
>>> The same way that a vector instruction would be represented?
>>>
>>> Vectors could be made to operate on sub-word quantities such as bytes,
>>> with microarchitectural SIMD underneath.
>>>
>>> I have to confess I do not know much of how compression and
>>> decompression algorithms work. What are the operations that need
>>> to be done with the chunk of bits that is grabbed?
>>>
>> That varies a _lot_! Absolute worst case in my experience is the CABAC
>> option for h264: Content-Adaptive-Binary-Arithmetic-Coding
>>
>> Here you normally extract single bits from the input stream, then you
>> immediately branch on the value of that bit (by definition completely
>> unpredictable, right?) to two separate code paths that really cannot be
>> combined into a single branchless/predicated stream.
>
> Interesting. You can do it in hardware in parallel, then select
> the result. I would assume that the workloads of the two branches
> are roughly the same?
>
> A general purpose CPU could do something similar. A superscalar
> in-order architecture could distribute the work between its
> pipelines. If the ISA has a way to specify separate execution
> units, so that (in SSA form)
>
> if (condition) {
> foo_1 = some work;
> }
> else {
> foo_2 = some other work;
> }
> foo = PHI (foo_1, foo_2);
>
> this could be implemented efficiently even on a superscalar
> in-order machine.
>
> I know this can be done with Mitch's shadow modifier for a limited
> number of instructions, and I also suspect that I am just describing
> a feature of the Mill.

It's a feature of any ISA than can predicate all non-idempotent
instructions of both branches. Mitch's projected predicates can
predicate any instruction; Mill only offers predication for instructions
that can have side effects, and ensures that the ISA has few of those
(in practice only loads and stores and control flow, because all the
potentially-excepting arithmetic instructions produce idempotent NaRs).

However, just because an ISA lets you merge the then and else without a
branch doesn't mean that you *should* merge them. Past an ISA-specific
code size, the cost of processing the instructions you won't execute
exceeds the savings from avoiding the branch.

On Saturday, January 15, 2022 at 4:01:09 AM UTC-6, Thomas Koenig wrote:
> Terje Mathisen <terje.m...@tmsw.no> schrieb:
> > Thomas Koenig wrote:
> >> Ivan Godard <iv...@millcomputing.com> schrieb:
> >>
> >>> Where ISAs really fall down is parsing a bit stream: grab a dynamic
> >>> number of bits off the front of a bit stream, advancing the stream; word
> >>> boundaries are not significant. The problem is that HW provides word
> >>> streams (loop/load) and mapping that to a bit stream is nasty. The logic
> >>> is the same as mapping a line stream into a (VL) instruction stream in
> >>> the decoder's instruction buffer, but how to represent that in an ISA?
> >>
> >> The same way that a vector instruction would be represented?
> >>
> >> Vectors could be made to operate on sub-word quantities such as bytes,
> >> with microarchitectural SIMD underneath.
> >>
> >> I have to confess I do not know much of how compression and
> >> decompression algorithms work. What are the operations that need
> >> to be done with the chunk of bits that is grabbed?
> >>
> > That varies a _lot_! Absolute worst case in my experience is the CABAC
> > option for h264: Content-Adaptive-Binary-Arithmetic-Coding
> >
> > Here you normally extract single bits from the input stream, then you
> > immediately branch on the value of that bit (by definition completely
> > unpredictable, right?) to two separate code paths that really cannot be
> > combined into a single branchless/predicated stream.
> Interesting. You can do it in hardware in parallel, then select
> the result. I would assume that the workloads of the two branches
> are roughly the same?
>
> A general purpose CPU could do something similar. A superscalar
> in-order architecture could distribute the work between its
> pipelines. If the ISA has a way to specify separate execution
> units, so that (in SSA form)
>
> if (condition) {
> foo_1 = some work;
> }
> else {
> foo_2 = some other work;
> }
> foo = PHI (foo_1, foo_2);
>
> this could be implemented efficiently even on a superscalar
> in-order machine.
>
> I know this can be done with Mitch's shadow modifier for a limited
> number of instructions,
<
My 66000 can predicate up to 8 instructions. Those 8 can be placed in the
then-clause or in the else-clause; so those 8 instructions are the sum of
both clauses.
<
Predication makes use of the momentum of the instruction fetch-decode
stream and pipelines.
<
> and I also suspect that I am just describing
> a feature of the Mill.

> A general purpose CPU could do something similar. A superscalar
> in-order architecture could distribute the work between its
> pipelines. If the ISA has a way to specify separate execution
> units, so that (in SSA form)
>
> if (condition) {
> foo_1 = some work;
> }
> else {
> foo_2 = some other work;
> }
> foo = PHI (foo_1, foo_2);
>
> this could be implemented efficiently even on a superscalar
> in-order machine.

Eagerly running both sides of the branches is "easy" only if both
branches are simple enough (using predication for example). If they
include function calls and/or loops you really enter into the
multithreading realm.

Stefan

On Saturday, January 15, 2022 at 11:47:21 AM UTC-6, Stefan Monnier wrote:
> > A general purpose CPU could do something similar. A superscalar
> > in-order architecture could distribute the work between its
> > pipelines. If the ISA has a way to specify separate execution
> > units, so that (in SSA form)
> >
> > if (condition) {
> > foo_1 = some work;
> > }
> > else {
> > foo_2 = some other work;
> > }
> > foo = PHI (foo_1, foo_2);
> >
> > this could be implemented efficiently even on a superscalar
> > in-order machine.
<
> Eagerly running both sides of the branches is "easy" only if both
> branches are simple enough (using predication for example). If they
> include function calls and/or loops you really enter into the
> multithreading realm.
<
Running both sides and throwing one side away is a waste of power
{the vast majority of the time}.
>
>
> Stefan

On 1/15/2022 9:47 AM, Stefan Monnier wrote:
>> A general purpose CPU could do something similar. A superscalar
>> in-order architecture could distribute the work between its
>> pipelines. If the ISA has a way to specify separate execution
>> units, so that (in SSA form)
>>
>> if (condition) {
>> foo_1 = some work;
>> }
>> else {
>> foo_2 = some other work;
>> }
>> foo = PHI (foo_1, foo_2);
>>
>> this could be implemented efficiently even on a superscalar
>> in-order machine.
>
> Eagerly running both sides of the branches is "easy" only if both
> branches are simple enough (using predication for example). If they
> include function calls and/or loops you really enter into the
> multithreading realm.
>
>
> Stefan

Yes. NYF.

Thomas Koenig wrote:
> Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
>> Thomas Koenig wrote:
>>> Ivan Godard <ivan@millcomputing.com> schrieb:
>>>
>>>> Where ISAs really fall down is parsing a bit stream: grab a dynamic
>>>> number of bits off the front of a bit stream, advancing the stream; word
>>>> boundaries are not significant. The problem is that HW provides word
>>>> streams (loop/load) and mapping that to a bit stream is nasty. The logic
>>>> is the same as mapping a line stream into a (VL) instruction stream in
>>>> the decoder's instruction buffer, but how to represent that in an ISA?
>>>
>>> The same way that a vector instruction would be represented?
>>>
>>> Vectors could be made to operate on sub-word quantities such as bytes,
>>> with microarchitectural SIMD underneath.
>>>
>>> I have to confess I do not know much of how compression and
>>> decompression algorithms work. What are the operations that need
>>> to be done with the chunk of bits that is grabbed?
>>>
>> That varies a _lot_! Absolute worst case in my experience is the CABAC
>> option for h264: Content-Adaptive-Binary-Arithmetic-Coding
>>
>> Here you normally extract single bits from the input stream, then you
>> immediately branch on the value of that bit (by definition completely
>> unpredictable, right?) to two separate code paths that really cannot be
>> combined into a single branchless/predicated stream.
>
> Interesting. You can do it in hardware in parallel, then select

Not needed.

> the result. I would assume that the workloads of the two branches
> are roughly the same?

You would be wrong: Those two paths can be completely different both in
size/time & complexity.

A HW decoder only has to keep up with 40 Mbit/s, so with a ~GHz clock it
has all the time in the world to figure which state machine to enter
now. I.e. I can't see any reason/need to predict/run-ahead/predicate
parallel blocks.

Terje

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

On 1/5/2022 10:40 PM, Ivan Godard wrote:
> On 1/5/2022 3:13 PM, EricP wrote:
>> Ivan Godard wrote:
>>> On 1/4/2022 9:48 AM, EricP wrote:
>>>> Ivan Godard wrote:
>>>>> On 1/4/2022 12:39 AM, Thomas Koenig wrote:
>>>>>> Ivan Godard <ivan@millcomputing.com> schrieb:
>>>>>>
>>>>>>> Perhaps you haven't noticed me saying: *the belt is not physically a
>>>>>>> shift register*.
>>>>>>
>>>>>> It's usually implemented as a circular buffer, correct?
>>>>>
>>>>> Not at all.
>>>>>
>>>>> Computed values are left where they were produced - FU's output
>>>>> latches, for example - just as in a forwarding bypass network. Move
>>>>> only happens if the location is needed by some other computation,
>>>>> and then only to an adjacent location, also on the bypass network -
>>>>> which the way issue happens guarantees is free.
>>>>
>>>> Moving results out of the way is what makes this work.
>>>> If you only have one adder FU and you get a bunch of add instructions
>>>> in a row, then you need to stash older results in other registers
>>>> and this becomes the equivalent of a delayed register writeback.
>>>> But I think you need a crossbar to accomplish this while a
>>>> traditional approach just needs some small number of result buses.
>>>>
>>>>
>>>
>>> Still not :-)
>>>
>>> Our FU slots can (and typically do) support operations of different
>>> natural latencies (pipe lengths). Each slot can accept one op per
>>> cycle, so if the latencies differ you can get more than one result
>>> retiring in the same cycle. Consequently the FUs have one result FF
>>> per supported latency.
>>>
>>> If a op of latency N retires in cycle C to FF#N, necessarily the
>>> following cycle C+1 the FF#N+1 is free (think about it).
>>> Consequently, the FU's FFs are daisy chained so that each cycle FF#N
>>> is moved to FF#N+1  and every result always is retiring to a known
>>> free FF; the set of FFs are right next to each other so the move is
>>> trivial.
>>
>> This sounds like it has a belt's worth of FF for each FU.
>> And some of them are shift registers?
>> I'm a bit confused.
>
> There can be (and usually are) several FUs per slot, forming in effect a
> "superFU". There is only one set of output FFs per slot, one per
> latency. These are daisy chained. I suppose that you can think of the
> output FF daisy as being a shift register, and it could be done that
> way, but it also could be done by simply rotating which FF is considered
> which latency, thereby replacing a physical data move with a
> result-to-FF fanout. That's a HW design choice; IANAHWG.

I thought I had at least a basic understanding of how you actually
implement the belt, but Eric's post made me question that, and I don't
think you addressed his exact question. So, suppose you have exactly
one add FU, and that it has a latency of 1. My understanding is that
there is therefore one set of FFs at the add FU's output. Suppose the
belt length is 16, though this isn't particularly critical.
Now suppose you have an instruction stream with say 4-5 consecutive
adds. I understand that this may take several instructions, as you only
have one add FU. After the first add, the result is in that FUs output
FFs, and has a some belt position. After the second add, since you want
the FUs output FFs to hold the result, but they still have the result
from the first add, you need some place to hold the first result. I
gather this is somewhere in the spiller. Now let's keep going to the
third add. Are there more spots in the spiller? If so, there must be
some limit, although it is probably configurable. What happens if the
number of consecutive adds exceeds that limit.

Anyway, I hope you can see my confusion and will clarity it.

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

On 1/17/2022 11:32 AM, Stephen Fuld wrote:
> On 1/5/2022 10:40 PM, Ivan Godard wrote:
>> On 1/5/2022 3:13 PM, EricP wrote:
>>> Ivan Godard wrote:
>>>> On 1/4/2022 9:48 AM, EricP wrote:
>>>>> Ivan Godard wrote:
>>>>>> On 1/4/2022 12:39 AM, Thomas Koenig wrote:
>>>>>>> Ivan Godard <ivan@millcomputing.com> schrieb:
>>>>>>>
>>>>>>>> Perhaps you haven't noticed me saying: *the belt is not
>>>>>>>> physically a
>>>>>>>> shift register*.
>>>>>>>
>>>>>>> It's usually implemented as a circular buffer, correct?
>>>>>>
>>>>>> Not at all.
>>>>>>
>>>>>> Computed values are left where they were produced - FU's output
>>>>>> latches, for example - just as in a forwarding bypass network.
>>>>>> Move only happens if the location is needed by some other
>>>>>> computation, and then only to an adjacent location, also on the
>>>>>> bypass network - which the way issue happens guarantees is free.
>>>>>
>>>>> Moving results out of the way is what makes this work.
>>>>> If you only have one adder FU and you get a bunch of add instructions
>>>>> in a row, then you need to stash older results in other registers
>>>>> and this becomes the equivalent of a delayed register writeback.
>>>>> But I think you need a crossbar to accomplish this while a
>>>>> traditional approach just needs some small number of result buses.
>>>>>
>>>>>
>>>>
>>>> Still not :-)
>>>>
>>>> Our FU slots can (and typically do) support operations of different
>>>> natural latencies (pipe lengths). Each slot can accept one op per
>>>> cycle, so if the latencies differ you can get more than one result
>>>> retiring in the same cycle. Consequently the FUs have one result FF
>>>> per supported latency.
>>>>
>>>> If a op of latency N retires in cycle C to FF#N, necessarily the
>>>> following cycle C+1 the FF#N+1 is free (think about it).
>>>> Consequently, the FU's FFs are daisy chained so that each cycle FF#N
>>>> is moved to FF#N+1  and every result always is retiring to a known
>>>> free FF; the set of FFs are right next to each other so the move is
>>>> trivial.
>>>
>>> This sounds like it has a belt's worth of FF for each FU.
>>> And some of them are shift registers?
>>> I'm a bit confused.
>>
>> There can be (and usually are) several FUs per slot, forming in effect
>> a "superFU". There is only one set of output FFs per slot, one per
>> latency. These are daisy chained. I suppose that you can think of the
>> output FF daisy as being a shift register, and it could be done that
>> way, but it also could be done by simply rotating which FF is
>> considered which latency, thereby replacing a physical data move with
>> a result-to-FF fanout. That's a HW design choice; IANAHWG.
>
> I thought I had at least a basic understanding of how you actually
> implement the belt, but Eric's post made me question that, and I don't
> think you addressed his exact question.  So, suppose you have exactly
> one add FU, and that it has a latency of 1. My understanding is that
> there is therefore one set of FFs at the add FU's output. Suppose the
> belt length is 16, though this isn't particularly critical.
> Now suppose you have an instruction stream with say 4-5 consecutive
> adds.  I understand that this may take several instructions, as you only
> have one add FU.  After the first add, the result is in that FUs output
> FFs, and has a some belt position.  After the second add, since you want
> the FUs output FFs to hold the result, but they still have the result
> from the first add, you need some place to hold the first result.  I
> gather this is somewhere in the spiller.  Now let's keep going to the
> third add.  Are there more spots in the spiller?  If so, there must be
> some limit, although it is probably configurable.  What happens if the
> number of consecutive adds exceeds that limit.
>
> Anyway, I hope you can see my confusion and will clarity it.

Looks like the confusion is the difference between FU and slot. A FU is
a unit of computation - an ALU or FPU for example. A slot is a unit of
encoding. All slots have at least one FU attached, but they can (and
usually do) have several. The only requirement is that decode be able
to supply to the slot everything that any of the attached FUs needs to
do for any of its supported instructions.

The result FFs are per-slot, not per-FU. There is one FF per latency
supported by any instruction of any FU attached to that slot, and for
any intermediate latency that happens not to have any instructions that
use it. The FFs are logically chained to make a shift register, although
for power reasons it may use a different implementation than a physical
shift register.

Your example with only one latency is unrealistic; typical arithmetic
(exu) slots have several FUs with an assortment of latencies: an ALU, a
FPU, an integer multiplier, an assortment of 2-cycle wide-data
operations, and so on. If it should happen that a slot has only one or a
few latencies then the member config may add one or more extra FFs so as
to lengthen the FF shift register, to make it more likely that a value
will die before it gets to the end of the SR.

A live result that gets to the end is moved to the spiller buffers,
which are just FFs, almost as if the spiller were just another slot. The
spiller buffers are able to accept one value from each slot each cycle,
because the slot SR can only have one value falling off the SR per
cycle. The spiller buffers get reused when a value they have goes dead;
the logic is essentially the same as is used in an OOO genreg machine to
assign physical registers, though the amount of logic is much less than
that required to assign several hundred genregs because the maximum live
population is bounded by the belt length.

The number of slots, slot FU (and instruction) populations, the length
of the per slot SR, the number of spiller buffers and so on are all
member config parameters, that is balanced for market, expected usage,
power and other constraints at chip design time.

To take your example of an empty belt and a string of adds: a+b+c+d+e,
all latency one. Say there is only one exu slot, and it has a 1-cycle
ALU, a 3-cycle multiplier, and a filler lat-2 FF even though the slot
has no lat-2 instructions. The belt is assumed to be longer than 5, so
no intermediate results die in the example.

In the first cycle:
cycle 1: (a+b)->lat1
cycle 2: lat1->lat2; (a+b)+c->lat1
cycle 3: lat2->lat3; lat1->lat2; (a+b+c)+d->lat1
cycle 4: lat3->sX; lat2->lat3; lat1->lat2; (a+b+c+d)->lat1
cycle 5: (sX); lat3->sY; lat2->lat3; lat1->lat2; (a+b+c+d+e)->lat1

I emphasize that only the moves from the end of the SR (lat3 here) to
the spiller are physical and cost power.

The number of spiller buffers is constrained by the length of the belt -
there can never be more live values than that. However, there may be
fewer at hardware option. The spiller must be able to hold an arbitrary
amount of data because the spiller is used to save the belt across
calls. If it runs out of buffers then values can move to an internal
SRAM; when it runs out of SRAM halues are written to the spiller stack
in memory. These overflow conditions can saturate the spiller bandwidth,
causing stalls. The spiller buffer and SRAM sizes are configured to
balance stalls vs chip cost.

Does this help?

> Your example with only one latency is unrealistic; typical arithmetic (exu)
> slots have several FUs with an assortment of latencies: an ALU, a FPU, an
> integer multiplier, an assortment of 2-cycle wide-data operations, and so
> on. If it should happen that a slot has only one or a few latencies then the
> member config may add one or more extra FFs so as to lengthen the FF shift
> register, to make it more likely that a value will die before it gets to the
> end of the SR.

IIUC your crossbar has a number of inputs equal to

nb-of-slots * nb-of-latencies + spiller (+ immediates?)

[ Modulo the fact that different slots may actually have different
latencies. ]

So adding latencies (well, adding extra FFs beyond the ones required by
the actual ops's latencies) might save power by avoiding moving the data
to the spiller, but it also increases the input size of the crossbar, so
there's a tradeoff which is why you have the spiller (rather than
extend all slots to have the same number of latencies as belt
positions).

Also you say the number of FFs in the spiller can be bounded by the
number of belt positions, but is it even possible to reach this bound?
I guess a tighter bound might be something like

belt-size - nb-of-latencies

right? And I guess if you can somehow make sure the code always spreads
its work among the slots this could be reduced closer to the ideal

belt-size - nb-of-slots * nb-of-latencies

tho I don't know how practical this is nor how close you can hope to get
to that.

Stefan

On 1/17/2022 1:19 PM, Stefan Monnier wrote:
>> Your example with only one latency is unrealistic; typical arithmetic (exu)
>> slots have several FUs with an assortment of latencies: an ALU, a FPU, an
>> integer multiplier, an assortment of 2-cycle wide-data operations, and so
>> on. If it should happen that a slot has only one or a few latencies then the
>> member config may add one or more extra FFs so as to lengthen the FF shift
>> register, to make it more likely that a value will die before it gets to the
>> end of the SR.
>
> IIUC your crossbar has a number of inputs equal to
>
> nb-of-slots * nb-of-latencies + spiller (+ immediates?)
>
> [ Modulo the fact that different slots may actually have different
> latencies. ]
>
> So adding latencies (well, adding extra FFs beyond the ones required by
> the actual ops's latencies) might save power by avoiding moving the data
> to the spiller, but it also increases the input size of the crossbar, so
> there's a tradeoff which is why you have the spiller (rather than
> extend all slots to have the same number of latencies as belt
> positions).
>
> Also you say the number of FFs in the spiller can be bounded by the
> number of belt positions, but is it even possible to reach this bound?
> I guess a tighter bound might be something like
>
> belt-size - nb-of-latencies
>
> right? And I guess if you can somehow make sure the code always spreads
> its work among the slots this could be reduced closer to the ideal
>
> belt-size - nb-of-slots * nb-of-latencies
>
> tho I don't know how practical this is nor how close you can hope to get
> to that.
>
>
> Stefan

Yep, it's all a game of tradeoffs, as in any HW design.

The spiller bound is (beltsize). You could (for a belt-16) have 16
unrelated drops, then enough drop-less cycles for all of them to migrate
to the spiller. The next drop (in the slot FFs) would kill one of the
spiller buffers, but that would eventually be filled when the 17th drop
made it to the spiller. Of course that is a very artificial situation in
real code, so an actual config can reduce the number of spiller buffers
if it judges that the rate of spiller stalls is acceptable.

The number of inputs to the crossbar is also logically bounded by the
belt size. However, the belt is scattered over what amounts to a bypass
network, so the number of physical inputs is (as you suggest) the sum of
the slot latency FFs, the spiller buffers, and some other sources such
as the load retire stations and the scratchpad. There are still a lot
fewer than on a genreg with similar performce - Silver (belt 16) has ~30
sources IIRC.

It helps that we have a patented cascaded crossbar. All the lat1 FFs go
direct to the xbar, but the rest first go through a N->3 pre-bar and the
three join with the lat1s in a (slot+3)->inputs post-bar. Because all
the sources for the pre-bar are lat2 or greater we push the pre-bar gate
cost into the sources.

This works because no instructions ever has an exact integral latency -
that 3-cycle multiplier is really 2-8/14ths. So there is 6/14th of a
cycle to do its pre-bar, so the crossbar actually takes only the
post-bar time, and the post-bar has only 20-25% of the overall sources
and can be fast. Sure, the odd long-latency instruction may be natively
so close to the cycle boundary that it has to push its pre-bar into
another cycle, but so what? Them's the tradeoffs :-)

On Monday, January 17, 2022 at 2:52:14 PM UTC-6, Ivan Godard wrote:

>
> In the first cycle:
> cycle 1: (a+b)->lat1
> cycle 2: lat1->lat2; (a+b)+c->lat1
> cycle 3: lat2->lat3; lat1->lat2; (a+b+c)+d->lat1
> cycle 4: lat3->sX; lat2->lat3; lat1->lat2; (a+b+c+d)->lat1
> cycle 5: (sX); lat3->sY; lat2->lat3; lat1->lat2; (a+b+c+d+e)->lat1
<
Why is cycle 4 not::
<
cycle 4: lat3->sX; lat2->lat3; lat1->lat2; (a+b+c+d)+e->lat1
<
The first 3 instructions perform an ADD why not cycle 4 ?

On 1/17/2022 2:36 PM, MitchAlsup wrote:
> On Monday, January 17, 2022 at 2:52:14 PM UTC-6, Ivan Godard wrote:
>
>>
>> In the first cycle:
>> cycle 1: (a+b)->lat1
>> cycle 2: lat1->lat2; (a+b)+c->lat1
>> cycle 3: lat2->lat3; lat1->lat2; (a+b+c)+d->lat1
>> cycle 4: lat3->sX; lat2->lat3; lat1->lat2; (a+b+c+d)->lat1
>> cycle 5: (sX); lat3->sY; lat2->lat3; lat1->lat2; (a+b+c+d+e)->lat1
> <
> Why is cycle 4 not::
> <
> cycle 4: lat3->sX; lat2->lat3; lat1->lat2; (a+b+c+d)+e->lat1
> <
> The first 3 instructions perform an ADD why not cycle 4 ?

Because I'm a bad proofreader?

In the first cycle:
cycle 1: (a+b)->lat1
cycle 2: lat1->lat2; (a+b)+c->lat1
cycle 3: lat2->lat3; lat1->lat2; (a+b+c)+d->lat1
cycle 4: lat3->sX; lat2->lat3; lat1->lat2; (a+b+c+d)+e->lat1
cycle 5: (sX); lat3->sY; lat2->lat3; lat1->lat2; (a+b+c+d+e)+f->lat1

On Monday, January 17, 2022 at 5:23:21 PM UTC-6, Ivan Godard wrote:
> On 1/17/2022 2:36 PM, MitchAlsup wrote:
> > On Monday, January 17, 2022 at 2:52:14 PM UTC-6, Ivan Godard wrote:
> >
> >>
> >> In the first cycle:
> >> cycle 1: (a+b)->lat1
> >> cycle 2: lat1->lat2; (a+b)+c->lat1
> >> cycle 3: lat2->lat3; lat1->lat2; (a+b+c)+d->lat1
> >> cycle 4: lat3->sX; lat2->lat3; lat1->lat2; (a+b+c+d)->lat1
> >> cycle 5: (sX); lat3->sY; lat2->lat3; lat1->lat2; (a+b+c+d+e)->lat1
> > <
> > Why is cycle 4 not::
> > <
> > cycle 4: lat3->sX; lat2->lat3; lat1->lat2; (a+b+c+d)+e->lat1
> > <
> > The first 3 instructions perform an ADD why not cycle 4 ?
> Because I'm a bad proofreader?
<
Are you surprised someone actually read what you wrote ?
<
> In the first cycle:
> cycle 1: (a+b)->lat1
> cycle 2: lat1->lat2; (a+b)+c->lat1
> cycle 3: lat2->lat3; lat1->lat2; (a+b+c)+d->lat1
> cycle 4: lat3->sX; lat2->lat3; lat1->lat2; (a+b+c+d)+e->lat1
> cycle 5: (sX); lat3->sY; lat2->lat3; lat1->lat2; (a+b+c+d+e)+f->lat1

On 1/17/2022 12:52 PM, Ivan Godard wrote:
> On 1/17/2022 11:32 AM, Stephen Fuld wrote:
>> On 1/5/2022 10:40 PM, Ivan Godard wrote:
>>> On 1/5/2022 3:13 PM, EricP wrote:
>>>> Ivan Godard wrote:
>>>>> On 1/4/2022 9:48 AM, EricP wrote:
>>>>>> Ivan Godard wrote:
>>>>>>> On 1/4/2022 12:39 AM, Thomas Koenig wrote:
>>>>>>>> Ivan Godard <ivan@millcomputing.com> schrieb:
>>>>>>>>
>>>>>>>>> Perhaps you haven't noticed me saying: *the belt is not
>>>>>>>>> physically a
>>>>>>>>> shift register*.
>>>>>>>>
>>>>>>>> It's usually implemented as a circular buffer, correct?
>>>>>>>
>>>>>>> Not at all.
>>>>>>>
>>>>>>> Computed values are left where they were produced - FU's output
>>>>>>> latches, for example - just as in a forwarding bypass network.
>>>>>>> Move only happens if the location is needed by some other
>>>>>>> computation, and then only to an adjacent location, also on the
>>>>>>> bypass network - which the way issue happens guarantees is free.
>>>>>>
>>>>>> Moving results out of the way is what makes this work.
>>>>>> If you only have one adder FU and you get a bunch of add instructions
>>>>>> in a row, then you need to stash older results in other registers
>>>>>> and this becomes the equivalent of a delayed register writeback.
>>>>>> But I think you need a crossbar to accomplish this while a
>>>>>> traditional approach just needs some small number of result buses.
>>>>>>
>>>>>>
>>>>>
>>>>> Still not :-)
>>>>>
>>>>> Our FU slots can (and typically do) support operations of different
>>>>> natural latencies (pipe lengths). Each slot can accept one op per
>>>>> cycle, so if the latencies differ you can get more than one result
>>>>> retiring in the same cycle. Consequently the FUs have one result FF
>>>>> per supported latency.
>>>>>
>>>>> If a op of latency N retires in cycle C to FF#N, necessarily the
>>>>> following cycle C+1 the FF#N+1 is free (think about it).
>>>>> Consequently, the FU's FFs are daisy chained so that each cycle
>>>>> FF#N is moved to FF#N+1  and every result always is retiring to a
>>>>> known free FF; the set of FFs are right next to each other so the
>>>>> move is trivial.
>>>>
>>>> This sounds like it has a belt's worth of FF for each FU.
>>>> And some of them are shift registers?
>>>> I'm a bit confused.
>>>
>>> There can be (and usually are) several FUs per slot, forming in
>>> effect a "superFU". There is only one set of output FFs per slot, one
>>> per latency. These are daisy chained. I suppose that you can think of
>>> the output FF daisy as being a shift register, and it could be done
>>> that way, but it also could be done by simply rotating which FF is
>>> considered which latency, thereby replacing a physical data move with
>>> a result-to-FF fanout. That's a HW design choice; IANAHWG.
>>
>> I thought I had at least a basic understanding of how you actually
>> implement the belt, but Eric's post made me question that, and I don't
>> think you addressed his exact question.  So, suppose you have exactly
>> one add FU, and that it has a latency of 1. My understanding is that
>> there is therefore one set of FFs at the add FU's output. Suppose the
>> belt length is 16, though this isn't particularly critical.
>> Now suppose you have an instruction stream with say 4-5 consecutive
>> adds.  I understand that this may take several instructions, as you
>> only have one add FU.  After the first add, the result is in that FUs
>> output FFs, and has a some belt position.  After the second add, since
>> you want the FUs output FFs to hold the result, but they still have
>> the result from the first add, you need some place to hold the first
>> result.  I gather this is somewhere in the spiller.  Now let's keep
>> going to the third add.  Are there more spots in the spiller?  If so,
>> there must be some limit, although it is probably configurable.  What
>> happens if the number of consecutive adds exceeds that limit.
>>
>> Anyway, I hope you can see my confusion and will clarity it.
>
> Looks like the confusion is the difference between FU and slot.

After reading through your response, I agree - that was my confusion.
See more below.

> A FU is
> a unit of computation - an ALU or FPU for example. A slot is a unit of
> encoding. All slots have at least one FU attached, but they can (and
> usually do) have several. The only requirement is that decode be able to
> supply to the slot everything that any of the attached FUs needs to do
> for any of its supported instructions.

So since a slot can encode one operation, of any type supported on that
slot, at a time, doesn't that lead to lots of "extra" functional units.
i.e. if you have two slots, each able to encode an add or a multiply,
I think you have four FUs, of which only two can be used in any given
instruction. Or am I still confused?

> The result FFs are per-slot, not per-FU.

Got it.

> There is one FF per latency
> supported by any instruction of any FU attached to that slot, and for
> any intermediate latency that happens not to have any instructions that
> use it. The FFs are logically chained to make a shift register, although
> for power reasons it may use a different implementation than a physical
> shift register.

OK. I understand.

> Your example with only one latency is unrealistic; typical arithmetic
> (exu) slots have several FUs with an assortment of latencies: an ALU, a
> FPU, an integer multiplier, an assortment of 2-cycle wide-data
> operations, and so on. If it should happen that a slot has only one or a
> few latencies then the member config may add one or more extra FFs so as
> to lengthen the FF shift register, to make it more likely that a value
> will die before it gets to the end of the SR.

OK. So each slot has a sort of addressable FIFO of FFs. It is
addressable in that each has its own belt position identifier, but it is
a FIFO in that adding a new entry "pushes" down the other entries. Is
that correct?

snip a lot of useful exposition.

> Does this help?

Yes, very much so. Thanks.

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

Ivan Godard wrote:
> On 1/17/2022 11:32 AM, Stephen Fuld wrote:
>> On 1/5/2022 10:40 PM, Ivan Godard wrote:
>>> On 1/5/2022 3:13 PM, EricP wrote:
>>>> Ivan Godard wrote:
>>>>> On 1/4/2022 9:48 AM, EricP wrote:
>>>>>> Ivan Godard wrote:
>>>>>>> On 1/4/2022 12:39 AM, Thomas Koenig wrote:
>>>>>>>> Ivan Godard <ivan@millcomputing.com> schrieb:
>>>>>>>>
>>>>>>>>> Perhaps you haven't noticed me saying: *the belt is not
>>>>>>>>> physically a
>>>>>>>>> shift register*.
>>>>>>>>
>>>>>>>> It's usually implemented as a circular buffer, correct?
>>>>>>>
>>>>>>> Not at all.
>>>>>>>
>>>>>>> Computed values are left where they were produced - FU's output
>>>>>>> latches, for example - just as in a forwarding bypass network.
>>>>>>> Move only happens if the location is needed by some other
>>>>>>> computation, and then only to an adjacent location, also on the
>>>>>>> bypass network - which the way issue happens guarantees is free.
>>>>>>
>>>>>> Moving results out of the way is what makes this work.
>>>>>> If you only have one adder FU and you get a bunch of add instructions
>>>>>> in a row, then you need to stash older results in other registers
>>>>>> and this becomes the equivalent of a delayed register writeback.
>>>>>> But I think you need a crossbar to accomplish this while a
>>>>>> traditional approach just needs some small number of result buses.
>>>>>>
>>>>>>
>>>>>
>>>>> Still not :-)
>>>>>
>>>>> Our FU slots can (and typically do) support operations of different
>>>>> natural latencies (pipe lengths). Each slot can accept one op per
>>>>> cycle, so if the latencies differ you can get more than one result
>>>>> retiring in the same cycle. Consequently the FUs have one result FF
>>>>> per supported latency.
>>>>>
>>>>> If a op of latency N retires in cycle C to FF#N, necessarily the
>>>>> following cycle C+1 the FF#N+1 is free (think about it).
>>>>> Consequently, the FU's FFs are daisy chained so that each cycle
>>>>> FF#N is moved to FF#N+1 and every result always is retiring to a
>>>>> known free FF; the set of FFs are right next to each other so the
>>>>> move is trivial.
>>>>
>>>> This sounds like it has a belt's worth of FF for each FU.
>>>> And some of them are shift registers?
>>>> I'm a bit confused.
>>>
>>> There can be (and usually are) several FUs per slot, forming in
>>> effect a "superFU". There is only one set of output FFs per slot, one
>>> per latency. These are daisy chained. I suppose that you can think of
>>> the output FF daisy as being a shift register, and it could be done
>>> that way, but it also could be done by simply rotating which FF is
>>> considered which latency, thereby replacing a physical data move with
>>> a result-to-FF fanout. That's a HW design choice; IANAHWG.
>>
>> I thought I had at least a basic understanding of how you actually
>> implement the belt, but Eric's post made me question that, and I don't
>> think you addressed his exact question.

Yeah, I didn't understand either. I found the patent for it (below) and
was looking at it for insights, but I wanted to get back to something else
I was looking at, Load-Store Queues, so I was going to get back again later.

>> So, suppose you have exactly
>> one add FU, and that it has a latency of 1. My understanding is that
>> there is therefore one set of FFs at the add FU's output. Suppose the
>> belt length is 16, though this isn't particularly critical.
>> Now suppose you have an instruction stream with say 4-5 consecutive
>> adds. I understand that this may take several instructions, as you
>> only have one add FU. After the first add, the result is in that FUs
>> output FFs, and has a some belt position. After the second add, since
>> you want the FUs output FFs to hold the result, but they still have
>> the result from the first add, you need some place to hold the first
>> result. I gather this is somewhere in the spiller. Now let's keep
>> going to the third add. Are there more spots in the spiller? If so,
>> there must be some limit, although it is probably configurable. What
>> happens if the number of consecutive adds exceeds that limit.
>>
>> Anyway, I hope you can see my confusion and will clarity it.
>
> Looks like the confusion is the difference between FU and slot. A FU is
> a unit of computation - an ALU or FPU for example. A slot is a unit of
> encoding. All slots have at least one FU attached, but they can (and
> usually do) have several. The only requirement is that decode be able to
> supply to the slot everything that any of the attached FUs needs to do
> for any of its supported instructions.

This is still confusing to me.
It may be because the term "latency" seems to be used two ways:
- latency to mean slot offset slot[0], slot[1]
- each HW FU has a latency and throughput (delay to start next operation).
ALU latency 1 throughput 1, int-MUL lat 4 thru 1, int-DIV lat 16 thru 16.

> The result FFs are per-slot, not per-FU. There is one FF per latency
> supported by any instruction of any FU attached to that slot, and for
> any intermediate latency that happens not to have any instructions that
> use it. The FFs are logically chained to make a shift register, although
> for power reasons it may use a different implementation than a physical
> shift register.

The Belt is a logical shift register - all FU's drop their results
into slot[-1] then shift that right into slot[0].
There is no OoO so if a slot[-1] result isn't ready the belt shift stalls.

If belt is length 16, then for any mix of instructions there are
only 16 logically valid results in this belt.
If I have 16 adds in a row, then FU.Alu must have a
16 FF shift registers to hold those results.
If there is a second Alu, then another 16 FF shift register for that.

Only 16 of those slots can hold valid values, but from your
description we'd need 32 FF and 32 xbar operand pair inputs,
and 2 xbar FU operand pair outputs.
If we toss in an IMUL and IDIV then 64 FF and xbar inputs,
with 4 xbar operand pair outputs.

From your description this would require the HW FF resources of a
OoO core with 64 physical registers, but derives not of the benefit
of producing

(This is why I assumed that Belt has a second xbar to route results
in my prior little diagram - it eliminates this slots*FU expansion.)

> Your example with only one latency is unrealistic; typical arithmetic
> (exu) slots have several FUs with an assortment of latencies: an ALU, a
> FPU, an integer multiplier, an assortment of 2-cycle wide-data
> operations, and so on. If it should happen that a slot has only one or a
> few latencies then the member config may add one or more extra FFs so as
> to lengthen the FF shift register, to make it more likely that a value
> will die before it gets to the end of the SR.

I don't understand this (maybe its the word latency again).
Each FU *MUST* have belt-length SR FF just in case that many instructions
show up. It could get 16 IDIV's in a row that eventually drop to slot[0:15].

> A live result that gets to the end is moved to the spiller buffers,
> which are just FFs, almost as if the spiller were just another slot. The
> spiller buffers are able to accept one value from each slot each cycle,
> because the slot SR can only have one value falling off the SR per
> cycle. The spiller buffers get reused when a value they have goes dead;
> the logic is essentially the same as is used in an OOO genreg machine to
> assign physical registers, though the amount of logic is much less than
> that required to assign several hundred genregs because the maximum live
> population is bounded by the belt length.
>
> The number of slots, slot FU (and instruction) populations, the length
> of the per slot SR, the number of spiller buffers and so on are all
> member config parameters, that is balanced for market, expected usage,
> power and other constraints at chip design time.
>
> To take your example of an empty belt and a string of adds: a+b+c+d+e,
> all latency one. Say there is only one exu slot, and it has a 1-cycle
> ALU, a 3-cycle multiplier, and a filler lat-2 FF even though the slot
> has no lat-2 instructions. The belt is assumed to be longer than 5, so
> no intermediate results die in the example.
>
> In the first cycle:
> cycle 1: (a+b)->lat1
> cycle 2: lat1->lat2; (a+b)+c->lat1
> cycle 3: lat2->lat3; lat1->lat2; (a+b+c)+d->lat1
> cycle 4: lat3->sX; lat2->lat3; lat1->lat2; (a+b+c+d)->lat1
> cycle 5: (sX); lat3->sY; lat2->lat3; lat1->lat2; (a+b+c+d+e)->lat1

EricP wrote:
> Ivan Godard wrote:
>>
>> To take your example of an empty belt and a string of adds: a+b+c+d+e,
>> all latency one. Say there is only one exu slot, and it has a 1-cycle
>> ALU, a 3-cycle multiplier, and a filler lat-2 FF even though the slot
>> has no lat-2 instructions. The belt is assumed to be longer than 5, so
>> no intermediate results die in the example.
>>
>> In the first cycle:
>> cycle 1: (a+b)->lat1
>> cycle 2: lat1->lat2; (a+b)+c->lat1
>> cycle 3: lat2->lat3; lat1->lat2; (a+b+c)+d->lat1
>> cycle 4: lat3->sX; lat2->lat3; lat1->lat2; (a+b+c+d)->lat1
>> cycle 5: (sX); lat3->sY; lat2->lat3; lat1->lat2; (a+b+c+d+e)->lat1
>
> This is the easy case with HW (lat,thru) of (1,1) to slot[0:4].
>
> Toss in a second ALU plus (lat,thru) of an IMUL (4,1) and IDIV (16,16).
> In each case the Belt slot inputs to those FU are all valid
> so all launch at once but drop to different slot offsets.

There are multiple things being juggled here.
There is the (latency,throughput) of each type of FU.
There can be multiple FU of each type.
To take advantage of Mill's wide decode we want to get
as many concurrent, pipelined operations going at once.
Then it orders the results as they drop onto the belt,
and if multiple results drop at the same clock then
some kind of predictable ordering into the belt slots
so the compiler knows where things appear to land.

So just to walk through an example to see if I get the basics....

At time T1 we start IMUL1 which drops its result at T4.
There are also 3 ADDs and only one FU.Alu.
ADD1 also starts at T1, ADD2 and ADD3 at T2 and T3,
which drop at T2, T3 and T4.
At T2 ADD1 is finishes so goes slot[0].
At T3 Add2 goes to slot[0], ADD1 shifts to slot[1].
At T4 ADD3 and IMUL1 finish at the same time, and lets say the rule is
first to start drops first, so ADD1, ADD2 shift to slot[3], slot[2]
and IMUL1 and ADD3 drop to slot[1] and slot[0] respectively.

So we wind up with a belt like:

slot[0] slot[1] slot[2] slot[3]
ADD3 IMUL1 ADD2 ADD1

If we had started a second concrrent, pipelined IMUL2 at T2
the result belt looks like:

slot[0] slot[1] slot[2] slot[3] slot[4]
IMUL2 ADD3 IMUL1 ADD2 ADD1

But in terms of FU result FF it looks like

FU.Alu FU.IMul XBAR
ADD3 IMUL2 =>------------
ADD2 IMUL1 =>
ADD1 =>------------
| | | |
v v v v
FU.Alu FU.IMul

On 1/17/2022 9:01 PM, Stephen Fuld wrote:
> On 1/17/2022 12:52 PM, Ivan Godard wrote:
>> On 1/17/2022 11:32 AM, Stephen Fuld wrote:
>>> On 1/5/2022 10:40 PM, Ivan Godard wrote:
>>>> On 1/5/2022 3:13 PM, EricP wrote:
>>>>> Ivan Godard wrote:
>>>>>> On 1/4/2022 9:48 AM, EricP wrote:
>>>>>>> Ivan Godard wrote:
>>>>>>>> On 1/4/2022 12:39 AM, Thomas Koenig wrote:
>>>>>>>>> Ivan Godard <ivan@millcomputing.com> schrieb:
>>>>>>>>>
>>>>>>>>>> Perhaps you haven't noticed me saying: *the belt is not
>>>>>>>>>> physically a
>>>>>>>>>> shift register*.
>>>>>>>>>
>>>>>>>>> It's usually implemented as a circular buffer, correct?
>>>>>>>>
>>>>>>>> Not at all.
>>>>>>>>
>>>>>>>> Computed values are left where they were produced - FU's output
>>>>>>>> latches, for example - just as in a forwarding bypass network.
>>>>>>>> Move only happens if the location is needed by some other
>>>>>>>> computation, and then only to an adjacent location, also on the
>>>>>>>> bypass network - which the way issue happens guarantees is free.
>>>>>>>
>>>>>>> Moving results out of the way is what makes this work.
>>>>>>> If you only have one adder FU and you get a bunch of add
>>>>>>> instructions
>>>>>>> in a row, then you need to stash older results in other registers
>>>>>>> and this becomes the equivalent of a delayed register writeback.
>>>>>>> But I think you need a crossbar to accomplish this while a
>>>>>>> traditional approach just needs some small number of result buses.
>>>>>>>
>>>>>>>
>>>>>>
>>>>>> Still not :-)
>>>>>>
>>>>>> Our FU slots can (and typically do) support operations of
>>>>>> different natural latencies (pipe lengths). Each slot can accept
>>>>>> one op per cycle, so if the latencies differ you can get more than
>>>>>> one result retiring in the same cycle. Consequently the FUs have
>>>>>> one result FF per supported latency.
>>>>>>
>>>>>> If a op of latency N retires in cycle C to FF#N, necessarily the
>>>>>> following cycle C+1 the FF#N+1 is free (think about it).
>>>>>> Consequently, the FU's FFs are daisy chained so that each cycle
>>>>>> FF#N is moved to FF#N+1  and every result always is retiring to a
>>>>>> known free FF; the set of FFs are right next to each other so the
>>>>>> move is trivial.
>>>>>
>>>>> This sounds like it has a belt's worth of FF for each FU.
>>>>> And some of them are shift registers?
>>>>> I'm a bit confused.
>>>>
>>>> There can be (and usually are) several FUs per slot, forming in
>>>> effect a "superFU". There is only one set of output FFs per slot,
>>>> one per latency. These are daisy chained. I suppose that you can
>>>> think of the output FF daisy as being a shift register, and it could
>>>> be done that way, but it also could be done by simply rotating which
>>>> FF is considered which latency, thereby replacing a physical data
>>>> move with a result-to-FF fanout. That's a HW design choice; IANAHWG.
>>>
>>> I thought I had at least a basic understanding of how you actually
>>> implement the belt, but Eric's post made me question that, and I
>>> don't think you addressed his exact question.  So, suppose you have
>>> exactly one add FU, and that it has a latency of 1. My understanding
>>> is that there is therefore one set of FFs at the add FU's output.
>>> Suppose the belt length is 16, though this isn't particularly critical.
>>> Now suppose you have an instruction stream with say 4-5 consecutive
>>> adds.  I understand that this may take several instructions, as you
>>> only have one add FU.  After the first add, the result is in that FUs
>>> output FFs, and has a some belt position.  After the second add,
>>> since you want the FUs output FFs to hold the result, but they still
>>> have the result from the first add, you need some place to hold the
>>> first result.  I gather this is somewhere in the spiller.  Now let's
>>> keep going to the third add.  Are there more spots in the spiller?
>>> If so, there must be some limit, although it is probably
>>> configurable.  What happens if the number of consecutive adds exceeds
>>> that limit.
>>>
>>> Anyway, I hope you can see my confusion and will clarity it.
>>
>> Looks like the confusion is the difference between FU and slot.
>
> After reading through your response, I agree - that was my confusion.
> See more below.
>
>> A FU is a unit of computation - an ALU or FPU for example. A slot is a
>> unit of encoding. All slots have at least one FU attached, but they
>> can (and usually do) have several. The only requirement is that decode
>> be able to supply to the slot everything that any of the attached FUs
>> needs to do for any of its supported instructions.
>
> So since a slot can encode one operation, of any type supported on that
> slot, at a time, doesn't that lead to lots of "extra" functional units.
>  i.e. if you have two slots, each able to encode an add or a multiply,
> I think you have four FUs, of which only two can be used in any given
> instruction.  Or am I still confused?
>

You are right; the density of FUs on slots means that many FUs can be
unused in any given cycle. It's all a game of configurations - scatter
the FUs and more can be used concurrently, but the crossbar gets bigger.

BTW, I agree with Mitch that a modern ALU is so small it's almost free,
so our current configs tend to put an ALU in every exu slot, and then
scatter the more expensive FUs more sparsely.

Also, remember that Mill is a wide issue machine with bundle encoding,
and the bundles have six (really four as two are data) independently
encoded blocks. Only the exu block (all two-in, one or two out slots and
all the compute instructions) have results that need using the FF
chains. Flow block (memory and control flow) and writer block (pure
sinks) have no results, and reader block (pure sources) has special
handling because some of the drops come from decode rather than from
pseudo-FUs.

>
>> The result FFs are per-slot, not per-FU.
>
> Got it.
>
>> There is one FF per latency supported by any instruction of any FU
>> attached to that slot, and for any intermediate latency that happens
>> not to have any instructions that use it. The FFs are logically
>> chained to make a shift register, although for power reasons it may
>> use a different implementation than a physical shift register.
>
> OK.  I understand.
>
>
>> Your example with only one latency is unrealistic; typical arithmetic
>> (exu) slots have several FUs with an assortment of latencies: an ALU,
>> a FPU, an integer multiplier, an assortment of 2-cycle wide-data
>> operations, and so on. If it should happen that a slot has only one or
>> a few latencies then the member config may add one or more extra FFs
>> so as to lengthen the FF shift register, to make it more likely that a
>> value will die before it gets to the end of the SR.
>
> OK.  So each slot has a sort of addressable FIFO of FFs.  It is
> addressable in that each has its own belt position identifier, but it is
> a FIFO in that adding a new entry "pushes" down the other entries.  Is
> that correct?

Each FIFO position has its own physical address, but may over time have
any logical belt position number, or none. Decode does the mapping
between belt position and physical address. There are various hardware
clevernessess involved in maintaining that mapping, some filed and some
NYF and all beyond my ken as a software guy.

>
> snip a lot of useful exposition.
>
>
>> Does this help?
>
> Yes, very much so.  Thanks.
>
>
>

On 1/18/2022 9:40 AM, EricP wrote:
> Ivan Godard wrote:
>> On 1/17/2022 11:32 AM, Stephen Fuld wrote:
>>> On 1/5/2022 10:40 PM, Ivan Godard wrote:
>>>> On 1/5/2022 3:13 PM, EricP wrote:
>>>>> Ivan Godard wrote:
>>>>>> On 1/4/2022 9:48 AM, EricP wrote:
>>>>>>> Ivan Godard wrote:
>>>>>>>> On 1/4/2022 12:39 AM, Thomas Koenig wrote:
>>>>>>>>> Ivan Godard <ivan@millcomputing.com> schrieb:
>>>>>>>>>
>>>>>>>>>> Perhaps you haven't noticed me saying: *the belt is not
>>>>>>>>>> physically a
>>>>>>>>>> shift register*.
>>>>>>>>>
>>>>>>>>> It's usually implemented as a circular buffer, correct?
>>>>>>>>
>>>>>>>> Not at all.
>>>>>>>>
>>>>>>>> Computed values are left where they were produced - FU's output
>>>>>>>> latches, for example - just as in a forwarding bypass network.
>>>>>>>> Move only happens if the location is needed by some other
>>>>>>>> computation, and then only to an adjacent location, also on the
>>>>>>>> bypass network - which the way issue happens guarantees is free.
>>>>>>>
>>>>>>> Moving results out of the way is what makes this work.
>>>>>>> If you only have one adder FU and you get a bunch of add
>>>>>>> instructions
>>>>>>> in a row, then you need to stash older results in other registers
>>>>>>> and this becomes the equivalent of a delayed register writeback.
>>>>>>> But I think you need a crossbar to accomplish this while a
>>>>>>> traditional approach just needs some small number of result buses.
>>>>>>>
>>>>>>>
>>>>>>
>>>>>> Still not :-)
>>>>>>
>>>>>> Our FU slots can (and typically do) support operations of
>>>>>> different natural latencies (pipe lengths). Each slot can accept
>>>>>> one op per cycle, so if the latencies differ you can get more than
>>>>>> one result retiring in the same cycle. Consequently the FUs have
>>>>>> one result FF per supported latency.
>>>>>>
>>>>>> If a op of latency N retires in cycle C to FF#N, necessarily the
>>>>>> following cycle C+1 the FF#N+1 is free (think about it).
>>>>>> Consequently, the FU's FFs are daisy chained so that each cycle
>>>>>> FF#N is moved to FF#N+1  and every result always is retiring to a
>>>>>> known free FF; the set of FFs are right next to each other so the
>>>>>> move is trivial.
>>>>>
>>>>> This sounds like it has a belt's worth of FF for each FU.
>>>>> And some of them are shift registers?
>>>>> I'm a bit confused.
>>>>
>>>> There can be (and usually are) several FUs per slot, forming in
>>>> effect a "superFU". There is only one set of output FFs per slot,
>>>> one per latency. These are daisy chained. I suppose that you can
>>>> think of the output FF daisy as being a shift register, and it could
>>>> be done that way, but it also could be done by simply rotating which
>>>> FF is considered which latency, thereby replacing a physical data
>>>> move with a result-to-FF fanout. That's a HW design choice; IANAHWG.
>>>
>>> I thought I had at least a basic understanding of how you actually
>>> implement the belt, but Eric's post made me question that, and I
>>> don't think you addressed his exact question.
>
> Yeah, I didn't understand either. I found the patent for it (below) and
> was looking at it for insights, but I wanted to get back to something else
> I was looking at, Load-Store Queues, so I was going to get back again
> later.
>
>>> So, suppose you have exactly one add FU, and that it has a latency of
>>> 1. My understanding is that there is therefore one set of FFs at the
>>> add FU's output. Suppose the belt length is 16, though this isn't
>>> particularly critical.
>>> Now suppose you have an instruction stream with say 4-5 consecutive
>>> adds.  I understand that this may take several instructions, as you
>>> only have one add FU.  After the first add, the result is in that FUs
>>> output FFs, and has a some belt position.  After the second add,
>>> since you want the FUs output FFs to hold the result, but they still
>>> have the result from the first add, you need some place to hold the
>>> first result.  I gather this is somewhere in the spiller.  Now let's
>>> keep going to the third add.  Are there more spots in the spiller?
>>> If so, there must be some limit, although it is probably
>>> configurable.  What happens if the number of consecutive adds exceeds
>>> that limit.
>>>
>>> Anyway, I hope you can see my confusion and will clarity it.
>>
>> Looks like the confusion is the difference between FU and slot. A FU
>> is a unit of computation - an ALU or FPU for example. A slot is a unit
>> of encoding. All slots have at least one FU attached, but they can
>> (and usually do) have several. The only requirement is that decode be
>> able to supply to the slot everything that any of the attached FUs
>> needs to do for any of its supported instructions.
>
> This is still confusing to me.
> It may be because the term "latency" seems to be used two ways:
> - latency to mean slot offset slot[0], slot[1]
> - each HW FU has a latency and throughput (delay to start next operation).
>   ALU latency 1 throughput 1, int-MUL lat 4 thru 1, int-DIV lat 16 thru
> 16.

Latency is the time (in issue cycles) between issue of and instruction
and the retire ("drop") or its result or the completion of its side
effects. Mill is statically scheduled so every kind of instruction has a
tape-out-time defined latency, known to the code scheduler (specializer)
and reflected in the generated code.

FUs do not have latency; individual instructions have latency. It is
common for a FU to support a mix of instructions of different latencies.
An FPU may support a SP FADD in three cycles and a DP FMUL in five. At
issue the FU uses signals from decode to adjust what it does and the
width it does it two. At retire, the FADD will drop its result in the
lat3 slot physical FF, and the FMULL will drop to the lat5 slot physical
FF. The mapping of belt # to physical will maintain the correct belt
physical ordering for as long as the drops remain live.

>> The result FFs are per-slot, not per-FU. There is one FF per latency
>> supported by any instruction of any FU attached to that slot, and for
>> any intermediate latency that happens not to have any instructions
>> that use it. The FFs are logically chained to make a shift register,
>> although for power reasons it may use a different implementation than
>> a physical shift register.
>
> The Belt is a logical shift register - all FU's drop their results
> into slot[-1] then shift that right into slot[0].
> There is no OoO so if a slot[-1] result isn't ready the belt shift stalls.
>
> If belt is length 16, then for any mix of instructions there are
> only 16 logically valid results in this belt.
> If I have 16 adds in a row, then FU.Alu must have a
> 16 FF shift registers to hold those results.
> If there is a second Alu, then another 16 FF shift register for that.
>
> Only 16 of those slots can hold valid values, but from your
> description we'd need 32 FF and 32 xbar operand pair inputs,
> and 2 xbar FU operand pair outputs.
> If we toss in an IMUL and IDIV then 64 FF and xbar inputs,
> with 4 xbar operand pair outputs.
>
> From your description this would require the HW FF resources of a
> OoO core with 64 physical registers, but derives not of the benefit
> of producing
>
> (This is why I assumed that Belt has a second xbar to route results
> in my prior little diagram - it eliminates this slots*FU expansion.)

Your description would be true iff the FF chain were the only residence
of belt values; that's why we don't do it that way :-)

Because a slot can support instructions of a mix of latencies, only one
of which can issue in a given cycle, if the instructions are issue with
the right timing you can get more than one retiring in the same cycle.
For example, if there were lat1, lat2, and lat3 supported, and in
consecutive cycles you issued ilat3 - ilat2 - ilat1 in that order, then
the following cycle would have three retires simultaneously, and so
necessarily (at least) three result FFs.

On 1/18/2022 10:42 AM, EricP wrote:
> EricP wrote:
>> Ivan Godard wrote:
>>>
>>> To take your example of an empty belt and a string of adds:
>>> a+b+c+d+e, all latency one. Say there is only one exu slot, and it
>>> has a 1-cycle ALU, a 3-cycle multiplier, and a filler lat-2 FF even
>>> though the slot has no lat-2 instructions. The belt is assumed to be
>>> longer than 5, so no intermediate results die in the example.
>>>
>>> In the first cycle:
>>> cycle 1: (a+b)->lat1
>>> cycle 2: lat1->lat2; (a+b)+c->lat1
>>> cycle 3: lat2->lat3; lat1->lat2; (a+b+c)+d->lat1
>>> cycle 4: lat3->sX; lat2->lat3; lat1->lat2; (a+b+c+d)->lat1
>>> cycle 5: (sX); lat3->sY; lat2->lat3; lat1->lat2; (a+b+c+d+e)->lat1
>>
>> This is the easy case with HW (lat,thru) of (1,1) to slot[0:4].
>>
>> Toss in a second ALU plus (lat,thru) of an IMUL (4,1) and IDIV (16,16).
>> In each case the Belt slot inputs to those FU are all valid
>> so all launch at once but drop to different slot offsets.
>
> There are multiple things being juggled here.
> There is the (latency,throughput) of each type of FU.

Latency is per-instruction-kind, not per FU; FUs can support
instructions kinds with different latencies. This is especially common
with arguments of different widths. Mill does not promote everything to
some common "register width", but instead works like SIMD lanes and
executes in the natural width of the data. A Mill FMUL may be lat3 in w
width, lat4 in d width, and lat5 in q width. A legacy ISA may do the
same using different instructions (FMUL vs. DMUL vs ALPHABET_SOUP), but
Mill has the data encode its own width.

> There can be multiple FU of each type.
> To take advantage of Mill's wide decode we want to get
> as many concurrent, pipelined operations going at once.
> Then it orders the results as they drop onto the belt,
> and if multiple results drop at the same clock then
> some kind of predictable ordering into the belt slots
> so the compiler knows where things appear to land.

Yes

> So just to walk through an example to see if I get the basics....
>
> At time T1 we start IMUL1 which drops its result at T4.
> There are also 3 ADDs and only one FU.Alu.
> ADD1 also starts at T1, ADD2 and ADD3  at T2 and T3,
> which drop at T2, T3 and T4.

A slot can only issue one instruction per cycle, so it is not possible
for the IMUL1 and ADD1 to start in the same cycle in the same slot.

> At T2 ADD1 is finishes so goes slot[0].

Slots are encoding notions naming collections of FUs that share input
paths and output FF sets. You will get mighty confused if you use "slot"
for physical FF or for belt position number :-)

> At T3 Add2 goes to slot[0], ADD1 shifts to slot[1].
> At T4 ADD3 and IMUL1 finish at the same time, and lets say the rule is
> first to start drops first, so ADD1, ADD2 shift to slot[3], slot[2]
> and IMUL1 and ADD3 drop to slot[1] and slot[0] respectively.
>
> So we wind up with a belt like:
>
>   slot[0] slot[1] slot[2] slot[3]
>   ADD3    IMUL1   ADD2    ADD1
>
> If we had started a second concrrent, pipelined IMUL2 at T2
> the result belt looks like:
>
>   slot[0] slot[1] slot[2] slot[3] slot[4]
>   IMUL2   ADD3    IMUL1   ADD2    ADD1
>
> But in terms of FU result FF it looks like
>
>   FU.Alu  FU.IMul     XBAR
>   ADD3    IMUL2    =>------------
>   ADD2    IMUL1    =>
>   ADD1             =>------------
>                       |  |   |  |
>                       v  v   v  v
>                      FU.Alu FU.IMul

s/slot//belt#/ and it make more sense. The actual ordering (you are
right that the hardware and compiler must agree) is member specific and
more complicated to deal with things like phasing, non-FU values, and
control flow.

Ivan Godard [2022-01-18 12:36:04] wrote:
[...]
> vs. DMUL vs ALPHABET_SOUP), but Mill has the data encode its own width.

That reminds me: where (physically) is this type information kept?
It seems to be that keeping it with the data itself could be a problem
because it makes it available only rather late.
Do you try and do "type inference/propagation" in the decoder and keep
track of types there (or in the belt's logical-to-physical mapping
maybe), or is it really kept alongside the data and is hence only made
available to the next instruction when the data itself is
made available (so e.g. we don't know the latency of a MUL until we get
its operands)?

Stefan

On Tuesday, January 18, 2022 at 2:58:39 PM UTC-6, Stefan Monnier wrote:
> Ivan Godard [2022-01-18 12:36:04] wrote:
> [...]
> > vs. DMUL vs ALPHABET_SOUP), but Mill has the data encode its own width.
> That reminds me: where (physically) is this type information kept?
> It seems to be that keeping it with the data itself could be a problem
> because it makes it available only rather late.
<
This is the kind of stuff one keeps with the instruction (bits).
<
> Do you try and do "type inference/propagation" in the decoder and keep
> track of types there (or in the belt's logical-to-physical mapping
<
MILL is software scheduled, so this is all known of at compile time.
<
> maybe), or is it really kept alongside the data and is hence only made
> available to the next instruction when the data itself is
> made available (so e.g. we don't know the latency of a MUL until we get
> its operands)?
>
>
> Stefan

On 1/18/2022 12:58 PM, Stefan Monnier wrote:
> Ivan Godard [2022-01-18 12:36:04] wrote:
> [...]
>> vs. DMUL vs ALPHABET_SOUP), but Mill has the data encode its own width.
>
> That reminds me: where (physically) is this type information kept?
> It seems to be that keeping it with the data itself could be a problem
> because it makes it available only rather late.
> Do you try and do "type inference/propagation" in the decoder and keep
> track of types there (or in the belt's logical-to-physical mapping
> maybe), or is it really kept alongside the data and is hence only made
> available to the next instruction when the data itself is
> made available (so e.g. we don't know the latency of a MUL until we get
> its operands)?
>
>
> Stefan

It is both kept with the data and projected by the decoder/mapper.
Execution follows the projected width; the actual (from the data) is
matched against the expected and faults on a mismatch.

> It is both kept with the data and projected by the decoder/mapper. Execution
> follows the projected width; the actual (from the data) is matched against
> the expected and faults on a mismatch.

Hmm... how/when would such a mismatch occur?
Do you have instructions whose output width is data-dependent?
Where is it useful/used? Do you then have instructions to dynamically
test the width of some belt slot?

Dynamically typed machine language?

Stefan

On 1/18/2022 7:35 PM, Stefan Monnier wrote:
>> It is both kept with the data and projected by the decoder/mapper. Execution
>> follows the projected width; the actual (from the data) is matched against
>> the expected and faults on a mismatch.
>
> Hmm... how/when would such a mismatch occur?
> Do you have instructions whose output width is data-dependent?
> Where is it useful/used? Do you then have instructions to dynamically
> test the width of some belt slot?
>
> Dynamically typed machine language?
>
>
> Stefan

Width mismatch can arise from software (specializer bug) or hardware
(gamma ray) error, or from an attack that generates or modifies
binaries, before or after execution begins. The Mill design cares *very*
much about RAS issues and sanity-checks everything it can.

Most instructions that have results have data-dependent output widths.
Usually the result width is the same as the argument widths, but all
instructions that can overflow (including nearly all arithmetic
instructions) have a variant that produces a double-width result.
Obviously the WIDEN and NARROW instructions change the width, and there
are a few odd-balls.

The belt evaporates too quickly to do much useful with it dynamically. A
debugger or exception handler that needs to dynamically interpret a belt
can call a few nested functions to cause it to be pushed into the
spiller and thence to DRAM, where software can see the widths in the
spill-format data.

Ivan Godard [2022-01-18 20:49:16] wrote:
> Width mismatch can arise from software (specializer bug)

That would be in a case like when we add a 32bit int and a 64 bit int?
These can be detected in the decoder/mapper part, right?

> or hardware (gamma ray) error,

Sanity checks, like ECC, are good, yes.

> Most instructions that have results have data-dependent output widths.
> Usually the result width is the same as the argument widths, but all
> instructions that can overflow (including nearly all arithmetic
> instructions) have a variant that produces a double-width result.

But the width is not data-dependent, in the sense that it's only depend
on the input widths, not the input values. So the decoder/mapper can
always correctly predict the output width (and it can also correctly
predict the mismatches like adding a 32bit to a 64bit arg), it never
needs to guess, right?

IOW, when you said:

> the actual (from the data) is matched against the expected and faults
> on a mismatch.

This is only needed to detect hardware errors.

Stefan