Hacker News Reader

Comment by unwind | Hacker News Reader

My only exposure to Mill (besides this page link) has been random comments in various stories here over the years.

They typically start with ("Mill team"), and then the rest sounds like it came from the future. It's all about getting the flux capacitors charged.

Can anyone post some low-level code (in assembly, or the closest equivalent if that term is no longer relevant with Mill) implementing some well-known simple algorithm on the Mill? Just to quickly get a feel of what it's all about, how it looks.

Something like computing n! for word-sized integers, or strcmp(), or whatever.

Does anyone have a quick link to something like that?

View on HN

I think this would implement factorial. I can't remember some of the specific mnemonics, but this is the gist:

        # entering factorial: argument n is b0
        # drop initial accumulator to belt; bail early if n==0
        con(1), cmpeq(b1, 0), brtrue(end);
        # now, b0 == 1, b1 == n
    loop:
        # multiply accumulator by n, then decrement n, then check if n stil not 0
        mul(b0, b1), sub(b1, 1), cmpeq(b1, 0), brfalse(loop);
    end:
        # no matter what, the most recent accumulator is b0
        ret(b0);

ConAsm (model-dependent assembler) for "Silver" model:

F("fact") %0; sub(b0 %0, 1) %1;

        gtrsb(b0 %1, 1) %2,
          retnfl(b2 %0),
          inner("fact$1_1", b1 %1, b2 %0);

L("fact$1_1") %3 %4;

        mul(b1 %3, b0 %4) %5;

        sub(b0 %4, 1) %6;

        gtrsb(b0 %6, 1) %7,
          retnfl(b1 %5),
          br("fact$1_1", b2 %6, b1 %5);

Note that integer multiply is specified as 3 cycles in this model, so the recurrence in the loop takes three cycles. Other ops are one cycle. Each semicolon is an instruction (and cycle) boundary, ops separated by commas issue and execute together.

Ah, of course. I've watched your videos so much, how could I have forgotten that multiply is 3 cycles? Thanks for chiming in!

Well, the Mill uses a skewed, exposed pipeline VLIW ISA so reading the assembly isn't going to be a picnic. I'd recommend either listening to the talks, which are interesting whether the whole thing works out or not, or looking at the wiki.

https://millcomputing.com/technology/docs/

http://millcomputing.com/wiki/Main_Page

Well, there's a couple of pieces of sample code on comp.arch in google groups / usenet. Sadly, I can't find any examples of genAsm anywhere, but a couple of fragments of conAsm. Maybe that's better, as conAsm is what's going to actually run.

This tread for example, talks about instruction density of Mill programs. Mill does somewhat poorly, with a pre-alpha quality compiler doing the codegen; https://groups.google.com/forum/#!topic/comp.arch/RY3Bk7O61u...

Comparing several ISAs on the simple program in the first post, a Mill Gold CPU binary weighs in at 337 bytes (and 33 instructions), compared to:

* powerpc: 212 bytes, 53 instructions * aarch64: 204 bytes, 51 instructions * arm: 176 bytes, 44 instructions * x86_64: 135 bytes, 49 instructions * i386: 130 bytes, 55 instructions * thumb2: 120 bytes, 51 instructions * thumb: 112 bytes, 56 instructions

Mind you, the Mill's split-stream instruction decoding means each decoder only has to deal with ~168 bytes and ~16 instructions, and there's a cache for both (I think?).

GenAsm for the factorial function (conAsm in a different reply, above): define external function @fact w (in w) locals($3, %9, &0, ^6) {

label $0:

    %1 = sub(%0, 1) ^0;

    %2 = gtrsb(%1, 1) ^1;

    br(%2, $1, $2);

label $1 dominators($0) predecessors($0, $1): // loop=$1 header

    %3 = phi(w, %5, $1, %0, $0);

    %4 = phi(w, %6, $1, %1, $0);

    %5 = mul(%3, %4) ^2;

    %6 = sub(%4, 1) ^3;

    %7 = gtrsb(%6, 1) ^4;

    br(%7, $1, $2);

label $2 dominators($0) predecessors($0, $1):

    %8 = phi(w, %0, $0, %5, $1);

    retn(%8) ^5;

};

Higher-end Mill models have more and bigger things to encode, and so a given program will occupy more bytes than it will on a lower-end member. Thus a belt reference on a Gold is 6 bits, but only 3 on a Tin.

Consider the CPU as a pile of ALUs, FPUs, load & store units, internal buffers, and the like. Each "instruction" is a variable-size set of parallel instructions, directing which output goes into which input for various stages of that clock cycle.

The layer that humans and HLL compiler developers end up with at the lowest seems to resemble a dataflow graph, and the system-specific code converts that into the parallel binary code stream.

The notion of the "belt" helps arrange how long data sticks around in live outputs & buffers, but isn't a physical element in the chip.

Yes

In one of their talks they show what strcpy would look like on the Mill: https://youtu.be/DZ8HN9Cnjhc?t=3416

Ah, always with the lectures. :) So, the code for strcpy() on the Mill seems to be:

    load    *src, bv
    eql     <load>, 0
    smearx  <eql>
    pick    <smearx0>,None,<load>
    store   *dest, <pick>
    brfl    smearx1, loop

This "vectorizes" a plain while-loop by loading as "byte vector". The size of the vector depends on the exact Mill family member implementation's choices, but is at least 8 according to the lecture. The lack of actual register names is of course a loud signal that the Mill is different.

Pretty cool, and I feel like I learned something. Thanks!

I refrained from posting the direct assembly, as without the talk the smearx and pick would be meaningless.

If you also look a bit further into the talk they show the 'remaining' instruction, which allows you to do this same thing with fixed-count loops.

From the talks, Mill assembly is ill-defined, it varies a lot from model to model. They have an intermediary representation, that I think is more like JVM bytecode than assembly, but I don't think they ever showed what it looks like.

Reply on news.ycombinator.com