Mill encoding presentation at Stanford 5/29 and online

[Ivan Godard]

Stanford EE Computer Systems Colloquium
4:15PM, Wednesday, May 29, 2013
Skilling Auditorium, Stanford Campus
http://ee380.stanford.edu

Drinking from the firehose
How the Mill CPU decodes 30+ instructions per cycle

Ivan Godard
Out-of-the-Box Computing

About the talk:

The military maxim "amateurs study tactics, professionals study
logistics" applies to CPU architecture as well as to armies. Less than
10% of the area and power budget of modern high-end cores is devoted to
real work by the functional units such as adders; the other 90%
marshalls instructions and data for those units and figures out what to
do next.

A large fraction of this logistic overhead comes from instruction fetch
and decode. Instruction encoding has subtle and far reaching effects on
performance and efficiency throughout a core; for example, the
intractable encoding used by x86 instructions is why the x86 will never
provide the performance/power of other architectures having friendlier
encoding.

Some 80% of executed operations are in loops. A software-pipelined loop
has instruction-level parallelism (ILP) bounded only by the number of
functional units available and the ability to feed them. The limiting
factor is often decode; few modern cores can decode more than four
instructions per cycle, and none more than 10. The Mill is a new
general-purpose CPU architecture that breaks this barrier; high-end Mill
family members can fetch, decode, issue and execute over 30 instructions
per cycle.

This talk explains the fetch and decode part of the Mill architecture.

Slides:

There is no downloadable version of the slides for this talk available
at this time.

About the speaker:

Ivan Godard has designed, implemented or led the teams for 11 compilers
for a variety of languages and targets, an operating system, an
object-oriented database, and four instruction set architectures. He
participated in the revision of Algol68 and is mentioned in its Report;
was on the Green team that won the Ada language competition; designed
the Mary family of system implementation languages; and was founding
editor of the Machine Oriented Languages Bulletin. He is a Member
Emeritus of IFIPS Working Group 2.4 (Implementation languages), and was
a member of the committee that produced the IEEE and ISO floating-point
standard 754-2011.

Ivan is currently CTO at Out-of-theBox Computing, a startup now emerging
from stealth mode. OOTBC has developed the Mill, a clean-sheet rethink
of general-purpose CPU architectures. The Mill is the subject of his
talk today.

Contact information:

Ivan Godard
Out-of-the-Box Computing
iv...@ootbcomp.com

ABOUT THE COLLOQUIUM:

See the Colloquium website, http://ee380.stanford.edu, for scheduled
speakers, FAQ, and additional information. Stanford and SCPD students
can enroll in EE380 for one unit of credit. Anyone is welcome to attend;
talks are webcast live and archived for on-demand viewing over the web.

WHERE IN THE WORLD IS SKILLING AUDITORIUM:

The Colloquium meets in Skilling Auditorium on the Stanford Campus. For
a map showing the location of Skilling Auditorium and recommended
parking, see http://ee380.stanford.edu/Skilling-Map.png. Parking
restrictions is free and unrestricted in most lots after 4PM.

MAILING LIST INFORMATION:

This announcement is sent to multiple mailing lists. If you are signed
up on our private EE380 list you can remove yourself using the widget at
the upper left hand corner of the Colloquium web page. Other lists have
other management protocols.

[EricP]

Ivan Godard wrote:
>
> Stanford EE Computer Systems Colloquium
> 4:15PM, Wednesday, May 29, 2013
> Skilling Auditorium, Stanford Campus
> http://ee380.stanford.edu
>
> Drinking from the firehose
> How the Mill CPU decodes 30+ instructions per cycle
>
> Ivan Godard
> Out-of-the-Box Computing

I missed the talk. If anyone notices it up on
http://www.youtube.com/stanford can you give a shout.

Thanks
Eric

[thomas....@gmail.com]

>
>
> I missed the talk. If anyone notices it up on
>
> http://www.youtube.com/stanford can you give a shout.
>
>

You can watch it here:
http://ee380.stanford.edu/cgi-bin/videologger.php?target=130529-ee380-300.asx

I found it very interesting.

Regards,

Thomas

[Ivan Godard]

Thank you :-)

There will be another talk on the Mill at ee380 next fall, probably
October, and probably on our branch prediction tech. You can sign up for
email announcements of such events at ootbcomp.com

Ivan

[John D. McCalpin]

On Friday, May 31, 2013 11:35:10 AM UTC-5, Ivan Godard wrote:

Thanks for posting the link to the video!

If a stack architecture is based on references to a LIFO queue structure, it sounds like "belt" on the Mill is a bit closer to a FIFO queue structure?

My understanding of modern processors cores is that the register file bypass network is often a serious problem with timing and is usually the biggest consumer of power. If the "belt" allows all the functional units to access all of the locations on the belt, don't you have much the same problem with physics?

john

[EricP]

Oh... windows media player... <grumble> open firewall...
<gumble> wont let me save the file for later...

yes... very interesting.

thanks
Eric

[EricP]

