Pipelining

Hmm. Looks like we needed another slide.

The point about the retire op is that with it there is no prologue code any more. The whole thing – prologue, steady-state body, and epilog, is the same physical piece of code in the cache. If there were a conventional prologue these ops would be in instructions of their own, occupying cache of the steady-state body, that we need anyway, for the prologue too.

Yes, the ops that are logically “before the beginning” get executed, but they have no visible consequences and occupy no space that we wouldn’t use anyway. Yes, these ops do cost power – but they do not cost code space, which is a much more significant constraint in the big loops with low iteration counts typical of general-purpose code.

As for assembler, we agree with you that Mill concrete assembler (in which the programmer explicitly specifies the pelt positions of op arguments) is inhumane both to read and write If you have a program that you have written in concrete assembler then you can run it in the present simulator and see the belt contents and track them, instruction by instruction; the Specification talk shows this being done, live. We expect that a debugger on real hardware will provide a similar interface.

If you are writing in abstract assembler (specializer input, without belt assignments, as opposed to specializer output concrete asm) then there is no “current status of the belt” to view, because the code may be specialized for, and run on, different family members with different belt lengths and operation/instruction schedules. Only when these member-dependent aspects are blended into your abstract code – by the specializer – can a tool, or the hardware, know what is happening on the belt.

Unfortunately, while we are hard at work on the abstract assembler and specializer, they won’t be ready for some months yet. When they are, we are considering making them and the simulator available running on our servers from our web site, for anyone to play with. We’ll see. There are also some more distant plans – hopes, really – to provide a visual UI for the sim or debugger so the programmer can see the movement of data and events inside the running program, visually reminiscent of the animations in the talks. Not soon, though.

@larryp; yeah, an explicit “retire” seems like an another complication at first… Until you think about it. Kinda reminds me of the branch-delay slot in MIPS and DSPs, which need not be wasteful flushes.

cheers, – vic

@carvac; isn’t a blurring job better suited to a GPU?

cheers, – vic

Given that the Mill will be capable of operating on vectors, I’d expect the RGB pixel to be represented, at least on large enough members, by a single vector. I’m not clear on what operations might be available for vector shift and element access, that might be useful for filtering a stream of data.

I just realized that the blur in my algorithm only happens on a single channel array, so ignore all mentions of three colors. ::sigh::

That was used in another context of the same program, and it was actually faster than separate arrays for each color, at least on x86. It is a weird algorithm indeed.

My original question still stands, though.

The spiller has unlimited size, because under the buffering is all of memory. The constraining factor the spiller presents is bandwidth – high end Mills with big belt have a lot of state to save and restore. The top of the spiller, the part that connects directly to the belt and the rest of the core, has enough bandwidth to eat all the core can throw at it into buffer registers. The next level down is an SRAM, and there’s not so much bandwidth between buffers and the SRAM. The final part of the spiller, between the SRAM and the bottom level cache and thence to DRAM, has the lowest.

Any one of these steps can be overwhelmed if the core really works at it, just as the regular load-store bandwidth can be overwhelmed, on a Mill or any machine. Both spiller and the memory hierarchy are able to issue-stall the core if they need to catch up. The individual Mill members have the bandwidths sized so that stall is rare, part of the resource balancing that goes into the detail work on each family member.

Other constraints limit the practical length of the belt to avoid impact on clock or power. We know 32-long works, and we think 64-long may be practical for high-end throughput-oriented members with slightly lowered clock rates, but 128 seems unlikely.

For your blur, if those 60 are really 20 RGB vectors (as PeterH suggests) then they will fit in the 32-belt of the mid- and upper-end members. I can imagine a member with say 16 FMA units and a 32-long belt, although we are starting to get into GPU-land with that. If there really is a distance of 60 then code even on the high general-purpose 64-members are going to use the scratchpad and its rotators as a belt extension, and the spills and fills of the belt overflow part that doesn’t fit will wind up needing to be pipelined with the rest of the code. The good news is that the scheduler in the specializer takes care of getting the spill-fill right, you don’t have to do it.

