So, I am now using Tomasula’s algorithm for my Thor processor to get OoO
operation. It looks like it should help hiding memory latency and other long running operations. Ordering is being controlled by sequence numbers rather than the buffer position, so instructions may be queued into any open buffer slot. It does not work as a circular buffer as is done in some designs.. There are four stages to the design, Fetch, Decode, Execute, and Write-back. There is a separate scheduler for each stage. Memory operations are strictly ordered, there are bits set aside in control register zero to allow more relaxed memory ordering.

Thor is using a 128-bit data-path mainly to support quad precision decimal floating-point. But the data-bus to registers is up to 512 bits to allow four registers to be updated or read at once.

I am considering adding a random element to the schedulers, so processing may be in a different order from one run to the next. The idea is to make the processor a little bit less predictable.

Also in consideration is encryption of the instruction set. It would not take much to have a simple decryption stage in the core. Installed software would need to use the correct decryption key to get a program to run. The idea is to make every installed base of software binary incompatible.

robf...@gmail.com wrote:
> So, I am now using Tomasula’s algorithm for my Thor processor to get OoO
> operation. It looks like it should help hiding memory latency and other long running operations. Ordering is being controlled by sequence numbers rather than the buffer position, so instructions may be queued into any open buffer slot. It does not work as a circular buffer as is done in some designs.. There are four stages to the design, Fetch, Decode, Execute, and Write-back. There is a separate scheduler for each stage. Memory operations are strictly ordered, there are bits set aside in control register zero to allow more relaxed memory ordering.

Where are the uOps stored if not a circular buffer?
How is that indexed?
How does that do checkpoint/rollback which requires
removing instructions from some mid point to the end?
How does that do Retire?

On Thursday, April 7, 2022 at 8:55:34 AM UTC-4, EricP wrote:
> robf...@gmail.com wrote:
> > So, I am now using Tomasula’s algorithm for my Thor processor to get OoO
> > operation. It looks like it should help hiding memory latency and other long running operations. Ordering is being controlled by sequence numbers rather than the buffer position, so instructions may be queued into any open buffer slot. It does not work as a circular buffer as is done in some designs.. There are four stages to the design, Fetch, Decode, Execute, and Write-back. There is a separate scheduler for each stage. Memory operations are strictly ordered, there are bits set aside in control register zero to allow more relaxed memory ordering.
>
> Where are the uOps stored if not a circular buffer?
> How is that indexed?
> How does that do checkpoint/rollback which requires
> removing instructions from some mid point to the end?
> How does that do Retire?

There are no uOps as most instructions are too simple, and it is a load / store architecture. The instructions are the micro-ops. Instructions are directly stored in any empty slot in the buffer until they are decoded. There are however macro instructions like PUSH, POP, ENTER and LEAVE used to improve code density which are composed of a list of regular instructions. These are stored in a table with its own micro-program counter. Since they are just regular instructions, the micro-program counter is stored in the link register along with the program counter, which allows the instructions to be interruptible. At least in theory. I have not got interrupts tested and working yet. They may work but it is not tested. TLB miss seems to work as that has been run into during testing.

The buffer has a separate index for each of Fetch, Decode, Execute, and Write-back. The index value moves around to where it is needed. They do not increment or decrement.
The rollback uses the sequence number associated with the instruction to determine which instructions to remove. If the sequence number is greater than that of the branch instruction then the instruction will be removed. This works similar to a branch tag only with more bits. It does not matter where in the buffer the instruction is. It does not remove from midpoint to end.. All instructions in the buffer are scanned for their sequence number.

Retirement works by retiring the instruction with the lowest sequence number in the buffer, once it is finished executing.

*It may not be the most hardware efficient solution, but it seems to work. Its more of a pedantic solution. It is easier for me to understand. I was getting a headache trying to fathom how the circular buffer works with rollback. It has a couple of advantages, no logic is required to adjust head and tail pointers, rather its part of scheduling. No need to worry about having consecutive buffer slots to process retirements.
Gets far enough in simulation to activate LEDs, running about 800 instructions, using an eight-entry buffer.