Yes, very interesting. Looking forward to next talk.
(I'd like to hear more details about CALL.)
Question...

There are the two bundle streams X (moves forward) and F (moves backward).
Then at time index 28:20, you start talking about half bundles.
Are (a) the half bundles coming from the two half iCaches,
or are (b) the two streams, X & F, coming from the two iCaches?
If (b) then what are the half bundles?


Eric

[Ivan Godard]

On 5/31/2013 11:19 AM, John D. McCalpin wrote:

>
> Thanks for posting the link to the video!
>
> If a stack architecture is based on references to a LIFO queue
structure, it sounds like "belt" on the Mill is a bit closer to a

FIFO queue structure?

The programming model is logically random-access fixed-length FIFO,
although physically it is very different. Alternatively, and perhaps
conceptually closer, you can think of it as a collection of independent
but interleaved stack machines with non-destructive random read. None of
this quite catches the essence and implications though, so a belt
machine is really a new category of machine model. The Mill is certainly
not the only design point within the belt machine category, but it is
the first.

>
> My understanding of modern processors cores is that the register
file bypass network is often a serious problem with timing and
is usually the biggest consumer of power. If the "belt" allows
all the functional units to access all of the locations on the
belt, don't you have much the same problem with physics?
>
> john
>

The data interconnect is indeed the limiting factor for increased
functional width, regardless of machine model; a naive bypass crossbar
increases as N squared, and you can't scale that for long. That's (one
of the reasons) why legacy architectures max out around eight slots
(execute pipelines), both superscalars and VLIWs. We found decode to be
the bigger pinch when we were doing the design, but we had to be just as
radical on the data side to to be able to handle 30-way MIMD.

There will be slides and white papers on this available, sign up for the
mailing list at http://ootbcomp.com.

Here's the details:

Terminology: an operation is an individual add, store, shift etc. An
instruction is the group of operations that semantically must issue
together. Instruction == operation on x86/RISC, but not on VLIW or Mill.
A bundle is the physical unit of decode. Bundle ==
operation==instruction on x86/RISC, bundle == instruction on VLIW/Mill,
but bundle != instruction on an Itanium.

Now, your question. Not all of those 33 ops take belt arguments, and of
those that do some take more (store) and some fewer (wr). The number of
argument belt ports (data sinks) is fixed by slot; while you can
populate an op taking fewer arguments into a slot, you can't configure
an op that needs more arguments than its slot supports. Consequently the
total number of ports does not equal (except by happenstance) the number
of issuable ops. Tin, our smallest configuration, uses eight sink ports;
that Gold in the presentation, as currently configured uses 36 if I'm
counting right, though that will almost certainly get tuned down some
(along with the op count). At a guess it will wind up ~28 ops per issue
peak and ~32 argument ports,.

The number of result ports (sources) is different from the number of
argument ports. This too is by slot as configured for each family
member, and is sigma(# of result latencies X # of results of that
latency) across all the slots. Some slots have no results; some
latencies in some slots have no results. The only ops with more than two
results are call and return, and those uses a special rename mechanism
rather than the kind of result paths that say add does, so (currently)
no slot latency has more than two results, although the model supports
that. There are also non-operation sources, so the actual source count,
while determined, is complicated to figure. Tin has nine sources and
Gold around 40, roughly.

The operand distribution crossbar that is behind the belt machine model
has to be able to let any source feed any or all sinks, so each source
feeds a mux tree for each sink, and each sink is fed by a mux tree from
each source. However, it is not implemented as a full crossbar, because
that has too much of a hit on the clock rate. Instead, the crossbar is a
two-stage network, and some sources are more equal than others. There is
a true full crossbar only for latency-one sources, which as a practical
matter means the ALUs. The full crossbar also has two additional
full-width sources and one one-bit source; these are staging sources
from all the other non-latency-one sources. On Tin there is one lat-1
source, so the full crossbar on Tin is thus 3->8 (ignoring the one-bit
tree), and Gold is 10->36, which is tolerable even at Nsquared.

This full crossbar (and the 32-bit add time that feeds it) determines
our clock rate, and, as always, the number of sources determines the
height of the crossbar trees and hence the transit time, so we are very
careful about lat-1 sources; number of sinks impacts only power and area
and not clock (except as a secondary effect from wire congestion), so we
are willing to be more spendthrift with those. Logically the lat-1
crossbar runs at the clock boundary, so any lat-1 op (an add, say) can
feed any other op (including lat-1 ops) in the very next cycle; our
add-to-add data-dependent bypass delay is zero clocks.

The staging crossbar feeds those two staging ports in the full crossbar,
from all the non-lat-1 sources. The staging crossbar runs in the prior
cycle to the lat-1 crossbar, stealing gate levels from the last stage of
each lat-2+ functional unit. There's the usual shoehorning to get
everything to fit in minimal clocks. So a high-latency op like a
multiply completes the operation and passes the results through the
staging crossbar in the last execute cycle, such that they are available
in the staging input of the lat-1 crossbar at the same point as a direct
lat-1 source like an ALU add. On Tin the staging crossbar is 8->2*9, and
on Gold it is (around) 32->2*26. That last is a huge number, but it is
by definition not on the critical path. We can also split the staging
crossbar the way the TI VLIWs do; whether that pays depends on the
configuration and the process (chiefly the mux standard cell) involved.

The cascaded crossbars appear to be the limiting factor for scaling up
the number of slots (and hence the number of concurrent issuing ops) on
a Mill. Our current best guess is that diminishing returns sets in
slightly above a Gold width configuration (the MIMD dimension).
Separately we can increase the vector height of each operand (the SIMD
dimension). Tin is 8 bytes high, the smallest possible. Gold is 16 bytes
high because Gold is not intended to be a HPC chip (HPC likes bigger
vectors). It's even more unclear where diminishing returns sets in with
height, being limited more in the memory datapaths than the core, but
certainly 32 bytes and maybe 64 bytes is possible with current packaging
and memory tech. It does not appear that we are ever limited by TDP in
one core even at maximum width and height, so TDP and the dark silicon
problem only comes into the number of cores configured on a chip.

Back when we started the Mill there was only a full crossbar, but that
was getting ridiculous real fast when scaling the configurations. Then
Art invented the staged crossbar, which moved the bottleneck somewhere
else. There's actually some more going on in the crossbars besides
operand distribution, but the filings for that aren't in yet.

Although it's definitely not my expertise, I am amazed at the scale of
the operand distribution networks in the OOO chips. Granted they have
many fewer sinks than we have, and they probably only bypass within a
single pipeline (or maybe take an extra cycle to cross pipes). But they
have several hundred rename registers for sources, and I'd guess there
are bypasses from all those load buffers too. Getting all that at high
clock, no wonder they have such long pipelines.

We go for width and throughput rather than speed, giving us a very short
pipe and much smaller mispredict sensitivity, but a lower clock. It's
real clear that our throughput is very much higher than legacy chips so
long as you can use the width; we are like a VLIW in that. A legacy chip
is much closer to competitive in open code with low ILP where all our
width buys nothing. However, in that kind of code the determining
factors are in the memory hierarchy and prediction, and we have quite a
few advantages there, too, so we're not really concerned. Of course,
both Mill and legacy are going to wait the same delay on a LLC miss.

One reason for splitting the bypass by latency was because we discovered
that high-latency operations are heavily biased toward
throughput-oriented applications, and latency-oriented applications tend
to be heavily latency-one ops (i.e. the ALUs, branches and load/store).
Even on Gold the apps that want fast (and hence are not doing FP or
multiplies or vector shuffle or ...) are only seeing a 10-to-one mux
tree in the data interconnect for the operations they actually use,
which is less than the bypass on a legacy chip.

In contrast, the apps that use FP and other long-latency operations are
throughput oriented and all the operations are in software-pipelined
loops. Yes, the staging crossbar can easily eat half a cycle on larger
Mill configurations, but that may (for example) raise an inherently
four-cycle op to five-cycles, or may be free if the four-cycle op is
really 3.5 cycles. Either way, the piped loop doesn't care what the op
latencies are, it only cares about the issue rate, and in a piped loop
we are a MIMD firehose.

This has been a much more complete explanation than you might have been
looking for; please ask for more if I left anything out.

Ivan

[Ivan Godard]

On 5/31/2013 11:55 AM, EricP wrote:

> Yes, very interesting. Looking forward to next talk.
> (I'd like to hear more details about CALL.)

The call operation takes an effective address (two modes: offset from
current EBB, and function pointer), and argument list of the positions
of arguments on the belt, and a result count. One cycle later (one issue
cycle always, and one physical cycle if prediction is doing its job) the
first instruction of the called function executes in a new belt that is
empty except for the formal parameters, i.e. the passed arguments. There
is no prologue, no state save, no nothing.

The return op takes an argument list, whose length must match the result
count given with the corresponding call. One cycle later the rest of the
instruction containing the call is executed (or the following
instruction if that was the last operation in the calling instruction),
in a belt environment identical to that immediately before the call
except with the actual results of the call, if any, pushed onto the
front of the belt and the same number of trailing belt operands pushed
off the end.

The Mill also supports cascaded calls, with more than one call operation
in a single instruction. These are executed in sequence in encoding
order, each seeing the result of the previous one. In cascaded calls,
the return of the first goes directly into the first instruction of the
second, without returning to the point of call in between. Consequently,
a = f(b + c, g(x+y)); is one Mill instruction on any member with two or
more adders.

> Question...
>
> There are the two bundle streams X (moves forward) and F (moves backward).
> Then at time index 28:20, you start talking about half bundles.
> Are (a) the half bundles coming from the two half iCaches,
> or are (b) the two streams, X & F, coming from the two iCaches?
> If (b) then what are the half bundles?
>
>
> Eric
>

I'm not sure that the camera kept up with the slides. Conceptually we
start with a stream of bundles, and then split each bundle in half while
collecting corresponding halves so we have two streams of half bundles.
Each stream of halves has its own decoder and iCache, which you can
think of as half-decoders and half-iCaches, except that the caches can
be as big as a single cache without penalty, which doubles the total
byte capacity.

The patent of course covers many uses of the split stream technique that
we don't ourselves use. In the Mill, the exe stream half-bundles encode
all the usual computation operations, the adds and shifts and so on; the
pure sources such as fill from scratchpad and read of specRegs like the
RTC; the pure sinks like spill to scratchpad and write to specReg; and
the triadic select operation. The flow stream half-bundles encode all
the control flow and memory reference operations; large constants (to
128 bits); some belt management ops; resource allocators like alloca;
and some odds and ends.

The two sides use different intra-bundle encoding. The exu bundle
contains three blocks, isolated from both ends of the bundle as
described in the presentation. Each block contains whole operations,
where the bit encoding length of all operations in the block is the
same. The assignment of operations to blocks is partly driven by
compactness issues - the operation size in a block must be as big as the
biggest intrinsic size of any of its operations, while you don't want to
waste bits for operations that are not intrinsically that big. You also
want all the ops of a given block to use the same or very similar
encoding formats, for simpler decode.

However, the most important driver for exu is when the decoded signals
are needed. Exu block 1 has all the pure source ops that do not require
belt arguments; this includes certain literal constants; fills from
scratchpad; and non-memory data fetches such as specReg reads. These
need as much time as possible to get the data available for the ops like
add in the rest of the instruction, so we put them in block 1 which is
fully decoded by the end of the D0 stage.

On the flow side there are also three blocks, though that is
coincidence. Only block 1 has actual operations; blocks 2 and 3 contain
arguments for those operations. Block 2 holds 0, 1, 2, or 3 morsels for
each of the ops in block 1; a morsel is a member-dependent number of
bits sufficient to hold a belt position number, and most of the argument
morsels are in fact belt numbers, although some are small literals,
width and scalarity indicators, and other info that fits in a morsel.
Flow block 3 holds 0, 1, 2, or 4 bytes of manifest constant for each of
the ops in block 1.

As an example, a store op (block 1) might have (block 2) a morsel for
the address base, a morsel for the index from the belt, a morsel for the
value to store from the belt, and two bytes of manifest offset (block
3). Each block 1 op has 2-bit fields saying how many block 2 morsels and
block 3 constants belong to it, and the decoder unpacks all that and
turns the operation into a canonical form with the opcode, three
morsels, and four bytes for later processing. This encoding keeps
average operation bit length low while still accommodating complex
addressing modes that need a lot more bits, but only when they are used.

Ivan

[Bill Findlay]

On 31/05/2013 19:19, in article
292ba508-c065-4276...@googlegroups.com, "John D. McCalpin"

<mcca...@tacc.utexas.edu> wrote:

> On Friday, May 31, 2013 11:35:10 AM UTC-5, Ivan Godard wrote:
>> On 5/31/2013 4:39 AM, Thomas Entner wrote:
>>
>>>
>>
>>>>
>>
>>>>
>>
>>>> I missed the talk. If anyone notices it up on
>>
>>>>
>>
>>>> http://www.youtube.com/stanford can you give a shout.
>>
>>>>
>>
>>>>
>>
>>>
>>
>>> You can watch it here:
>>
>>>
http://ee380.stanford.edu/cgi-bin/videologger.php?target=130529-ee380-300.asx

Am I the only one for whom this is a silent movie?

--
Bill Findlay
with blueyonder.co.uk;
use surname & forename;

[Quadibloc]

On May 24, 7:58 pm, Ivan Godard <i...@ootbcomp.com> wrote:

> How the Mill CPU decodes 30+ instructions per cycle

Oh, dear. If you need to do that, it kind of forces you to have
instructions all the same length, because otherwise instruction
decoding ultimately depends on the decoding of previous instructions.

But, wait, there is one hope: one can have multiple threads, and then
the limit is one instruction per cycle per thread.

John Savard

[Ivan Godard]

Did you perhaps not watch the video?

Ivan

[Quadibloc]

On Jun 1, 2:53 am, Ivan Godard <i...@ootbcomp.com> wrote:

> Did you perhaps not watch the video?

I haven't watched it yet. And I seem to be encountering some sort of
technical issues in viewing it as well.

I simply assumed because of the popularity of RISC architectures, that
one problem I saw as intractable - although I should have noted that
using a flag bit to indicate where instructions begin or end, like the
1401 did, would have solved the problem - likely was avoided.

John Savard

[Ivan Godard]

Some people with Macs are reporting audio trouble when trying to access
the video: you should have the latest version of Flip4Mac
(http://www.telestream.net/flip4mac/overview.htm). Windows Media Player
seems to be working fine.


The real stream is here:
http://lang.stanford.edu/courses/ee380/130529/130529-ee380-500.wmv;
connecting directly may help.

Ivan

[Ivan Godard]

Some people with Macs are reporting audio trouble: you should have the

[Robert Swindells]

On Sat, 01 Jun 2013 20:45:14 -0700, Ivan Godard wrote:

> The real stream is here:
> http://lang.stanford.edu/courses/ee380/130529/130529-ee380-500.wmv;
> connecting directly may help.

Trying to download that URL (without the semicolon) just gives me a 185
byte file containing this:

[Reference]
Ref1=http://lang.stanford.edu/courses/ee380/130529/130529-ee380-500.wmv?
MSWMExt=.asf
Ref2=http://192.168.10.101:80/courses/ee380/130529/130529-ee380-500.wmv?
MSWMExt=.asf
r

[Ivan Godard]

Odd. On my machine Windows Media Player will play it fine directly, but
won't play the download either. I'll see if Stanford's copyright policy
will let us co-host the file on our site.

Ivan

[Bill Findlay]

On 02/06/2013 04:44, in article koeesd$g4b$1...@dont-email.me, "Ivan Godard"

<iv...@ootbcomp.com> wrote:

> Some people with Macs are reporting audio trouble when trying to access
> the video: you should have the latest version of Flip4Mac
> (http://www.telestream.net/flip4mac/overview.htm). Windows Media Player
> seems to be working fine.
>
>
> The real stream is here:
> http://lang.stanford.edu/courses/ee380/130529/130529-ee380-500.wmv;
> connecting directly may help.

Thanks, Ivan. A new Flip4Mac does the trick for me on Mountain Lion.

[Quadibloc]

Even removing the semicolon from the end of

http://lang.stanford.edu/courses/ee380/130529/130529-ee380-500.wmv

did not help. Even though I'm using a Windows machine. But it is
attempting to display the video using VLC, _not_ Windows Media Player.

John Savard

[Quadibloc]

On Jun 2, 2:56 am, Robert Swindells <r...@fdy2.co.uk> wrote:

> Trying to download that URL (without the semicolon) just gives me a 185
> byte file containing this:

In that case, maybe the URL

http://lang.stanford.edu/courses/ee380/130529/130529-ee380-500.wmv?MSWMExt=.asf

will work better. Or not, as it may not like direct use.

John Savard

[Quadibloc]

I put the URL into IE; that launched WMP, and it works.

John Savard

[Quadibloc]

This is certainly a novel and original design.

Since instructions are issued in bundles that execute simultaneously,
they can be ordered by length, and a prefix field identifies how many
of each length you have; that allows a variable length to be handled
almost as well as a fixed length.

Since even with the prefix field, you still have a polynomial-time
problem (although one that isn't that slow to handle), you split the
instruction stream into two halves - by functional type - and yet
avoid having jumps with two addresses by going off in both directions
from the unique entry point of each extended basic block you branch
to!

Perhaps it's unfair to so characterize it, but one oversimplified way
to describe this design might be as the Itanium "done right" - with
creative thinking and new ideas.

John Savard

[Quadibloc]

Also:

While I didn't continue to listen to the whole question period, the
response to the first question could be improved.

Samsung doesn't need to make a new type of memory chip, because while
we normally think of memory locations as lying along a one-dimensional
line, the space in which memory locations are placed can easily be
thought of as having as many dimensions as there are bits in the
address.

So all you really have to do is increment your program counter funny.
And then branch and run off in four directions at once:

addr = (H,L) -> (H+1,L), (H-1, L), (H, L-1), (H, L+1)

The real reason you wouldn't want to do this is then your instruction
stream would not fit well into L2 cache. Also, plus signs don't fit on
a 2-D sheet with no space left over the way line segments fit on a
line with no space left over.

John Savard

[EricP]

Ivan Godard wrote:
> On 5/31/2013 11:55 AM, EricP wrote:
>
>> Yes, very interesting. Looking forward to next talk.
>> (I'd like to hear more details about CALL.)
>
> The call operation takes an effective address (two modes: offset from
> current EBB, and function pointer), and argument list of the positions
> of arguments on the belt, and a result count. One cycle later (one issue
> cycle always, and one physical cycle if prediction is doing its job) the
> first instruction of the called function executes in a new belt that is
> empty except for the formal parameters, i.e. the passed arguments. There
> is no prologue, no state save, no nothing.

Ok, you give CALL an arg (a gather) list, but anything pass-by-value
must be copied before the first instruction of the callee,
otherwise you would change the semantics of the call.
Also args can be pass-by-value objects like arbitrary sized structs.

That can't all be copied in 1 cycle.

Also some languages like Ada has specific rules about argument
copy-in, copy-back which must be done in prologue & epilogue.

> The return op takes an argument list, whose length must match the result
> count given with the corresponding call. One cycle later the rest of the
> instruction containing the call is executed (or the following
> instruction if that was the last operation in the calling instruction),
> in a belt environment identical to that immediately before the call
> except with the actual results of the call, if any, pushed onto the
> front of the belt and the same number of trailing belt operands pushed
> off the end.

What about languages like Ada which allow
variable, run-time sized function values
(i.e. the function decides how big its return value will be)?

Eric

[MitchAlsup]

On Sunday, June 2, 2013 11:11:08 AM UTC-5, EricP wrote:
> Ok, you give CALL an arg (a gather) list, but anything pass-by-value
> must be copied before the first instruction of the callee,
> otherwise you would change the semantics of the call.
> Also args can be pass-by-value objects like arbitrary sized structs.

> That can't all be copied in 1 cycle.

I, personaly, can see all of them being coppied--after all the machine does
have the ability to do 30-odd MOVEs per clock--that overs the very vast
majority of parameter passing. Make Call a 2 cycle operation, the first
cycle it executes with other instructions, the second cycle it translates
the gather list into move operations. Presto, moves galore.

> Also some languages like Ada has specific rules about argument
> copy-in, copy-back which must be done in prologue & epilogue.

Consider result passing <backs>:: Epilog is a very wide gather move of
the Outs (and INOuts) to the front of the belt, again. Then the useage
on the calling side is use them or loose them.

Note: I'm guessing here, completely guessing.

Mitch

[Ivan Godard]

An excellent summary.

Thank you especially for the comparison with the Itanium. In many ways
Bob Rao and his team shared motivations with our Mill team - an emphasis
on software pipelining and speculation and a dislike of OOO, for
examples. If Rao had had a relatively uninterrupted decade to rethink
what a CPU actually is, and hadn't had Intel and HP management and
marketing on his back, he might well have come up with something more
like a Mill than an Itanium. Unfortunately, he didn't live long enough
to get a second chance. We also have the advantage of thirty years of
Moore's Law; many issues he had to worry about are only history for us.

We chose encoding as the start for our splash of the architecture
because encoding is relatively free-standing and our advances are
accessible without understanding the rest of the machine. I have my work
cut out for me in future presentations - the rest of the Mill is both
more novel than our encoding, and doesn't isolate into pieces well.

The next talk is at USENIX Vail, June 23-26, and will be about the Belt
and the internal operation-to-operation dataflow. We will get a video of
that up shortly thereafter, either taken at USENIX or a redo for the camera.

Ivan

[Ivan Godard]

On 6/2/2013 9:11 AM, EricP wrote:
> Ivan Godard wrote:
>> On 5/31/2013 11:55 AM, EricP wrote:
>>
>>> Yes, very interesting. Looking forward to next talk.
>>> (I'd like to hear more details about CALL.)
>>
>> The call operation takes an effective address (two modes: offset from
>> current EBB, and function pointer), and argument list of the positions
>> of arguments on the belt, and a result count. One cycle later (one
>> issue cycle always, and one physical cycle if prediction is doing its
>> job) the first instruction of the called function executes in a new
>> belt that is empty except for the formal parameters, i.e. the passed
>> arguments. There is no prologue, no state save, no nothing.
>
> Ok, you give CALL an arg (a gather) list, but anything pass-by-value
> must be copied before the first instruction of the callee,
> otherwise you would change the semantics of the call.

The semantics are pass-by-value. At this scale, the Mill is a Static
Single-Assignment machine (like SSA form inside a compiler) and there
are no destructive updates. You can't change a value in a register
because there are no registers.

> Also args can be pass-by-value objects like arbitrary sized structs.

The discussion refers to the kind of arguments that are passed in
registers on a legacy machine; we pass them on the belt instead. Large
objects on the Mill are passed by (implicit) reference, just like
legacies do. The reference pointer itself is passed on the belt, of
course. Also like legacies, we pass in memory any excess arguments
beyond what fit in the belt, with the usual semantics; the same for VARARGS.

> That can't all be copied in 1 cycle.

That's true. That's why there is no copying - at all. And yes, we do it
in one cycle for a correctly predicted local call. Mispredict has the
usual penalty, and calls across protection boundaries add two memory
references (probably in cache) additional.

> Also some languages like Ada has specific rules about argument
> copy-in, copy-back which must be done in prologue & epilogue.

All languages define their rules "as if"; the implementation is
permitted to do anything it wants so long as the program cannot see the
difference. In effect, the Mill has copy-in-copy-out semantics for all
(short) arguments and results, but we skip the copy-out step for
in-arguments and the copy-in step for results.

No actual copy takes place in the call itself, and the result (or
copy-out) appears on the belt in the same way that the result of a
native machine operation like an add does. The caller can then use it
immediately in further computation, store it in some data structure, or
set it aside for later reuse, just as it could for an add result.

Incidentally, I was on the Honeywell/CII "Green" team that won the Ada
context.

>> The return op takes an argument list, whose length must match the
>> result count given with the corresponding call. One cycle later the
>> rest of the instruction containing the call is executed (or the
>> following instruction if that was the last operation in the calling
>> instruction), in a belt environment identical to that immediately
>> before the call except with the actual results of the call, if any,
>> pushed onto the front of the belt and the same number of trailing belt
>> operands pushed off the end.
>
> What about languages like Ada which allow
> variable, run-time sized function values
> (i.e. the function decides how big its return value will be)?

Unless they have added something more to Ada since I last looked (quite
possible), Ada does not dynamically change the size of a scalar type.
Consequently the two ways by which a variable-sized object can be
returned is through what in C would be a union, and via variable-length
arrays.

In the case of a union, if the maximum size of the object is small then
it can be returned on the belt, just as it could be returned in a
register on a legacy machine. Whether the compiler defines an ABI that
uses that possibility is up to it. Larger unions are passed/returned by
implicit reference, using a temporary if by value; this is exactly the
same as what a legacy machine does and the Mill is no different.

Similarly, returning a variable-length array involves actually returning
a buffer by descriptor, where the buffer contains the actual data.
Legacies use different strategies for this case: the buffer may be
maximally allocated by the caller and the callee merely returns the
descriptor; the buffer may be allocated on the heap by the callee who
returns the descriptor; the callee may allocate the buffer on the
callee's stack, which the caller must then move someplace else before
doing another call; or you can have a push-me-pull-you stack in which
all results appear on the caller's stack while the callee is running.

On a Mill the language ABI does not have all these choices. We looked at
but ultimately did not choose to implement a pushmepullyou stack because
we felt we had a better use for the other side of the stacklet (its used
for the control and spiller stack). The gain from the pushmepullyou
stack in languages that could benefit was more than outweighed by
doubling the page load for transient stacklets for all languages.

We also do not let the caller return data in the vacated frame. The Mill
protection system does not let a caller browse in a callee's frame; this
is both an anti-bug and anti-exploit measure.

All other variable-length return protocols should work exactly the same
on a Mill as they do on an x86, PowerPC, or whatever.

Ivan

[Ivan Godard]

Good guess, but it's even simpler than that. Like all belt manipulation
on a Mill, there are no moves. It is all renames. Call (and return, and
conform, and cycle boundaries between ordinary instructions) broadcast
renames for the whole belt.

For the typical mid-range Mill with a 16-position belt, that means we
are broadcasting four bits to each of 20-odd places. That is much
cheaper than moving 20 operands each of which may be 128 bits long. Much
much cheaper.

I very much like your description of results/out parameters as "use them
or lose them". With your permission I will start using the phrase in our
descriptive material, in lieu of our present klunky description. Very apt.

And FWIW, the Mill has no move operation. It has no registers to update,
so there's no need for a move.

Also, while a Gold (say) can do 30 ops/clock peak, it can't do 30 of a
single operation type per clock; the 30 counts the mix of available
functional units and what they can do.

For example, Gold has only 8 ALUs, so you can't do more than eight total
add/sub/shift/gtr/etc. in one clock. It also has only five reader pipes,
so you can't pull more than five operands from scratchpad, special
registers, or popCons, total. And so on. Configuring a Mill family
member is an exercise in trading off hardware cost vs. expected
application operation mix, and even in software pipelines that have
maxed out one FU category you will always have other FUs idle because
the loop doesn't use them.

There's nothing architecturally that prevents you from configuring a
Mill family member with say 30 ALUs, and that member could then do 30
adds per clock. Whether such a Mill would be cost effective is an
application, fab process, and marketing issue, not an architectural one.

Ivan

[Ivan Godard]

True; I'd never considered the possibility. Though I think that you'd
still need to get Samsung involved, because the chip wants to stay in an
open reading frame and your plus signs would tend to muck that up.

Ivan

[Quadibloc]

On Jun 2, 12:02 pm, Ivan Godard <i...@ootbcomp.com> wrote:
> I have my work
> cut out for me in future presentations - the rest of the Mill is both
> more novel than our encoding, and doesn't isolate into pieces well.

Somehow this doesn't surprise me.

That the Belt is sort of like dataflow, I anticipated from the talk.

Incidentally, though, there is one thing that occurred to me upon
reflection. It seems to me that, given the format of your instruction
bundles, the N in which decoding time is polynomial would be *the
number of different instruction lengths* rather than the number of
operations in a bundle. In that case, this going off in two directions
from a branch point would not actually buy you any efficiencies in
decoding (although it could do wonders in other, more conventional,
instruction formats).

John Savard

[Ivan Godard]

If we, like x86, permitted random ordering of different length
operations then N would be total number of operations. Because we impose
bundle-level ordering constraints, we have changed N from operation
count (~30) to operation-length count (~6).

Independently, going in two directions cuts N to N/2, whether
bundle-level encoding is used or not. Combined, we have cut
variable-length encoding N from ~30 to ~3, which is tractable as Intel
demonstrates.

Doubling the iCache capacity is an extra freebie :-)

The cost is the header with its length fields, or, on the flow side, the
equivalent length indicators in the ops. When using the "fat format" in
the presentation, we are ahead on any bundle with two or more ops
because the ops are shorter than in a one-size-fits-all encoding.

There is a special encoding, not described in the talk, for bundles with
exactly one operation ("svelt format"), that omits the header. There is
also a special encoding ("skinny format") for a few selected bundles of
arbitrary format; skinny is simply macro-replaced by the corresponding
fat format bundle in the decoder. Thus "belt position 0 + 1", "return",
and "belt position 0 == 0" are one-byte bundles, where the corresponding
svelte would be two or three bytes (on representative members) and fat
would be four. This helps in open code outside of loops, in which data
dependencies can cut your ILP to one, on one side or the other.

Of course, the Mill has a bundle size of zero when the ILP is reduced to
zero, using the no-op encoding as described in the talk. I know of no
other machine for which the smallest encodable instruction occupies zero
bits.

You can never have enough iCache, and the best iCache is the iCache
that's free because you have a compact encoding.

Ivan

[Quadibloc]

On Jun 2, 3:18 pm, Ivan Godard <i...@ootbcomp.com> wrote:
> If we, like x86, permitted random ordering of different length
> operations then N would be total number of operations. Because we impose
> bundle-level ordering constraints, we have changed N from operation
> count (~30) to operation-length count (~6).

Yes, I agree with that.

> Independently, going in two directions cuts N to N/2, whether
> bundle-level encoding is used or not.

Now, that's something I question. The number of different lengths of
operations, I would have thought, might indeed decrease, but not
decreasing at all would seem more likely than being cut in half -
although that could happen occasionally too.

Of course, if your operations occupy an arbitrary number of bits, so
that N is quite high, then N/2 might well be approached.

John Savard

[Ivan Godard]

The partition across the two sides is not actually simply putting half
the instruction set in one side and half in the other, which would lead
to N/2. Instead we roughly balance the decode effort and total bandwidth
of the sides. Because the average size of the exu operations is small
compared to the average size of the flow operations (because flow has
effective address arguments, that are frequently big), we actually put a
larger part of the instruction set on the exu side, and have more (but
smaller) operations encoded there.

The result is that the (internally fixed length) blocks on the exu
contain more elements than the blocks on the flow side, but this doesn't
matter because, being fixed length, we can decode as many as we want in
one clock; only isolating the block matters, not the count of the block
contents.

As it happens, we have done the encoding so there are three blocks on
each side. Without split-stream, the double-ended decode would have to
parse six blocks. The parse isolates two blocks per cycle after the
first, so parsing six would take four cycles. With split-stream too,
there are only three blocks to parse, which takes two cycles.

The assignment of operations to blocks is only partly based on operation
size; it is also based on when the block's decode is needed. So you are
right that it isn't really operation count reduced to width count, and
thence to half width count; there are other considerations than width.
But it works out the same number of cycles as if there really were six
widths: we decode 30+ ops in two cycles.

Ivan

[Terje Mathisen]

Ivan Godard wrote:
> Of course, the Mill has a bundle size of zero when the ILP is reduced to
> zero, using the no-op encoding as described in the talk. I know of no
> other machine for which the smallest encodable instruction occupies zero
> bits.

I'll quibble here: I still don't know of any machine where any form of
actual information occupies zero bits.

I.e. you have to spend some (fractional) bits somewhere else in order to
be able to skip them here.

>
> You can never have enough iCache, and the best iCache is the iCache
> that's free because you have a compact encoding.

See .sig.

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

[Ivan Godard]

On 6/3/2013 12:18 AM, Terje Mathisen wrote:
> Ivan Godard wrote:
>> Of course, the Mill has a bundle size of zero when the ILP is reduced to
>> zero, using the no-op encoding as described in the talk. I know of no
>> other machine for which the smallest encodable instruction occupies zero
>> bits.
>
> I'll quibble here: I still don't know of any machine where any form of
> actual information occupies zero bits.
>
> I.e. you have to spend some (fractional) bits somewhere else in order to
> be able to skip them here.
>>
>> You can never have enough iCache, and the best iCache is the iCache
>> that's free because you have a compact encoding.
>
> See .sig.
>
> Terje

Well, we repurpose bits we would have had to spend anyway, so perhaps
you would prefer "the smallest encodable instruction occupies zero
*additional* bits"?

The other way makes the better brag, though :-)

Ivan

[Michael S]

On May 31, 7:35 pm, Ivan Godard <i...@ootbcomp.com> wrote:
> On 5/31/2013 4:39 AM, thomas.entne...@gmail.com wrote:
>
>
>
> >> I missed the talk. If anyone notices it up on
>
> >>http://www.youtube.com/stanfordcan you give a shout.
>
> > You can watch it here:
> >http://ee380.stanford.edu/cgi-bin/videologger.php?target=130529-ee380...
>

I still didn't hear up to end.
But your claim that MIPS/(W*$) metric is industry standard is...
weird.
I had never ever seen anybody using it before, and for a good reason.
If you insist on a single figure of merit, then use, at least,
(MIPS^2)/(W*$), it makes a little more sense.

[Quadibloc]

On Jun 3, 1:53 am, Michael S <already5cho...@yahoo.com> wrote:
> But your claim that MIPS/(W*$) metric is industry standard is...
> weird.
> I had never ever seen anybody using it before, and for a good reason.
> If you insist on a single figure of merit, then use, at least,
> (MIPS^2)/(W*$), it makes a little more sense.

It's true that more common metrics are MIPS/$ and MIPS/W. Does this
mean that the metric presented has a dimensional analysis problem?
Then, indeed, the whole premise that there is a huge gap between
signal-processing chips and desktop microprocessors just waiting to be
filled would be called into question.

Indeed, your claim makes sense. For the same technology, a chip that's
"twice as big" would have twice the MIPS, use twice as much power, and
cost twice as much - and be just as good; it's two of the same chip,
for example.

For myself, I would have liked to see the MIPS/$ and MIPS/W for, say,
one of those Tegra chips used in advanced smartphones compared, to see
just how far alternatives to Intel have already filled the gap where
power efficiency and cost are major concerns.

John Savard

[Michael S]

On Jun 3, 3:14 pm, Quadibloc <jsav...@ecn.ab.ca> wrote:
>
>
> For myself, I would have liked to see the MIPS/$ and MIPS/W for, say,
> one of those Tegra chips used in advanced smartphones compared, to see
> just how far alternatives to Intel have already filled the gap where
> power efficiency and cost are major concerns.
>

Leading phone chips vendors are much more secretive about exact price
and power consumptions of their SoCs than Intel/AMD are about their
server chips or TI are (were?) about their DSPs.

BTW, Tegra is not used much in smartphones - has a market share of 1%
or so. They are much more successful in tablets. Majority of advanced
smartphones of today feature processors from made Qualcomm, Apple and
Samsung. In slightly older models you will see plenty of TI chips.

Now I'd like to add couple of pieces of mostly useless information:

1. TI C67 family of VLIW floating point processors was mostly
unsuccessful. Their main competitor Analog Devices did better with
their TigerSharc line, which is also VLIW, but not as wide as C67 on
instruction side and with stronger SIMD emphasis. So, may be, ability
to decode many instructions is not the most important thing in the
world?

2. When evaluated by MIPS/(W*$) Xeon E5-2643 is not the best
representative of x86 ISA, to say the least. More so, it's not the
best even within its own premium Xeon E5 family.

Few examples:
Xeon E5-2643 - 4*3300 MHz/(130 W * 885 $) - our baseline
Xeon E5-1620 - 4*3600 MHz/(130 W * 294 $) - this one is cheaper
because it does not support SMP
Xeon E5-2640 - 6*2500 MHz/(95 W * 885 $) - slower, but cooler and more
cores
Xeon E5-2430L - 6*2000 MHz/(60 W * 662 $) - slower yet, cooler yet,
cheaper
Xeon E5-2450L - 8*1800 MHz/(70 W * 1107 $) - more cores, a bit pricy :
(
Xeon E5-2403 - 4*1800 MHz/(80 W * 188 $) - cheap SMP-capable Xeon for
user that need plenty of RAM, but are less concerned with CPU speed

Now, what's Intel can sell to those who don't need Xeon-E5:
Core i7-3537U - 2*2000 MHz/(17 W * 346 $) - premium ultrabook CPU, on-
chip GPU probably consumes 1/3rd of the power
Celeron 1037U - 2*1800 MHz/(17 W * 86 $) - cheap ultrabook CPU

[Ivan Godard]

You are quite right that getting ARM numbers is pretty near impossible.
We also can't go as low power as the 32-bit ARMS; in current fab
processes, sub-1W is probably not a Mill because the Mill is inherently
64-bit.

The comparison chips in the presentation were ones for which I could
finds public numbers and were top-of-the-line when I did the look up;
"top" changes daily. As stated, the discussion was using the high end
for the example, because it's at the high end at which the width
matters. The Mill member was picked to roughly match in total performance.

As I recall, the Celeron has a sustained issue rate of 2 (not sure, and
don't have time to go dig it up). That gives it 7.2 Gips at 5.0
Mips/W/$, which is a tenth the Xeon horsepower at much better figure of
merit; horsepower is expensive. For roughly equal total horsepower, we
might offer a single-core Mill Copper configuration: 1300 MHz; 9
ops/cycle peak for a total horsepower of 11.7 Gips, at a projected
(highly unreliable numbers) 4.2 Watts and $22 for 126 Mips/W/$. That's
somewhat unfair though, because Copper is for an embedded market and has
no floating point.

Moving to a single-core Silver (which does have FP), horsepower goes to
21 Gips, at a projected 102 Mips/W/$. That is serious overkill versus a
Celeron or a high-end ARM; maybe we should work up a configuration that
is a Tin or Copper but with FP.

But the takeaway is that we (believe we) can configure for X10 M/W/$ at
comparable horsepower at any point in the Intel line.

[Michael S]

Celeron in question is normal IvyBridge with few parts and abilities
fused off.
Most significanr fused parts are
1. Half of L3 cache (2MB instead of 4MB)
2. Turbo boost
3. Hyperthreading
4. AVX
5. AES NI

Sustained issue rate is not affected.

>That gives it 7.2 Gips at 5.0
> Mips/W/$, which is a tenth the Xeon horsepower at much better figure of
> merit; horsepower is expensive. For roughly equal total horsepower, we
> might offer a single-core Mill Copper configuration: 1300 MHz; 9
> ops/cycle peak for a total horsepower of 11.7 Gips, at a projected
> (highly unreliable numbers) 4.2 Watts and $22 for 126 Mips/W/$. That's
> somewhat unfair though, because Copper is for an embedded market and has
> no floating point.

Also I'd estimate that `1/4th of Celeron's TDP is GPU.

>
> Moving to a single-core Silver (which does have FP), horsepower goes to
> 21 Gips, at a projected 102 Mips/W/$. That is serious overkill versus a
> Celeron or a high-end ARM; maybe we should work up a configuration that
> is a Tin or Copper but with FP.

Also, FPUs are not created equal. In particular, on IvyBridge Celerons
AVX is fused off. Not so on core-i3/i5/i7.

Playing your figure of merit game, let's take desktop core-i3, because
it is cheaper than mobiles:
Core i3-3220T - (2*2.8 GHz)/(35W*117$)
This chip is capable of 2*8*2.8=44.8 DP GFLOP/s or 89.6 SP GFLOP/s

And that's old-generation core-i3. For Haswell you'll have to double
up.

>
> But the takeaway is that we (believe we) can configure for X10 M/W/$ at
> comparable horsepower at any point in the Intel line.

My point is: people do not care about MIPS/(W*$).
Some care about MIPS, some about MIPS/$, some others about MIPS/W.
Few could even care about MIPS/(W^aplha*$^(1-alpha)) each with his own
alpha. But never MIPS/(W*$).

[Ivan Godard]

On 6/3/2013 9:18 AM, Michael S wrote:

>
> My point is: people do not care about MIPS/(W*$).
> Some care about MIPS, some about MIPS/$, some others about MIPS/W.
> Few could even care about MIPS/(W^aplha*$^(1-alpha)) each with his own
> alpha. But never MIPS/(W*$).

Of course. But remember the context: a couple of slides to establish
motivation for the technical advance which was the subject of the talk;
not a benchmark comparison for chips that won't even exist for several
years.

As I said in the presentation: this was an apples to oranges comparison,
inherently inaccurate, inapt and unfair, but sufficient to give an
order-of-magnitude idea of what we are working toward.

The day will no doubt come when our marketing department (I am not
looking forward to when we actually have one) are fighting benchmark
wars. For now we are presenting advances that don't need benchmarks to
show their worth: by inspection, those decode patents 1) double the
effective iCache; and 2) can decode more ops than anyone has ever done
before.

Who cares which SKU is the best x86 chip? None of them, and no future
chip either, can crack the 5-wide issue barrier in the x86 ISA. We can.

Ivan

[EricP]

If I understand you correctly, this applies to values that are
already 'on the belt'. The CALL specifies N belt values in
arbitrary order and 'arranges them' at the front of the belt.
This is done by mapping rather than moving the values.

Other args would be passed in memory.

But without registers how do you have a stack?

>> Also some languages like Ada has specific rules about argument
>> copy-in, copy-back which must be done in prologue & epilogue.
>
> All languages define their rules "as if"; the implementation is
> permitted to do anything it wants so long as the program cannot see the
> difference. In effect, the Mill has copy-in-copy-out semantics for all
> (short) arguments and results, but we skip the copy-out step for
> in-arguments and the copy-in step for results.
>
> No actual copy takes place in the call itself, and the result (or
> copy-out) appears on the belt in the same way that the result of a
> native machine operation like an add does. The caller can then use it
> immediately in further computation, store it in some data structure, or
> set it aside for later reuse, just as it could for an add result.
>
> Incidentally, I was on the Honeywell/CII "Green" team that won the Ada
> context.

Yes I know - you did the subtyping (one of the parts I like).
I'm just tossing it out as an example 'non-C' ABI
that is a little more difficult to impliment.

The method I'm thinking of on a register arch,
the callee allocates a variable sized object on its stack,
manipulates that object, then returns without restoring
the stack pointer, the net effect is that a variable
sized object appears in the callers frame.

On a RISC arch with branch-and-link style call this is quite
straight forward. On a VAX with CALLG it gets messy and you spend
a lot of code fighting against built in mechanism of the cpu.

So I thought this is a more challenging example than a C return.

> On a Mill the language ABI does not have all these choices. We looked at
> but ultimately did not choose to implement a pushmepullyou stack because
> we felt we had a better use for the other side of the stacklet (its used
> for the control and spiller stack). The gain from the pushmepullyou
> stack in languages that could benefit was more than outweighed by
> doubling the page load for transient stacklets for all languages.
>
> We also do not let the caller return data in the vacated frame. The Mill
> protection system does not let a caller browse in a callee's frame; this
> is both an anti-bug and anti-exploit measure.
>
> All other variable-length return protocols should work exactly the same
> on a Mill as they do on an x86, PowerPC, or whatever.
>
> Ivan

I don't quite follow this.
Could explain the term 'push-me-pull-you stack'.

Eric

[EricP]

Ivan Godard wrote:
>
> Independently, going in two directions cuts N to N/2, whether
> bundle-level encoding is used or not. Combined, we have cut
> variable-length encoding N from ~30 to ~3, which is tractable as Intel
> demonstrates.
>
> Doubling the iCache capacity is an extra freebie :-)
>
> The cost is the header with its length fields, or, on the flow side, the
> equivalent length indicators in the ops. When using the "fat format" in
> the presentation, we are ahead on any bundle with two or more ops
> because the ops are shorter than in a one-size-fits-all encoding.

Would both program counters have to increment/decrement in lock step?
If there is a miss on one iCache but not the other does that stall?
I think they would have to.

Eric

[Ivan Godard]

On 6/3/2013 11:56 AM, EricP wrote:
> Ivan Godard wrote:
>> On 6/2/2013 9:11 AM, EricP wrote:

>>> That can't all be copied in 1 cycle.
>>
>> That's true. That's why there is no copying - at all. And yes, we do
>> it in one cycle for a correctly predicted local call. Mispredict has
>> the usual penalty, and calls across protection boundaries add two
>> memory references (probably in cache) additional.
>
> If I understand you correctly, this applies to values that are
> already 'on the belt'. The CALL specifies N belt values in
> arbitrary order and 'arranges them' at the front of the belt.
> This is done by mapping rather than moving the values.

Yes, you've got it. If an argument is not on the belt already then there
must be code to get it there - a load maybe, or a fill from the
scratchpad. This is directly equivalent to the situation in legacy
architectures that pass arguments in the registers; if they are not
already in the right place then you must have code to put them there.

> Other args would be passed in memory.

Yes.

> But without registers how do you have a stack?

It's not that the Mill has no registers - it has quite a few of them.
What it doesn't have is *general* registers. For calls, there are the
usual frame and stack pointer registers for example. But these are
specRegs, manipulated by the call and return ops, and you can't write to
them unless you have memory access permissions to the MMIO address where
they live. The OS and/or language runtime systems provide a safe API to
get at these, for use by debuggers etc.

Apps can also reach some specRegs by the reader (rd) or writer (wr) ops
that are also used to spill/fill the scratchpad. Thus rtcReg (real time
clock) is readable, while watchReg (watch point address) is writable.
And some are reachable as a consequence of other operations; for
example, you can get the value of the frame pointer using an LEA.

>>>> The return op takes an argument list, whose length must match the
>>>> result count given with the corresponding call. One cycle later the
>>>> rest of the instruction containing the call is executed (or the
>>>> following instruction if that was the last operation in the calling
>>>> instruction), in a belt environment identical to that immediately
>>>> before the call except with the actual results of the call, if any,
>>>> pushed onto the front of the belt and the same number of trailing belt
>>>> operands pushed off the end.
>>>
>>> What about languages like Ada which allow
>>> variable, run-time sized function values
>>> (i.e. the function decides how big its return value will be)?
>>

>

> The method I'm thinking of on a register arch,
> the callee allocates a variable sized object on its stack,
> manipulates that object, then returns without restoring
> the stack pointer, the net effect is that a variable
> sized object appears in the callers frame.
>
> On a RISC arch with branch-and-link style call this is quite
> straight forward. On a VAX with CALLG it gets messy and you spend
> a lot of code fighting against built in mechanism of the cpu.
>
> So I thought this is a more challenging example than a C return.

Similar issues arise with continuations and longjmp.

There is nothing in the architecture that precludes such an operation
when the call is local; I'd have to think about whether it would work
when the call is across a protection boundary. However, we have no such
operation and are unlikely to add it unless and until there is semantic
support from high-level languages for the concept. We explicitly avoid
operations that require assembler or intrinsics to use.

>> On a Mill the language ABI does not have all these choices. We looked
>> at but ultimately did not choose to implement a pushmepullyou stack
>> because we felt we had a better use for the other side of the stacklet
>> (its used for the control and spiller stack). The gain from the
>> pushmepullyou stack in languages that could benefit was more than
>> outweighed by doubling the page load for transient stacklets for all
>> languages.
>>
>> We also do not let the caller return data in the vacated frame. The
>> Mill protection system does not let a caller browse in a callee's
>> frame; this is both an anti-bug and anti-exploit measure.
>>
>> All other variable-length return protocols should work exactly the
>> same on a Mill as they do on an x86, PowerPC, or whatever.
>>
>> Ivan
>
> I don't quite follow this.
> Could explain the term 'push-me-pull-you stack'.

In a pushm-pullyu stack (courtesy Dr. Dolittle), a single thread has two
stacks that grow toward each other. If the current frame is on stack B
and you want to make a call then you push the arguments on the other
stack T; the call creates a new frame on T that includes the arguments
as callee locals. The return reverses this; from the frame on stack T
you push the results on stack B, and then switch back to the frame on B
while discarding the frame on T. The results of the call are now locals
in the caller's frame on B.

Pushmi-pullyu has been used in several interpreted languages. I'm not
sure whether they have ever seen hardware. Anybody know?

Ivan

[Ivan Godard]

A cache miss on either side stalls everything if it reaches issue; we
are a statically-scheduled in-order exposed-pipeline machine, similar to
your typical DSP. This behavior is in general true for any machine for
which an issue unit can span more than one cache line.

However, the stall only happens at issue, at the bottom of decode, not
at fetch at the top of decode. That is because we have zero-length
no-ops that turn into empty instructions in the decode pipe; note that
these are not bubbles, they are real, albeit no-op, bundles. Say you
have a long sequence of code that uses only one side, with the other
side filled to vacancies. The no-op side may fetch stall (on the first
non-no-op bundle) without the stalling the machine because its decode
pipe doesn't need fetch to fill in the no-ops.

Consequently the accurate answer is that both sides issue synchronously,
or rather that the whole instruction is issued as one piece even though
it comprises two bundles. However, fetch, and hence miss, is only
semi-synchronous on the sides. And even without no-ops, we let the
in-flight decodes go through and issue even if we are missing on the
following instructions. After all, the ones we can issue may contain an
unpredicted transfer of control, which obviates the lines we are missing on.

Ivan

[Michael S]

Actually, as long as the code resides in Decoded ICache, it would be
technically very easy for Intel to feed Micro-op Queue with 5 or even
6 micro-ops per clock. The fact that they didn't do it in 3
consecutive iterations of the uArch probably suggest that according to
their simulations it wouldn't improve perf/Watt.

Also look at what they now call "Legacy Decode Pipeline". On FP-
intensive workloads it typically ends up bottlenecked by instruction
fetch bandwidth rather than by parse (predecode, using Intel's terms)
or by decode. Again, it would be technically very easy to increase
IFetch bandwidth from current 16 B/clock to 32 B/clock, however Intel
didn't do it. Which probably suggests that according to their
simulations it wouldn't improve perf/Watt.

BTW, TI C6000 family that you presented, especially the first
generation of it (C62/C67), is an excellent example of the processor
cores that can decode more operations than competitors and
nevertheless relatively to those competitors (primarily TigerSharc,
but also BlackFin and, to less extent, TI's own C5000) it sucks.

[Ivan Godard]

On 6/3/2013 2:31 PM, Michael S wrote:

> Actually, as long as the code resides in Decoded ICache, it would be
> technically very easy for Intel to feed Micro-op Queue with 5 or even
> 6 micro-ops per clock. The fact that they didn't do it in 3
> consecutive iterations of the uArch probably suggest that according to
> their simulations it wouldn't improve perf/Watt.

I suppose it depends what "is" means :-) Seems to me that's just pushing
the decode bottleneck someplace else; they still can't decode five ops
into a decoded icache either.

For that matter, they can dedicate the other cores to on the fly binary
translation, and hit 30+ ops/clock with no trouble. That's not what I
mean be "decode" either, but YMMV.

> Also look at what they now call "Legacy Decode Pipeline". On FP-
> intensive workloads it typically ends up bottlenecked by instruction
> fetch bandwidth rather than by parse (predecode, using Intel's terms)
> or by decode.

If you restrict the input to the subset of the instruction set that
looks like fixed-length RISC instructions then you can do better than
five easily; any fixed-length decoder can. And in effect that's what
they do, with fast parse for the subset. Of course, if the code contains
any of the instructions outside the subset then you are down to one
instruction/cycle. I don't call that "decode" either; we can do 30+ on
arbitrary code that uses the entire instruction set. And the rest of the
machine can keep up with it on general-purpose code.

Again, it would be technically very easy to increase
> IFetch bandwidth from current 16 B/clock to 32 B/clock, however Intel
> didn't do it. Which probably suggests that according to their
> simulations it wouldn't improve perf/Watt.

I have no doubt you are right; OOO superscalar bottlenecks on the data
side too, and there's little point to improving one side without the
other. But that's a different talk; see you at USENIX :-)

I don't want to appear to be attacking Intel or the x86 here. The x86
encoding was entirely reasonable for when it was done, better than
reasonable really considering how compact they were able to make it. And
the x86 vendors, faced with legacy compatibility, do truly heroic things
in hardware for support; kudos.

The Mill was designed as a green-fields ISE, and can do things new and
better. I don't mock core memory because DRAM is faster, smaller, and
lower power, either; tech evolves. When as and if the Mill enters x86
markets (certainly not the first target) then I'm sure that Intel, AMD
and VIA will have a response. I'm very interested to see what it will be.

Ivan

[Stephen Fuld]

On 5/31/2013 4:39 AM, thomas....@gmail.com wrote:

snip

> I found it very interesting.


I too found it interesting. Who'da thunk there could be such a
different way of doing decode?! :-)


Do you have any data that you could share about the distribution of the
number of instructions per bundle in whatever you consider typical code?



But my question is about the conveyor.

I took it that the conveyor advances one slot per cycle. So something
that was at position 3 in cycle N will be at position 4 in cycle N+1. I
get that. But ISTM that knowing how many cycles ago a value was put on
the conveyor is not enough information to know how to retrieve it.

Since there could be multiple functional units depositing things on the
conveyor in the same cycle, don't you need some way to indicate, in the
subsequent retrieve, which functional unit put the data on the conveyor?

I'm sure I am missing some understanding.



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

[Ivan Godard]

On 6/3/2013 4:16 PM, Stephen Fuld wrote:
> On 5/31/2013 4:39 AM, thomas....@gmail.com wrote:
>
> snip
>
>> I found it very interesting.
>
>
> I too found it interesting. Who'da thunk there could be such a
> different way of doing decode?! :-)
>
>
> Do you have any data that you could share about the distribution of the
> number of instructions per bundle in whatever you consider typical code?

It's completely different between pipelined loops and open code. In
loops there is unbounded ILP available, so the density is determined by
how closely the distribution of functional units matches the
distribution of operations in an iteration; actual code always runs out
of something while having an excess of something else. For wide family
members and narrow iterations the compiler sometimes has to unroll a
round or two to fill up the width. That said, while I don't have enough
data for an accurate number, I would WAG an average operation density of
2/3rds. So those Golds would be seeing loops with 20 ops or so per
instruction.

Open code has only the natural ILP, which is much less as is well known.
There are other novelties in the Mill that help to bring available ILP
up, not described in the presentation or discussion. Particularly
important are argument lists (a call can extend over several slots and
so counts as multiple ops from the hardware point of view), large
constants (ditto), phased issue (a single Mill instruction can contain
three-deep dependent dataflows that would require three cycles on a
legacy), cascaded calls (more than one call in an instruction), first
winner rule (ditto but for branches), and several more that the filings
are not yet in for.

With all that, an ILP of three or so seems representative. A counting
artifact makes this lower than might be expected compared to a
hidden-pipe machine, because we expose and count the cycles when we have
nothing to do: if there is a data-dependent multiply with nothing else
to do until it finishes, the Mill must count the waiting no-ops against
ILP while a legacy has the same wait but doesn't count it.

> But my question is about the conveyor.
>
> I took it that the conveyor advances one slot per cycle. So something
> that was at position 3 in cycle N will be at position 4 in cycle N+1. I
> get that. But ISTM that knowing how many cycles ago a value was put on
> the conveyor is not enough information to know how to retrieve it.

Nope. The belt advances as many positions as operands drop. Position 3
moves to position 4 if one new item dropped during the cycle, to
position 7 if four dropped, and stayed at position 3 if nothing dropped.

> Since there could be multiple functional units depositing things on the
> conveyor in the same cycle, don't you need some way to indicate, in the
> subsequent retrieve, which functional unit put the data on the conveyor?
>
> I'm sure I am missing some understanding.

The belt drops are always dense and non-overlapping. If you, the coder
or compiler, know how many ops retire their results in a cycle then you
know where everything is. And because it's an exposed pipe with all
operations having statically known fixed latencies (no early-outs), if
you know when ops issue then you also know when they retire. So you (or
the compiler back-end) code things to issue so they will retire when you
want their result to be on the belt for somebody else.

Basic code generation for exposed pipes, common on DSPs, is 30-year-old
tech and not original with us.

[Stephen Fuld]

On 6/3/2013 6:37 PM, Ivan Godard wrote:
> On 6/3/2013 4:16 PM, Stephen Fuld wrote:

Thanks for the info on ILP.

>> But my question is about the conveyor.
>>
>> I took it that the conveyor advances one slot per cycle. So something
>> that was at position 3 in cycle N will be at position 4 in cycle N+1. I
>> get that. But ISTM that knowing how many cycles ago a value was put on
>> the conveyor is not enough information to know how to retrieve it.
>
> Nope. The belt advances as many positions as operands drop. Position 3
> moves to position 4 if one new item dropped during the cycle, to
> position 7 if four dropped, and stayed at position 3 if nothing dropped.

OK, got it. But see below.

>> Since there could be multiple functional units depositing things on the
>> conveyor in the same cycle, don't you need some way to indicate, in the
>> subsequent retrieve, which functional unit put the data on the conveyor?
>>
>> I'm sure I am missing some understanding.
>
> The belt drops are always dense and non-overlapping. If you, the coder
> or compiler, know how many ops retire their results in a cycle then you
> know where everything is.

If say two ops retire on a particular cycle, say one from an add
instruction and another from a subtract, how do I know whether position
1 is the add or the subtract?

[Ivan Godard]

There is a canonical ordering. Operations vary in latency, in which slot
in the initial instruction they were encoded, and by result number for
those ops that drop more than one result. Any result has a unique
combination of those three values, so the order is determined by a
function of those three things.

It doesn't really matter what sort order is used, so long as the
compiler and the hardware agree on what it is. Actually, it does matter
in some cases, but that hasn't been filed yet; sorry.

Ivan

[Mark Thorson]

So the claim is 20 ILP on loops and 3 ILP
on the straightaway. You have a simulator.
Do you have a compiler, and are these numbers
based on compiling examples of real applications?

This is the most eyebrow-raising part of your
presentation. You mentioned some work by Patt
and Singh showing the ILP is out there, but
I want to know whether you've seen that ILP
on your architecture with your compiler and
realistic applications.

[Stephen Fuld]

On 6/3/2013 7:49 PM, Ivan Godard wrote:
> On 6/3/2013 7:27 PM, Stephen Fuld wrote:
>> On 6/3/2013 6:37 PM, Ivan Godard wrote:
>
>>>
>>> The belt drops are always dense and non-overlapping. If you, the coder
>>> or compiler, know how many ops retire their results in a cycle then you
>>> know where everything is.
>>
>> If say two ops retire on a particular cycle, say one from an add
>> instruction and another from a subtract, how do I know whether position
>> 1 is the add or the subtract?
>>
>>
>>
>
> There is a canonical ordering. Operations vary in latency, in which slot
> in the initial instruction they were encoded, and by result number for
> those ops that drop more than one result. Any result has a unique
> combination of those three values, so the order is determined by a
> function of those three things.

OK, that makes sense. I was confused by the "simplification" of using
just a single number in the examples.

> It doesn't really matter what sort order is used, so long as the
> compiler and the hardware agree on what it is.

Right.

> Actually, it does matter
> in some cases, but that hasn't been filed yet; sorry.

No problem. Just from what you have told us it gives a lot of food for
thought. Thanks.

[Ivan Godard]

On 6/3/2013 8:51 PM, Mark Thorson wrote:

> So the claim is 20 ILP on loops and 3 ILP
> on the straightaway. You have a simulator.
> Do you have a compiler, and are these numbers
> based on compiling examples of real applications?
>
> This is the most eyebrow-raising part of your
> presentation. You mentioned some work by Patt
> and Singh showing the ILP is out there, but
> I want to know whether you've seen that ILP
> on your architecture with your compiler and
> realistic applications.
>

We have, well, had, a compiler; the old EDG front end and in-house
middle end are being scrapped in favor of clang/LLVM because we don't
want to do the vectorization code ourselves. Our back-end is still the
in-house one and will remain so. We thought we'd have the reintegration
with LLVM done by now, but the last nine months were completely
overtaken by patents, of which I am so thoroughly sick :-(

Incidentally, the Mill by design has no need for compiler magic; I write
compilers so I get the hardware guys to do all the work. :-)
Vectorization is 40-year-old tech, but it's still a lot of work to do
from scratch, and with our limited resources we don't want to do
anything we can use from outside. We also want to be able to use the
LLVM plug-in tools as well; another reason to abandon our middle-end.

Now to your question. Even the old compiler could not handle "realistic"
applications, because realistic applications require full OS and
language runtime system support, and we have hardly started the Unix
port, other than looking for gotchas in the architecture. Our sim gives
you a bare machine; you even have to provide the power-up sequence. And
you are given the real machine. For example, you come up with the clock
set at the configured hardware crystal frequency, and your (simulated)
code has to diddle the (simulated) PLLs to change the (simulated)
frequency from inside the (simulated) program - and both (simulated)
behavior and the results you get change in consequence.

This is typical of real hardware development, as opposed to academic
projects that run abstract simulations. Real hardware sim is primarily
for verification rather than measurement That's true even before you
start to do sim at the gate level (we're not to the gates yet except in
certain subsystems thought to be clock-critical).

Measurement sim is mostly for tuning: picking up 10% here, 17% there. We
will do a lot of it when we start to settle on the particular family
member configurations that we want to spend millions to get fabbed.
Right now however, we are mostly concerned with the kind of
order-of-magnitude design issues that are obvious by eyeball to someone
who understands the architecture.

For example, our team has much experience in the embedded world, and we
know that a software pipeline can soak up all the hardware you are
willing to give it, so long as you can solve the stalling problems. It's
not worth measuring the difference between two FP units configured vs.
three; we'll deal with decisions at that level later.

That said, yes, we have done some programs, both hand code and compiled
to the extent that our very-alpha compiler could do them. As mentioned,
the compiler does not yet do vectorization and hence no software
pipelines, so all our numbers for that are hand code. We've done many of
the common small benchmark: hunks out of linpack, the Unix wc program,
8-queens, that kind of thing. In many cases we have altered the Mill
design to let a Mill pipe a particular style of loop the other machines
can't handle.

Our conclusion: Patt's result of 80% of operations being in loops is
accurate for general-purpose code. It is not accurate for BLAS-type HPC
code, where the number is more like 99%. We confirm other results that
25%-33% of overall cycles is spent in memcpy and its relatives. We find
that if the application is dedicated (hydrodynamics say, or embedded)
then careful member configuration can improve the figure of merit by 50%
over a one-size-fits-all general purpose configuration.

We still have a few loops that we have not been able to pipeline. The
most glaring example is those that have been expressed as recursion
instead of iteration, because the compiler often cannot recognize the
idiom. We hope that LLVM will help us there, and reduce such loops to
iterations that we have already solved.

Otherwise, we have largely solved the kinds of things that cause
pipeline trouble for legacy machines (and hence reduce the average ILP
they can achieve), even for pipe-oriented architectures like the
Itanium. We can pipe while loops; loops containing control flow or
calls; reductions; high iteration intervals; and so on. Unfortunately
none of the pipelining-related patents are in yet, so I can't describe
how we do it.

Incidentally, if you want published numbers on the ILP gain from
pipelining you should do a lit search for Bob Rau,and the Itanium and
its architectural predecessors. However, take those numbers as a lower
bound.

Ivan

[Ivan Godard]

On 6/3/2013 10:51 PM, Ivan Godard wrote:
> On 6/3/2013 8:51 PM, Mark Thorson wrote:
>
>> So the claim is 20 ILP on loops and 3 ILP
>> on the straightaway. You have a simulator.
>> Do you have a compiler, and are these numbers
>> based on compiling examples of real applications?
>>
>> This is the most eyebrow-raising part of your
>> presentation. You mentioned some work by Patt
>> and Singh showing the ILP is out there, but
>> I want to know whether you've seen that ILP
>> on your architecture with your compiler and
>> realistic applications.

p.s. Patt reported ILP up to 24 *ALUs*; that doesn't count other kinds
of operations. We do not expect to be able to get anywhere near 24 ALUs
due to data-side and pin bandwidth constraints; our 30+ is *total
operations* of all kinds, and (in Gold) only includes eight ALUs. As I
mentioned in another post, I suspect that Gold is over-provisioned for
its potential market and the total op count will drop when we do final
configuration tuning; my WAG is ~28 total ops peak. Alternatively we
might drop it back to ~24 and add another member between the present
Gold and Schadenfreude; it will depend on what happens to the clock when
the gate-level work is done.

[Michael S]

On Jun 4, 8:51 am, Ivan Godard <i...@ootbcomp.com> wrote:
> On 6/3/2013 8:51 PM, Mark Thorson wrote:
>
>
> Our conclusion: Patt's result of 80% of operations being in loops is
> accurate for general-purpose code.

When you say "loops" do you mean only innermost loops or 2 levels of
nesting?

> It is not accurate for BLAS-type HPC
> code, where the number is more like 99%.

I happened to spend last couple of weeks researching "BLAS-type code",
although not in the context that people consider HPC.
If we only count innermost loops then for the size of matrices I am
currently interested in the number is closer to 90% then to 95%.
Nowhere near 99%. And the time spent in inner loops is probably less
than 80%.
Without SIMD the percentage of time spent in the inner loop will be
much higher, but if one is using processor without decent SIMD for
dense matrix math then he lost before he even started.

[nm...@cam.ac.uk]

In article <d0392826-60db-40c9...@bz1g2000vbb.googlegroups.com>,
Michael S <already...@yahoo.com> wrote:

>On Jun 4, 8:51=A0am, Ivan Godard <i...@ootbcomp.com> wrote:
>> On 6/3/2013 8:51 PM, Mark Thorson wrote:
>>
>> Our conclusion: Patt's result of 80% of operations being in loops is
>> accurate for general-purpose code.
>
>When you say "loops" do you mean only innermost loops or 2 levels of
>nesting?

That's not the only question. A more important one, where the
hardware question differs from the 'program proving' one, is whether
there is a loop at any level in the call stack.

Generally, most instructions are in loops in the 'program proving'
sense, if only because most programming languages don't provide
any method of handling arbitrary-sized aggregates except loops.
In languages with other primitives (including modern Fortran,
incidentally), you can see programs where many of the 'loops' are
implicit.

>> It is not accurate for BLAS-type HPC
>> code, where the number is more like 99%.
>
>I happened to spend last couple of weeks researching "BLAS-type code",
>although not in the context that people consider HPC.
>If we only count innermost loops then for the size of matrices I am
>currently interested in the number is closer to 90% then to 95%.
>Nowhere near 99%. And the time spent in inner loops is probably less
>than 80%.
>Without SIMD the percentage of time spent in the inner loop will be
>much higher, but if one is using processor without decent SIMD for
>dense matrix math then he lost before he even started.

I have seen 99.5% in inner loops with no BLAS-like functions being
applicable; I have also seen matrix code where SIMD optimisations
were completely inapplicable. And, of course, the ones where 99%
of the time could go in a SIMD unit :-)

At best, these figures are context-dependent rules of thumb.


Regards,
Nick Maclaren.

[Michael S]

On Jun 4, 12:10 pm, n...@cam.ac.uk wrote:
> In article <d0392826-60db-40c9-8ba4-41c58edba...@bz1g2000vbb.googlegroups.com>,

> Michael S  <already5cho...@yahoo.com> wrote:
>
>
>
> I have also seen matrix code where SIMD optimisations were completely inapplicable.
>

That's interesting. I'd really like to see an example of dense linear
algebra algorithm which is O(N^2.5) or slower that would not profit at
all from 4-way or wider SIMD when N is more than few dozens.

[Bakul Shah]

On 6/2/13 11:47 AM, Ivan Godard wrote:
> The discussion refers to the kind of arguments that are passed in registers on a legacy machine; we
> pass them on the belt instead. Large objects on the Mill are passed by (implicit) reference, just
> like legacies do. The reference pointer itself is passed on the belt, of course. Also like legacies,
> we pass in memory any excess arguments beyond what fit in the belt, with the usual semantics; the
> same for VARARGS.

So given something like

f(int a, int b) {
printf("a=%d, b=%d\n", a, b);
...
}

You'd have to copy a and b to memory? And is this memory in the caller's memory
frame or callee's?

> We also do not let the caller return data in the vacated frame. The Mill protection system does not
> let a caller browse in a callee's frame; this is both an anti-bug and anti-exploit measure.

So no tail-call elimination?

Do you also protect the memory based portion of the frame?

What about cases like this?

f(int n) { char *v = malloc(n); g(v); char w[999]; g(w);}
g(char* x) { strcpy(x+1000, "boo!"); }

Can you protect memory past the end of v and w?

On a separate topic: you guys should do a simple lisp/scheme/python
based demo implementation using symbolic instruction to get the
essential ideas across. This can be easily enhanced as you add
more details. Or is that giving away too many details? Yost can
probably do this in his sleep!

[nm...@cam.ac.uk]

In article <18f2394f-6aa7-4492...@w5g2000vbd.googlegroups.com>,

Michael S <already...@yahoo.com> wrote:
>>
>> I have also seen matrix code where SIMD optimisations were completely
>inapplicable.
>
>That's interesting. I'd really like to see an example of dense linear
>algebra algorithm which is O(N^2.5) or slower that would not profit at
>all from 4-way or wider SIMD when N is more than few dozens.

Not all matrix code is dense linear algebra :-)


Regards,
Nick Maclaren.

[Michael S]

On Jun 4, 1:14 pm, n...@cam.ac.uk wrote:
> In article <18f2394f-6aa7-4492-8035-0b9f350f5...@w5g2000vbd.googlegroups.com>,

> Michael S  <already5cho...@yahoo.com> wrote:
>
>
>
> >> I have also seen matrix code where SIMD optimisations were completely
> >inapplicable.
>
> >That's interesting. I'd really like to see an example of dense linear
> >algebra algorithm which is O(N^2.5) or slower that would not profit at
> >all from 4-way or wider SIMD when N is more than few dozens.
>
> Not all matrix code is dense linear algebra :-)
>
> Regards,
> Nick Maclaren.

Sure. But would matrix code in question profit from Ivan's style MIMD?
Assuming that Ivan changed his mind about Gold not targeting HPC and
outfitted Gold core with 4 DP adder and 4 DP multipliers.

[Quadibloc]

On Jun 3, 4:40 pm, Ivan Godard <i...@ootbcomp.com> wrote:
> The Mill was designed as a green-fields ISE, and can do things new and
> better.

"green-fields" ISE? Idiom unclear. Possibly your intended meaning is
equivalent to that of "clean sheet of paper design", meaning that it
is not constrained by legacy compatibility considerations.

John Savard

[Quadibloc]

On Jun 2, 1:16 pm, Ivan Godard <i...@ootbcomp.com> wrote:
> True; I'd never considered the possibility. Though I think that you'd
> still need to get Samsung involved, because the chip wants to stay in an
> open reading frame and your plus signs would tend to muck that up.

Actually, if you want six different kinds of instruction, for "three
dimensional" memory, there is a trivial way to do it:

c1 eldnub
b1 eldnub
a1 eldnub
pointer1 <- branch here
pointer2
bundle 2a
bundle 2b
bundle 2c
c3 eldnub
b3 eldnub
a3 eldnub
bundle a4 <- pointer1 points here
bundle b4
bundle c4
c5 eldnub
b5 eldnub
a5 eldnub
bundle 6a <- pointer2 points here
bundle 6b
bundle 6c

John Savard

[Ivan Godard]

As I recall Patt was counting single-thread scalar ops. Because of
variations in vector height from machine to machine, counting scalars is
the only way to make meaningful comparisons (well, you could count
vector and scalar and then scale the vector back to scalar). His point,
if I understood it, was that available loop-level parallelism is much
higher than is currently exploited.

To exploit the loop-level parallelism, the hardware can be replicated on
the SIMD dimension (from scalar to vector, or bigger vectors), or on the
MIMD dimension (more independent scalar functional units) or a mix of
both. His numbers, and point, seem valid to me. After all, it's no
different in power, area, or latency whether you put two ALUs
side-by-side (superscalar or wide issue), or on top of each other (2-way
vector), and likewise for any other parallelism factor.

So 80% and 99% of scalar-equivalent ops fits our experience. Whether it
is more profitable to go wider (MIMD) or higher (SIMD, bigger vector)
depends on other parts of a design. For example, if you are decode
limited then you have little choice but to go higher, and the x86 has
been doing that with each generation. On the other hand, if you can
handle it then MIMD has flexibility advantages over the equivalent
amount of SIMD; there lots of loops that can be software pipelined that
cannot be vectorized for one reason or another.

On the Mill, the MIMD and SIMD dimensions can be independently
configured to fit a particular market. The operation set is regular; all
ops have vector forms except those like control flow for which it is not
meaningful. That simplifies the compiler. If Patt is right that there is
use for 24 ALUs, then we can configure twelve two-high vector ALUs, or
six four-high. Actually, for 32-bit integer our Silver configuration is
already pretty close to that - 5 MIMD ALUs, each four SIMD ints high.

Whether the market will pay for that SKU is a different question; but we
can build it.

[Ivan Godard]

https://www.google.com/search?q=green-field+development+definition

Compare "brown-field development"

[Ivan Godard]

On 6/4/2013 2:33 AM, Bakul Shah wrote:
> On 6/2/13 11:47 AM, Ivan Godard wrote:
>> The discussion refers to the kind of arguments that are passed in
>> registers on a legacy machine; we
>> pass them on the belt instead. Large objects on the Mill are passed by
>> (implicit) reference, just
>> like legacies do. The reference pointer itself is passed on the belt,
>> of course. Also like legacies,
>> we pass in memory any excess arguments beyond what fit in the belt,
>> with the usual semantics; the
>> same for VARARGS.
>
> So given something like
>
> f(int a, int b) {
> printf("a=%d, b=%d\n", a, b);
> ...
> }
>
> You'd have to copy a and b to memory? And is this memory in the caller's
> memory
> frame or callee's?

It depends on the ABI design. Passing all VARARGS in memory is a simple
ABI. A few decades back some machines adopted ABIs that passed VARARGS
in registers as far as they could before passing the rest in registers.
This is substantially more complicated, especially if the machine has
different RFs for different purposes and scatters the VARARGS by type.

It is certainly possible for the Mill to use an ABI in which VARARGS are
pass (like regular arguments) on the belt, up to some number, and
overflowing to memory. Or not - it's op to the language and runtime ABI.
Personally, I would favor dumb and simple. To the best of my knowledge,
no program exists for which you can measure a performance different
between passing all VARARGS in memory and passing some in registers.

>> We also do not let the caller return data in the vacated frame. The
>> Mill protection system does not
>> let a caller browse in a callee's frame; this is both an anti-bug and
>> anti-exploit measure.
>
> So no tail-call elimination?

Yes, tail-call elimination, but not yet filed.

> Do you also protect the memory based portion of the frame?

Yes

> What about cases like this?
>
> f(int n) { char *v = malloc(n); g(v); char w[999]; g(w);}
> g(char* x) { strcpy(x+1000, "boo!"); }
>
> Can you protect memory past the end of v and w?

The Mill has a hardware-known stack but not a hardware-known heap. It is
also not a capability machine (though I truly wish...). Consequently in
the malloc case, for the overrun to be caught the language runtime would
have to use the hardware protection facilities to protect individual
heap allocations. That's certainly possible to do, though I suspect
that few malloc implementations will do so.

For the stack allocation case, if the overrun extends outside the frame
then the hardware will catch it, but if it merely klobbers data inside
the frame then it won't.

> On a separate topic: you guys should do a simple lisp/scheme/python
> based demo implementation using symbolic instruction to get the
> essential ideas across. This can be easily enhanced as you add
> more details. Or is that giving away too many details? Yost can
> probably do this in his sleep!

There are many things we ought to do, but lack the resources to get to.
That's one of them.

Ivan

[Joe keane]

In article <cb60afbd-3754-4f89...@k4g2000yqb.googlegroups.com>,
Quadibloc <jsa...@ecn.ab.ca> wrote:
>It's true that more common metrics are MIPS/$ and MIPS/W. Does this
>mean that the metric presented has a dimensional analysis problem?

it makes no sense

the correct metric is

MOPS/($ + 14*W)

[EricP]

(Just speculating...) It might be possible to allow each
stream some amount of asynch execution. If the header on
each half-bundle (HB) had a count of the number of belt slots
consumed by the *alternate* stream HB, if there was a stall on
the other stream then it can advance the belt count and mark
the skipped slots as Invalid. An attempt to read an invalid
slot causes an issue stall.

Because the belt is write once, there are no WAW and WAR
hazards to consider.

That could allow each PC to proceed somewhat independently.
A special alt-count value could indicate sync with the other
stream is required, for jumps, calls etc.

Eric

[Ivan Godard]

That's a clever extension of the belt idea, but my snap guess (needs
thought to confirm) is that it wouldn't pay.

