Execution

True, the analogy doesn’t stand up to such scrutiny 🙂

Your compiler is still responsible for Tail-Call-Optimisation to turn recursion into loops. The CPU does what it’s told.

Yes, Mill cascade is not the same as recursive tail-call, although the benefits are somewhat similar.

“permute” is an operation that supports general vector reorder, including element duplication. There are some specialized forms that do specific permutations at much smaller encoding cost.

Does the mill support (arbitrary) vector element swizzling?

Yes. There is a shuffle op for arbitrary rearrangements of a vector.

I’m just wondering if the same functionality that enables free pick might also allow free swizzles.

I believe its in the op phase.

I could see how it might be machine dependent due to different vector sizes.

Well, you can always use the remainder op to create a mask that you then pick against with 0s or Nones to create a partially filled vector? This was covered in the strcpy example in the Metadata talk and the Introduction to the Mill CPU Programming Model post.

Since shuffle is op phase and the pick phase is after the op phase (iirc), could shuffle+pick on a vector happen in a single instruction and on literal 0 or None? (That is, no explicit 0 or None vector needs to take up a belt position.).

I guess that would get what I was asking for, except you’d need a way to generate and park the vector to pick on, unless you can pick on a vector literal, if such a thing exists.

Function arguments are specified the same way as for operations except you can have up to 16 of them. They also return any reasonable number of results just like operations. See the first talk on instruction decoding.

The function gets a brand-new belt with all of its arguments loaded in order. I think that was described in more detail in the second talk.

Edit: I’m not sure if I actually answered your question about the mechanics of passing those arguments to functions in the assembly language. I don’t know if that has been specifically mentioned.

• This reply was modified 10 years, 10 months ago by  baking.

Ganging is supported on both sides. On the flow side, ganging is used for bulky arguments that don’t fit in the encoding of one slot. A Quad-precision pi constant, for example, needs three slots to supply 128 bits. This is also used for long argument lists for operations that use them, including call.

The value of N for N-way branches us determined by the number of branch functional units, not the number of operands on the belt. It is quite common for two branches to reference the same condition value, but with opposite sense:
btrt(b0, <then>), brfl(b0, <else>);

Not yet; there are still a few ops that are NYF.

Congratulations! A remarkably complete summary.

The short answer is that there are no issue constraints in your example. However, because you are issuing loads and expecting immediate retire then you will get several cycles of stall between the load and con instructions; that’s why deferred loads exist, see the Memory talk for details. The data cache cannot get you data instantaneously.

More generally however, the operation set and hardware have almost no issue hazards. “almost” being the operative word here. An example of an issue hazard that does exist is FMA. While you can issue an FMA every cycle in all slots that support it, if you issue an FMA now and then try to issue a plain FP add in the cycle when the multiply part of the FMA is done then both the add and the add part of the FMA will be trying to use the adder hardware in the same cycle; no dice. The hardware throws a fault if you try.

And currently that’s the only case.

Answering particular parts of your question where I can:

> Wow much of the selection of the current phasing setup was a result of the way the hardware works, and how much profiling actual code to see what would be useful in practice?

Well, definitely informed by code analysis. There’s an upcoming talk on Configuration, and its been described in the talks and in the Hackaday interview.

A central tenet of the Mill is that people building products can prototype custom processor specifications in the simulator very quickly and choose a configuration with the best power performance tradeoff informed by benchmarking representative code.

> With regard to calls, how many cycles do they normally take in overhead?

One. Calls and branches (that are correctly predicted) transfer already in the next cycle. In the case of mis-predictions where the destination is in the instruction cache, again the Mill is unusually fast; it has a penalty of just five or so cycles.

Additionally, there is is none of the conventional pre- and post-ambles.

This wouldn’t be a Mill architecture, but I wonder if there would be a problem with adding more phases and having different otherwise identical functional units do their work in different phases. For example, maybe read, pick1, op1, call, op2, pick2, write. I suppose that would induce limitations as to how quickly you could schedule instructions back to back, but it would make decoding easier for a given width. Were there other important benefits and limitations I’m not thinking of? Wow much of the selection of the current phasing setup was a result of the way the hardware works, and how much profiling actual code to see what would be useful in practice?

The phase structure is largely dictated by the encoding and the decode process. It takes three cycles to fully decode the extremely wide Mill instructions, but ops in some blocks are completed in each of those cycles and we issue them right way as soon as available; that gives us three phases. The pick op has no cycle, and the call op uses the cycle of the called function, which gives us five phases in all.