In practice, the retire op has variants with arguments to cope with this and other implementation details.

Actually, it’s simpler even than Will says; I wish I could have gone into the mechanics in more detail, but the talks have time constraints.

It comes down the the fact that drops are always at the front of the belt, not at some slot index position as if the belt were an array rather than the FIFO that it is. Consequently the hardware must use a canonical ordering of drops so the software can ask for the values in the right place when it wants them later. That ordering is latency order: if a multiply (latency 3) and an add (latency 1) drop in the same cycle, the add will be at a higher position number (say b1) than the multiply (say b0).

The Nones that are dropped by retire are stand-ins for values that are in flight and haven’t dropped yet, and the reason they are in flight is because they are the result of a long-latency operation that hasn’t reached its steady-state yet. Consequently, the latency-order of drop says that the ones that haven’t dropped yet would have been at low belt numbers if they were in steady state. Consequently all the Nones from retire, no matter how many there are, will be in a block at the front of the belt, followed by any real retires, followed by the rest of the pre-drop belt.

Getting that to work without a special op to say where things should go is what makes Dave’s Device so clever IMO.

Will is right that there are two forms of retire. Recall that Mill operands have metadata tags telling the operand’s width and scalarity, which guide the functional units when the operands later become arguments to ops. Nones, including those dropped by retire, need width tags too. There is one form of retire that gives the desired widths explicitly. There is also another form that gives only a drop count, as shown in the talk, and that form drops Nones with a tag with an Undef width.

When an Undef width is later eaten by an op, the width is defaulted to a width that makes sense to that op, following defined rules, and the op’s result (always a None of course) carries the width that would have resulted from that default. However, for some ops the defaulting rules can result in a wrong width, different from what the real non-None would have done, that can screw up the belt for other operations. The scheduler in the specializer knows when that happens, because it knows what the desired width is, and when it detects that the default would be wrong it uses the explicit-width form of retire.

That would have been another ten slides and an explanation of width tagging, and there wasn’t time for it.

Sorry, NYF

We hope to have some of the hardware team give one or more talks on the gate-level hardware this fall. Don’t hold your breath for Verilog though

What to do when you run out of scratchpad:

The next and final level is “extended scratchpad”, in memory. The extended space is not (at present; some arguments) accessible to load/store, but uses specific spill/fill ops and its own allocator and a stack-like allocation regime. As with regular scratchpad, the extended spill/fill deal with operands, not bytes, and unlike memory but like scratchpad the operands retain their metadata. As a consequence, an extended spill/fill must double-pump the cache datapaths, once to get the operand data and once to get the metadata. Extended is cached normally.

Epilogue:

There are loop bodies where you have loop work that still needs to be done after a while-predicate has determined the that exit should occur. If you want to think about it, the general solution is to cause any data sources in the pipeline after the predicate to produce Nones. However, how to do that depends on the kind of source, some of which are NYF, and all really need pictures to explain what to do. We’re also not sure we have found all the cases yet.

Wiki:

Working to get the ISA Wiki doc mechanically generated from the specs.

Ivan wrote:

size of scratch in different members:
Copper: 128
Decimal16: 256
Decimal8: 256
Gold: 512
Maxi: 2048
Mini: 128
Silver: 256
Tin: 128

Ivan,

Thanks for that info!

In the bargain, we learn the names of four, previously unmentioned (so far as I’m aware) Mills. From two of those names, I’ll assume that there’s been some real interest in decimal floating-point capability. I wonder who/what market sector?

I find it interesting that Maxi has so much more scratchpad (4x) than a “mere” Gold. Is Maxi associated with the request (from Lawrence Livermore Labs, if I recall) about a supercomputing version? (The one that would have needed over a thousand contacts bonded out?)