For maximum overall performance, the compiler schedules as tightly as it
can, so produced values are immediately used by consumers. This lets us
keep the belt short (use-before-lose), lessens spill/fill bandwidth to
the scratchpad, and keeps the latency of the longest dataflow (which
controls overall elapsed execution time) minimal. In addition to that,
the encode sides of a producer and a consumer have no relationship -
exe-to-exu (add to shift), flow-to-flow (load to store), exu-to-flow
(add to store), and flow-to-exu (load-to-add).

Consequently, a result is likely to be needed pretty much at once by ops
encoded by the other side. Yes, you could stall issue on one side alone
as you suggest - but almost immediately you will be stalling the other
side too, so you may as well keep it simple and stall both right away.

Another aspect: you can't stop a core on a dime. It takes three clocks
just to get everything stopped on a big Mill. The easiest stall is to
stall issue, because issue is all in one compact place, and you don't
have to really stall the rest of the machine, you simply switch to
issuing "wait...wait...wait". Compared to that, trying to stop a
multiply in mid-stream is real hard. Hardware is weird :-)

The idea would more interesting if we were finding iCache miss to be
that much of a problem, but we don't. The way our prediction machinery
work, we have pretty much perfect code fetch and you almost never miss
except on a mispredict, up to the limit of pin bandwidth. If we are
running out at the pins then both sides will be missing big time, and
there's not much to do except wait for bandwidth to free up.