We could do as you suggest and have added phases with dedicated FUs. However, the ops for those phases would already have been decoded and would just be waiting for their phase, so why not issue them at once? We could of course go to a five-block encoding, which would take four cycles to decode, requiring another phase. However, three seems to be all that’s useful.

Assignment of ops to blocks (and hence phase) is ad hoc but guided by hardware constraints. For example, it is not possible to get the belt bypass set up in parallel with decoding the first (reader) block, so ops in reader phases cannot have belt arguments. Consequently the reader phase can only have pure-source ops or administration ops that do not take a belt argument. Reader phase also cannot have an op taking a large constant (such as the stackf frame allocation op) because the constant would wreck the entropy of the encoding of the other reader ops which are quite small.

• This reply was modified 10 years, 9 months ago by  Ivan Godard.
• This reply was modified 10 years, 9 months ago by  Ivan Godard.
• This reply was modified 10 years, 9 months ago by  Ivan Godard.

What happens if you have an FMA instruction but fail to also issue an Args? Or is it that the existence of an Args in an instruction turns the multiply operation into a FMA operation?

Am I right in guessing that which operations are connected to which in ganging is a result of which slot in the instruction the ops occupy?

Decode never needs to look at an adjacent slot to disambiguate an operations; needing to do so would complicate and slow down decode. Consequently FMA is a distinct opcode and not a mul-with-baggage.

The sanity check for ganging (at least on the exu side where these ops live) is done during execution. The FMA functional unit knows that it needs arguments from its buddy, but it has the execution cycle to work out whether or know it has a buddy with the right arguments. No buddy causes an invalidOperation fault, even though the decoder proper didn’t complain.

Gangs are always encoded in adjacent slots. Otherwise there are encoding issues and added data paths to get everything to the FU involved.

Good question. Its the former, and its done using naming, as you guessed.

Internally, each belt item has a frame id; this is how the CPU ensures the caller’s and callee’s belts are separate.

Operations mark their output belt items with the frame id their instruction was issued in. The spiller takes care of saving and restoring this in the background.

This was described in the Belt talk, about 30 minutes in.

Short answer: it’s all done in the naming.

Longer answer: the decoders map logical belt numbers in the code to physical belt numbers in the execution engine. There are twice as many physical numbers as the logical length of the belt, to accommodate drops that occur during phasing.

In your example of G cascading to F, say that G has a single result. Consequently the pre-existing belt value that would be b3 as an argument to G will be b4 as an argument to F (you see why hand-coding a Mill is not recommended 🙂 ). The decode hardware knows that G will drop one result (it’s in the encoding of the call op), so it adds one to the running logical-to-physical bias that it uses for the call of G to get the bias for the mapping for F. For a 16-long belt that’s only a 5-bit add, so speed is not an issue.

When a call returns, the physical belt is the same as it was before the call courtesy the spiller; a previously unoccupied physical position number is now filled with the result, but no existing values change physical numbers. The arguments of the second call are then picked up by their physical numbers (already available due to the mapping in the decoder), and copies made in free buffers. The copies are assigned physical numbers with the new frame number. Bump the frame number, and you’re good to go.

That’s what happens without cascading. It should be clear that it’s not actually necessary to reify the whole belt. All that is really needed is to assign the right physical number to the result of the first call, and to create copies of second-call arguments in the spiller with suitable numbers.

The spiller doesn’t really have time to do that if there’s no cycle between return and next call and it doesn’t get the I-need-this-list for the arguments until after the return. But the decoder already has the I-need-this list for the second call even before the instruction is issued, so it just gives the list to the spiller to save along with the rest at the first call. The spiller can then just do the copies as soon as it knows the return is happening.

There is actually a problem even with the advance notice if the return is conditional, because predicates are not evaluated until writer phase in the next cycle, which with cascading is actually the first cycle of the second-called function. We can go with the prediction and unwind if it is wrong, or simply not cascade conditional returns; its an implementation choice in the hardware, and members will likely differ.

We also have a way to do call arguments without copying, but it’s NYF.

Now for the rest of your question:

1) The return in a cascade goes direct to the next called function, delta the conditional-return case above.

2) Called functions start with no data stack frame; they must explicitly allocate one with stackf if they need it. Return does automatic cutback though. The called belt is created as described above – a call with no arguments need only bump the frame number and presto – new empty belt.

