Search code examples
algorithmassemblyknuthtaocpmmix

Purpose to set to 0 least significant bits in MMIX assembly with memory operations?

In the documentation to MMIX machine mmix-doc page 3 paragraph 4:

We use the notation to stand for a number consisting of consecutive bytes starting at location . (The notation means that the least significant t bits of k are set to 0, and only the least 64 bits of the resulting address are retained. ...

Solution

  • The notation M2t[k] is just a formal symbolism to express an address divisible by 2t.

    This is confirmed just after the definition

    All accesses to 2t-byte quantities by MMIX are aligned, in the sense that the first byte is a multiple of 2t.

    Most architectures, specially RISC ones, require a memory access to be aligned, this means that the address must be a multiple of the size accessed.
    So, for example, reading a 64 bits word (an octa in MMIX notation) from memory require the address to be divisible by 8 because MMIX memory is byte addressable(1) and there are 8 bytes in an octa.

    If all the possible data sizes are power of two we see a pattern emerge:

    Multiples of     Multiples of     Multiples of
   2                 4                 8

 0000               0000              0000
 0010               0100              1000
 0100               1000
 0110               1100
 1000
 1010
 1100
 1110

    Multiples of 2 = 21 have the least bit always set to zero(2), multiples of 4 = 22 have the the two least bits set to zero, multiples of 8 = 23 have the three least bits set to zero and so on.

    In general multiples of 2t have the least t bits set to zero.
    You can formally prove this by induction over t.

    A way to align a 64 bit number (the size of the MMIX address space) is to clear its lower t bits, this can be done by performing an AND operation with a mask of the form 

    11111...1000...0
\      / \    /
 64 - t     t

    Such mask can be expressed as 264 - 2t.

    264 is a big number for an example, lets pretend the address space is only 25.
    Lets say we have the address 17h or 10111b in binary and lets say we want to align it to octas.
    Octas are 8 bytes, 23 so we need to clear the lower 3 bits and preserve the other 2 bits.
    The mask to use is 11000b or 18h in hexadecimal. This number is 25-23 = 32 - 8 = 24 = 18h.
    If we perform the boolean AND between 17h and 18h we get 10h which is the aligned address.

    This explains the notation k ∧ (264 − 2t) used short after, the "wedge" symbol ∧ is a logic AND.
    So this notation just "pictures" the steps necessary to align the address k.

    Note that the notation k ∨ (2t − 1) is also introduced, this is the complementary, ∨ is the OR and the whole effect is to have the lower t bits set to 1.
    This is the greatest address occupied by an aligned access of size 2t.
    The notation itself is used to explain the endianess.

    If you wonder why aligned access are important, it has to do with hardware implementation.
    Long story short the CPU interface to the memory has a predefined size despite the memory being byte addressable, say 64 bits.
    So the CPU access the memory in blocks of 64 bits each one starting at an address multiple of 64 bits (i.e. aligned on 8 bytes). Accessing an unaligned location may require the CPU to perform two access:

    CPU reading an octa at address 2, we need bytes at 2, 3, 4 and 5.

Address    0 1 2 3 4 5 6 7 8 9 A B ...
           \     / \     /
              A       B

CPU read octa at 0 (access A) and octa at 4 (access B), then combines the two reads.

    RISC machine tends to avoid this complexity and entirely forbid unaligned access.

    (1) Quoting: "If k is any unsigned octabyte, M[k] is a 1-byte quantity".

    (2) 20 = 1 is the only odd power of two, so you can guess that by removing it we only get even numbers.