If we mispredict then both sides get reset to the correct path, and the
happenstance of cache replacement may give us one-sided misses for a
while, until the new predicted fetching catches up. But miss in
correctly predicted code is essentially unknown; Mill prediction,
including how we avoid miss, is not filed yet so I can't explain the
mechanism.

Usable or not, I am impressed that you came up with your idea; it's a
quite reasonable possibility, one we had never thought of, and we've
been looking at the Mill for a lot longer than you have :-)

Incidentally, feel free to invent more in the decode and other areas I
talk about freely, but please don't speculate about anything for which I
say "not filed yet". If you happen to come up with the same solution
that we have and you publish it here then you would muck up our patent.
The US is no longer on a "first-to-invent" system.

Ivan

[Quadibloc]

But I presume that before going to silicon, you will be running some
sort of software simulation so you can get performance numbers, to
determine if your design is working as intended?

John Savard

[Bakul Shah]

I am sure they are running simulations. I was talking more about a
simpler "executable" model so that people can get a better grasp of
what they are doing. Actually it wouldn't be too hard to come up
with an interpreter that fits the details revealed so far. Might
make a good project for a student!

[Ivan Godard]

Yes, we run sims, and you can see the machine working in excruciating
detail. The sim is at the machine level, and will make no sense if you
do not already understand the machine. I think that Quadiblock is
looking for performance-comparison sim, which is a completely different
thing. Those we don't have; we lack the software environment to take a
random C main(), compile and run it.