The return op itself has no understanding of what it is returning to. It does have an argument list, encoded just like the list of a call, that gives the belt positions of the result(s). Necessarily these will become b0… in the caller (returns drop at the front as usual), so all it needs is the mapping bias and the frame number of the returned-to frame. Change the physical belt number and frame of those values and the result handling is done. The bias and frame have been saved in the spiller. Hardware implementations will vary, but I expect that the result handling is done by the part of the spiller that does cascading, and the return FU deals only with getting the address and predicate right and dealing with First Winner Rule.

• This reply was modified 10 years, 8 months ago by  Ivan Godard.

No, it occupies one three-input slot in the same encoding block with writers (writerBlock). It is able to do so because pick is not actually moving any data, the way that copying bits to the input register of an adder does. Pick only controls the routing of the data going someplace else. There’s no real pick FU, in the sense of an adder FU.

The two-input block (exuBlock, adds and muls and such) does have real data movement and the wires to carry it. Real writers (not the pick that is encoded in the same block, put the pure sink operations that move data to the scratchpad or specRegs) have only one input. ReaderBloc operations (popular constants, specReg and scratchpad reads) have no inputs. And the whole flow side (control flow, memory) has an extremely ad hoc data movement pattern in which different slots can have different operand counts depending on what FUs are connected where.

It’s as regular as we can make it, but no more than that 🙂

Currently the highest fixed arity is four, in the fma family. However, many ops are polyadic with unbounded arity, such as call, and some ops have member-dependent maximum arity, such as conform. There are field extract and insert operations, similar to those of other machines.

As far as the specializer is concerned, add.eql (add and a predicate gang) is a single op that encodes in two slots and has two results. The emulation can replace both together with code that also has two results. There is no way to replace only the add with emulation and leave the eql as native, because the horizontal signals are not visible in the program model.

Diagrams are hard 🙂 I’ll try an explanation.

The phase of an operation (or the phase of a sub-action within an operation that is multi-phase, like store) is determined by explicit specification. The phases are reader, op, call, pick, and writer, and are evaluated/executed in that order; there are a couple more in the sim code for ease of implementations, but these don’t really exist in the hardware. There may be multiple instances of callPhase, one for each call in the instruction.

All ops must be decoded before they can be executed, and on the Mill decode takes more than one cycle, and some blocks in the instruction complete decode before others do. Consequently, it is convenient to place ops that must execute in an earlier phase so that they are in blocks that are decoded earlier too. Consequently readerPhase ops are placed in the block that decodes first, while writerPhase ops, while they could go in any block, are in practice placed in a block that decodes last because they are not in a hurry to execute.

The assignment of ops to blocks is also impacted by encoding format issues; slots in any block should contain only ops with similar bitwise format, for encoding entropy reasons and simpler decode. Thus the con operation, whose format is completely unlike the other readerPhase ops, is off in the same block with call (callPhase) and conform (writerPhase).

Now, as to the call op. CallPhase occurs after opPhase (when we do things like add). The physical belt changes only at cycle boundaries. To accommodate the intra-cycle logical changes of belt content, the physical belt is actually twice as long as the logical belt in the program model. If the code in the current frame C is F(a+b), where a and b are on the belt, then the add happens in the opPhase cycle, and the result is physically available at the end of that cycle. The result will be identified as C:b0, assuming nothing else drops, and the former C:b0 will become C:b1, C:b1 becomes C:b2, and so on.

Meanwhile, the hardware makes a copy of the result of the add and identifies it as F:b0, i.e. the first belt position in the called function. There are no other operands identified as F:bX, so the rest of the belt of the callee is empty. All this happens essentially at the cycle boundary, so that the first instruction of the callee sees the arguments and nothing else. In effect, callPhase is really that first callee instruction cycle. Because we go directly from the caller cycle containing the call to the callee cycle, the call in effect takes no time at all.

ReaderPhase is likewise free. After an opPhase op has been decoded, it takes a cycle to set up the crossbar to get the op its input data, so an add (for example) cannot execute immediately after decode, but instead there is an “issue” stage between the second decode and the execute stage. However, readerPhase ops do not take a belt argument, and so they don’t need a setup stage for the crossbar. So we can execute then in the same cycle in which the opPhase ops are getting ready for issue. So the timing is:

decode 0
decode 1
readerPhase execute/opPhase issue
opPhase execute
callPhase/first called instruction
… repeated
writerPhase (which is also opPhase of the next instruction and readerPhase of the one after that)