I am tempted to add a simple hardware decryptor that works on 16-bit instruction parcels, using a rotate and xor. The idea being that a binary file cannot just be copied to the machine and run without knowing the decryption key.

Also, the scheduler could possibly schedule instructions in a randomized order when it has more than one to choose from. I think the result may be slightly different run times and memory access patterns. I wonder if this would make virus software more difficult to come up with.

On Thursday, April 7, 2022 at 3:53:32 AM UTC-5, robf...@gmail.com wrote:
> So, I am now using Tomasula’s algorithm for my Thor processor to get OoO
> operation. It looks like it should help hiding memory latency and other long running operations. Ordering is being
> controlled by sequence numbers rather than the buffer position, so instructions may be queued into any open buffer
<
You should look into Find First circuits. You can do a find-circular-first on 36-entry reservation station
in 4 gates of delay. Use FFs as your "picker", then the queue is circular and the insert logic free. What
you do is make the insert logic require find first.
<
> slot. It does not work as a circular buffer as is done in some designs. There are four stages to the design, Fetch,
> Decode, Execute, and Write-back. There is a separate scheduler for each stage. Memory operations are strictly
> ordered, there are bits set aside in control register zero to allow more relaxed memory ordering.
<
You will find this a bit of a problem.
>
> Thor is using a 128-bit data-path mainly to support quad precision decimal floating-point. But the data-bus to registers is up to 512 bits to allow four registers to be updated or read at once.
>
> I am considering adding a random element to the schedulers, so processing may be in a different order from one run to the next. The idea is to make the processor a little bit less predictable.
<
Unnecessary if you use Find-Firsts.
>
> Also in consideration is encryption of the instruction set. It would not take much to have a simple decryption stage in the core. Installed software would need to use the correct decryption key to get a program to run. The idea is to make every installed base of software binary incompatible.
<
How do you do shared libraries ?

On Thursday, April 7, 2022 at 10:32:56 AM UTC-4, MitchAlsup wrote:
> On Thursday, April 7, 2022 at 3:53:32 AM UTC-5, robf...@gmail.com wrote:
> > So, I am now using Tomasula’s algorithm for my Thor processor to get OoO
> > operation. It looks like it should help hiding memory latency and other long running operations. Ordering is being
> > controlled by sequence numbers rather than the buffer position, so instructions may be queued into any open buffer
> <
> You should look into Find First circuits. You can do a find-circular-first on 36-entry reservation station
> in 4 gates of delay. Use FFs as your "picker", then the queue is circular and the insert logic free. What
> you do is make the insert logic require find first.

That is something I will look into. I was thinking also of using a fifo to store free slot indexes. It would be
only three bits wide, and FPGAs have built in fifos, dynamic shift registers. It may only be a handful of
LUTs to implement. But the logic gets more difficult to understand. I called the buffer a random-entry-buffer or REB
instead of ROB.

> > Also in consideration is encryption of the instruction set. It would not take much to have a simple decryption stage in the core. Installed software would need to use the correct decryption key to get a program to run. The idea is to make every installed base of software binary incompatible.
> <
> How do you do shared libraries ?

Shared libraries can be accommodated if the decryption key is known when they are installed on a machine. The
library could be encrypted during installation. The machine would also be able to run unencrypted software. The
encryption could also be easy to break. The idea is not to turn the machine into a fortress, but to make it more
reliable against the random virus.

Blew the LUT budget. Something I just did added about 35,000 LUTs to the design.