On the other hand, if you have experience porting Linux then I'd like to
talk with you :-)

Ivan

[Carl Shapiro]

Ivan Godard <iv...@ootbcomp.com> writes:

> The return op takes an argument list, whose length must match the
> result count given with the corresponding call.

Is the result count provided in the call known to the callee? How is the
correspondance enforced?

Languages like Lisp can return 0 or more arguments but the number of
values expected by the caller is not known to the callee at compile
time. If the callee provides fewer return values than expected the
missing return values default to nil. If the calle provides more return
values than expected the excess return values are ignored.

A count of return values is usually transmitted by the callee to the
caller. The actual conventions optimize for the common 0 or 1 return
value cases but returning a number of values up to the number of return
value registers in the convention is effectively free.

[Ivan Godard]

On 6/5/2013 6:26 PM, Carl Shapiro wrote:
> Ivan Godard <iv...@ootbcomp.com> writes:
>
>> The return op takes an argument list, whose length must match the
>> result count given with the corresponding call.
>
> Is the result count provided in the call known to the callee? How is the
> correspondance enforced?

The call operation specifies the expected result count. This is static
and determined by the compiler, and must match the length of the result
list provided by the return operation or the hardware will fault the
program and control winds up in an illegal-operation handler. The count
is part of the frame state, preserved over the call.

