forwardcom forum

• Introduction
• Basic architecture
• Proposed code structure
• FPGA
• Extensibility
• Portability
• ABI and calling conventions
• Assembly syntax
• Summary of advantages
• Can existing instruction sets be fixed?

• The instruction set should have a simple and consistent design.
• The instruction set should represent a suitable compromise between the RISC principle that enables fast decoding, and the CISC principle that makes more efficient use of code cache resources.
• The design should be expandable so that new instructions and extensions can be added in a consistent and predictable way.
• The instruction set should be designed through an open process with the participation of the international hardware and software community.
• The instruction set should be non-proprietary and allow anybody to make compatible software, hardware and equipment for test, debugging and emulation.
• Decisions about design and extensions should not be determined by the short term marketing considerations of an oligopolistic microprocessor industry but by the long term needs of the entire hardware and software community and NGOs.
• The design should allow appliction-specific extensions.

• Set multiple registers to the same constant value (typically zero). The first register and the number of registers is specified.
• Read multiple registers from consecutive memory addresses. Optionally increment pointer by the size. Can use the stack pointer or any other pointer register.
• Save multiple registers to consecutive memory addresses. Optionally increment or decrement pointer by the size. Can use the stack pointer or any other pointer register.
• Combined arithmetic operation and conditional jump.

• Instruction pointer + 32 bit sign-extended offset
• Instruction pointer + index register + 32 bit sign-extended offset
• Base register + 8 or 32 bit sign-extended offset
• Base register + index register + 32 bit sign-extended offset
• Base register + scaled index register + 32 bit sign-extended offset

• 3 registers (1 dword).
• 2 registers and a predicate (1 dword).
• 1 register and a predicate and an 8-bit immediate (1 dword).
• 1 register and a memory operand with base and 8 bit offset, scalar only (1 dword).
• 2 registers and a predicate and a 32-bit immediate (2 dwords).
• 1 register and a memory operand with base and 32 bit offset (2 dwords).
• 2 registers and a predicate and a memory operand with base and index and 32 bit offset (3 dwords).
• 2 registers and a predicate and a 64-bit immediate (3 dwords).

• 2 registers of 32-bit integers only, a condition code and an 8 bit displacement (1 dword).
• 2 registers, a condition code and a 32 bit displacement (2 dwords).
• 1 register, an 8 bit immediate, a condition code and a 32 bit displacement (2 dwords).

• 3 registers and a predicate and option bits (2 dwords).
• 2 registers and a predicate and a memory operand with base and index and 32-bit offset and option bits (3 dwords).

• Code reserved for future use. Generates interrupt so that it can be emulated.
• Code reserved for future use. Generates no interrupt, but behaves as a nop (no operation). Can be used for future purposes that allow the code to be ignored on processors that do not support it.
• Code guaranteed to never be used. Will generate interrupt also on all future processors. Can be used for application-specific emulation or forced error messages.

Agner, what's your opinion on the Itanium instruction set in isolation, assuming a compiler is written and backwards compatibility do not matter?

You should take a look at RISC-V [1], which satisfies all the requirements you set, has broad involvement of academia and strong interest by the industry.
[1] riscv.org

• It is not completely orthogonal
• Arithmetic instructions cannot have memory source operands
• Immediate constants have odd sizes. It is not possible to include floating point immediates, which I argue would be more efficient than loading floating point constants from data memory
  There are no predicated or masked instructions
• 128-bit integers are not supported, except as pointers in 128-bit address mode
• Support for vectors is not well developed. Vector size is limited to 1024 bits
• There is no way to save and restore a vector register that is guaranteed to be compatible with future extensions
• Software has to be recompiled each time a different processor with different maximum vector size becomes available
• There is no support for integer vectors, Boolean vectors, masked vector operations, broadcast, etc.
• long int can be 32 or 64 bits. There is no standardized way of specifying 64-bit and 128-bit integers. This inconsistency is causing annoying compatibility problems today which need to be fixed in any new ABI.

This has the advantage that it simplifies considerably the code that must deal with the initial or final parts of the arrays whose sizes are not a multiple of the size of a vector register or which do not have a correct alignment.

For AVX-512 and longer vector registers it is likely that the code dealing with all the possible cases of lengths and alignments will be much larger than the code for the main loop, and it will increase in geometric progression for each new maximum vector length.

With a vector length register, this extra code will be much smaller and its size will remain unchanged when the size of the vector registers will be increased.

"There are no predicated or masked instructions"

"Arithmetic instructions cannot have memory source operands?"
"Immediate constants have odd sizes. It is not possible to include floating point immediates, which I argue would be more efficient than loading floating point constants from data memory"
"128-bit integers are not supported, except as pointers in 128-bit address mode"

"Support for vectors is not well developed. Vector size is limited to 1024 bits"
"Software has to be recompiled each time a different processor with different maximum vector size becomes available"
"There is no support for integer vectors, Boolean vectors, masked vector operations, broadcast, etc."

"long int can be 32 or 64 bits. There is no standardized way of specifying 64-bit and 128-bit integers. This inconsistency is causing annoying compatibility problems today which need to be fixed in any new ABI."

• Keep the stack aligned by the required size and propagate this alignment through the chain of function calls. A function must insert unused space on the stack before calling another function, if needed, in order to keep the stack aligned. The problems with this method are: it wastes stack space; it requires extra instructions in functions even when the alignment is not actually used; it does not take into account future systems with bigger vectors requiring higher alignment; and it may fail if different parts of the code have been compiled for different alignments.
• Adjust the stack frame to the required alignment inside any function that needs aligned storage. This requires more instructions than method 1, but only when alignment is actually needed. A further disadvantage is that is uses an extra register for addressing the aligned stack frame or for saving the stack pointer.

Add with Carry:
It's true that if you want to do lots of BIGNUM computation, then you'll definitely want a flags registers [...] Or perhaps you could use scalar integer registers as flags on SIMD operations designed for BIGNUMs.

try {
  ... a long series of calculations ...
}
catch (signed_integer_overflow e) {
  ... error message ...
}

• You will need more space in the opcode to contain 4 registers.
• Handling multiple inputs is just as difficult as multiple outputs. For many years, Intel had a limitation of 2 inputs per micro-operation, and they had to split add-with-carry and several other instructions into 2 microoperations for the same reason.
• The instruction might have a latency of 2 clock cycles unless you can implement it with two double-speed adders. Mixing instructions with different latencies is a problem because a 2-clock instruction may need the result bus at the same time as a subsequent 1-clock instruction. It is best to standardize instruction latencies and have as few different latencies as possible.
• It is problematic to make a hardware design that cannot handle instructions with two outputs. You also need two outputs for integer division (output quotient and remainder) and for full length integer multiplication.

• Use one instruction with two output registers.
• Use two separate instructions, possibly executed simultaneously, one for each output.
• Use two elements of a vector register.

Checking for integer overflow is very complicated in high-level languages

c = a modulo_op b;
d = a sat_op b;
if (c != d) { overflow }

How about you support 2 kinds of arithmetic - saturation and modulo. To check if the arithmetic operation overflowed, do this:
c = a modulo_op b;
d = a sat_op b;
if (c != d) { overflow }

We could add two more flags bits which are accumulating, i.e. the signed and unsigned overflow condition is ORed with the previous value of the flag bit. The program can then check these accumulating overflow flags after a series of instructions.

How about limiting instruction length to power of 2

• It makes bank selection for loads more complex, potentially increasing load latency by a cycle (presumably from 3 cycles to 4 cycles with address calculation included) due to having more multiplexers on address inputs on each bank, more multiplexers on writebacks, more different stalling scenarios and probably requiring an increase in the number of banks.
• It makes load/store address conflict detection harder since you need to check even more reads against pending writes in the write buffer, and deal with more scenarios like multiple reads trying to access forwarded store values.
  I've played around with various concepts to deal with this but I'm not sure I've found anything really interesting yet:
• A L0 cache could be introduced. Probably something very small, single-way, duplicated multiple times, probably loading whole cache lines from L1 on every miss and probably only used when there are too many loads per cycle to be satisfied by the L1. Problems: this is still limited to 1 store per cycle, filling values from L1 competes with stores for the single write port, doesn't simplify address conflict detection with the store queue. (if I'm not mistaken, GPUs use something like this?)
• Pointers could be stored in special registers, and when a pointer register is updated, data from nearby addresses (say, possibly something like adr+0 to adr+63) are automatically pre-read into registers, and there is an automatic check that none of the other pointer registers are pointing to the same data with data modifications. You would possibly also have load/store instructions that bypass these special pointer registers (but with address conflict checking). This is very complex (especially the address checking, which is unfortunately necessary for C++ compilers), and it doesn't help you at all if your data is widely spaced or uses indexed offsets (register+register*n). But on the other hand, data accesses that do fall into this pattern (like loading/storing a whole bunch of contiguous stack addresses or object member variables) become register accesses, they can be renamed, reordered willy-nilly, pretty much every instruction can load/store a value, misaligned addresses don't matter anymore (except when changing a pointer register), and if the address is divisible by 64 you can conceivably load/store a whole cache line in one go.

how could gather/scatter be implemented in hardware?

If you have, for example, 8B - 2B - 8B, then the second 8B instruction will be misaligned, and the advantage disappears.