Ran out of time; sorry. We hope to get a white paper out at some point.

It’s hard to explain without the animations, but the general solution recognizes that if the exit condition depends on (or can be scheduled to depend on) all non-speculable operations in the body then the leave operation (conditional on the exit condition) replaces the epilog.

That’s a perfectly reasonable implementation path for C++.

The compiler will still have to recognise it for what it is in order to know to use the Mill’s saturating opcodes in the emitted binary.

More generally, many uses of saturating arithmetic is in DSP and graphics programs which are often written in C.

Moreover, one would like a notation for literals, something like “17usl” for an unsigned saturating long, which cannot be done in either language even with overloading, and casts would be necessary.

Just FYI, Haskell has a nice solution for extensible literals without suffixes: All numeric literals are [implicitely applied](http://www.haskell.org/onlinereport/basic.html#numeric-literals) to an overloaded function fromInteger, which will be optimized away by the compiler when a concrete numeric type is known. So implementing all the saturated/signalling/etc. numeric types in Haskell together with overloaded arithmetic operations (the typeclasses already exist) would be really easy.

Of course, lazy evaluation is not everyone’s cup of tea. Sometimes I wish there was a C variant with a Haskell-style type system.

The Mill pipelining code in the middle-end will be contributed. However, we don’t expect there to be much. As I understand it, LLVM already does pipeline analysis, and we will use that. Our job will be to remove/bypass the LLVM code that actually does pipelinin transformations and simply pass on the fact that pipelining is applicable, and detected parameters such as iteration interval, to the specializer where the needed transformations will be applied.

The specializer is coming along nicely. LLVM is still to unfamiliar to project a schedule.

I thank you for your comments on dynamic language issues. They prompted internal design work that has led to a new approach for VMs on the Mill. NYF though

Well, now that you ask, I’ll go with “pedantic”

Yes, the total number of operations performed by a loop is the product of the number of operations per iteration and the number of iterations, which is finite if the loop ever terminates. Termination is in general undecidable but is assured for many loops of interest.

I prefer to avoid a 20-minute digression into the halting problem in a public general-interest talk. The point of the “unbounded” remark is to refute the widely bandied-about claim that MIMD (and width in general) is pointless because there is only 2X ILP in code. The data of the studies showing 2x is reasonable, but the interpretation of that data is misleading and the design conclusions are flat-out wrong.

Yes, there are loops with iteration counts so low (like, one) that the total operations count cannot fill a MIMD design. But by definition such loops are not where the program spends its time, and are irrelevant. The loops that matter all last long enough to be piped. More, they last long enough that no practical MIMD design can run out of iterations, so from the designer’s point of view, yes, they are unbounded.

The 2x claim has been used to hamstring designs in open, non-loop code also. From saying “there are only an average two operations that are independent of each other and hence can issue together” to saying “more than two pipe are wasted” is to assume that issue must be sequential. Open code on the Mill gets 6 operations in an instruction from 2x ILP code because phasing lets us have three steps of a dependency chain going at once. The 2x data is not wrong, but the conclusions from that data show a woeful lack of imagination.

One must distinguish pipelining from vectorization; the two are often conflated but present very different issues.

Essentially any closed loop can be scalar pipelined on a Mill, although it may not be worthwhile. Because the compiler does not have all the code available (due to specialize-time emulation substitution and inlining of external functions and templates) we must determine the applicability of SPL in the specializer; this is done after all the control-flow folding has been done and the code is ready to schedule. If-conversion (including pick) is done at this stage, as well as conventional control-flow simplification like jump-to-jump elimination. We also flop the sense of branches so that the fall-through case is the likely one (if profile info is available) or the longest path (which gives better schedules). We also recognize loops at this point, and replace exiting branches with leave ops and put an inner op in the loop head (the dominator that is the entry to the loop).

The heuristic for SPL is straightforward: we count the latency of one full iteration (following the dataflow of execution) as if it were straight-line code, and count the number of ops in that code in the various resource categories. Because we know how many resources (of each category) are present on the target, we know the minimal number of issue cycles that are needed if every op were completely packed into the available width. If the linear latency (following the dataflow) is twice or more the packed latency (maximal entropy) then we SPL. The “twice” is heuristic’ we could pack three linear into two packed, for example, but don’t have enough experience to know if it’s worth it.

Scheduling is pretty much the same as for open code, except that open code uses an extensible linear tableau to allocate slots to ops, whereas SPL uses a slice of the tableau that is packed-latency high and schedules it as a torus, with wraparound as it looks for free slots. The schedule is guaranteed to be feasible by the definition of the packed latency, but the placement is greedy and does not necessarily lead to a feasible placement (the bin-packing problem is NP). If it fails then the packed latency is increased by one and the whole mess is rescheduled. This is guaranteed to lead to a feasible placement, because eventually the increase in packed-latency will be enough for an open-code placement, which is always feasible.

Once placement is done, we calculate belt lifetimes of intermediates. This is the same as for open code, although we must distinguish the intermediates from different iterations that are simultaneously live. As with open code, those lifetimes are measured in terms of relative position on an infinite belt, rather than in terms of cycles, and if the relative position between producer and consumer exceeds the actual belt size then we insert spill and fill ops at the producer and the first consumer that needs a lost operand. There can be several of these of course. If this is the first spill/fill we add a rotate op at the top of the loop and put a scratchf op (scratchpad allocation) in the loop head; these get fixed up later when we know how much scratchpad will be used. If we added any spill/fill then we throw away the schedule and redo everything from the top with the modified code. This too is guaranteed to reach a feasible schedule, because the limit is for every produced value to be spilled and the belt reduced to a single position. In practice, one reschedule is needed ~20% of the time, two in single-digit percents, and we’ve not found any code that needs more.

The torus schedule is a normal schedule and may embed control flow, and represents the steady state. Any dataflow on the back arc to the entry point represents either a recurrence (for example the loop control variable) or a loop-carried temporary. The recurrences are those with a dataflow from the loop head (or earlier) into the loop; those with flows in from the head but not on a back arc are initialization, not recurrences. Initialization flows are handled like any other dataflow across a join point, and may require injection of a conforms op to get all the arcs into the top of the loop to have a congruent belt. Back-arc-only flows require creation of a None value in the loop head, which acts as an initializer just like explicit initialization. And true recurrences need both the initial value and the injection of a recurs op at the join. We could be smarter about recurs injection; it’s only needed if a None can reach the recurrence. Truth be told, there’s probably other cases where we could be smarter, but by and large the resulting code looks decent.

While SPL needs very little from the compiler and is mostly specializer only, vectorization needs a lot from the compiler. We need the compiler to tell us the iteration interval, the expected iteration count (if it can tell), and the strides of all recurrences. These are hard for the specializer to figure out, so we don’t try to recognize vector loops in the specializer, so far anyway. From the target description we know what the vector size will be for each reference, and from the iteration interval we can tell if that size is feasible or if we have intra-vector recurrences. There are ways to handle such recurrences in the lit, but don’t hold your breath. If it’s feasible we transform the loop to one that is still a scalar loop but where each “scalar” is a vector of the appropriate size; this involves scaling the control variable calculations. The smear operations for while loops are inserted at this point, and the trailing reductions when the loop yields a vector that must be reduced to a scalar. The result is just a normal loop, but with some funny operations in the code, and is scheduled (including SPL) normally.

Only some of all this is working as I write this; in particular none of what the specializer needs from the compiler is yet available. If you have compiler experience (especially LLVM) and are willing and able to put in significant time on a sweat-equity basis then send me a resume.

Sorry, NYF. There will be a talk on compilation as soon as we can get to it, expected to be in Seattle.