Because we use temporal addressing and return results on the belt, if
the number of returned operands varied from call to call then subsequent
code would not know where the pre-call data (saved and restored over the
call) is to be found on the belt. Thuse if a datum of interest was in b2
before the call, and the call drops one result, then the datum will be
in b3 after the call. But if the call drops two results then the datum
will be in b4, not b3.

Like register references in a legacy machine, belt references on a Mill
must be static, so a subsequent add (say) must be able to settle on b3
or b4 at code generation time, just as an x86 must settle on R3 or R4
for a datum at code-generation time.

> Languages like Lisp can return 0 or more arguments but the number of
> values expected by the caller is not known to the callee at compile
> time. If the callee provides fewer return values than expected the
> missing return values default to nil. If the calle provides more return
> values than expected the excess return values are ignored.

LISP doesn't run in native hardware :-)

For languages whose semantics require varying result counts, like
languages whose semantics require varying argument counts (VARARGS) must
use an above-the-machine API to specify what is going on. A reasonable
implementation might package all the returned values into a tuple and
return a reference to that, possibly with the common case returned
directly (i.e. zero results returns two nils on the belt, one result
returns the result and a nil on the belt, and more than one returns the
first and a reference to the tuple; as far as the hardware is concerned
you have returned two results).

> A count of return values is usually transmitted by the callee to the
> caller. The actual conventions optimize for the common 0 or 1 return
> value cases but returning a number of values up to the number of return
> value registers in the convention is effectively free.
>

Well, not quite free, because the unused return registers must be nil'd
out. You could do much the same on the Mill, returning say six values
where the unused results are explicitly nil.

Ivan

[Andy (Super) Glew]

On 6/3/2013 3:40 PM, Ivan Godard wrote:
> On 6/3/2013 2:31 PM, Michael S wrote:
>
>> Actually, as long as the code resides in Decoded ICache, it would be
>> technically very easy for Intel to feed Micro-op Queue with 5 or even
>> 6 micro-ops per clock. The fact that they didn't do it in 3
>> consecutive iterations of the uArch probably suggest that according to
>> their simulations it wouldn't improve perf/Watt.
>
> I suppose it depends what "is" means :-) Seems to me that's just pushing
> the decode bottleneck someplace else; they still can't decode five ops
> into a decoded icache either.

No, but *you* say, Ivan, that 80% of code is in loops. So you only have
to decode the 20% irregularly, and then decode the 80% of instructions
in a fast manner.

Heck: Intel could use the MILL approach inside the decoded I$.

Not that I don't enjoy the Mill. Neat stuff.

And, I agree that the best instruction cache is the cache that you don't
need to build.

--
The content of this message is my personal opinion only. Although I am
an employee (currently of MIPS Technologies, which has been acquired by
Imagination Technologies; in the past of companies such as Intellectual
Ventures and QIPS, Intel, AMD, Motorola, and Gould), I reveal this only
so that the reader may account for any possible bias I may have towards
my employer's products. The statements I make here in no way represent
my employers' positions on the issue, nor am I authorized to speak on
behalf of my employers, past or present.

[Andy (Super) Glew]

On 6/3/2013 6:37 PM, Ivan Godard wrote:

> With all that, an ILP of three or so seems representative. A counting
> artifact makes this lower than might be expected compared to a
> hidden-pipe machine, because we expose and count the cycles when we have
> nothing to do: if there is a data-dependent multiply with nothing else
> to do until it finishes, the Mill must count the waiting no-ops against
> ILP while a legacy has the same wait but doesn't count it.

Huh?

IPC = number of instructions divided by number of cycles.

More importantly, number of useful instructions, not counting NOPS.

It seems to me that what you say about NOPS would increase your ILP as
measured by IPC, not decrease it.

IPC is not the only metric for ILP. Some folks count number of ALU ops.
Ideally, the number of ALU ups as measured on code compiled to minimize
the number of ALU ops - i.e. no speculativ execution, no optimizations
that replicate code.

Perhaps the best metric would be derived from a visit count of lines of
the original high level program, as executed by an interpreter.

Plus, I must mention MLP.

--
The content of this message is my personal opinion only. Although I am