struct {
double a /* 8B */;
short b /* 2B */;
double c /* 8B */;
} foo_t;

P = address of array
J = size of array (in bytes)
L = maximum vector length (depends on processor)
X = a vector register
P += J;   // point to end of array
while (J > 0) {
   X = whatever_operation[P-J]{vectorlength J}
   J -= L
}

for(int i=0; i<nb_samples_to_do;)
{
int block_samples = nb_samples_to_do - i;
if(block_samples > 64) { block_samples = 64; }
[process block_samples items];
i += block_samples;
}

would it make sense to adapt the code for different maximum SIMD vector length in the relocation pass? (ie when correcting all jump offsets when loading a DLL or doing address layout randomization to prevent hacking when loading executables)

• One universal register set for everything.
• Two register sets, one for scalars and one for vectors. Same registers are used for integers and floating point.
• Two register sets, one for integer scalars and one for everything else: floating point scalars, integer vectors and floating point vectors.
• Three register sets, one for integer scalars, one for floating point scalars and one for vectors of all types.

what do you think about a transport-triggered architecture? Could your framework benefit from elements of a TTA? Instruction and code size could be reduced if certain registers automatically squared their contents, for example, or if designated pairs of registers automatically summed their contents. There are many possibilities. (Is there already an incrementer (by 1) register in existing architectures?

• Load from memory #1
• Long chain of dependent math #1
• Store to memory #1
• Load from memory #2
• Long chain of dependent math #2
• Store to memory #2

• The Idempotent Architecture, which eliminates recovery from mis-speculation. research.cs.wisc.edu/vertical/papers/2011/micro11-idem.pdf
• ISA extension for hashing, with huge speedups: www.adms-conf.org/2014/adms14_arnold.pdf
• Logarithmic number system processor as alternative to floating point unit: https://www.ece.ucsb.edu/~parhami/pubs_ ... to-flp.pdf

why 32 registers?

You also see stack-like register windows (SPARC, i960, Am29k) and rotating register files (Itanium) but the general consensus seems to be that this is overdesigned and MIPS does just as well with 32 ordinary registers.

If there's any hope to get a language that's more efficient than C++, I'd say that IMHO it's probably a language that forces a limitation of "absolutely no pointer aliasing" - so probably with no pointers, no references, no side-effects (and probably copy-on-write objects).

instructions can read / write the top, say, 32 elements. Or whatever the window size is. Call / return adjust the stack

• Program code (TEXT). This is executable and read-only. Can be shared between multiple processes.
• Read-only program data (CONST). This contains constants and tables used by the program. It may be shared by multiple processes unless it contains pointers that need to be relocated at load time.
• Static read/write program data (DATA+BSS). This is used for global data and for static data inside functions. It needs multiple instances if multiple processes are running the same code.
• Stack data (STACK). This is used for non-static data inside functions. This is the most common and most efficient way of storing program data. Each process or thread has its own stack, addressed relative to the stack pointer.
• Local heap. Used for dynamic memory allocation by an application program
• Global heap. Used for dynamic memory allocation by the operating system and device drivers.
• Thread data. Allocated when a thread is created and used for thread-local static data. Rarely used.

• Program code. In current systems, program code may contain absolute addresses. These addresses are modified (relocated) by the loader if the code is loaded at a different address than expected by the linker. The relocation is often avoided by using virtual address translation. Multiple programs that do not need to call each other can be loaded at the same virtual address.
  My proposal is to avoid the need for relocation by using relative addresses as much as possible. All addresses within the same code segment are addressed relative to the instruction pointer.
• Read-only program data. Current systems use either relative or absolute addresses to address read-only data. These addresses often need to be relocated by the loader.
  My proposal is to make the read-only data segment contiguous with the program code segment, and access it with addressing relative to the instruction pointer. This needs relocation at the link stage, but not at the load stage.
  This segment may contain pointers. This is typically needed in switch/case jump tables, virtual function tables, function pointers and data pointers. Current systems often use absolute addresses in these cases, needing relocation by the loader. Some compilers use self-relative pointer tables or pointers relative to an arbitrary reference point (used in 64-bit Windows and Mac OS).
  My proposal for jump tables, virtual function tables and code pointers is to use 32-bit self-relative addresses or addresses relative to the code base.
  Tables of constant pointers to data is a problem because - in order to use relative pointers - we need to know whether the pointer target is in the read-only data or the read/write data segment. Preferably, such a table should be placed in the same segment as its targets, either the read-only data segment or the read/write data segment. This makes it possible to use self-relative pointers. If it contains a mixture of both, then it should be placed in the read/write data segment, and any targets in the read-only data segment should be moved to the read/write data segment.
• Static read/write program data. Current systems use absolute or relative addresses to access read/write data in the same way as read-only data. If multiple processes are running the same program then there will be one instance of the read/write data segment for each process. The multiple instances will typically share the same virtual address, while having different physical addresses. This requires virtual address translation. We want to get rid of this translation.
  My proposal is to have a dedicated register for pointing to the read/write data segment. All data in the read/write data segment are addressed relative to the value in this register. We may implement a special addressing mode for this or, alternatively just let the application copy the data segment register to a general purpose register which is used as pointer. Read-only data may optionally be stored here rather than in a separate segment.
  The data segment pointer register needs to be saved and restored when one program calls another program. It does not need to be saved when calling a DLL, which I will explain below.
• Stack. Each process and each thread has its own stack which is addressed by the stack pointer. No problem here.
• Heap. You get a pointer when allocating data on a heap. Heap data are addressed through this pointer. No problem here.
• Thread-local data. Current systems may have a "thread environment block" which contains various information about the thread and a pointer to the thread-local data segment. In x86, it is addressed through a special segment register. It also contains information about stack size, exception handler, process environment, etc.

• The required stack size can be predicted and sufficient stack space is allocated when a program is loaded and when additional threads are created.
• Static variables are addressed relative to the data section pointer. Multiple running instances of the same program have different values in the data section pointer.
• The heap manager can handle fragmented physical memory in case of heap overflow.
• There is sufficient memory so that no application needs to be swapped to a hard disk.

• Recursive functions can use unlimited stack space. We may require that the programmer specifies a maximum recursion level in a pragma.
• Allocation of variable-size arrays on the stack using the alloca function in C. We may require that the programmer specifies a maximum size.
• Run-time dynamic linking. Dynamic link libraries (DLLs) are usually linked at load time and the loader will be able to include these in the calculation of stack requirements. But a program can need to load and call a DLL at run-time if the choice of DLL depends on user input or if the DLL is called from a script. We may need to guess the required stack size, perhaps based on statistics.
• Lazy loading. A large program may have certain code units that are rarely used and loaded only when needed. Lazy loading can be useful to save memory, but it may require virtual memory translation and it may cause memory fragmentation. A straightforward solution is to implement such code units as separate executable programs, but this can complicate the exchange of data between mother program and subunits.
• Script interpreters. Some programming languages are implemented as scripts which are interpreted at run-time rather than compiled. We cannot calculate the required stack size in advance for interpreted scripts. Obviously, it will be more efficient to compile the script if a compiler is available. Self-modifying scripts cannot be compiled.
• User-defined macros. Macros are similar to small scripts. Depending on the implementation, macros may use heap space or stack space or both, but usually the memory requirement is limited.
• Many programs running. The memory can become fragmented when many programs of different sizes are loaded and unloaded randomly.

The user unexpectedly loads a 300mb file in program 2, which causes a surprise 300mb allocation on the heap. Where does the OS place this allocation?

• Allocate more heap space somewhere else. Make an extra entry in the memory map for it.
• Same as 1. Use virtual address translation to keep it contiguous in order to make the heap manager simpler. This requires that you allocate a lot of unused virtual address space for each program as it starts. This method works also for the stack.
• As a last resort, when memory space has become hopelessly fragmented and you are out of memory map entries. Swap the data of the least used program to disk. Reorganize the fragmented data by actually moving the values to make them contiguous in physical memory (assuming that they were already contiguous in virtual address space). This will cause an annoying delay to the user, but we already have such delays in current systems when you run out of memory. You may signal a warning to the user: Memory low, please close some programs.

One suggestion: remove "Indexing into the register file".

2nd suggestion: Make operand size for tiny format 32bits, not 64bits (except mov). Consider trading tiny setbit/clearbit/xor/reversesubtract/andnot for arithmetic shift right and 64bit add/sub. Consider adding the option for 32bit signed indexes in address calculations or sign extending instead of zero extending 32bit operations to 64bit by default.

1. Allocate more heap space somewhere else. Make an extra entry in the memory map for it.

2. Same as 1. Use virtual address translation to keep it contiguous in order to make the heap manager simpler.
This requires that you allocate a lot of unused virtual address space for each program as it starts. This method
works also for the stack.

3. As a last resort, when memory space has become hopelessly fragmented and you are out of memory map entries.
Swap the data of the least used program to disk. Reorganize the fragmented data by actually moving the values to
make them contiguous in physical memory (assuming that they were already contiguous in virtual address space).
This will cause an annoying delay to the user, but we already have such delays in current systems when you run out
of memory. You may signal a warning to the user: Memory low, please close some programs.

I want to avoid complex instructions for saving and restoring all or many registers. Any suggestions for an alternative to
writing 64 consecutive save instructions or having a complex microcoded save-all instruction?

I am not sure if you are trying to save power by doing a 32-bit addition instead of 64 bits. The hardware may actually
disable the upper part of the heavy carry-lookahead circuit if it can detect quickly that the values are small. Otherwise,
I don't see the problem of using 64-bit addition on 32-bit values. The value will simply be truncated if it is later used
in a 32-bit (not-tiny) instruction. The compiler will recognize the need to sign-extend a 32-bit signed index or optimize
the program by replacing it with a 64-bit index variable. Or you may use an unsigned 32-bit index and use the carry
flag for detecting end of loop if the index is counting down. I would rather keep array indexes 64-bit because setting
a 2 GB size limit to arrays is a problem for the programming language standard, and the value may cross zero when
a count-down loop ends.

Any suggestions for an alternative to writing 64 consecutive save instructions or having a complex microcoded save-all instruction?

For general purpose registers, you're going to do 32 consecutive loads/stores so it's always going to take 'some' time.
I'd suggest mandating 16-byte stack alignment in the ABI, and having store-dual and load-dual instructions that can save/restore two registers in a single whole 128bit memory access.

The compiler will probably have to add an instruction to sign-extend all 32bit indexes. It cannot replace 32bit variables with 64bit variables because that changes behavior - instead of 'int' being "32bits", it becomes "32bits except if the compiler decided to make it 64bits but it can still revert to 32bits at any time depending on if the value is in a register.

I am just hoping to keep the number of memory sections and fragments so small that we can get rid of the fixed size
memory pages and have a limited number of variable size memory blocks instead.

One solution is to have "save register and increment pointer" instructions in tiny form for both integer registers and full
length vectors. Same for restore. Then you can save everything with 64 tiny instructions = 128 bytes of code.

I just made an experiment to see what compilers actually do with a signed 32-bit index variable in 64-bit mode (x86-64).
Both Ms and Gnu compilers simply replaced my 32-bit integer with a 64-bit integer. I don't think it is worth the effort to
make a special addressing mode with sign-extended 32-bit index.

I'm really curious about how the hardware would be able to do that mapping in a very short time (ideally in a single
cycle, and in a way that the L1 cache data lines that get read don't depend on virtual address translation).

It has many other parts that would be more complex or would require microcode.

Well, "load register and increment pointer" writes to 2 registers so it's similar in complexity to "load dual".

I just checked msvc's x64 output, and I'm admit I'm very spooked. It does stuff like loading an index into eax, then using rax as an array index, even though the variable is clearly signed in the code. Some code locations seem to use movsx for sign extension, but most don't.

The way MIPS stays simple is that they disallow any sort of multi step situational thing with lots of changing registers and multiple memory accesses... No push/pop, no call/return, no automatic loading of selector offsets and segment size like on 286, and especially no task switch instruction.
This is also why RISC-V is designed that way: the idea is that by having no multi result instructions, but having higher throughput because it's easier to make a CPU with out of order execution and lots of execution units, you still come ahead in overall speed.

Hubert Lamontagne wrote:

The way MIPS stays simple is that they disallow any sort of multi step situational thing with lots of changing registers and multiple memory accesses... No push/pop, no call/return, no automatic loading of selector offsets and segment size like on 286, and especially no task switch instruction.
This is also why RISC-V is designed that way: the idea is that by having no multi result instructions, but having higher throughput because it's easier to make a CPU with out of order execution and lots of execution units, you still come ahead in overall speed.

Why is it so much more difficult to have two-result instructions?

• If your limiting factor is issue width (how many different instructions per cycle you can issue), then multi-result
  instructions are good because you're doing more work out of your few available instructions. x86 tends to
  fall in this case due to the whole instruction length business, and good x86 designs tend to do lots of work
  from few instructions (AMD's 3-issue Athlon is a perfect example of this - and a good example of "fast CISC").
• If your limiting factor is register-file and rename ports, then multi-result instructions are bad because they
  won't be faster than multiple instruction sequences and they make the pipeline more complex overall (since
  the multiple results have to be committed together and so forth).
• If your limiting factor is L1 cache read and write ports, then it's all a wash.

We need two-result instructions for: add-with-carry,

overflow detection,

pop register,

ld r4 [sp + #0],
ld r5 [sp + #4],
ld r6 [sp + #8],
ld r7 [sp + #12],
add sp #16

return

read-and-increment-pointer,

ALU-and-conditional-jump.

If we want an efficient implementation of add-with-carry with a single register, we may have an extra bit in the register for this purpose. Or we may use every second element in a vector for carry bit, at the cost of getting half the work done. The same for overflow detection.

Function calling also becomes complicated if we do not allow multiple results. The call of a non-leaf function will be: (1) copy instruction pointer to link register, (2) jump to target, (3) subtract from SP, (4) save link register on stack. And the return will be: (5) recall link register from stack, (6) add to SP, (7) jump to link register. That is seven instructions instead of two. Does the increase in speed really make up for that?

it all comes down to what's your limiting factor:
- If your limiting factor is issue width (how many different instructions per cycle you can issue), then multi-result
instructions are good because you're doing more work out of your few available instructions. x86 tends to
fall in this case due to the whole instruction length business, and good x86 designs tend to do lots of work
from few instructions (AMD's 3-issue Athlon is a perfect example of this - and a good example of "fast CISC").
- If your limiting factor is register-file and rename ports, then multi-result instructions are bad because they
won't be faster than multiple instruction sequences and they make the pipeline more complex overall (since
the multiple results have to be committed together and so forth).
- If your limiting factor is L1 cache read and write ports, then it's all a wash.

We need two-result instructions for: add-with-carry,

I don't think ADC is used often enough to warrant being included in a general purpose instruction set.

overflow detection,

Careful use of comparison instructions handle this case adequately, as far as I can tell. For instance, when doing unsigned addition, you only have to compare the result with a source operand.

pop register,

Ok, this one is actually fairly common in general purpose code.

read-and-increment-pointer,

That case is similar to pop register: on one hand, you get two results for the price of one if your front-end can
only generate a limited number of instructions (which is why ARM has this instruction), but on the other hand,
separating reading and pointer-increment lets you combine a whole bunch of updates to the same pointer
together, which is often good since it reduces the number of intermediary results for the pointer value

why do we still use conventional -- and enormous -- memory addresses?

We use 64-bit (or 48 actual I think on x64). Since it's a program's exclusive virtual memory space, a universe of our own, why can't we use arbitrary and much, much smaller addresses? Like 1, 2, 3, etc., basically a byte or two.

Separately, I think it would be fruitful to think about how an ISA could be designed to help JITs, and common parsing workloads like the web. If we designed an ISA to increase the performance of browser JS engines,. NET and Java VMs, etc. what would that look like? Would it be instruction selection that mattered most, or other aspects of the architecture?

Intel rolled out some great instructions for string parsing in SSE 4.2, but my impression is that hardly any developers know about them or use then

Most operating systems have now switched to 64-bit addresses. It is true that most applications can do with a private 32-bit address space, but not all. A video editing program, for example, may need more than 4 gigabytes of data, and future needs may be still more. Better have 64-bit addresses to fit future needs than using complicated memory bank swapping and the like.

I don't know if a JIT compiler needs anything special. Maybe string compare, but we can do that with vectors of 8-bit elements (this will work with UTF-8 strings). Anything else you have in mind for JIT compilers?

My proposal includes variable-length vector registers that enable the software to adapt automatically to the different vector sizes of different processors without recompiling. If one compiled executable file fits all variants of the processor, why do we need JIT compilers at all?

The SSE4.2 instructions are ingenious, but very complicated for programmers to use. Most text strings intended for human reading are not so long that the speed of text processing really matters. The SSE4.2 instructions may be useful for other purposes, e.g. DNA sequence analysis.

XML documents are made up of storage units called entities, like Character Data, Element, Comment, CDATA Section, etc. Each type of entity has its own well-formed definition that is a serious of character range rules.[1] The main work of Intel XML parsing is to recognize these entities and their logic structures.

From Intel XML Parsing Accelerator, we found that character checking loop occupies more than 60% CPU cycles of the whole parsing process, depending on the property of benchmark. There are two kinds of important behavior in this loop, read bytes and check whether it is legal for its corresponding entity type. Without any parallel instructions for string comparison, this process must be implemented in serializing mode.

• Put the two big numbers into vector registers A and B, or as much of the numbers that will fit into the maximum vector length
• Calculate the sums of all 64-bit vector elements: C = A + B
• Make a vector of the carries, one bit in each 64-bit element: D = (C < A)
• Find elements with all ones: E = (C == -1)
• Combine bit 0 of each element of C into an integer bitfield: D1 = convert_boolean_vector_to_bitfield(D)
• Do the same with E: E1 = convert_boolean_vector_to_bitfield(E)
• Use integer operations to do the carry look-ahead. D1 is the elements that generate carry, E1 is the elements that propagate carry. F = E1 xor (E1 + 2D1 + carry_in)
• Convert back from bitfield to vector: F1 = convert_bitfield_to_boolean_vector(F)
• Add the propagated carries: Sum = C + F1
• Carry out if more rounds needed: Carry_out = F >> number_of_vector_elements

Thank you for your comments. It is nice to have sparring partners to discuss with. We are really getting somewhere.

I think there are many advantages to storing the vector length in the vector register itself. This makes it much cheaper to save callee-save registers: You only have to save the part of the register that is actually used. I plan to make special instructions for save/restore. These instructions will save or restore the length and as much of the data as is actually used. The save instruction can increment a pointer by the actual amount of space used. The restore instruction will have to be followed by an extra instruction to increment or decrement a pointer by the amount of space used. The same instruction can be used to adjust the stack pointer before saving. This will save a lot of data cache. If a very long vector register actually contains only a floating point scalar then we need not save any more than that. If the vector register is unused, which will probably happen more than 50% of the time, then we only need to save the length, which is zero. Also, we don't need a complicated lazy save mechanism for task switches. And we get one less input dependence because we don't need a separate register for vector length.

SUB sp, 12
; special instruction that gets the number of empty bytes to adjust vsp so that
; the next vector save is aligned and can be done in a single DCache cycle
GETVECTORSTOREPREPAD r0, vsp, v0.size
ST r0, [sp + 0]
ADD vsp, r0
ST v0, [vsp]
GETVECTORSTOREPREPAD r1, vsp, v1.size
ST r1, [sp + 4]
ADD vsp, r1
ST v1, [vsp]
GETVECTORSTOREPREPAD r2, vsp, v2.size
ST r2, [sp + 8]
ADD vsp, r2
ST v2, [vsp]

The disadvantage is, of course, that the compiler needs to distinguish between saving the data of a vector and saving everything for a later complete restore. Once we have this distinction, however, there is little extra cost to also saving a few carry flags. 

The idea of having separate registers for system code only, sounds good. Would eight 64-bit registers be a suitable number?

Hubert and Agner, I have a related but slightly tangential question, since we're talking about TLBs.

In our applications, within a virtual memory space, why do we still use conventional -- and enormous -- memory addresses?

We use 64-bit (or 48 actual I think on x64). Since it's a program's exclusive virtual memory space, a universe of our own, why can't we use arbitrary and much, much smaller addresses? Like 1, 2, 3, etc., basically a byte or two. If the TLB is going to have to translate anyway, is it a problem to translate small addresses into conventional physical ones? Processes could have unique IDs - one byte would be ample most of the time - so the TLB would have a unique identifier for all addresses (process ID + the process' internal small memory addresses), and it would often take only two or three bytes total.

You could do a variety of things with pages and their sizes in that scenario. What am I missing here? I usually stick to managed languages.

Separately, I think it would be fruitful to think about how an ISA could be designed to help JITs, and common parsing workloads like the web. If we designed an ISA to increase the performance of browser JS engines,. NET and Java VMs, etc. what would that look like? Would it be instruction selection that mattered most, or other aspects of the architecture? Intel rolled out some great instructions for string parsing in SSE 4.2, but my impression is that hardly any developers know about them or use then (I couldn't find them in nginx or Apache source, or browsers I checked, and they could really benefit.) That raises a separate issue in getting developers to pay attention to ISAs and optimization wins...

If we don't need extra carry bits for high precision arithmetics, then the only need for these extra bits is for detecting and propagating integer overflow.

If we don't have the extra carry flags, then we will need special instructions for checking if an addition, multiplication, etc. overflows. After each addition or other arithmetic instruction, issue another instruction with the same inputs just to check if the operation overflows. The outputs of all the overflow checks for a series of calculations should then be OR'ed together. The total number of instructions will be three times the number of instructions needed without overflow check.

So what are the costs and benefits? Without the extra flag bits we need three times as many instructions if we want to check for integer overflow. We can avoid overflow in many cases by using 64-bit integers, but even 64-bit integers can easily overflow if the calculation has many multiplications. Compiler support for checking integer overflow is rare, unfortunately, so any mechanism for detecting integer overflow will perhaps not be used much. On the other hand, if an efficient method was available, we would probably see compilers that support it and programmers that use it. In fact, many programmers are frustrated over how difficult it is to detect signed integer overflow. Traps for integer overflow exception is not good for vector code. One solution is to use floating point calculations instead of integer, but I don't see that solution used much. Floating point calculations have longer latencies, of course. No solution seems to be really good here.

res = (int16_t)a * (int16_t)b;
res = res >> 15;
if(res == 32768)
res = 32767; // clamp the particular case of -32768 x -32768
(int16_t)out = res

One catch is that vector registers need special alignment. For instance, if your vector regs are 512bits and your DCache width is 512bits, you want your vectors to be 512bit aligned when saved to the stack, so you need to 512-align your stack pointer.

There's an extra cost, it's just in a different non-obvious place: it forces the compiler to figure out if the carry bits are relevant for each operation in a chain, and if the compiler can't figure it out it will output less efficient. Whereas if carry flags are in their own register, and only written/read by some operations (on ARM, when SUB generates flags it is called SUBS and is a different instruction), then the compiler only ever has to worry about carry flags for instructions that expressly read/write them (ADDS / ADC / ADCS / SUBS / SBC / SBCS / CMPS etc), and then it just becomes one extra register pool in the compiler's register allocator.

CPUID could be replaced by a bunch of read-only system registers that give the CPU model for instance.

Since it's a program's exclusive virtual memory space, a universe of our own, why can't we use arbitrary and much, much smaller addresses?

String parsing also falls in this kind of case. For instance, checking the length of a string is not so obvious: often the interpreter knows the number of bytes of a string, but some of those bytes are UTF-8 characters, and if you account for special cases (like ending up with Latin-1 aka CP-1252 text), then there's often really no alternative to just looping through the string byte per byte

I write C++ sound code, and for code with lots of multiplications that could overflow, I use floating point code _all the time_. :3

Since it's a program's exclusive virtual memory space,
a universe of our own, why can't we use arbitrary and
much, much smaller addresses?

My priority is the performance of big systems. That's
why I have 64-bit address space. All addresses are
relative to some pointer (instruction pointer, data
section pointer, stack pointer, or an arbitrary
pointer) with a signed offset of 8 bits or 32 bits.
The instruction size will not be reduced by having a
smaller address space, but of course we could save
some stack space by having a 32-bit mode. I don't like
having two different modes, though. Then we would have
problems with stack alignment for doubles, etc. Byte
code languages can have their own smaller address
space of course.

Hardware multipliers are expensive, and divisors are even more expensive. I wonder if we need to support multiplication and division of all operand sizes, including vectors of 8-bit and 16-bit integers, if programmers are using floating point anyway?

Does an ISA really need to specify the number of architectural registers? What would the implications be of not doing so, and having an infinite number of architectural registers like LLVM's IR?

Might it be useful to also have an unspecified register – call it Rx – that basically tells the CPU "give me whatever register you have – I don't care which one".

then your SP is not 8-byte aligned anymore for 64bit integer and floating-point value. So you must save the vector size word to 0x01FE0 instead, with some extra padding (and the CPU either stores the amount of padding in the vector size word, or recalculates the amount of padding from SP alignment and vector size when reloading the vector).

Generally, 8-bit and 16-bit vector multiplications are provided in SIMD instruction sets to do stuff like movie decoding and software rendering

Question: Does an ISA really need to specify the number of architectural registers? What would the implications be of not doing so, and having an infinite number of architectural registers like LLVM's IR? It seems like the number of registers is a fiction anyway (I was stunned to discover that x86-64 processors from Intel and AMD have nearly 200 physical registers.) This would make the number of registers implementation-dependent, rather than part of the ISA specification. See Vikram Adve's recent talk at Microsoft: http://research.microsoft.com/apps/vide ... ?id=249344 (The Microsoft Research people must have been having a bad day or something – their questions and comments reveal that they thoroughly misunderstood his ideas.)

Question 2: Let's assume that we have registers R0 - R31. Might it be useful to also have an unspecified register – call it Rx – that basically tells the CPU "give me whatever register you have – I don't care which one". I can imagine some scenarios where this might be useful for a compiler. And it seems to fit with the reality of register renaming anyway.

Yes, this is a complication. I want to handle it in software without any complex instructions. If the size of the saved register image is not guaranteed to be a multiple of the stack word size then I would first calculate the amount of space needed for all the vector registers I want to save, then save the stack pointer to another register, then subtract the necessary size from the stack pointer, then align the stack by 8 ( AND SP,-8 ), then use a temporary register as pointer to the save area, and then save the registers, incrementing the pointer each time. The restore process is easier.

Generally, 8-bit and 16-bit vector multiplications are provided in SIMD instruction sets to do stuff like movie decoding and software rendering

x86 does not have a complete set of vector multiply instructions. NEON has 8, 16, and 32 bits. I don't see what you would you need 8-bit vector multiply for?

- 3-bytes can't be aligned to cache lines. If you have an array of pointers, eventually one of the pointers has to straddle 2 cache lines and that's a much larger penalty than some wasted DCache due to using 4-byte pointers.
- 3-bytes is only a 16 Mb address space, and few languages want to be limited to something that small. You cannot start with 3-byte pointer program and then dynamically upgrade everything to 4-bytes if you ever run out of space. Might as well make everything 4-byte from the start.

Agner wrote:
Joe Duarte wrote:

Does an ISA really need to specify the number of architectural registers? What would the implications be of not doing so, and having an infinite number of architectural registers like LLVM's IR?

What do you mean? If we have 1023 virtual registers like LLVM then we need 10 bits in the opcode for each register. Or do you want a rolling register stack? Then we have a problem when the register stack overflows. That would be quite wasteful if the overflow happens in the innermost loop.

Joe Duarte wrote:
Hubert said:

- 3-bytes can't be aligned to cache lines. If you have an array of pointers, eventually one of the pointers has to straddle 2 cache lines and that's a much larger penalty than some wasted DCache due to using 4-byte pointers.
- 3-bytes is only a 16 Mb address space, and few languages want to be limited to something that small. You cannot start with 3-byte pointer program and then dynamically upgrade everything to 4-bytes if you ever run out of space. Might as well make everything 4-byte from the start.

You're assuming byte-addressable memory. I'm assuming that these pointers or references would point to memory objects of arbitrary size, determined by what the variable, object, or function needs. I don't see why a program can't just tag its objects and entities in a virtual memory space with clean and compact pointers (but without garbage collection – just virtual memory.) I feel like there's not enough *virtual* in virtual memory right now – we should be able to abstract more.

https://www.irisa.fr/alf/downloads/roho ... _CGO11.pdf

On the issue of a Rx register, I think it might be a useful abstraction in some cases. You said that CPUs do this already, that we don't know what register we're getting. Yet, we're still naming registers explicitly, and you find it useful to retain named registers in an ISA. There are benefits to have named architectural registers, and I think there would be benefits from anonymous register semantics. Hubert asked how we'd refer back to it. There would be rules about how such register semantics could be used, and how to manage them – they wouldn't be the same as the normal registers. There are few ways to go about it.

Hi, related to the JIT discussion I think the proposed ISA needs specific instruction for memory copying, initialization and comparison. Especially, memory copying from small number of bytes to big is important in GC related scenarios. Often memory copy ends up being implemented as multiple complicated vector instructions, when an ISA instruction would be so much better (the CPU could then handle this in the most optimized way for it). Some research has been done on this where adding "cpblk", "initblk" instructions where evaluated and these showed great benefit for code size and speed. I would allow these instructions to have element size defined i.e. 1, 2, 4, 8, 16 bytes for example so one can initialize a "double" array quickly, perhaps even a zero out "zeroblk" instruction since this is used a lot in managed memory scenarios.

Thank you for the reference to Explicit Data Graph Execution (EDGE) https://en.wikipedia.org/wiki/Explicit_ ... _execution
If the EDGE principle can be implemented smoothly, it might be more efficient than splitting a job into multiple threads running in multiple cores. The thread management, synchronization, and communication between threads is very complicated and inefficient in current systems. An alternative would certainly be worth exploring.

However, I don't quite understand how the Hyperblocks are coded and delimited.

I do have a design in store that does what EDGE does, and should be targettable from C++ compilers but it's kinda weird:

- Registers are the accumulator (ac), and a rotating register file with 4 partitions of 16 registers (a0-a15, b0-b15, c0-c15, d0-d15). The ALLOC instruction shifts down register file names, so for instance ALLOC d10..d15 will move down the previous contents of d15 to d9, the content of d14 to d8, d13->d7, d12->d6, d11->d5, d10->d4, d9->d3, d8->d2, d7->d1, d6->d0, and the contents of d0..d5 are lost. The new values in registers d10..d15 are marked as "uninitialized" and instructions that try to read them will stall until the registers are written to.

Thank you for explaining your idea. It might be a problem that you have only one accumulator.

The best candidate for an independent instruction block is a loop iteration with no loop-carried dependency. I think it would be easier for the compiler in this case to just use a very long vector register with variable length to cover multiple iterations of the loop at once.
The main problem with very long vectors is instructions that move data horizontally across a vector. The latency of horizontal data moves may increase with the vector length. I have an idea to mitigate this problem a little. All instructions that involve horizontal data movement across a vector have information about the distance of the move (e.g. index or shift count) in a separate register or an immediate constant. The scheduler wants to know the latency of the instruction as early as possible. It will be allowed to read the "distance register" at an early stage in the pipeline before the other operands are ready. This value will typically be available early anyway thanks to out-of-order execution. There is probably no way to avoid the data transfer delay, but horizontal moves will be rare anyway. Current designs are already reading registers used in address calculation earlier in the pipeline than operand registers. I want to use a similar mechanism for predicting instruction latency.
It will also be an advantage to know the vector length early so that it can clock gate or power down unused parts of the buses and ALUs to save power.

If you need a second accumulator, that means that your calculations has two branches to it (either from a split or a join), which means it has some parallelism to it

that's not too hard to do if the vector lengths are in the normal register file, and the SIMD unit is running late compared to the scalar integer unit. Maybe you could have multiple swizzles with different granularities and delay times - like a 1 byte granularity scramble, and then maybe a 4 byte scramble, 16 byte scramble, a 64 byte scramble... Maybe the cpu could look in the swizzle data and figure out how many 0 bits there are and use the coarsest correct granularity.

I think the proposed ISA needs specific instruction for memory copying, initialization and comparison.

BOOST: Berkeley's Out-of-Order Stack Thingy

high = a + b
low = a + b - high // (with extra precision in the intermediate)

high = a + b;
if (abs(a) > abs(b)) {
   low = b - (high - a);
} else {
   low = a - (high - b);
}

It should be too late.
but since I found a research today, I ask for it.

BOOST: Berkeley's Out-of-Order Stack Thingy
https://www.researchgate.net/publicatio ... ack_Thingy

Same as "register renaming" for register machine, these researcher propose "address renaming" for stack machine to implement out-of-order execution.
So I think there are no reasons to prevent stack machine for performance problem.
Since stack machine instruction sets never bother us with number of registers, I think stack machine's ISA is more extensible than register machine's.
Also, stack ISA is easer for compilers as UCSD p-System showed.
it should also hold true for Just In-time Compiling.

The one thing I do like about stack based architectures is how they reduce the number of register file read/writes, and intuitively I'd be more interested into a model that (1) also has registers (ie it's not using the stack to store values but rather to keep track of very short lived temporary values - and it has the nice property that the lifespan of values is well known) (2) has a limited stack stack depth - something like 16 values with no automatic spilling (ie just enough for calculations, function calls would still be done using the normal RISC mechanism and explicit memory operations for register/stack spills) (3) you're supposed to keep the stack empty as often as possible so that the CPU can automatically figure out which sections it can run in parallel (each time the size falls to 0, that's a new parallelizable section).

Hubert Lamontagne wrote:

The one thing I do like about stack based architectures is how they reduce the number of register file read/writes, and intuitively I'd be more interested into a model that (1) also has registers (ie it's not using the stack to store values but rather to keep track of very short lived temporary values - and it has the nice property that the lifespan of values is well known) (2) has a limited stack stack depth - something like 16 values with no automatic spilling (ie just enough for calculations, function calls would still be done using the normal RISC mechanism and explicit memory operations for register/stack spills) (3) you're supposed to keep the stack empty as often as possible so that the CPU can automatically figure out which sections it can run in parallel (each time the size falls to 0, that's a new parallelizable section).

That sounds useful, but isn't this the same as x87? The main problem with x87 is that you have to do a lot of register swapping to get each operand to the top of the stack when you need it. Each value gets swapped to different positions several times through its life time so that it gets difficult to track where each value is. I haven't seen any compiler that can handle register variables nicely and keep them on the stack. If you want to avoid all that swapping then you need to access registers that are not on the top of the stack, and then the stack idea sort-of disappears. Is there a better way of doing this?

loop:
push r9
shr 16
push short [r8 + stack*2]
pop r0 ;renames r0

;this section can execute in parallel (once registers have been renamed)
push r9
shr 16
add 1
push short [r8 + stack*2]
sub r0 ;waits after renamed r0
push r9
and 0xffff
mul stack
sar 16
add r0
pop short [r7]

;this section can execute in parallel
push r9
add r10
pop r9 ;renames r9

;this section can execute in parallel
push r7
add 2
dup
pop r7 ;renames r7
cmp r11
branch if lower to loop

Do you have any plans for writing an assembler or a simulator?
(or other more involved stuff like a verilog/vhdl implementation or a c compiler... though that's a lot of work!)

• The most important system functions have fixed ID numbers which can be inserted at compile time.
• The ID number can be found at load time in the same way as relocation works. The loader will find the ID number and insert it in the code before running the program.
• The ID number is found at run time before the first call to the desired function.

progress will be slow as long as this is a one man project.

Could I suggest that you move the development incl. discussions of CRISC to GitHub instead?

Could I suggest that you move the development incl. discussions of CRISC to GitHub instead?

• Static linking. This will work the same way as today.
• Load-time linking. The library is linked with the executable program by the loader when the program is loaded into memory.
• Run-time linking. The library is loaded by commands in a running program.

• The main program may have reserved extra memory space for the library functions. This information is stored in the header of the executable program file. The library function is accessed through a function pointer which is returned by the load_library function. Any DATA section in the library can be addressed through DATAP, using the normal relocation procedure.
• If there is no reserved space, or the reserved space is too small, then the loader must place the library function somewhere else in memory. If there is a vacant memory space within a distance of +/- 2 GB from the address in DATAP then the same method as above is used.
• If there is no vacant space within 2 GB of DATAP then the loader can insert a stub that changes DATAP to point to the DATA section of the library function. The function is called through this stub, which changes DATAP when called, and restores the old value of DATAP on return. If the function can throw an exception then the exception handler needs to restore DATAP as well.
• The library function can be compiled with a compiler option that tells it not to use DATAP. The function will load the absolute address of its DATA section into a general purpose register and access its data with this register as pointer.

• There is only one type of function libraries. The same library can be used with any of the three methods: static linking, load-time linking, and run-time linking.
• Only the part of the library that is actually needed is loaded.
• The code and data of the library is contiguous with the code and data of the calling program in most cases. This makes memory management simpler, avoids memory fragmentation, and improves caching.
  There are no intermediate import tables, procedure linkage tables or global offset tables to reduce the performance.

How would you deal with non-reentrant functions (and their global data) belonging to the same library in all your three types?
And subsequent non-exported & helper functions internal to the library that could potentially modify those global data?

GUIs tend to use a lot of library code. I'm worried that copying so much code into private memory for every process will use significant amounts of memory.

most programs will use the same libc functions

Linux supports custom executable file formats, or for this experiment we could use ELF with a different dynamic linker as a custom ELF-interpreter.

GUIs can be implemented very lightly now with immediate-mode libraries like imgui: https://github.com/ocornut/imgui

Statically-linked executables are gaining momentum with Go and, on the C side, musl. A musl executable is much lighter than a glibc one.

Agner, it seems like your proposal could either eliminate the need for tree-shaking, or require a new kind of tree-shaking, depending on implementation details. Would code be tree-shaken by default, in that nothing is included unless it's used, kind of an opt-in vs opt-out scenario?

You'll have to cover the security angles here or no one will accept it. There are lots of pointer memory management add-ons to C right now that make decisions about which kinds of pointers will be stored where and so forth. How will your ISA integrate with those methods? I'm thinking of things like Code Pointer Integrity and SafeStack: dslab.epfl.ch/proj/cpi/

With regards to static vs dynamic linking it is probably worth considering the following note by Ulrich Drepper

have you checked out the work of Darek Mihocka who some years ago wrote a multi-part series on fixing x86 (and, interestingly, proposed eliminating hardware paging)

What about debugging?

Agner wrote:

Hubert Lamontagne wrote:

The other reason I can think of to have user-accessible stack is supporting coroutines.

If coroutines are implemented with a call stack, it would be filled up. Are you thinking about removing an entry from the call stack before calling another routine? The same functionality can be obtained with a tail call or a state machine.

The next version of my proposal will have a calling convention that makes tail calls possible in all cases. In the rare case that there are more than 16 integer parameters or 16 vector parameters to a function, the remaining parameters will not be stored on the stack but in a list pointed to by a register. The same method applies to a variable arguments list.

As for the cases where you have more than 16 integer or vector/float parameters, how do you allocate that list for extra parameters? Isn't the simplest way to do that to allocate it on the stack? Or would you call malloc()?

If you want multiple stacks for coroutines, why not use multiple threads? Anyway, a coroutine switch would work much the same as a thread switch does in the operating system.

the catch is that a thread switch goes through the thread scheduler. That's totally fine if you're doing something that doesn't need any tight timing (ex: server software), but it's a problem in very real time apps

Hubert Lamontagne wrote:

the catch is that a thread switch goes through the thread scheduler. That's totally fine if you're doing something that doesn't need any tight timing (ex: server software), but it's a problem in very real time apps

You are right. We need to think about real time applications. Is there anything special we need to do to support real time operating systems? It would be nice to be able to reserve one or more CPU cores in a multicore processor for a particular critical task, but that is an operating system issue. The hardware just needs to support fast task switching. We can have extremely fast task switching if the CPU has multiple on-chip memory maps that it can switch between.

• Security features added.
• Support for dual stack.
• Some instructions and formats modified, including more formats for jump and call instructions.
• System call, system return and trap instructions added.
• New addressing mode for arrays with bounds checking.
• Memory management and ABI standards described in more detail.
• Instruction list in comma separated file instruction_list.csv to be used by assemblers, emulators, debuggers, etc.
• Object file format defined in file elf_forwardcom.h

• The ForwardCom instruction set is a compromise between the RISC and CISC principles, combining the fast and streamlined decoding and pipeline design of RISC systems with the compactness and more work done per instruction of CISC systems.
• The ForwardCom design is scalable to support small embedded systems as well as large supercomputers and vector processors without losing binary compatibility.
• Vector registers of variable length are provided for efficient handling of large data sets.
• Array loops are implemented in a new flexible way that automatically uses the maximum vector length supported by the microprocessor in all but the last iteration of a loop. The last iteration automatically uses a vector length that fits the remaining number of elements. No extra code is needed to deal with remaining data and special cases. There is no need to compile the code separately for different microprocessors with different vector lengths.
• No recompilation or update of software is needed when a new microprocessor with longer vector registers becomes available. The software is guaranteed to be forward compatible and take advantage of the longer vectors of new microprocessor models.
• Strong security features are a fundamental part of the hardware and software design.
• Memory management is simpler and more efficient than in traditional systems. Various techniques are used for avoiding memory fragmentation. There is no memory paging and no translation lookaside buffer (TLB). Instead, there is a memory map with a limited number of sections with variable size.
• There are no dynamic link libraries (DLLs) or shared objects. Instead, there is only one type of function libraries that can be used for both static and dynamic linking. Only the part of the library that is actually used is loaded and linked. The library code is kept contiguous with the main program code in almost all cases. It is possible to automatically choose between different versions of a function or library at load time, based on the hardware configuration, operating system, or user interface framework.
• A mechanism for calculating the required stack size is provided. This can prevent stack overflow in most cases without making the stack bigger than necessary.
• A mechanism for optimal register allocation across program modules and function libraries is provided. This makes it possible to keep most variables in registers without spilling to memory. Vector registers can be saved in an efficient way that stores only the part of the register that is actually used.

Hi Agner – Can you recap how you resolved the objection that Hubert had to unified int/floating point registers?

How do you situate your ISA in the context of the current trend toward heterogeneous computing, GPGPU, AMD's HSA, OpenCL, OpenMP, OpenACC, FPGAs, etc.? Will the new ISA help, hinder, or be neutral to heterogeneous programming?

This is an interesting time to develop a new ISA because of the oft-claimed end of Moore's Law scaling. How do the anticipated physics of the next 10 – 20 years of microprocessor design impact ForwardCom? Is the physical substrate irrelevant?

Is ForwardCom extensible to a unified RAM (volatile) and non-volatile memory space? There are a few proposals out now, including Moneta D, that rethink the file system and make calling solid state storage a lot like calling a memory address (or just the same thing). They mostly hinge on faster-than-SSD media.

I think it would be interesting if applications could set a few custom constants at start time. A while back I asked about having useful constants hardwired in the CPU (e.g. π), and you guys explained why it probably wouldn't be worth it. I think letting each application tell the CPU to save a few constants that the application will often use might be more useful. The point is to be able to invoke the constant without an immediate, but just with a much smaller shortcode (two or three bits). It's kind of like an application-specific cache

An expanded version of this would be to be able to define and save specific, short code sequences. (I see your Chapter 6, but it seems like a placeholder for now.)

What's the exact algo for determining if an OP contains a memory load?

What's the exact algo for determining if an OP is integer or FPU/vector?

• The mode field is 0 or 1 when ignoring M (format 0.0, 0.1, 0.8, 0.9, 1.0, 1.1, 1.8, 2.0, 2.1, 2.8.x, 2.9, 3.0, 3.1)
• Format 2.6
• Tiny instruction with OP1 < 16
• Jump instructions with no M field (format 1.5, 2.7.2, 2.7.3, 2.7.4) or M = 0.
• Registers operands for pointer, index and vector length are always general purpose registers

• The mode field is 2-7, except format 2.6
• Tiny instruction with OP1 ≥ 16
• Jump instructions with an M field (format 1.4, 2.7.0, 2.7.1, 3.0.1) and M = 1

• Format 1.4 and 1.5
• Format 2.7 with OP1 = 0-4
• Format 3.0 with OP1 = 1

Some questions about your memory model:

- For every Load/Store, how is the CPU going to differentiate which memory map entry it falls into? If you have 16 memory map entries, does it compare every load/store address to all 16 block start addresses? (which requires 16 comparators in hardware if you want to calculate it in a single cycle?! or multiple cycles of latency and 4~5 comparators?!?)

If I understand your memory allocation scheme correctly, every program's heap size is determined beforehand, and when it grows beyond that size, you absolutely have to use up one more memory map entry? Wouldn't that use up memory map entries really fast and go through hundreds of memory map entries for complex applications like a web browser?

Wouldn't you at least require memory blocks to be aligned to L1 cache way size? (usually 4k~32k on modern CPUs?)... Or at very least, wouldn't it have to be aligned to L1 cache line size? (32~64 bytes typically?)

My reason for using the same registers for floating point scalars and floating point vectors is that floating point code often contains calls to mathematical function libraries. Such a library can use variable-length vectors for parameters and results. The same library function can be called with a scalar or a vector because a scalar is simply handled as a vector with one element. This will make it easy for the compiler to vectorize the code. ForwardCom has a separate register set for integer scalars. These are useful for pointers, loop counters, array indexes, etc. that don't need vectors, and they are easier to save and restore than vector registers.

for (int i = 0; i < N; i++) {
    if(a(i) != 0)
        b(i) = sin(a(i));
}

Does the ABI define a register as the "current mask" (GPU-like)? Or should the caller compact input vectors to have only contiguous elements, and expand the output vectors (vector processor-like)?

my point is that the mask could be part of the ABI, just as vector length (implicitly) is. This would enable vectorization-agnostic composition of function calls.

By the way, have you considered the micro-architecture and compiler implications of using a subset of vector registers as masks?

Instructions take up 5 input operands from vector registers (RS, RT, RU, Mask, RD). The old register value RD is required to merge the result.

making the operation dependent on the former value of the architectural destination register defeats the purpose of register renaming: write-after-read dependencies are still there.

A more acceptable implementation would break down each masked instruction into 2 µops: first a computation on the whole vector, then a merge (I believe that is how Knights Landing and Skylake handle masked AVX-512 instructions).

More generally, masks encode control flow information, while vector registers encode data flow information.

A function may have an unlimited number of input parameters and an unlimited number of outputs (through pointers or references or class members or whatever, all of which could in principle have different masks. That would add a lot of complexity to the ABI for something that is rarely needed. I prefer to specify a mask as an explicit function parameter in the rare cases that it is needed.

So, the total maximum number of input dependencies is five, but the maximum number of input dependencies at one stage in the pipeline can be limited to three if necessary.

making the operation dependent on the former value of the architectural destination register defeats the purpose of register renaming: write-after-read dependencies are still there.

All superscalar processors handle this by renaming the register so that the input and output use two different physical registers.

I have not been able to get my hands on any AVX-512 processor yet, so I am not able to test it. If you have any information on the microarchitecture of these processors then please give me a link.

AVX-512 permits instructions to use masking. The best performance usually happens for instructions that do not use masking. Instructions that mask with zeroing usually have similar performance. Instructions that mask with merging can occasionally perform much slower, since there is an additional dependency introduced to the instruction. Keep in mind performance considerations when selecting the masking mode.

Agner wrote:

So, the total maximum number of input dependencies is five, but the maximum number of input dependencies at one stage in the pipeline can be limited to three if necessary.

The pipeline stage does not make a difference. If you want to sustain an execution rate of three 5-input instructions per clock cycle, you need the bandwidth to read 15 inputs per cycle on average from the register file. It does not matter in which order and at which pipeline stage they are read.

Yes, x86 instructions also output flags, but x86 CPUs use tricks to turn them into single-output instructions by having slightly wider physical registers, storing the flags in the physical destination register, and renaming the architectural flags register to the physical destination of the last instruction issued.

Masked code

mul_add.d v0, v1, v3, v4, mask=v8
mul_add.d v0, v5, v6, v7, mask=v9

Renaming still maps v0 to different physical registers p0 and p1, but the second FMA now has a data dependency on the older value of v0, which is p0.

for (i=0; i < vectorlength; i++) 
    v0([i] = v5[i] ? v1[i] + v3[i]*v4[i]  :  v1[i];

AVX-512 permits instructions to use masking. The best performance usually happens for instructions that do not use masking. Instructions that mask with zeroing usually have similar performance. Instructions that mask with merging can occasionally perform much slower, since there is an additional dependency introduced to the instruction. Keep in mind performance considerations when selecting the masking mode.

Their formulation suggests they follow the single-instruction approach with naive scheduling. They do not appear to split in two µops after all. But if they write "much slower" they probably mean it...

The takeaway is that the masking mode (zeroing or merging) should be available as early as possible in the pipeline, ideally at decode just by looking at the instruction. And the programmer/compiler should use zeroing whenever possible.

Could you have two separate sets of regiser read ports, one that is wired to the address calculation stage in the pipeline (general purpose registers only), and one that is wired to the execution stage?

Interesting. I wonder where you have all this information from?

No. Without zeroing, the mask chooses between the result and the first input operand, which is not the destination operand.

Correction: I meant WAW dependencies in my previous messages, not WAR dependencies.
Agner wrote:

Could you have two separate sets of regiser read ports, one that is wired to the address calculation stage in the pipeline (general purpose registers only), and one that is wired to the execution stage?

If both sets of ports access the same physical array of registers, then the RF component still needs m+n ports, regardless of where its ports are connected to.
If you replicate the array itself to make two copies of the register file, then yes, it works.

Then another complication is the bypass network, which does not scale well with the number of ports either.

Interesting. I wonder where you have all this information from?

Unfortunately, academic papers seldom go down to that level of detail, so you have to microbenchmark, speculate, and read patents.

Even on these 20 year-old architectures, you can see the renaming techniques are quite involved. (Thanks to the infamous INC/DEC instructions that only update a subset of the Flags register...)

I was expecting the semantics of masked instructions to be "pretend nothing happens on lanes with a 0 bit mask".

Do you have code examples showing how a compiler can perform if-conversion from some arbitrary code?

Also are there instruction encodings to chose between the result and the second operand (e.g. v0 = v5 ? v1 + v3 * v4 : v3; for a conditional Horner step) ?

Can you bypass a result to multiple in-flight instructions using the same bus? If so, you need only few bypass buses.

Do you have any references on how the register read ports are designed and why they are so expensive?

Do you have code examples showing how a compiler can perform if-conversion from some arbitrary code?

A branch in a vectorized loop is translated to a mask. All the good compilers can do this today.

for all i {
  int x = a[i];
  int y = b[i];
  if(x > y) {
    y = x + 1;
  }
  c[i] = y;
  d[i] = x;
}

That was not my plan, but of course such an instruction could be defined if there is a need for it. But why would you have a conditional inside a polynomial?

Rixner et al., Register Organization for Media Processing, HPCA 2000.
www.ai.mit.edu/projects/aries/papers/im ... gister.pdf
evaluates the tradeoffs using analytical models and considers various distributed and SIMD RF organizations.

Which code is generated when you vectorize :

for all i {

(And the compiler has to assume that arithmetic exceptions might be enabled.)

• Use a flag output. This gives every ALU instruction an extra output dependency, and also an extra input dependency if you want the overflow bit to be propagated through a series of calculations. The extra input and output dependencies hamper out-of-order processing.
• Add an extra overflow bit for each vector element in a vector register. This adds an extra complication for saving the overflow bits when a vector register is spilled to memory.
• Use exception traps (interrupts) to catch integer overflow. This requires a minimum of complexity to the instruction set, but it has a problem with vector code.
• Use the even-numbered elements in a vector register for calculation and the odd-numbered elements for propagating overflow information. This is relatively easy to implement but wasteful because only half of the ALUs are used.

The following methods for detecting integer overflow may be considered:

• Use a flag output. This gives every ALU instruction an extra output dependency, and also an extra input dependency if you want the overflow bit to be propagated through a series of calculations. The extra input and output dependencies hamper out-of-order processing.
• Add an extra overflow bit for each vector element in a vector register. This adds an extra complication for saving the overflow bits when a vector register is spilled to memory.
• Use exception traps (interrupts) to catch integer overflow. This requires a minimum of complexity to the instruction set, but it has a problem with vector code.
• Use the even-numbered elements in a vector register for calculation and the odd-numbered elements for propagating overflow information. This is relatively easy to implement but wasteful because only half of the ALUs are used.

Method 1 has been rejected. The other three methods are still being considered for use in ForwardCom.

Sylvain Collange wrote:

What about:
5. Same as 3, and use "traditional" masking on all SIMD instructions.
In traditional masking, an SIMD instruction working on vectors of n operands takes an n-bit mask. For each lane i: If bit i is set, the operation is performed normally on lane i (including triggering exceptions as needed). If bit i is unset, nothing happens on lane i (including silencing exceptions). If multiple exceptions happen in the same vector, you may either report them all at once by exposing an exception mask, or report them one by one in a well-defined order.

I can think of a couple more options:

Method 5 : Have an extra instruction that applies the operation but generates potential-overflow-or-exception flags instead of result values. This is equivalent to option 1 but using 2 instructions instead of one (but is roughly the same cost in the pipeline since you need 2 micro-ops in both case to store all the results), or it's like option 4 but without having the two results interlaced together.

Method 6 : Have separate vector flags registers. This is like method 1 but instead of having the extra inputs and outputs go to the same register file (which requires more ports and thus more micro-ops), they go to a separate register file that only deals with flags which means that they can have their own register renamer and have their own ports, which avoids the N^2 growth associated with adding more ports.

Method 7 : Do it all in software. This makes checked operations take multiple instructions which might be slower. But it reduces the overall complexity of the design which means that you might be able to run 1 or 2 more instructions per cycle, which probably offsets the extra cost of separate checking. This can probably be combined with option 5 (just have a couple extra instructions for speeding up overflow checking for the cases that really need it).

Very rough cost-benefit analysis:

• If the purpose is to abort the application in case of overflow for security reasons then method (3) might be the easiest solution.
• If the purpose is to recover from an overflow condition by re-calculating with bigger integers then method (3) might also be acceptable if overflows are rare.
• If the purpose is to detect the carry output of unsigned addition then we may perhaps prefer method (4).
• If the purpose is some kind of advanced compensation for signed overflow then I don't know what method is best.

Perhaps the choice of method depends on the purpose of overflow detection:

• If the purpose is to abort the application in case of overflow for security reasons then method (3) might be the easiest solution.

If the purpose is to recover from an overflow condition by re-calculating with bigger integers then method (3) might also be acceptable if overflows are rare.

If the purpose is to detect the carry output of unsigned addition then we may perhaps prefer method (4).

If the purpose is some kind of advanced compensation for signed overflow then I don't know what method is best.

I consider this as implied in (3) because the mask in ForwardCom suppresses all error conditions for disabled elements. Maybe I didn't express this clearly enough. It is still a problem that the behavior depends on the vector length. If a loop generates two exceptions then these exceptions may happen simultaneously if vectors are long, but separately if the same code is run on another processor with shorter vectors. It is difficult to construct the exception handler so that it is guaranteed to generate the same result regardless of the vector length of the microprocessor.

If you have enabled exceptions for integer overflow and you want to avoid the hypothetical overflow exception in a not-taken branch then you have to put the mask on the addition instuction as well. In other words, you will have two masked instructions using the same mask.

This is the reason why exceptions are not good in a vector processor. In floating point code you can disable exceptions and rely on the propagation of NAN and INF values to detect numeric errors. But there is no easy way of detecting integer overflow. I have discussed this in a previous post, but there seems to be no good solution. Many compilers and programming languages simply have no easy way of detecting integer overflow, but this may be a security problem, so I thought that we must provide some method. The following methods for detecting integer overflow may be considered:

• Use a flag output. This gives every ALU instruction an extra output dependency, and also an extra input dependency if you want the overflow bit to be propagated through a series of calculations. The extra input and output dependencies hamper out-of-order processing.
• Add an extra overflow bit for each vector element in a vector register. This adds an extra complication for saving the overflow bits when a vector register is spilled to memory.
• Use exception traps (interrupts) to catch integer overflow. This requires a minimum of complexity to the instruction set, but it has a problem with vector code.
• Use the even-numbered elements in a vector register for calculation and the odd-numbered elements for propagating overflow information. This is relatively easy to implement but wasteful because only half of the ALUs are used.

Method 1 has been rejected. The other three methods are still being considered for use in ForwardCom.

• Requires 2 micro-ops. Note that this is fine if you have to support 2 micro-op operations for other reasons.
• Effects depends on the ABI. If you mandate that callees don't have to save the flags and can trash them, then you only need special save/restore in interrupt handlers.
• Depends on if the design is in-order or out-of-order. For in-order, this makes an Arm NEON style delayed-SIMD pipeline impossible because all downstream instructions become conditional. On out-of-order, this adds an extra path from the SIMD unit to the retirement unit to signal potential interrupts (plus more complex conditional writeback of other operations retiring on the same cycle).
• Potentially adds more shuffling of values around to add and remove space for flags. Plus, you're potentially getting half as much vector processing for a given register size.
• Adds more ALU instructions to deal with. Added instructions are kinda quirky.
• Requires addition of full vector flags handling unit, some instructions to load/store flag reg values, potential stalls if too many flags instructions are issued at the same time.
• Error checked code that isn't limited by memory or branch prediction might run slower, but non-error-checked code might run faster. Simpler architecture is easier to implement and verify.

Joe Duarte wrote:

I think it would be interesting if applications could set a few custom constants at start time. A while back I asked about having useful constants hardwired in the CPU (e.g. π), and you guys explained why it probably wouldn't be worth it. I think letting each application tell the CPU to save a few constants that the application will often use might be more useful. The point is to be able to invoke the constant without an immediate, but just with a much smaller shortcode (two or three bits). It's kind of like an application-specific cache

ForwardCom can have constants embedded in instructions. This includes integer constants of all sizes and floating point constants of half, single and optionally double precision (requires 1, 2 and 3 word instruction size, respectively). Your idea would require an extra register set for saving and restoring data that will be needed later. This extra register set would just require two extra instructions for copying data from a normal register to an extra register and vice versa. This could be useful for many purposes and it would reduce the pressure on the data cache. The only problem I can see is that it will be an extra complication to the function calling convention because we need to know whether a function modifies the extra registers or not.

Agner, by the way, I just learned that my idea for small cache for constants (preferably in the form of special registers, or at least an L1 speed cache) has been widely implemented for years in Nvidia GPUs. It's called "constant memory", and reserves 64 KiB.

In fact, I don't think ISAs should settle on 32-bit and 64-bit types and registers unless those turn out to be optimal sizes, which I think is unlikely. As long as we can take care of alignment issues, I would determine the right type and register sizes empirically, based on what we know about common workloads and applications, as well as foreseeable future workloads.

The Itanium did not have success with "explicit parallelism" because it was too difficult to handle for the compiler. Maybe "explicit caching" will be easier to handle. You might want to specify explicit caching for the top of the stack in the innermost loop or for often-used constants, jump tables or global variables.

Another possibility would be to reserve the extra cache for a particularly critical process. This process would monopolize the extra cache in one or more CPU cores while less important processes would be prevented from accessing it. That's an extra complication for the operating system to keep track of, but it is a quite common scenario that one process is speed-critical while all other processes are unimportant background processes.

Another possibility, which is perhaps simpler to handle, is an extra set of registers which are used for extra storage. Assume, for example, that we supplement the vector registers v0 - v31 by an extra set of vector registers w0 - w31. The extra registers can perhaps do nothing but read and write, e.g.

w8 = v5;
v2 = w8;

These extra registers can be used for often-used constants, for global variables, and for temporarily storing a normal register rather than saving it on the stack.

With an extra set of registers you have the complication of calling conventions. ForwardCom has a mechanism for telling the compiler which registers are modified by e.g. a library function. This mechanism could be extended to the extra registers. A library function could save a callee-save register to an extra register rather than saving it on the stack and reserve this extra register by indicating in the object file which extra registers it is using. The extra registers still have to be saved at every task switch if they are used.

For example, maybe some instructions are only allowed at the start of a process. After a certain milestone, some instruction codes switch to represent different instructions – instructions that cannot be used at the start of a process, only after the milestone.

I wonder if we could use a powers-of-two type, such that the literal binary value would represent an exponent of two, e.g. 10001101 would mean 2^141. Something like that would help with encoding some large numbers, though powers of two might not be the right form.

Relatedly, instead of hard-coding a single constant like π the way I was thinking several months ago, there could be a type that represented a set of constants – maybe four or five bits to encode 16 to 32 predesignated constants that were empirically determined to recur frequently enough in a wide range of applications to be worth encoding.

And I wonder about simpler, more specialized cores. Right now you've got all these powerful AVX, AVX2, BMI, FMA, TSX instructions and all the legacy x86 and 386 instructions supported on every single core. Maybe it would make sense to have a couple of Turbo cores or something that were SIMD-only, or optimized for heavy compute or HPC workloads. There's been some research on how to design a processor tailored for OpenCL, for example. Maybe ForwardCom could have a simpler, faster subset of the ISA designed for highly parallelized applications using OpenMP, OpenCL, or something like Threaded Building Blocks. It would be like Big/Little, but more specifically aimed at high performance parallel code in the little cores. A new ISA doesn't have the backwards compatibility constraints Intel is limited by, where they throw the kitchen sink into every core.

It is probably not difficult to create a new x86 version that is user mode compatible with most modern programs but lacks things like segmentation (including the GDT/LDT) and real mode. New OS versions would be required, but most modern user mode programs would work with few if any modifications. Anyone want to do a proposal for that?

What do you think of "branch delay slots" ?

One thing software developers know is which procedure will be called on a function pointer (because of polymorphism, indirect branches have become quite popular), but the hardware couldn't possible know it.

Cache miss is also a big topic. Suppose I have five functions (functions in the mathematical sense), A, B, C, D, E, which can be fully executed in parallel. The calls instructions are laid in the following order:

CALL A; CALL B; CALL C; CALL D; CALL E;

But only the data for the E function is ready (is on the cache). Would the processor stall, while waiting for the data of A, B, C, D arrive? And, even worse, wait for the completion of A, B, C and D?

I like that vectors are present on this new instruction set and are an important part of it. Many algorithms use matrix multiplication, which can greatly benefit from instruction-level parallelism, but the current instructions sets are simply disappointing.

What do you think of "branch delay slots" ?

Cache miss is also a big topic. Suppose I have five functions (functions in the mathematical sense), A, B, C, D, E, which can be fully executed in parallel. The calls instructions are laid in the following order: CALL A; CALL B; CALL C; CALL D; CALL E; But only the data for the E function is ready (is on the cache). Would the processor stall, while waiting for the data of A, B, C, D arrive? And, even worse, wait for the completion of A, B, C and D?

Many algorithms use matrix multiplication, which can greatly benefit from instruction-level parallelism, but the current instructions sets are simply disappointing [...] it's simply not possible to express it nicely with the instructions given by x86 or x64.

A possible route forward would be a SIMD "transpose with broadcast" instruction, taking a single vector of P contiguous elements and broadcasting each element across one of P output SIMD registers.