Superscalar Stack Processor: Details

The continuation of a series of articles exploring the idea of ​​a superscalar processor with OoO and the frontend of a stacked machine.
The topic of this article is the call of functions, inside view.

Previous articles:
1 - description of work on a linear piece
2 - function calls, save registers

Having concentrated in the last article on the outside of function calls, we lost sight of how all this will be executed inside. The author does not consider himself a specialist in hardware, but still anticipates problems.

We mentioned that after returning from a function, I want to get the processor in the same state as before it. And precisely for this, we were concerned about maintaining the state of the registers. But the state of the processor is not only registers. but also queues of mops, the state of pipelines ...

Imagine a situation when, at the time of the function call, we have:

• some mops in the decoder stack
• mops removed by the decoder from the stack but awaiting execution of the parent mops
• conveyor mops

As a result, you can’t just start executing a new function because

• for this, there may not be enough mops - those that remain from the parent function will not be released until we return from this
• the stack of mop indices in the decoder has a fixed depth and can easily overflow with recursion or just a long chain of calls
• mops in the pipelines will be executed after (after calling a new function) the numbering of registers is changed

It might seem that we took certain measures to avoid the described problems when we declared a function call with a generalized instruction, which should wait before the call to calculate all its arguments.

However, there is a problem with the fact that the decoder will have time to process the code after calling the function, if it is independent by data. For instance:

    int i, j, k;
…
    i = foo (i + 1);
    j += k;
    bar (i, j);

After returning from foo, we cannot rely on the fact that j managed to be calculated and saved (and then restored) in the context of the current task, nor on the fact that the mops from j + = k were preserved; if she didn’t have time to calculate.

Suppose, having seen a function call, the decoder stops its work until it returns from this function. Then what about this situation:

    int i, j, k;
…
    bar (foo (i + 1), j += k);

One decoder is not enough. It seems that after returning from the function, you just need to start decoding and executing further code again.

But after all, basically, these problems, caused by superscalarity, are not unique to our architecture, it may not be necessary to reinvent the wheel, but it’s worth looking at how it has already been solved earlier.

Ok, let's take a look at Intel's Sandy Bridge (thanks to Tasit Murka aka Felid )
and also here

Sandy Bridge.

Presumably Sandy Bridge frontend,

• the executable code enters the pre-encoder buffer (in the upper left corner of the circuit) from the cache of instructions of the first level (L1I)
• the precoder can process up to 7 instructions per cycle, depending on their combined length and complexity
• tagged teams fall into one of two queues (IQ) of teams - one per thread (hyperthreading), for 20 teams each
• the decoder alternately reads the commands from the queues and translates them into mops
• depending on the type of command, the decoder uses different types of translators
• decoding result goes to mops cache and two mops buffers (hyperthreading)
• cached aligned pieces (portions) of 32 bytes of source code, while:
  
  • the key is the entry point to the portion, if in one portion there were transitions to different places, this portion will be propagated in the cache
  • portion decoding starts at its entry point
  • only portions that spawned no more than 18 mops are cached - 3 lines of 6 mops each
  • instruction divided by the border of two servings relates to the first of them
  • from a portion it is allowed to have no more than 6 transitions, only one of them can be unconditional - and the last at a time. This is important because a function call is an unconditional transition and everything that happens after it does not fall into the current caching unit, which means it will not be executed until we try to go back.
  • if the portion does not end with an unconditional jump, there is a transition to the first instruction of the next section at the address
  • Mops cache (L0m) is synchronized with L1I, the last line of the cache is 64 bytes, so when the line L1I is pushed out, everything about two portions is deleted from L0m
  • just curious, L1I works with physical addresses, L0m works with virtual
• As for speculative execution:
  
  • transition predictor (BPU) is able for the conditional transition mop to report the probability of occurrence of the event of this transition
  • because in the current queue of mops, the decoder has already identified all potential transitions, you can check them
  • if the transition probability is high enough, it makes sense to preload the right portion of the code and execute it speculatively
  • if the transition really happens, we will get at least a decoded portion of the data, perhaps some of the instructions (which do not have data dependencies) will succeed
  • if there is no transition, instructions that have not yet been executed should be discontinued, those that have worked out should not cause irreparable consequences. All captured resources are freed.
  • which means that they will be executed in a special speculative mode:
    
    • write to memory should be delayed
    • reading from memory is carried out only if the data is already in the data cache, otherwise execution is blocked (in order to avoid useless cache misses and subsequent access to the swap)
    • everything that can cause an exception (division by 0, for example) is marked accordingly and is also blocked, however, this is a generalization of the previous paragraph. Now, when the transition occurs, we can honestly restart blocked mops
    • and, of course, it’s worth recalling that all these are just assumptions, only Intel knows the real picture

How is the function called?
Let's look at the following example.

int i, j, k, l, m, n;
...
i = 1 + foo (1 + bar (1 + biz (1 + baz (1 + j) + k) + l) + m) + n;

We will be naive to assume that all this code will fit in one 32 byte chunk and the order of code generation (with the optimizer turned off) will correspond to the order of the text. Let's mark the code according to which instance of the section it falls into the L0m cache:

int i, j, k, l, m, n;
...
1>    i = 1 + 
4>            foo (
1>                   1 + 
3>                            bar (
1>                                   1 +  
2>                                            biz (
1>                                                   1 +  
1>                                                            baz (1 + j) 
2>                                                   + k) 
3>                                   + l) 
4>                    + m) 
5>         + n;

This snippet will apparently occupy 5 cache lines out of 256 available.
Not surprisingly, the compiler is struggling to inline small functions.

conclusions

So, we looked at how functions are called in one of the very sophisticated micro-architectures, what benefit can be drawn from this?

We highlight the objective points:

• An instruction cache is needed, without this no intelligible processor is possible.
• The cache is granular, at the moment the typical size is a string of 64 bytes.
• Decoding (for x86_64, at least) is a rather expensive operation, it makes sense to cache the decoded code in the form of strings of mops
• Access at the entry point is a great idea, is it possible to do without duplication of records - the implementation issue
• No more than one mandatory solution - a simple and natural solution, eliminating a lot of problems

It may seem that all this will work for our architecture with a stack frontend. But there is a nuance.
Let us illustrate with an example. Here is the Ackerman function :

int a(int m, int n)
{
    if (m == 0)
        return n + 1;
    if (n == 0)
        return a(m - 1, 1);
    return a(m - 1, a(m, n - 1));
}

It looks simple, but demonstrates the wonders of recursion. The following graph shows the dynamics of the nesting depth for the call a (3, 5), with x the step number, with y the call depth.

Since we decided to consider the function call as a generalized instruction with an arbitrary number of parameters, in the case m * n! = 0, the first argument (m-1) will remain on the stack of mops, while the second argument will be calculated: a (m, n- 1). Well, if the first argument has time to calculate and its value will be stored when called in the register stack. But it may happen that the expression for the first argument will be evaluated longer than the arguments of the child call in the second argument. And then at us in considerable quantities malfunctioning mops hang up.
The parent call mop will also wait until the child call has completed. The depth of calls can easily reach (tens) of thousands of units, in SandyBrige, for example, there simply aren’t as many mops.

The essence of the problem is that, recognizing the call as a generalized instruction, we thereby recognized the program as a generalized expression. And the tree of this expression due to recursion can be of any height. On the other hand, our expression stack is limited. And the stack elements are indexes of mops, of which there is also a limited number.

But we are not used to giving up so easily, so plan B. comes into play.

Plan b

Superscalar register processors have no such problems since the identification of connections between mops occurs later - at the stage of renaming registers.
In our country, these relations are stored in the stack of indexes of mops.

Maybe save the state of the stack? It’s not enough to maintain indexes of mops, as we found out, mops themselves also need our care. It seems natural to organize the preservation of mops through the stack, allocated or not, the question is completely separate.

And here we are faced with the same problems that we encountered when trying to save the registers. Namely, with a single (for all functions) identification of mops:

• the order of use of mops depends on the background of calls
• inside a function, it is defined dynamically
• there is no guarantee that after the FILL operation we will not get a conflict with the already occupied mop

The way to solve these problems is the same:

• ring buffer mops
• each function has its own numbering of mops, for example, 0 ...
• FILL and SPILL are made for the whole function, which allows, if necessary, to bind the register stack and the stack of mops to one memory area
• FILL and SPILL are made only for mops awaiting completion, therefore, the mask (or enumeration) of serialized mops is also placed on the stack
• the stack of indexes of mops, we must also save

At first glance, the need to drive decoded mops through memory seems monstrous. But when the catecholamines burn out, it becomes clear that the scale of the disaster is not so great.

1. although in modern processors the parameters (at least part of them) are transmitted through the registers, with a recursive call there is nowhere to save the parameters, except on the stack, in addition:
   
   • return address and frame pointer are also stored on the stack
   • volatile registers are stored on the stack by the caller
   • non-volatile registers are also stored on the stack, but by the called party
2. expressions like 'a (m - 1, a (m, n - 1))' the compiler can break up by introducing (explicitly or indirectly) a temporary variable equal to a (m, n - 1). This reduces the number of mops that need to be saved.
3. all failed conditional branches by the time of the unconditional transition, which is a function call, we already threw
4. all mops for the upcoming challenge, we can also throw them out or just not load them, using a technique similar to that in SandyBridge
5. but we can leave it, then upon returning from the function, we get a bonus, ready for execution, or already partially executed (data independent)
6. in the most "economical" version, only one serialized call mop gets on the stack, and this is not much different from sending a frame-fuffer address, for example
7. (de) serialization of mops does not look like a costly operation, in addition, it can be performed in the background, in advance, without blocking the current return from the function
8. saving mops on the stack along with loading is supposed to be an alternative to the l0m cache, which is now simply not needed
9. the size of the serialized mop is not too large, for SandyBridge the initial mop size is estimated at a maximum of 147 bits, in compressed form - 85 bits (and there are x87, SSE and AVX of all stripes)
10. the fact that the technological features of the processor are becoming accessible from the outside and any technical secrets can be compromised does not scare the author. In the end, let the processor xor this data with a one-time pad.

What's next

So far, we have not paid attention to the weak point of all stacked machines - excessive memory accesses.
So we will deal with them in the next article .