an employee (currently Imagination Technologies, which acquired MIPS; in
the past of companies such as Intellectual Ventures/QIPS, Intel, AMD,

Motorola, and Gould), I reveal this only so that the reader may account

for any possible bias I may have towards my employers' products. The

[Andy (Super) Glew]

On 6/4/2013 11:53 AM, Ivan Godard wrote:

> For maximum overall performance, the compiler schedules as tightly as it
> can, so produced values are immediately used by consumers. This lets us
> keep the belt short (use-before-lose),

By the way, I think this is an interesting counterpoint to those who say
the Mill is a VLIW.

The classic VLIWs, and even the non-classic, like Itanium, had big
register files. Sought parallelism. Dumped values into the register
files to exploit parallelism. And suffered bloated instruction sets as
a result.

The Mill, with its belt, seldom has to encode a destination. Saves bits.

The belt probably is implemented like a register file array. Worse, a
CAM indexed register file array - CAMs because of its in-place renaming.
But CAMs are not so bad, if small, and as Ivan says it may be dealing
with 4 bitbelt numbers. (Or, they could do what we did in P6, and add a
pipestage to map belt numbers to positions in a static register file.
Or, better yet, to positions in a small register file at the output of
every execution unit.)

But, anyway: the Mill differs from many VLIWs in that it balances
dependencies as well as parallelism.

[Ivan Godard]

On 6/6/2013 6:04 PM, Andy (Super) Glew wrote:
> On 6/4/2013 11:53 AM, Ivan Godard wrote:
>
>> For maximum overall performance, the compiler schedules as tightly as it
>> can, so produced values are immediately used by consumers. This lets us
>> keep the belt short (use-before-lose),
>
> By the way, I think this is an interesting counterpoint to those who say
> the Mill is a VLIW.
>
> The classic VLIWs, and even the non-classic, like Itanium, had big
> register files. Sought parallelism. Dumped values into the register
> files to exploit parallelism. And suffered bloated instruction sets as
> a result.
>
> The Mill, with its belt, seldom has to encode a destination. Saves bits.

Never does, actually. Unless you include ops like store and spill, whose
whole point is to move a value to a destination. But never on the belt.

> The belt probably is implemented like a register file array. Worse, a
> CAM indexed register file array - CAMs because of its in-place renaming.
> But CAMs are not so bad, if small, and as Ivan says it may be dealing
> with 4 bitbelt numbers. (Or, they could do what we did in P6, and add a
> pipestage to map belt numbers to positions in a static register file.
> Or, better yet, to positions in a small register file at the output of
> every execution unit.)

There is no register file, neither shared nor at each FU. The physical
flops that hold belt values are distributed across the FU slots, with
one at each FU slot output register for each possible concurrent output.

For example, a slot configured with nothing but an integer ALU will
supports ops that produce one result after one cycle (a 4-byte add for
example), ops that produce one result after two cycles (a 64-bit add for
example), and ops that produce two results after two cycles (an
I-can't-mention-it-yet for example). Consequently this slot can retire
at most three results in any given cycle, one from a latency-1 op issued
the previous cycle and two from a latency-2 op issued two cycles ago.

Each of these retires has a dedicated hardware register (flops, not an
addressable register) built into the functional unit that acts as the
respective FU output register, just like on any other machine. The
collection of those registers over all slot and non-slot FUs comprises
the belt storage. All of these output registers are connected by a
forwarding network to all the possible FU inputs, of which there are
roughly two per slot. The network is a two-stage crossbar.

The latency-1 registers (i.e. the output registers used by latency-1
ops) are directly connected to the bottom crossbar stage and are few in
number. Consequently routing from a latency-1 op to any input passes
through only one (low end) or two (high end) 4-to-1 muxes, which happens
over the clock boundary. This lat-1 crossbar time, and the time of the
critical lat-1 functions like add, together define the Mill cycle time.

All other belt registers (the two lat-2 outputs in this example) go
first through the top crossbar stage (the lat-n crossbar) and then
through the lat-1 crossbar. The lat-n crossbar has many more inputs than
the lat-1 crossbar and so takes longer to traverse, but the data flowing
through it had already needed two or more cycles to compute so the
additional delay is less important.

All data steering occurs in the forwarding crossbar. We commonly
describe it as comprising a CAM in which each output register is tagged
with the belt position number of its contents. In this model, each
consumer asks for its input by position number (from decode) and the
CAM-like behavior forwards the selected data.

While conceptually simple to describe it as a CAM, in fact it doesn't
work like that. Decode knows what the upcoming operations want for
inputs, and by tracking the history of the flow of data it also knows
which register will hold which belt position in that cycle. Consequently
it can determine the correct mux steering bits during the last decode
cycle, and send them direct to the crossbar muxes with no lookup.

This approach still takes a cycle to figure everything out, which is
about the same amount of time that a CAM would take, but in the Mill
approach the figuring occurs in advance of production of the data rather
than afterwards, so there is no dedicated retire pipeline stage needed.
The figuring-out overlaps with the last decode stage, which we need anyway.

Philosophically our approach has the same goal as the predictive
forwarding that some OOO use, but the context and mechanism are quite
different, mostly because everything on the Mill is lockstep and we
never have to deal with replay (tornadoes), one-pipe stalls, or early out.

> But, anyway: the Mill differs from many VLIWs in that it balances
> dependencies as well as parallelism.

Or, perhaps, the Mill is similar to a VLIW in that it is wide-issue and
statically scheduled, but is otherwise unrelated.

[Ivan Godard]

On 6/6/2013 5:43 PM, Andy (Super) Glew wrote:
> On 6/3/2013 3:40 PM, Ivan Godard wrote:
>> On 6/3/2013 2:31 PM, Michael S wrote:
>>
>>> Actually, as long as the code resides in Decoded ICache, it would be
>>> technically very easy for Intel to feed Micro-op Queue with 5 or even
>>> 6 micro-ops per clock. The fact that they didn't do it in 3
>>> consecutive iterations of the uArch probably suggest that according to
>>> their simulations it wouldn't improve perf/Watt.
>>
>> I suppose it depends what "is" means :-) Seems to me that's just pushing
>> the decode bottleneck someplace else; they still can't decode five ops
>> into a decoded icache either.
>
> No, but *you* say, Ivan, that 80% of code is in loops. So you only have
> to decode the 20% irregularly, and then decode the 80% of instructions
> in a fast manner.
>
> Heck: Intel could use the MILL approach inside the decoded I$.

Fair enough. But Intel hasn't increased the decode bandwidth, whereas
they have when they could e.g. the twelve-wide decode on the new Itanium.

You know where the bodies are in the x86 if anybody does, so tell us:
assuming there were ILP to burn and you wanted to increase the
concurrency of an x86 OOO, where would be the first place you would hit
a limit as you scaled up the machine? If not decode, where? Forwarding
network? Rename? Load-store buffers? Pin bandwidth? Something else I can
only dimly comprehend?

Inquiring minds would like to know :-)

[Ivan Godard]

On 6/6/2013 5:50 PM, Andy (Super) Glew wrote:
> On 6/3/2013 6:37 PM, Ivan Godard wrote:
>
>> With all that, an ILP of three or so seems representative. A counting
>> artifact makes this lower than might be expected compared to a
>> hidden-pipe machine, because we expose and count the cycles when we have
>> nothing to do: if there is a data-dependent multiply with nothing else
>> to do until it finishes, the Mill must count the waiting no-ops against
>> ILP while a legacy has the same wait but doesn't count it.
>
> Huh?
>
> IPC = number of instructions divided by number of cycles.
>
> More importantly, number of useful instructions, not counting NOPS.
>
> It seems to me that what you say about NOPS would increase your ILP as
> measured by IPC, not decrease it.
>
> IPC is not the only metric for ILP. Some folks count number of ALU ops.
> Ideally, the number of ALU ups as measured on code compiled to minimize
> the number of ALU ops - i.e. no speculativ execution, no optimizations
> that replicate code.
>
> Perhaps the best metric would be derived from a visit count of lines of
> the original high level program, as executed by an interpreter.
>
> Plus, I must mention MLP.
>
>

All true, and illustrating how important it is to look at the
definitions behind any proffered numbers. In my case, I am counting
issued operations, which on a Mill includes one no-op in any cycle in
which there is nothing else to issue. The no-op is explicitly present
because the whole machine works in lock-step; if there is an in-flight
in the multiplier then it must advance to the next stage whether or not
something was issued in the cycle, so it is simplest just to always
issue something, even if the something is nothing.

On a machine that is full of buffers and queues this consideration of
the Mill is not meaningful. I was just pointing out that our counts
include some things that other machines (correctly for how they work) do
not.

What really matters is how well you own particular app does on
contrasting machines. Lies, damned lies, statistics, and benchmarks :-)

[Michael S]

On Jun 7, 5:27 am, Ivan Godard <i...@ootbcomp.com> wrote:
> You know where the bodies are in the x86 if anybody does, so tell us:
> assuming there were ILP to burn

Bold assumption. Esp. for legacy code base. Which is paying for bread
and butter.

> and you wanted to increase the
> concurrency of an x86 OOO, where would be the first place you would hit
> a limit as you scaled up the machine? If not decode, where? Forwarding
> network? Rename? Load-store buffers? Pin bandwidth? Something else I can
> only dimly comprehend?
>
> Inquiring minds would like to know :-)

What you mean by "scaled up the machine"? Widening front end + adding
more non-memory execution ports in the OoO part + widening retirement
stage? Or all of above + deeper OoO window? Or all of above + 3rd L1D
access port?

[nm...@cam.ac.uk]

In article <51AD643E...@sonic.net>,
Mark Thorson <nos...@sonic.net> wrote:
>Ivan Godard wrote:
>>
>> It's completely different between pipelined loops and open code. In
>> loops there is unbounded ILP available, ...

Er, no. That is true only for loops where each iteration is independent,
and that accounts for far fewer loops than most people realise. People
who teach OpenMP seriously have to spend a lot of time on that one!

>>
>> With all that, an ILP of three or so seems representative. A counting
>> artifact makes this lower than might be expected compared to a
>> hidden-pipe machine, because we expose and count the cycles when we have
>> nothing to do: if there is a data-dependent multiply with nothing else
>> to do until it finishes, the Mill must count the waiting no-ops against
>> ILP while a legacy has the same wait but doesn't count it.
>

>So the claim is 20 ILP on loops and 3 ILP
>on the straightaway. You have a simulator.
>Do you have a compiler, and are these numbers
>based on compiling examples of real applications?
>
>This is the most eyebrow-raising part of your
>presentation. You mentioned some work by Patt
>and Singh showing the ILP is out there, but
>I want to know whether you've seen that ILP
>on your architecture with your compiler and
>realistic applications.

Yes. I haven't looked at the presentation, and don't have time
to just now but, if that is the paper I think that it is, its
conclusions are unjustified. Sorry, but prescient oracles are
not implementable! If there is a mathematically decent paper
that shows the ILP is out there, I have yet to see it.

What a lot of people miss is that many of the programming
standards communities are doing their level best to eliminate
ILP. They don't realise it, of course, but I am one of the very
few people left who is saying that the combination of a largely
unconstrained serial specification model and deterministic results
is not compatible with high ILP.

ISO SC22 WG5 understands, but WG21/WG14 does not, nor does IEEE 754.
Guess which the majority of programmers rely on?


Regards,
Nick Maclaren.

[Michael S]

On Jun 7, 11:22 am, n...@cam.ac.uk wrote:
> In article <51AD643E.7D1F8...@sonic.net>,

>
> ISO SC22 WG5 understands, but WG21/WG14 does not, nor does IEEE 754.
> Guess which the majority of programmers rely on?
>