On Thursday, April 7, 2022 at 10:33:09 AM UTC-5, robf...@gmail.com wrote:
> On Thursday, April 7, 2022 at 10:32:56 AM UTC-4, MitchAlsup wrote:
> > On Thursday, April 7, 2022 at 3:53:32 AM UTC-5, robf...@gmail.com wrote:
> > > So, I am now using Tomasula’s algorithm for my Thor processor to get OoO
> > > operation. It looks like it should help hiding memory latency and other long running operations. Ordering is being
> > > controlled by sequence numbers rather than the buffer position, so instructions may be queued into any open buffer
> > <
> > You should look into Find First circuits. You can do a find-circular-first on 36-entry reservation station
> > in 4 gates of delay. Use FFs as your "picker", then the queue is circular and the insert logic free. What
> > you do is make the insert logic require find first.
> That is something I will look into. I was thinking also of using a fifo to store free slot indexes. It would be
> only three bits wide, and FPGAs have built in fifos, dynamic shift registers. It may only be a handful of
> LUTs to implement. But the logic gets more difficult to understand. I called the buffer a random-entry-buffer or REB
> instead of ROB.
> > > Also in consideration is encryption of the instruction set. It would not take much to have a simple decryption stage in the core. Installed software would need to use the correct decryption key to get a program to run. The idea is to make every installed base of software binary incompatible.
> > <
> > How do you do shared libraries ?
> Shared libraries can be accommodated if the decryption key is known when they are installed on a machine. The
> library could be encrypted during installation. The machine would also be able to run unencrypted software. The
> encryption could also be easy to break.
<
Sounds like you would end up needing 37 keys to run a single application.
Or a single key to a vector of keys.
<
> The idea is not to turn the machine into a fortress, but to make it more
> reliable against the random virus.
<
In my opinion, preventing SW from mangling the stack goes a long way in this direction.
For example: My 66000 has a stack used to preserve the state of the caller which cannot
be accessed by LD and ST instructions (because RWE = 000), but can be used by ENTER
and EXIT. This eliminates stack-smashing attacks, minimizes the opportunity for ROP
attacks, and prevents control flow changes due to buffer overruns.
>
> Blew the LUT budget. Something I just did added about 35,000 LUTs to the design.

In article <91614533-3d1a-474b-aec0-7275177bd169n@googlegroups.com>,
robfi680@gmail.com () wrote:

> I am considering adding a random element to the schedulers, so
> processing may be in a different order from one run to the next.
> The idea is to make the processor a little bit less predictable.

This is a poor idea on any architecture that will be used for
computationally intensive work. Tuning software for performance is a lot
harder if performance isn't consistent. Adding randomness without
creating occasional pathological cases will be very hard. Saying it's
unlikely will not help unless the probability is so low that it won't
happen in several hundred hours of full-speed execution. Murphy's law
loves cases like this.

It also won't help in the slightest with avoiding viruses. Viruses are
not built to exploit instruction timing variations: if they were, they'd
fail on different processor models with the same instruction set. You may
be thinking about avoiding the high-resolution timing necessary for some
Spectre-style attacks, but you can't do that by cycle-counting in code on
a processor that's taking interrupts. The way to deprive malware of
high-resolution time information is to not provide it in the sandboxes
used to run downloaded code. Depriving JavaScript code of high-
resolution time access was one of the more effective things that's been
done about Spectre.

> Also in consideration is encryption of the instruction set. It
> would not take much to have a simple decryption stage in the core.
> Installed software would need to use the correct decryption key to
> get a program to run. The idea is to make every installed base of
> software binary incompatible.

To handle shared libraries, and callbacks between applications and shared
libraries, you're going to need to have decryption keys associated with
address ranges, which are going to complicate your page tables and TLBs.
You're also going to have to potentially change the decryption key on
every subroutine call, every subroutine return, and every branch if you
allow tail-call elimination. Your decryption also has to be extremely
fast. Brute-forcing it is likely to be practical.

John

