belt architecture

[Mark Thorson]

Probably the most interesting part of the Mill
is the belt architecture. I'd like to say what
I think it is, so Ivan can correct my
misunderstandings.

1. The belt only moves when an operation puts
something on it. I think Ivan said this.

2. The writes to the belt occur between the
execution of blocks. I don't see how it could
work any other way. If the belt moves during
the execution of a block, that would open a real
can of worms (keeping track of operands, race
conditions, etc.).

3. Writes to the belt generated in one cycle go
onto the belt in an order determined by a linear
priority assigned to the writers (functional units).
That's how the compiler knows what's on the belt
and where it is.

4. Temporal addressing is just an offset from
the end of the belt. Although the offset to a
particular operand changes whenever the belt moves,
the compiler always knows the current position of
the operand, so it can plug the correct offset
into the encoding for the operation.

5. I'm guessing there are at least two belts,
one for data and one for addresses. There may
be another one for floating-point operands and
maybe others for coprocessors such as media data
(GPUish operands, like packed data structures
for pixels, audio samples, etc.). How many belts
are there?

[Ivan Godard]

On 6/5/2013 8:12 PM, Mark Thorson wrote:
> Probably the most interesting part of the Mill
> is the belt architecture. I'd like to say what
> I think it is, so Ivan can correct my
> misunderstandings.
>
> 1. The belt only moves when an operation puts
> something on it. I think Ivan said this.

Yes. The operation "retires" and "drops" its result(s) on the front of
the belt.

> 2. The writes to the belt occur between the
> execution of blocks. I don't see how it could
> work any other way. If the belt moves during
> the execution of a block, that would open a real
> can of worms (keeping track of operands, race
> conditions, etc.).

Blocks in an instruction are mere encoding devices. All the operations
of all six blocks of one instruction issue together. The operations may
differ in latency, so that an add (say) may drop a result (and advance
the belt) one cycle later, while a multiply in the same instruction (and
on the Mill encoded in the same block, although that is incidental and
irrelevant) drops its result (and advances the belt) three cycles later.
Where "one" and "three" are the per-family-member-dependent defined
latencies of the respective operations, whatever they are.

The belt advance is unrelated to the decode organization, and it is also
not directly related to when operations issue. Belt advance is
determined by when (and how many) operations retire, regardless of which
instructions those operations were in and when they issued. The Mill is
an exposed pipeline machine, like most DSPs are, and the program sees
the exact latency (time between issue and retire) of the operations.

> 3. Writes to the belt generated in one cycle go
> onto the belt in an order determined by a linear
> priority assigned to the writers (functional units).
> That's how the compiler knows what's on the belt
> and where it is.

Minor terminological quibble: in Mill terminology, a "writer" is a
particular kind of operation that takes an operand *from* the belt and
puts it somewhere, typically a special register.

I'd rephrase you as "Drops to the belt retired in one cycle go onto the
belt in an order determined by a combination of a linear priority
assigned to the functional units, the latency of the retiring operation,
and a defined order within multi-result operations. That's how the

compiler knows what's on the belt and where it is."

> 4. Temporal addressing is just an offset from
> the end of the belt. Although the offset to a
> particular operand changes whenever the belt moves,
> the compiler always knows the current position of
> the operand, so it can plug the correct offset
> into the encoding for the operation.

Exactly.

And because belt values are write-once, the whole belt is an SSA (static
single-assignment) structure and the RAW and WAR hazards that arise with
general registers are impossible. Consequently the belt needs no rename
stage and no rename registers, nor (being in order) any reorder stage or
ROBs.

Getting rid of the instruction buffers, the rename (and architectural)
registers, and the reorder buffers means that a Mill is around a quarter
the size and consumes about a quarter the power of an OOO superscalar
with the same complement of functional units.

Getting rid of the schedule, issue, retire and reorder stages means that
the Mill pipeline comprises only instruction fetch, decode, and execute,
so the mispredict penalty is five clocks when the correct path hits in
the top level iCache, six if the instruction half-bundles cross a line
boundary on either side.

> 5. I'm guessing there are at least two belts,
> one for data and one for addresses. There may
> be another one for floating-point operands and
> maybe others for coprocessors such as media data
> (GPUish operands, like packed data structures
> for pixels, audio samples, etc.). How many belts
> are there?

There is only one belt, which holds all in-flight data of all types,
kinds and sizes. The (potential) size of a belt operand is fixed for any
given family member, but will be at least eight bytes. Thus a belt
position on Tin, with an 8-byte height, may hold a scalar datum of 1, 2,
4, or 8 bytes in any position, or vectors of 8 1-byte, 4 two-byte, 2
four-byte, or 1 eight-byte elements. A Gold is 32 bytes high, so it has
all the scalars of Tin plus 16-byte (quad) scalars in hardware, plus
vectors of all scalar element widths whose cumulative length is 32 bytes.

