5 ms·
As to finding instruction boundaries with a variable-length instruction format: you could use the trick they use to start two instruction streams from a single
by Someone 11y ago
As to finding instruction boundaries with a variable-length instruction format: you could use the trick they use to start two instruction streams from a single address by using it for a stream of fixed-length instruction sizes running down that can be used to find the border in the stream of variable-length instructions running in the ’normal’ direction.
You could have:
offset : -----000000000111111
offset : 54321012345678901234
contents: 64212iijkkllllmmmmmm (digits are instruction lengths, letters are instructions)
So, reading offsets -1, -2, -3, etc. you read off the sizes of the instructions you can read in offsets 1, 2, 3, etc. If you have 4 decode units, you can replace the sizes of the instructions by their offsets, resetting the offset every 4th instruction.
With instruction sizes of 1-4 bytes, you could store instruction sizes in 2 bits per instruction. That would lower the pressure on your cache for the extra information you store. There also would be more space in your instruction set because you no longer would have to worry about creating an instruction that has a prefix that also is a valid instruction. For example, you could use 0x01 both for INC and ADD IMMEDIATE VALUE, where it means the former if the instruction length is 1, the latter if it is longer, with the size of the immediate determined by the size of the instruction.
Would that be a net win? I wouldn’t know, but it seems simpler (but ’simpler’ looks like a negative in their worldview) than creating those two streams that somehow must work together to do what a single statement sequence in the source code does.
- igravious 11y agoI don't really understand your solution, but then again I did not understand the Mill's solution. Can you explain it again? All I will say is that they seem to have really tried to simplify and regularize the Mill _except_ in the opcode stream / decode step where they say that two streams is optimal! Seems like it would be a nightmare and introduce all sorts of complexities. Was the only bit of the talk I didn't grok, whereas most others bits had me nodding my head and thinking "oh, neat".
- mike_hearn 11y agoThe Mill is designed to be fast, not simple. The split streams is more complicated but increases speed (or lowers power draw I guess).
- Someone 11y agoOK. Here's a simpler way to describe it: if every instruction starts with a bit sequence indicating the length of the instruction, you only need to read those bits to find instruction boundaries, but you still need to linearly scan the instructions to find, say, the 6th instruction. With this two-stream approach, you can split the bits that describe the instruction lengths from the bits that are the actual instructions, and move the former into the downward-moving 'CPU counter'. That way, you have a simple array containing those bits. That allows you to find the length of an instruction or, alternatively, its offset within its group in O(1) fashion. From another comment, it seems that doesn't solve the main problem, which is that, with variable-length instructions, you need the ability to shift about any contiguous sequence of bits from a cache line (worst case: cache lines) into an execution unit. That wouldn't be that hard, if it didn't have to be very fast, too.
- igodard 11y ago(Mill team) The streams are not streams of instruction; they are streams of half-instructions. The Mill is a wide-issue machine, like a VLIW or EPIC; each instruction can contain many operations, which all issue together. Each instruction is split roughly in half, with some of the ops in one half and some in the other. On the Mill, the split is based on the kind of operation and the info that ikt needs to encode: all memory and control flow ops on one side, all arithmetic on the other, although other divisions are possible. Each half is grouped with the same half of other instructions to make a stream, and the two streams decode together, step by step, so each cycle one instruction, comprising both halves, decodes and issues. The result is to double the available top level instruction cache, and cut in half the work that has to be handled by each of the two decoders.
- CarVac 11y agoThe twin instruction streams have the advantage in that the instructions are split between two completely separate caches that can have reduced latency relative to (total) capacity, bringing benefits in the case of branch mispredict.
- Veedrac 11y agoThat doesn't really solve the problem, and has several deficiencies. A split stream might seem complicated, but IMHO it's an amazingly clean way of simplifying the problem. --- The problem is not figuring out what sizes things are, but the routing. When you have 30+ instructions a cycle, you need to route a lot to a lot of different places. You also can't do a parallel read since the size of previous instructions affects the placement of the next instruction - you will eventually fix this with routing but it's not easy. Consider a 30-wide instruction. Decoding it involves knowing where in the instruction stream it starts. This can only be known once the prior instruction is partially parsed. Consider its later half - this can only be read after the first half is read. In your case, you actually only need to read the 2-bit prefixes but the difficulty remains. With a split instruction stream, since there are two independent (at least until a branch) program counters so you have twice the contextual information. You already know where the second half starts from the prior instruction. One more great thing about this is that the contextual information is preserved in jumps, without increasing the size of jump instructions. Even if prior instructions had metadata about splitting the next instruction for parsing (at yet more space wastage), this would be lost across jumps. That would worsen jump latency, which is a common bottleneck. The above point is way more important if you expect a flow instruction almost every bundle, due to the massive ILP the Mill has. --- > With instruction sizes of 1-4 bytes, you could store instruction sizes in 2 bits per instruction. However, the Mill does not constrain its instruction sizes to multiples of 8 bits. This means either you'd lose that bonus or you'd need even more bits. The Mill also splits which instructions are allowed in each half. Not only does this give you a free implicit bit, it again halves the amount of work for each decoder. This could probably happen with interleaved halves like you describe, but not without difficulty. > For example, you could use 0x01 both for INC and ADD IMMEDIATE VALUE, where it means the former if the instruction length is 1, the latter if it is longer, with the size of the immediate determined by the size of the instruction. Would that be a net win? The answer is no. The instructions codes are generated to be space optimal. I'm not sure how this is done, but it has been stated. They also leave it open for metadata like you mention to be included in each instruction stream, and in fact their blocks do have headers. > creating those two streams that somehow must work together to do what a single statement sequence in the source code does Given the instructions are disjoint and they only need synchronization at jumps, I would be very surprised if this was problematic.
- darkmighty 11y agoI don't understand why they don't use simply a prefix-free code, for example the Huffman code. You can have arbitrary length instructions at entropy-optimal efficiencies that way, and decoding in binary-tree fashion should be linear and very fast in hardware.
- infogulch 11y agoCould a prefix-free code work with all the instruction arguments like arbitrary 64 bit immediates? Perhaps you could have a separate argument stream but you still need to parse all the prior instructions to get the offset.
- darkmighty 11y agoNot my area of expertise, but in principle any set of instructions can be encoded into a prefix-free code (e.g. a binary argument just expands the set of instructions by a factor of 2). If both arguments have equal probabilities this simplifies to simply appending the argument as a prefix. If the probabilities are unequal, you can save bits (entropy) by bundling frequently occurring arguments together in the Huffman scheme, at the cost of increased decoding complexity. I heard bandwidth/cache sizes is a much greater problem than circuit area though. You are right that you need to parse all previous instructions to get an offset. Again, this is far from my area of expertise (first time I read about CPU design), but it seems this problem could easily be alleviated by slight modifications to Huffman codes, for example by setting "blocks" of instructions of certain sizes and assigning a prefix to each block containing the number of instructions in each -- you then can get offsets very quickly.
- JoeAltmaier 11y agoAnything is possible. But consider: Intel length-encoded opcodes for the 8086. Decades later, turns out they made bad choices. The shortest instructions (xchg r1, r2) are NEVER used. Compilers have changed; nobody codes much ASM any more. Its a crap-shoot.
- Veedrac 11y ago