On Thursday, April 7, 2022 at 6:14:25 PM UTC-4, John Dallman wrote:
> In article <91614533-3d1a-474b...@googlegroups.com>,
> robf...@gmail.com () wrote:
>
> > I am considering adding a random element to the schedulers, so
> > processing may be in a different order from one run to the next.
> > The idea is to make the processor a little bit less predictable.
> This is a poor idea on any architecture that will be used for
> computationally intensive work. Tuning software for performance is a lot
> harder if performance isn't consistent. Adding randomness without
> creating occasional pathological cases will be very hard. Saying it's
> unlikely will not help unless the probability is so low that it won't
> happen in several hundred hours of full-speed execution. Murphy's law
> loves cases like this.
>
> It also won't help in the slightest with avoiding viruses. Viruses are
> not built to exploit instruction timing variations: if they were, they'd
> fail on different processor models with the same instruction set. You may
> be thinking about avoiding the high-resolution timing necessary for some
> Spectre-style attacks, but you can't do that by cycle-counting in code on
> a processor that's taking interrupts. The way to deprive malware of
> high-resolution time information is to not provide it in the sandboxes
> used to run downloaded code. Depriving JavaScript code of high-
> resolution time access was one of the more effective things that's been
> done about Spectre.

Okay.

> > Also in consideration is encryption of the instruction set. It
> > would not take much to have a simple decryption stage in the core.
> > Installed software would need to use the correct decryption key to
> > get a program to run. The idea is to make every installed base of
> > software binary incompatible.
> To handle shared libraries, and callbacks between applications and shared
> libraries, you're going to need to have decryption keys associated with
> address ranges, which are going to complicate your page tables and TLBs.
> You're also going to have to potentially change the decryption key on
> every subroutine call, every subroutine return, and every branch if you
> allow tail-call elimination. Your decryption also has to be extremely
> fast. Brute-forcing it is likely to be practical.
>
I was thinking the encryption key could be a global entity, so that there is no
need to change it on subroutine call return. It would be using the same key all
the time for the machine. Different libraries would all be using the same key.
It would be by virtual address range. The encryption would just be a 16-bit
rotate and xor so encryption and decryption can occur really quickly.
There is already a table with page related information in my design. It would
not be that difficult to add another key, although unnecessary if it is global. A
24-bit access key associated with a memory page is already present in the
design which is tempting to use. I have included an ‘encrypted’ page indicator
with the page information when I added compressed page indicators so pages
may be stored encrypted on secondary storage. No looking at the swap file
to get at sensitive information.

> I was thinking the encryption key could be a global entity, so that
> there is no need to change it on subroutine call return. It would
> be using the same key all the time for the machine.

So it's a global property of the machine, and libraries have to be
encrypted with the machine key at install time. Unencrypted code will
also run, and you need an "encrypted" flag as part of the executable file
format. Is that the idea?

This isn't terribly compatible with the code signing systems that are
already in use, although their usefulness varies.

If this scheme were to become popular, there would be a new kind of
malware for it, whose purpose was to find out machine keys and send them
back to the malware author - or just publish them.

How does this work for the case when storage moves from one machine to
another? Taking disks or SSDs out of a failed machine and plugging them
into a different machine happens, in organisations with lots of computers.

Clustered machines, and machines that run executables from networked
storage that's accessible to many machines, all have to be "the same"
machine. That means the key has to be settable when a machine is set up.

Is this actually providing something useful, as opposed to being a neat
idea?

> I have included an _encrypted_ page indicator with the page
> information when I added compressed page indicators so pages
> may be stored encrypted on secondary storage. No looking at the
> swap file to get at sensitive information.

That's a better idea.

John

On Thursday, April 7, 2022 at 3:53:32 AM UTC-5, robf...@gmail.com wrote:
>
> Also in consideration is encryption of the instruction set. It would not take much to have a simple decryption
> stage in the core. Installed software would need to use the correct decryption key to get a program to run. The
> idea is to make every installed base of software binary incompatible.
<
The more I think about this, the worse the idea becomes.
<
First: it basically ruins a whole bunch of stuff computer scientists have desired for a long time.
a) libraries of functionality
b) which can call other libraries of functionality,
c) shared at different virtual addresses by different threads,
d) all stored at the original location on disk/SSD,
e) under the rules of Position Independent Code,
f) so the linking loader has the least amount of work to do,
g) where even the OS can share application code,
h) where the hypervisor can share Guest OS and application library code.
<
It does little to add to real security while greatly increasing the burden on "just running"
<
It vastly complicates libraries "over the network"
<
My guess is that there is a lot more that can be done helping security
without taking even the first step in this direction.