Design of a SPECTRE-Resistant High-Performance CPU

[xfcemint]

Conclusion

For a selected execution semantics:
- it is either SPECTRE-proof or SPECTRE-vulnerable
- whether it is in-order or out-of-order is likely not a meaningfull distinction
- if an execution semantics is SPECTRE-proof, then there is no meaningfull distinction between the speculative perspective and nonspeculative perspective of the same execution semantics.
- execution semantics necessarily contains the description of the entire system: CPU, memory capacity, attached devices etc...

A selected execution semantics can likely (in my opinion) be viewed as being either out-of-order or in-order. Both views are just two perspectives on one execution semantics.

You can view a selected SPECTRE-proof execution semantics as either speculative or nonspeculative, it's just a perspective. A lot of caution has to be taken in CPU design because in the theoretical model, speculative instances do not communicate, but in the real world they usually do. If they communicate, the execution semantics changes. It immediately turns into some-thing mostly incomprehensible that can be called a SPECTRE-vulnerable execution semantics.

[xfcemint]

Corrections, ommisions, etc...

Previously I defined "rejected execution path" as: "an execution path that CPU was considering in the past, but at the initial branching point of the rejected execution path the CPU took a different execution path. Initial branching point of a rejected execution path is always on the accepted execution path."

It should be clarified that the initial branching point of a rejected execution path is not a part of the said rejected execution path. Therefore, rejected execution path has an initial branching point, but this point is not on the path, it only touches it. There is also a similar confusion in the definition of a "speculated execution path".

There could be a question whether DIRECTION bits are a part of the system state. I think that, since the amount of information in the system state should be calculated excluding the DIRECTION bits, then it is probably better to think of them as not being a part of a speculative instance system state. On the other hand, and to be more precise, the amount of information that the DIRECTION bits add to the system state is exactly zero; but then the amount of information in the system state should be more carefully calculated.

Another question could be about "modern CPUs" not performing but emulating speculative execution, how do I know that?
I actually used quite an inappropriate word there. They are not "emulating" speculative execution, they are actually mimicking it.
For a machine to correctly perform speculative execution implies that the machine is SPECTRE-proof.

[xfcemint]

So, what is speculative execution?

If you prefer a nonspeculative view of execution semantics, then it is a way of delaying a decision on a branching point.

If you prefer a speculative view of execution semantics, then it is the ability of a CPU+memory to create multiple instances of itself at branching points of an execution tree.

Regards,
xfcemint

=============== End of very mathematical discussion (hopefully) ===============

[xfcemint]

The above discussion about the meaning of the term "speculative CPU" implies that speculative execution has very little to do with execution semantics. Apparently, speculative execution is some property related to available storage capacity.

[xfcemint]

Also, the term "in-order" apparently has no distinctive meaning. It's just our imagination. All CPUs are in-order. Out-of-order CPUs don't exist, in my opinion, because execution semantics is always in-order.

Perhaps the term "out-of-order" can be perceived as a CPU design guideline (how to design a CPU), but not as a sensible difference between kinds of CPUs.

[xfcemint]

I think that some of the definitions I have written, and some of the phrases I have used are not exactly the most beautifully worded. Let's attempt to improve them:

Program: finite number of instructions organized in an execution tree valid by the execution semantics.

Total storage capacity of a nonspeculative CPU in a given system: The maximum amount of information that can be retrieved from the CPU to the attached memory after being stored to the CPU from the attached memory by any possible program.

Not every given system has a well-defined total storage capacity of the CPU, because the CPU can have a finite or an infinite storage capacity.

Let's correct the definition of implementable CPU to: in-order nonspeculative CPU that has a finite total storage capacity.

I am unable, at this moment, to think of a definition of some other sensible measure of CPU's information capacity. The implication is that there is a confusion in the definitions above. There is, apparently, no difference between implementable CPU and constrained-storage CPU. An implementable modern SE CPU does not perform speculative execution, instead it can be said that it emulates speculative execution.

Now it appears that the original definitions of SPECTRE-proof and SPECTRE-vulnerable CPUs were correct, and the new ones are just badly worded.

[xfcemint]

So, those definitions are actually incorrect, because an implementable CPU can have sufficient storage capacity to perform speculative execution (as modern CPUs do).

Let's correct those definitions:
A SPECTRE-proof CPU is a CPU whose external behavior in time can be implemented by a constrained storage in-order-nonspeculative CPU connected to the memory of the same capacity, same external reference timer and the same keyboard.

A SPECTRE-vulnerable CPU is a CPU whose external behavior in time cannot be implemeted by a constrained storage in-order-nonspeculative CPU connected to the memory of the same capacity, same external reference timer and the same keyboard.

[xfcemint]

Lets define implementable CPU as: in-order nonspeculative CPU that has a constant-size finite internal storage (but "hidden" and "delayed" bits are allowed).

Then this statement appears to be true: For every implementable CPU there exists a constrained storage in-order nonspeculative CPU that can emulate it (in the sense that external behavior in time and all I/O are the same, but the execution semantics may be different).

This is different then the 100% compatibility between nonspeculative CPUs and certain speculative CPUs that I have described earlier, because in that case the speculative and nonspeculative semantics were essentially identical.

[xfcemint]

Let's examine the validity of the two definitions I have posted earlier:

A SPECTRE-proof CPU is a CPU whose external behavior in time can be implemented by an in-order-nonspeculative CPU connected to the memory of the same capacity, same external reference timer and the same keyboard.

A SPECTRE-vulnerable CPU is a CPU whose external behavior in time cannot be implemeted by an in-order-nonspeculative CPU connected to the memory of the same capacity, same external reference timer and the same keyboard.

SPECTRE definition 1: A microarchitectural CPU design error that converts a SPECTRE-proof CPU design into a SPECTRE-vulnerable CPU design.

Let's define a constrained storage nonspeculative CPU as: a nonspeculative CPU that has internal information storage capacity constant in time and equal for any program, and exactly equal to the amount of information that can be transferred from it to the attached memory by any desired instruction sequence.

In other words: there are no "hidden", "unreadable", "purposeless" or "delayed" bits of information in a constrained storage nonspeculative CPU.

If all nonspeculative CPUs have constrained storage, then the definitions above seem to be meaningful.

Even if some kind of "branch in both directions" instruction is added to the execution semantics, it won't help, because the nonspeculative CPU has insufficient internal storage capacity to perform speculative execution.

[xfcemint]

The title of this thread is Design of a SPECTRE-Resistant High-Performance CPU

This thread so far demonstrates:
- every nonspeculative CPU is SPECTRE-proof by definition.
- for every imaginable nonspeculative CPU there exists a 100% compatible speculative CPU

Since all of today's real CPUs have nonspeculative predecessors, a new speculative CPU can be designed that is 100% compatible with a nonspeculative SPECTRE-proof predecessor of any modern CPU.

In other words, the desired SPECTRE-resistant CPU can employ speculative execution and remain SPECTRE-proof. This is a desirable property to be able to attain high-performance. As stated in the post #5:

D2) uses SE (speculative execution)