You happened to catch work in progress. The Wiki shows a periodically-updated snapshot of the actual specs for the members, and so may be internally inconsistent with reality at times as various things are being worked on. We still have no plans to have hardware div, rem, or divRem operations, but they are part of the abstract Mill and so the tool chain and sim must support them for eventual family members. Of course, to test the software we need a member spec that does define these ops, and Silver seemed to have gotten elected. I expect it will go away again.

Frankly, nobody has written the divide emulation code yet, so we have no numbers; it’s in the pipeline, but the emulation team has mostly been worrying about FP. If you’d like to help then feel free to post candidate code for div, rem, and divRem for the various widths. Remember that either or both inputs can be NaR/None. I do not expect there to be a loop; simply unroll the whole thing.

That said, the emulation substitution occurs at the start of the specializer where we are still working with dataflows, so if there is any code that is part of a different flow than the divide then the code will overlap.

Like I said, we haven’t done anything about it yet. As for the correct values, use the C/C++ standard for everything. For divide by zero, return NaR(undefinedValueNaR).

Things are tricky when the domain is signed and either or both arguments are negative; see https://en.wikipedia.org/wiki/Modulo_operation. Currently we do not have a mode argument in the spec for these ops, but we probably should; the natural candidate is the roundingCode attribute that FP ops use. The integral result would then be the value produced by an infinitely precise FP divide operation followed by the FP integerize operation, plus the Euclidean rule for the remainder. As far as I can see the available rounding codes provide all the sign rules demanded by the various languages listed in the Wikipedia article, plus some (nearest-ties-to-even for example) that don’t seem to be used.

I suggest that you see how far you get in unsigned, and when that gets through the specializer (you’ll write in genAsm) then we can revisit signed and decide whether to use roundingCode, a new attribute, or roundingCode with some enumerates faulting as undefined.

It’s OK to post your code here, although I’d suggest starting anew topic. Other readers/posters may chime in on your efforts; please be polite. When you have something that you believe works then either we will have published access to the tool chain for all or (if that’s still not done) we can NDA and let you use our servers.

You have permission, and can conduct your business here or on the Wiki as seems best to you.

In addition, you may propose novel helper ops beyond rdevu if you find the need, but please send the proposal for such an op to me directly first for vetting before putting it in the public space.

It seems you should use <pre> tags for code on the Wiki. I’ve edited it in.

Hardware div units are expensive and don’t pipeline well. On a microcoded OOO box that doesn’t matter much, but the Mill doesn’t microcode and is in-order. Other machines also use macrocode after a seed value, so we knew it was possible and would fit with the rest of the machine regardless of the algorithm, so we left the details to arm-waving until later. The emulation codes are like that in general: obviously software emulation of e.g. floating-point is possible, but it’s a rat’s nest that needs a specialist, so the details were deferred until we had a specialist.

We now have those specialists (Terje and Allen, and now Larry), so the arm-waving is being turned into code. Right now the bottleneck is genAsm. Speaking of which, I better get back to work 🙂

I’ll give you the best present most recent final word about GC, but must caution that we have not yet implemented a GC and this may not be as final as we’d like.

1) Pointers reserve three bits for use by the garbage collector; hardware knows this and for example does not examine these bits when testing pointer equality. There are a set of hardware masks that are checked when a pointer is used to access memory; the three bits index into the mask, or, when storing a pointer, the concatenated bits of the pointer being stored and the address being stored to are used as the index. If the indexed bit is set then the operation traps to software. With this, one can write a generation GC that does not “stop the world” because by setting the masks and allocators right one can get a trap whenever there is an up-generation store of a pointer and add the stored pointer to its roots.

2) There are several situations in which software must be able to access program state held in the spiller. GC is one such situation, but also debuggers and various statistics and diagnostics tools as well. System software presents a trusted API for such inspection; there is no direct access because spiller state is not in application address space. The API interacts with the portal call mechanism and permission granting. For example, if the app makes a portal call passing a callback function which the service then calls, and then takes a segv in the callback, the debugger will be able to inspect the state of the callback and of the app, but not the state of the service that is between the two (unless it requests and is granted permission for that address space too, of course).

The API only has bitwise access to the contents of the spilled data stack, but not the spilled control stack. The API provides enough information to construct a backtrace, but the debugger does not have direct access to return addresses, downstack links, and the rest of the call machinery; Mill is very attentive to matters of security.

3) GC and other software such as debuggers can get permissions to mutate saved state such as spilled pointers.