Neither?
Fortran is not popular and WG5 can do nothing about it.
'C' remains popular, but WG14 work mostly ignored. C89 is still a
leading standard.
WG21 is much more influential among real-world C++ users/implementors
than WG14 among 'C' user, but popularity of the C++ language itself
is way past its peak. I continue to like it, but I am rather old-
fashioned :(
IEEE 754 is implemented by compiler vendors and then ignored by
programmers that tend to have compiler switches like fast-math turned
on.

[nm...@cam.ac.uk]

In article <4ef43339-db1b-461f...@y5g2000vbg.googlegroups.com>,

Michael S <already...@yahoo.com> wrote:
>>
>> ISO SC22 WG5 understands, but WG21/WG14 does not, nor does IEEE 754.
>> Guess which the majority of programmers rely on?
>
>Neither?

Partly true, but misleading.

>Fortran is not popular and WG5 can do nothing about it.

Erroneous. Fortran has retreated to its heartland and remains
popular there. I expect it to outlast C++.

>'C' remains popular, but WG14 work mostly ignored. C89 is still a
>leading standard.

That is very true, but is very misleading.

>WG21 is much more influential among real-world C++ users/implementors
>than WG14 among 'C' user, but popularity of the C++ language itself
>is way past its peak. I continue to like it, but I am rather old-
>fashioned :(

What you have missed is that WG21 remains a dependent standard, and
much of its execution semantics is simply adopted by reference from
the C standard. Also, C++ is not the only standard and programming
interface that uses that practice, either explicitly or implicitly.

>IEEE 754 is implemented by compiler vendors and then ignored by
>programmers that tend to have compiler switches like fast-math turned
>on.

It is not, however, ignored by compiler and programming interface
developers. I am not saying that they follow it, but they DO use
it to downgrade optimisations.


Regards,
Nick Maclaren.

[Ivan Godard]

On 6/7/2013 12:43 AM, Michael S wrote:
> On Jun 7, 5:27 am, Ivan Godard <i...@ootbcomp.com> wrote:
>> You know where the bodies are in the x86 if anybody does, so tell us:
>> assuming there were ILP to burn
>
> Bold assumption. Esp. for legacy code base. Which is paying for bread
> and butter.

Of course, but an answer of "the limit is the parallelism exposed by the
usual program" isn't interesting. Pick something like hydro, and start
adding ALUs and FPUs to a standard x86 OOO superscalar - what pinches
first, if not decode?

>> and you wanted to increase the
>> concurrency of an x86 OOO, where would be the first place you would hit
>> a limit as you scaled up the machine? If not decode, where? Forwarding
>> network? Rename? Load-store buffers? Pin bandwidth? Something else I can
>> only dimly comprehend?
>>
>> Inquiring minds would like to know :-)
>
> What you mean by "scaled up the machine"? Widening front end + adding
> more non-memory execution ports in the OoO part + widening retirement
> stage? Or all of above + deeper OoO window? Or all of above + 3rd L1D
> access port?
>

Anything and everything that would result in better IPC given unbounded
available ILP in the program and the usual instruction mix of
general-purpose code, such that all instructions make forward progress
and none are deferred indefinitely.

[Ivan Godard]

On 6/7/2013 2:23 AM, nm...@cam.ac.uk wrote:
> In article <51AD643E...@sonic.net>,
> Mark Thorson <nos...@sonic.net> wrote:
>> Ivan Godard wrote:
>>>
>>> It's completely different between pipelined loops and open code. In
>>> loops there is unbounded ILP available, ...
>
> Er, no. That is true only for loops where each iteration is independent,
> and that accounts for far fewer loops than most people realise. People
> who teach OpenMP seriously have to spend a lot of time on that one!

You can pipeline loops with inter-iteration dependencies, so long as the
iteration interval is not itself varying, dependent and unbounded.If it
is fixed or even bounded then unroll the loop to the maximal interval
and pipeline normally.

Unpipeable loops exist but are rare. I doubt you could locate one in the
wild, although of course they are trivial to contrive.

[timca...@aol.com]

Er, in order walk of a tree structure?


- Tim

[Stefan Monnier]

> There is no register file, neither shared nor at each FU. The physical flops
> that hold belt values are distributed across the FU slots, with one at each
> FU slot output register for each possible concurrent output.

Aha! So in a sense it's a bit like a move architecture.

If you perform two adds in a row in the same FU, do you have to use the
first add's result before the second add terminates, otherwise the
first add's result is lost?


Stefan

[MitchAlsup]

On Thursday, June 6, 2013 9:27:22 PM UTC-5, Ivan Godard wrote:
> You know where the bodies are in the x86 if anybody does, so tell us:
> assuming there were ILP to burn and you wanted to increase the
> concurrency of an x86 OOO, where would be the first place you would hit
> a limit as you scaled up the machine? If not decode, where? Forwarding
> network? Rename? Load-store buffers? Pin bandwidth? Something else I can
> only dimly comprehend?

Marker bit technology has demonstrated that one can parse 6+ instructions per
cycle, after parsing, one can decode as many as desired. You may have to do
a prepass the first time instructions are encountered to set up the market bits
but after that, decode is not that much of a problem. {1-bit per byte overhead.}

I suspect if one really wanted to, one could add a second layer of marker bits
and parse as many as 20-odd instructions per cycle.

All of this instruction decode BW would then require crap-loads of ports into
the rename structure, which are not buildable in todays technology in my
opinion. In K9 we were going to use 22-odd ports into the register MAP and this
proved to be a big but not unsurmountable problem (from a decoded trace-based
instruction cache.)

In the end, power was the problem.

Mitch

[Ivan Godard]

Can't be vectorized, but is easily pipeable. Perhaps you are not
distinguishing between the two?

Ivan

[Ivan Godard]

On 6/7/2013 9:42 AM, MitchAlsup wrote:
> On Thursday, June 6, 2013 9:27:22 PM UTC-5, Ivan Godard wrote:
>> You know where the bodies are in the x86 if anybody does, so tell us:
>> assuming there were ILP to burn and you wanted to increase the
>> concurrency of an x86 OOO, where would be the first place you would hit
>> a limit as you scaled up the machine? If not decode, where? Forwarding
>> network? Rename? Load-store buffers? Pin bandwidth? Something else I can
>> only dimly comprehend?
>
> Marker bit technology has demonstrated that one can parse 6+ instructions per
> cycle, after parsing, one can decode as many as desired. You may have to do
> a prepass the first time instructions are encountered to set up the market bits
> but after that, decode is not that much of a problem. {1-bit per byte overhead.}

I agree that works (someone else here had the same suggestion), but it's
not what I mean by sustained decode. It's kind of like saying that you
can access memory in only three cycles sustained, so long as someone
else (that you don't count) has already moved the data to the L1 :-)

>
> I suspect if one really wanted to, one could add a second layer of marker bits
> and parse as many as 20-odd instructions per cycle.

Really? Can you expand a bit? I don't doubt you; I'd like a better
understanding of how it would work.

> All of this instruction decode BW would then require crap-loads of ports into
> the rename structure, which are not buildable in todays technology in my
> opinion. In K9 we were going to use 22-odd ports into the register MAP and this
> proved to be a big but not unsurmountable problem (from a decoded trace-based
> instruction cache.)

That's the data-side bottleneck, which is the subject of my upcoming
USENIX talk. Solving it was easier for us that the decode side
bottleneck, but a different team might have found the difficulties
inverted. We couldn't do crap-loads of rename ports either, so the
obvious thing to do was not to rename. Unfortunately, the only example
of wide issue without hardware rename was the Itanium, which does
compiler rename. That gives it crap-loads of ports into the architected
register file and 300+ registers to feed them, which doesn't work any
better.

So we wanted no software rename either. Rename exists to avoid spurious
hazard when register names are used as producer-consumer linkage rather
than as a kind of memory for multiple use. Split those usages, and all
the P/C links are just one-shot names, which can be handled with
single-assignment form with no hazards. Are there any SA machines? Of
course - a stack machine is SA, and hazard free.

But a stack machine is like an accumulator machine; it is inherently
narrow-issue because there is a single point of data availability. So
what you want is a whole pile of stack machines running in parallel and
able to reference each others' products.

We call it the belt.

Ivan

[Terje Mathisen]

Huh?

Pretty much every state-machine based processing engine I have ever
optimized ended up as a loop over data-dependent processing, with lookup
tables removing the need for (most) test & branch code.

I.e. my almost-but-not-quite winning Word Count code which looks for
transitions, so it needs some form of memory.

The actual processing speed is totally limited by load-to-use memory
latency.

Terje

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

[Andy (Super) Glew]

On 6/7/2013 4:48 AM, Ivan Godard wrote:
> On 6/7/2013 12:43 AM, Michael S wrote:
>> On Jun 7, 5:27 am, Ivan Godard <i...@ootbcomp.com> wrote:
>>> You know where the bodies are in the x86 if anybody does, so tell us:
>>> assuming there were ILP to burn
>>
>> Bold assumption. Esp. for legacy code base. Which is paying for bread
>> and butter.
>
> Of course, but an answer of "the limit is the parallelism exposed by the
> usual program" isn't interesting. Pick something like hydro, and start
> adding ALUs and FPUs to a standard x86 OOO superscalar - what pinches
> first, if not decode?

I haven't studied hydro in depth. How typical is it?

GCC tends to be my favorite. In gcc, the usual bottleneck is cache
misses or branch mispredictions.


There's lots of parallelism in gcc, but it tends to be a long way away -
between loops, rather than within loops. Between loops that call
functions nested deep, which themselves have many loops.

In some ways, gcc really should be a more parallel app - it is already
parallel per file in a Makefile. On a single compilation unit, it
perhaps could be parallel per (include) file, and once parsing is done,
parallel per function (assuming code generation is done per function,
with a subsidiary step for function inlining optimizations.

What are the Mill's GCC numbers?

BTW, gcc has changed a lot over the years. Netly, it seems to be
getting more parallel. It is fun to look at older gcc nuimbers versus
newer gcc numbers.


After GCC, any reasonable database app. (BTW, could somebody please
create a standardizable benchmark using sqlite? or some other open
source database? [*] SPEC probably won't do it or accept it, because
they will say "There are already plent of database benchmarks". But it
would be nice to see an open source database benchmark in wide use.
http://osdb.sourceforge.net/ is a start, but I haven't seen it in wide
use; plus, I would be happy to see one tweaked so that it was not I/O
bound, e.g. by operating on flash rather than rotating storage.)

(Heck, I suppose even PerlSQL could be a possibility.)

--
The content of this message is my personal opinion only. Although I am

an employee (currently Imagination Technologies, which acquired MIPS; in
the past of companies such as Intellectual Ventures/QIPS, Intel, AMD,

Motorola, and Gould), I reveal this only so that the reader may account

for any possible bias I may have towards my employers' products. The

[Ivan Godard]

No, there is no overwrite. Instead the data must be physically copied
someplace else in time that the adder result register can capture the
next result. Art invented the up-latency migration that makes this
tractable.

Recall that each function pipeline has an output register for each
different latency of the ops that can execute in that pipe; in the
example there were ops of two latencies, lat-1 and lat-2, so (ignoring
the two-result operation) there are two output registers, each dedicated
to one of the latencies. Recall also that decode can only issue one
operation per cycle to any one pipe.

So in your question, if we just got a lat-1 result into the register and
there is another one coming right away, those must necessarily be the
result of two consecutive lat-1 ops; two adds in a row, say. But if both
the prior ops were lat-1, then neither were lat-2, and there couldn't
have been a lat-2 op issued two cycles ago that is about to come out now.

Consequently, the lat-1 result we want to save can be moved to the lat-2
register, which is guaranteed not to be overwritten this cycle. The
present lat-2 register contents can be moved to the lat-3 register, and
so on up the latencies until we reach the longest-latency output
register of the FU pipe, which has to go somewhere else.

The up-latency register-to-register moves are unconditional and single
destination, so there is no control circuitry and no muxes; in effect
the output registers concatenate into a single longer shift register
that advances one step per cycle. Further, the individual registers are
close to each other, so the move takes little power.

Note that we don't have to actually spend the power to move the bits for
those operands that are still on the belt. We know whether a particular
output register is still on the belt because we keep the belt number
tags attached to the operands. By the time (6 cycles) that a lat-1
result has cascaded all the way to the lat-6 quad multiplier output
register it is very unlikely to still be on the belt. This saves power.

That takes care of the great majority of sources: instead of needing a
place for each source, which Andy expected would take a whopping big
multiport register file (and I agree), we only need to deal with one
value per FU pipeline rather than one value per FU. Thus any pipeline
with a FPU on it will have registers for latencies 1-6+, but we only
have to move one value per cycle somewhere else, not all seven at once
as would be required without the up-latency cascade.

We still have to deal with the "someplace else", albeit at lower
bandwidth due to the up-latency cascade (the bandwidth reduction depends
on the member-dependent distribution of latencies across the pipes, but
a factor of three is typical). "Someplace else" is a set of skid
buffers, logically organized as a compressible queue, that act as non-op
sources for the forwarding crossbar and also act as part of the belt
save/restore mechanism for interrupts and function calls. Because a long
sequence of no-ops will cause the whole belt to cascade to the skid
buffers, the number of buffers must equal the length of the belt, from 8
(low end) to 32 (high end) positions.

I have described the straight-forward, low power implementation, in
which the cascades advance every cycle whether the registers have belt
content or not, and always run off to the skids. It is of course
possible to replace the skid buffers with circuitry that moves a value
from the top of a cascade to a vacant register in the same or a
different FU pipeline. However that would be a many-source-many-sink
crossbar like the forwarding network itself, albeit with fewer sources,
and has its own costs. There are other possible implementations; the
whole thing is invisible to software, so the choice is up to the
hardware guys.

Summary: values on the belt are never lost until they fall of the end;
there is no register file; operands are moved around to make room, and
the move pattern is determined and so known to the decoder cycle that
does belt addressing; and the timing-critical forwards are those from
the lat-1 output registers and those have a shortcut through the
forwarding crossbar, while the other registers (and skid buffers if
used) have lots of time whether they hold a new latency-n result or a
previous lat-1 result that was cascaded.

Ivan

[Ivan Godard]

On 6/7/2013 11:53 AM, Andy (Super) Glew wrote:
> On 6/7/2013 4:48 AM, Ivan Godard wrote:
>> On 6/7/2013 12:43 AM, Michael S wrote:
>>> On Jun 7, 5:27 am, Ivan Godard <i...@ootbcomp.com> wrote:
>>>> You know where the bodies are in the x86 if anybody does, so tell us:
>>>> assuming there were ILP to burn
>>>
>>> Bold assumption. Esp. for legacy code base. Which is paying for bread
>>> and butter.
>>
>> Of course, but an answer of "the limit is the parallelism exposed by the
>> usual program" isn't interesting. Pick something like hydro, and start
>> adding ALUs and FPUs to a standard x86 OOO superscalar - what pinches
>> first, if not decode?
>
> I haven't studied hydro in depth. How typical is it?

Not trying for typical, because typical doesn't have unbounded ILP; the
question is not "where is the pinch in practice" for some practical
program. I was asking where is the limit which *no* program can exceed.

>
> GCC tends to be my favorite. In gcc, the usual bottleneck is cache
> misses or branch mispredictions.
>
>
> There's lots of parallelism in gcc, but it tends to be a long way away -
> between loops, rather than within loops. Between loops that call
> functions nested deep, which themselves have many loops.
>
> In some ways, gcc really should be a more parallel app - it is already
> parallel per file in a Makefile. On a single compilation unit, it
> perhaps could be parallel per (include) file, and once parsing is done,
> parallel per function (assuming code generation is done per function,
> with a subsidiary step for function inlining optimizations.
>
> What are the Mill's GCC numbers?

We are still quite a way from being able to run the gcc benchmark; no OS
or runtime system yet, for example.

[nm...@cam.ac.uk]

In article <5nj98a-...@ntp-sure.tmsw.no>,
Terje Mathisen <"terje.mathisen at tmsw.no"> wrote:

>Ivan Godard wrote:
>>>
>>> Er, no. That is true only for loops where each iteration is independent,
>>> and that accounts for far fewer loops than most people realise. People
>>> who teach OpenMP seriously have to spend a lot of time on that one!
>>
>> You can pipeline loops with inter-iteration dependencies, so long as the
>> iteration interval is not itself varying, dependent and unbounded.If it
>> is fixed or even bounded then unroll the loop to the maximal interval
>> and pipeline normally.
>>
>> Unpipeable loops exist but are rare. I doubt you could locate one in the
>> wild, although of course they are trivial to contrive.
>
>Huh?
>
>Pretty much every state-machine based processing engine I have ever
>optimized ended up as a loop over data-dependent processing, with lookup
>tables removing the need for (most) test & branch code.

Yes. That is one example of many.

Another is iterative methods, as in successive approximation
techniques, which includes Newton-Raphson, most root finders and
eigensystem analyses and so on.

But another, slightly more marginal one, is classic linear algebra
and similar tasks, where each iteration depends on a value returned
from the previous one.


Regards,
Nick Maclaren.

[Ivan Godard]

Looks like you too are equating pipeable and vectorizable. Not the same
thing.

In general, code of the form:
while (predicate(x)) x = arbitrary(x);
is pipeable but not vectorizable.

This doesn't take a Mill - you can pipe it on an Itanium too. For that
matter, if you use Lam's unroll trick in lieu of hardware rename support
then you can pipe it on any legacy (x86, ARM, Power, ...) too. Although
it is much easier on the compiler if the hardware was architected with
piping in mind, as both the Itanium and the Mill were :-)

Ivan

[Ivan Godard]

On 6/7/2013 1:13 PM, nm...@cam.ac.uk wrote:

>>
>> Huh?
>>
>> Pretty much every state-machine based processing engine I have ever
>> optimized ended up as a loop over data-dependent processing, with lookup
>> tables removing the need for (most) test & branch code.
>
> Yes. That is one example of many.
>
> Another is iterative methods, as in successive approximation
> techniques, which includes Newton-Raphson, most root finders and
> eigensystem analyses and so on.
>
> But another, slightly more marginal one, is classic linear algebra
> and similar tasks, where each iteration depends on a value returned
> from the previous one.
>
>
> Regards,
> Nick Maclaren.
>

Iterative methods only preclude piping when the *entire* computation, in
machine terms, is one linear (not branching) dataflow and the code is
not speculable. Such codes exist, but are surprisingly rare. Surprising
to me anyway :-)

Look at the machine code for a candidate loop, and see what an OOO
machine would do with it. If the OOO finds *any* opportunity to issue
more than one operation at a time then the loop is pipeable. Because
essentially that's what a software pipeline is.

Your definition may vary :-)