In addition, any belt datum (and any element of a belt vector datum)
carries certain metadata as well as the raw bits. However, the filings
on the metadata and what they do are not yet in; sorry :-(

Ivan

[EricP]

Ivan Godard wrote:
>
> There is only one belt, which holds all in-flight data of all types,
> kinds and sizes. The (potential) size of a belt operand is fixed for any
> given family member, but will be at least eight bytes. Thus a belt
> position on Tin, with an 8-byte height, may hold a scalar datum of 1, 2,
> 4, or 8 bytes in any position, or vectors of 8 1-byte, 4 two-byte, 2
> four-byte, or 1 eight-byte elements. A Gold is 32 bytes high, so it has
> all the scalars of Tin plus 16-byte (quad) scalars in hardware, plus
> vectors of all scalar element widths whose cumulative length is 32 bytes.

In your talk you say that 80% of all vars are used once.
I assume that any belt value that is not used before
falling off the belt must be explicitly saved someplace,
scratch register or memory similar to a register spill.

I think you said the belt had 32 positions (or is that model dependent?).
Any idea what the average value lifespan is, relative to belt length?
That is to ask, of those read-once values, what percentage can
be consumed before falling off a 32 position belt,
verses have to be explicitly saved?

Eric

[Ivan Godard]

On 6/6/2013 9:58 AM, EricP wrote:
> Ivan Godard wrote:
>>
>> There is only one belt, which holds all in-flight data of all types,
>> kinds and sizes. The (potential) size of a belt operand is fixed for
>> any given family member, but will be at least eight bytes. Thus a belt
>> position on Tin, with an 8-byte height, may hold a scalar datum of 1,
>> 2, 4, or 8 bytes in any position, or vectors of 8 1-byte, 4 two-byte,
>> 2 four-byte, or 1 eight-byte elements. A Gold is 32 bytes high, so it
>> has all the scalars of Tin plus 16-byte (quad) scalars in hardware,
>> plus vectors of all scalar element widths whose cumulative length is
>> 32 bytes.
>
>
> In your talk you say that 80% of all vars are used once.
> I assume that any belt value that is not used before
> falling off the belt must be explicitly saved someplace,
> scratch register or memory similar to a register spill.

You have to do something about values you are about to lose but are
still wanted. Storing to memory is possible, but loses metadata attached
to the belt operands (a well known problem for x86 too). Spill to the
scratchpad retains the metadata (scratchpad is not memory).

In addition, a value can be retained on the belt without spill. Consider
what happens to the value in belt position 15 (on a 16 position belt) if
you execute "add b15, 0". The result of the add will drop to the belt,
pushing the former b15 off the end. But now b0 is a copy of the old b15.
:-)

This idea is generalized to the Mill "rescue" op, which takes a belt
argument list like the call operation, and renames the belt so that the
rescued operands are at the front of the belt.

> I think you said the belt had 32 positions (or is that model dependent?).

Model dependent.

> Any idea what the average value lifespan is, relative to belt length?

The spill-to-fill latency using the scratchpad is three cycles at our
current clock rates, so if you need a value within the next three cycles
then you need to keep it on the belt rather than run it out to
scratchpad and back. So we set the belt length to (roughly) the number
of operands that will drop in three cycles at high confidence level at
peak load.

For the rare cases where the code is dropping too many results in those
three cycles then we use rescue or similar to keep them around. The
problem is that high-drop code is usually in pipelined loops, and those
loops also tend to be slot bound so we don't want to waste any of the
encode/execute capacity on rescue ops. The alternative is to use spill
fill and wait for the extra latency, because latency is largely
irrelevant in piped loops. However, spill/fill also chew up operation
slots, so you are not really that much better off.

Complicating configuration definition is that the belt length really
wants to be a power-of-two for encoding reasons, whereas drop rate is a
much smoother function of the number of functional units. As one
increases the number of FUs, the drop rate increases until it bumps so
hard against the belt length that rescue is common and you have to add
slots to make sure you can do all the work you want and a rescue too.

Eventually with increasing FUs you have to bump up the belt length, and
suddenly rescue becomes almost unknown again. This step-function in
constraint is exactly the same problem that designers of
general-register legacy ISAs have to deal with when they are deciding
the number of register to use. At least in our case we don't have a hard
number of bits that we have to encode three register numbers into :-)

> That is to ask, of those read-once values, what percentage can
> be consumed before falling off a 32 position belt,
> verses have to be explicitly saved?

The code generator schedules operations in data-flow order so the
producers and consumers are close to each other in time, and hence in
belt distance. As a practical matter, transient values (one use) almost
never spill; belt is cheap, so we just make it long enough to ensure this.

In addition, program non-loop frame-local scalar variables with multiple
references are allocated in the scratchpad and not on the stack and so
are spilled for later use anyway. As a result they have multiple lives
on the belt: once when first created, and again each time they are
re-filled from scratchpad. As a rule of thumb, half of all references to
such data will be satisfied from the belt without re-filling; i.e. each
lifetime satisfies two references average.

Lastly, loop-carried variables (iteration variables and recurrences) can
be numerous enough that they get pushed off the belt by transient
results before they are updated by the next iteration. Think of code like:
for(int i = 0; i < N; i++)
sum += A[i] + B[i] + C[i];
Here sum is a recurrence and i is an iteration variable. Each gets a new
value in each iteration and so both live in the belt throughout the
loop; they have neither memory nor scratchpad presence.

However, the array references and the add results are transients, which
must also co-exist with sum and i on the belt. If the computation
generates enough transients, sum and i may be off the end of the belt
before the next iteration. You don't want to run the recurrence out to
scratchpad, because the loop is banging one iteration every cycle and
the spill-to-fill latency is three, which would wast a lot of cycles. So
you use rescue on sum and i in every iteration, to lift them out of the
belt rubble of other computation. This is essentially the only place
where you see rescue with any frequency at all.

All this is rules of thumb and guidelines for configuration. We expect
to see a rescue op in complicated piped loops, but I've never seen a
loop with so many recurrence variables that it needs more belt than one
rescue per iteration provides. We expect to spill/fill open-code scalar
locals that have long lifetimes and many references. Other than that, a
spill rate over 1% I would consider cause for reconfiguring to fewer FUs
or more belt.

Ivan