Block copy instructions

[westfw]

Isn't this getting into the "much ado about nothing" when your pipelined instruction stream is churning along at less than 1cycle (<1ns) per instruction, but your memory is taking 60ns or so for each access?  block copies are going to be more limited by cache architectures and memory system than whether you have a specialized instruction or not.

(ok, I'm curious - the cache on modern CPUs is pretty complex and generally under-documented.  For an N-byte block copy, what percentage of the memory accesses (both source and destination) are likely to hit what level of cache?)

(and this overlooks common block copies, ie for IO, where either source or destination is KNOWN to be in "external" memory.)

[Nominal Animal]

This is not correct. Adding autoincrement loads to an ISA such as RISC-V suddenly requires that it be possible for an integer instruction to write results to two registers instead of one.

That only applies to loads.  Another possibility for loads is to merge the autoincrement/decrement into the pointer comparison branching instruction. (Then only two additional instructions are needed: one that autoincrements a register and branches if it is less than (or equal to) another register; and another that autodecrements a register and branches if it is greater than (or equal to) another register.  Technically, branching whenever not equal suffices.  Whether the register store is done always, or only when the branch is taken, and whether the autoincrement/decrement occurs before or after the comparison, is irrelevant as long as it is consistent.)

Note that my analysis is not based on instruction count: it is based on the commonality among all these block functions.  The address increment/decrement is the common factor, and if it can be merged with one of the other functions without additional cycle cost, it will bring the savings.  The reason I assumed they would be done in conjunction with the loads and stores – although I explicitly said I don't care if the addresses are pre- or post-incremented/decremented – is that many architectures have that.

Just because autoincrement/decrement is problematic with loads, I would not throw out the entire idea.

[brucehoult]

Isn't this getting into the "much ado about nothing" when your pipelined instruction stream is churning along at less than 1cycle (<1ns) per instruction, but your memory is taking 60ns or so for each access?  block copies are going to be more limited by cache architectures and memory system than whether you have a specialized instruction or not.

For copies that don't hit in cache, absolutely right, though you do need to consider that your 60 ns access time is then going to give you at least 64 bytes of data -- so 16 loops of register copies on a 32 bit machine, or 8 loops on a 64 bit machine.

Also loads from L2 into L1 will for sure be in the L1 cache line size and will be a lot less latency than 60 ns (I think 5 to 7 ns is typical), while loads from RAM into L2 have big latency but may return several L1 cache lines worth of data.

For copying thing that are in cache, every instruction matters.

[brucehoult]

That only applies to loads.  Another possibility for loads is to merge the autoincrement/decrement into the pointer comparison branching instruction.

Agreed that the argument doesn't apply to stores (which is why I didn't mention them), and also that inc/dec and branch is a much less disruptive instruction.

There is also the possibility of combining autoincrement stores and loads with base+offset addressing, which I have written about here before. This fits well with typical code that reads more than one data item per loop but only stores one result.

[gf]

For copies that don't hit in cache, absolutely right, though you do need to consider that your 60 ns access time is then going to give you at least 64 bytes of data

In order to utilize the full memory bandwidth, multiple memory transactions must overlap over time. Consequently it is important to fill the CPU pipeline with enough memory fetch microinstructions, which can be pending simultaneously then, and/or arrange asynchronous prefetch to L1 cache. The former is usually achieved by unrolling the loop, the latter can be done explicitly via prefetch instructions or happens automatically. The CPU's automatic prefetch may take a couple of memory transactions, though, until it detects the sequential access pattern an joins in. Optimizing all this stuff depends very much on the particular microarchitecture.

In order that two instructions in the pipeline can be executed simultaneously, they must not have data dependencies. A sequence of auto-increment instructions like r2=*r1++, r3=*r1++,... actually has data dependencies (via r1), i.e. r3=*r1++ cannot start before r2=*r1++ has finished (unless the CPU splits them internally to microinstructions w/o auto-increment like r2=*r1, r1++, r3=*r1, r1++,... -- then the memory fetch microoperations can overlap again).

EDIT:
Yet another point which has not been considered/discussed yet (or maybe I missed it?) is branch misprediction of the copy loop's conditional branch. Branch misprediction penalty of 1..3 dozens of clock cycles is not unusual. In detail it depends of course on the particular microarchitecture, and the CPU's state and operations in progress when it happens.

[brucehoult]

In order that two instructions in the pipeline can be executed simultaneously, they must not have data dependencies. A sequence of auto-increment instructions like r2=*r1++, r3=*r1++,... actually has data dependencies (via r1), i.e. r3=*r1++ cannot start before r2=*r1++ has finished (unless the CPU splits them internally to microinstructions w/o auto-increment like r2=*r1, r1++, r3=*r1, r1++,... -- then the memory fetch microoperations can overlap again).

Right.

Yet another reason that r2=0[r1]; r3=1[r1]; r4=2[r1]; r5=3[r1] r1+=4 is a much better idea.

[gf]

In order that two instructions in the pipeline can be executed simultaneously, they must not have data dependencies. A sequence of auto-increment instructions like r2=*r1++, r3=*r1++,... actually has data dependencies (via r1), i.e. r3=*r1++ cannot start before r2=*r1++ has finished (unless the CPU splits them internally to microinstructions w/o auto-increment like r2=*r1, r1++, r3=*r1, r1++,... -- then the memory fetch microoperations can overlap again).

Right.

Yet another reason that r2=0[r1]; r3=1[r1]; r4=2[r1]; r5=3[r1] r1+=4 is a much better idea.

Yes, this eliminates even the data dependency via ADD instructions between the memory fetch instructions (although the ADD is usually just a single cycle, i.e. likely still neglligible when the memory fetch does not hit the cache).

[Nominal Animal]

Yet another reason that r2=0[r1]; r3=1[r1]; r4=2[r1]; r5=3[r1] r1+=4 is a much better idea.

Which works for large block copies, and does nothing to help with the other related operations.

[brucehoult]

EDIT:
Yet another point which has not been considered/discussed yet (or maybe I missed it?) is branch misprediction of the copy loop's conditional branch. Branch misprediction penalty of 1..3 dozens of clock cycles is not unusual. In detail it depends of course on the particular microarchitecture, and the CPU's state and operations in progress when it happens.

Ahhh ... 3 *dozens* of clock cycles? No way. I can't think of any machine that would apply to.

The penalty for a branch mispredict -- with both possible targets already in cache -- is strictly less than or equal to the pipeline length.

For example, the SiFive FE-310 (32 bit microcontroller) and FU-540 (64 bit Linux capable) both have 5 stage pipelines, and both have 3 cycle penalty for mispredicted branches.

The SiFive FU-740 has an 8 stage pipeline (two pipelines, as it is dual-issue). Mispredicted conditional branches usually have a 4 cycle penalty, except when they depend on the result of an instruction that issues in the same clock cycle as the branch (in the other pipeline). In this case there is a 6 cycle penalty.

Mispredicted indirect branches (i.e. JALR) have a 6 cycle penalty. As these are not conditional branches, the "misprediction" involved is failure of branch target prediction (including a mismatch in the return stack cache in the case of RET) rather than branch taken/not taken prediction.


The Out-of-Order U84 core has a 12 stage pipeline, and a 10 cycle branch mispredict penalty.

The AMD Zen 3 has an 11 to 18 cycle branch mispredict penalty. Skylake and Zen 1 are 19 or 20 cycles. ARM A72 is 15 cycles. A76 is 11 cycles.

I don't know of anything that is 2 dozen, let alone 3 dozen.

Note that with modern branch predictors that use a branch history table as part of the predictor (a series of true/false bits indicating whether the last N branches were taken or not taken, it is typical for loops that iterate just a few times (anywhere from 10 to 30) to have EVERY branch correctly predicted, including the final branch that exits the loop.

[gf]

Ahhh ... 3 *dozens* of clock cycles? No way. I can't think of any machine that would apply to.

I'm basically referring to the analysis of the authors of this paper which say that

    "the branch misprediction penalty can be substantially larger than the frontend pipeline length
     (which is often equated with the misprediction penalty)"

if the indirect side-effects of the misprediction are taken into account. Figure 1 shows the analyzed average penalties for a couple of different application profiles, and they range from 9 to 35 cycles. They are obviously very application-dependent. I was surprised, too, that the indirect effects can be so significant.

Note that with modern branch predictors that use a branch history table as part of the predictor (a series of true/false bits indicating whether the last N branches were taken or not taken, it is typical for loops that iterate just a few times (anywhere from 10 to 30) to have EVERY branch correctly predicted, including the final branch that exits the loop.

Luckily there are cases where this indeed works, but I still doubt that every branch inside a memcpy function can be predicted correctly, given that the function can be called with a different size argument upon each invocation.

Another point is that the BPT is basically yet another N-way cache (indexed by a couple of bits from the branch instruction's address), so that the former history of of a branch can get evicted, and the entry reused for other branch instructions in the program which happen to map to the same index.

[SiliconWizard]

Ahhh ... 3 *dozens* of clock cycles? No way. I can't think of any machine that would apply to.

I'm basically referring to the analysis of the authors of this paper which say that

    "the branch misprediction penalty can be substantially larger than the frontend pipeline length
     (which is often equated with the misprediction penalty)"

if the indirect side-effects of the misprediction are taken into account. Figure 1 shows the analyzed average penalties for a couple of different application profiles, and they range from 9 to 35 cycles. They are obviously very application-dependent. I was surprised, too, that the indirect effects can be so significant.

Thanks for the paper, I'll have a look. Certainly things can get hairy with superscalar CPUs.

Another point is that the BPT is basically yet another N-way cache (indexed by a couple of bits from the branch instruction's address), so that the former history of of a branch can get evicted, and the entry reused for other branch instructions in the program which happen to map to the same index.

Yep, but typical memory copy loops are pretty tight, which means addresses are relatively near, so the probability of a branch target being evicted in a tight loop is pretty low (since BTB indexing is most often on the lower bits of the addresses).

Of course, that is true only if the whole copy executes without any context switch. In case of a context switch in the middle of the copy, all bets are off.

[brucehoult]

Ahhh ... 3 *dozens* of clock cycles? No way. I can't think of any machine that would apply to.

I'm basically referring to the analysis of the authors of this paper which say that

    "the branch misprediction penalty can be substantially larger than the frontend pipeline length
     (which is often equated with the misprediction penalty)"

if the indirect side-effects of the misprediction are taken into account. Figure 1 shows the analyzed average penalties for a couple of different application profiles, and they range from 9 to 35 cycles. They are obviously very application-dependent. I was surprised, too, that the indirect effects can be so significant.

So they are talking about a different thing.

Their basic results seem to be that mispredicted branches frequently depend on a value loaded from RAM or L2 and that the ROB drains while waiting to resolve it. And that this happens often enough to be a significant factor.

I can well well believe this is true for the machine they base their results on!

The paper is rather old (written in 2005 for a conference in early 2006), and studies only one particular invented/simulated machine that is not at all representative of the machines of today:

- 4 wide Out-of-order superscalar
- 64 entry ROB
- 16 KB L1 dcache, 1 MB L2
- 12 cycle L2 access time, 200 cycle RAM access time

Machine we discuss here tend to be either microcontrollers running out of SRAM or else OoO desktop/smartphone CPUs with rather more execution resources.

4-wide is still typical for modern OoO CPUs. Apple has built an 8-wide monster, but let's ignore that for now -- benchmarks clearly indicate that they have the effect of mispredicts well under control.

- 64 entry ROB with 4-wide execution means there is only 16 cycles of instructions buffered. This compares badly to the 12 cycle L1 miss time, let alone RAM. Current CPUs from Intel and AMD have typical ROB sizes of 192 or 224 with the latest Zen 3 having 256 and Intel’s Sunny Cove and Willow Cove 352. Tests show Apple's M1 has around a 630 entry ROB.

- 12 cycle L1 miss / L2 access time is still typical, but happens a good bit less often because L1 cache sizes are typically 32 KB. Also now when L2 misses we have 8 MB or more of L3 with typical access times around 40 cycles, which is vastly different to 200 for RAM.

- with clock speeds now around 4 to 5 GHz and RAM stuck at 60 ns, RAM access is even a bit more than assumed in the paper, at 240 to 300 cycles. But with those big L3 caches it happens a lot less frequently.


For me, the glaring thing here is the ROB containing only 16 cycles of instructions, barely enough to cover an L1 miss, and simply dying on an L2 miss.

Current CPUs ROBs buffer 50 to 90 cycles worth of instructions, while servicing most L2 cache misses from L3 in 40 cycles instead of 200+ for RAM.

I think the same study done with real current CPUs would show very different results.

Note that with modern branch predictors that use a branch history table as part of the predictor (a series of true/false bits indicating whether the last N branches were taken or not taken, it is typical for loops that iterate just a few times (anywhere from 10 to 30) to have EVERY branch correctly predicted, including the final branch that exits the loop.

Luckily there are cases where this indeed works, but I still doubt that every branch inside a memcpy function can be predicted correctly, given that the function can be called with a different size argument upon each invocation.

You don't have to get *every* branch correct, only the vast majority.

Branch prediction uses the history of where the memcpy() was called from. In most cases any particular caller calls memcpy() with the same size.

[Nominal Animal]

An example piece of RISC-V (RV32I) assembly code for a block copy of N 'words' looks like (do not hesitate to provide more optimized code if there is):
[Assume: a0 contains N, a1 the source start address and a2 the destination start address]

Something brucehoult mentioned above made me realize we haven't discussed these operations at the pipeline stage level, to discover what the theoretical maximum copy rate is on your target processor.  I assume, it can only do one RAM access per clock cycle (load or store); and only one register file store per clock cycle.
What else? What operations can be done in parallel within the same clock cycle?

(I am talking about lowest-level operations, within the instruction pipeline; not about superscalarity or individual full instructions.)

Based on the above, the utter maximum theoretical copy rate is half a word (of native register size) per clock cycle, or equivalently two clock cycles per native register size word coped.  (For string operations, two cycles per byte copied, unless you have a branch instruction "branch if none of the bytes in the target register are zeroes".)

Because we cannot create an unrolled version for every single length, up to one cycle per iteration is taken by the loop branch.  As brucehoult showed earlier, that overhead depends on the number of unrolled copies per loop iteration – but then the block size needs to be at least as large as the copy step.

That leaves the address register updates.  With offset addressing (a small immediate constant, a multiple of the native register size, added to a register), that too boils down to one or two cycles per loop iteration (depending on whether updating a register value can be done in a single cycle or not).  If the register update can be done in parallel with a load or store or the loop branch, its "cost" vanishes.

It seems to me that both block-memcpy instruction and a normal assembly loops should be able to get arbitrarily close to two cycles per native word copied (using the above assumptions), and that anything better than this, you need e.g. wider single-cycle memory accesses, or something else outside the box here, so to speak.  If you agree, then shouldn't we look at which low-level operations can be done in parallel in the same clock cycle on your processor design, to see how to reach the two cycles per word copy rate?  And what kind of instructions would get there?

[gf]

What operations can be done in parallel within the same clock cycle?
(I am talking about lowest-level operations, within the instruction pipeline; not about superscalarity or individual full instructions.)

Depends on the processor's microarchitecture. "RISC-V" is not a particular processor implementation, but an open Instruction Set Architecture. Optimizations at this level are no longer generic, but microarchitecture-dependent.

[Nominal Animal]

What operations can be done in parallel within the same clock cycle?
(I am talking about lowest-level operations, within the instruction pipeline; not about superscalarity or individual full instructions.)

Depends on the processor's microarchitecture. "RISC-V" is not a particular processor implementation, but an open Instruction Set Architecture. Optimizations at this level are no longer generic, but microarchitecture-dependent.

That's exactly why I wrote, "on [SiliconWizard's] target processor".  If we limit to RISC-V alone, then there is nothing to discuss, is there?

As SiliconWizard has mentioned, they envision these instructions as a custom extension; and I do believe discussing the limitations/abilities of the underlying implementation is necessary to discuss what kind of instructions would be most effective.

[SiliconWizard]

So that we don't run in circles, if possible...
As I said earlier:

* On superscalar architectures, on which the increment/decrement instructions can be executed in parallel with the loads/stores, dedicated instructions would probably not have any sizeable performance benefit. OTOH, on simpler architectures, they can be considered, and my rationale is that dedicated instructions with a relatively simple "accelerator" would be much, much simpler to implement than a superscalar architecture - so they could have a benefit for simpler processors.

* As we discussed with Bruce, loop unrolling and offset addressing can mitigate the inc/dec, but that takes a lot more instructions overall.

* And in any case: dedicated instructions would yield smaller code size.

Not completely sure what Nominal Animal meant here: "I am talking about lowest-level operations, within the instruction pipeline; not about superscalarity or individual full instructions."
Any instruction can do many things at once as long as the logic path doesn't exceed your requirements. For instance, RISC-V CSR instructions involve read, modify and write of CSRs and that can be done (that's what I do) in a single cycle.

Loading or storing AND incrementing or decrementing of the address with a single instruction while having a CPI=1 throughput is no problem whatsoever.
(The problem, though, as we said earlier, is with loads, because if the instruction modifies 2 registers instead of one - the read value and the address register - this is a royal pain. Stores are no problem.)

[Nominal Animal]

Not completely sure what Nominal Animal meant here: "I am talking about lowest-level operations, within the instruction pipeline; not about superscalarity or individual full instructions."
Any instruction can do many things at once as long as the logic path doesn't exceed your requirements.

The question is, what are the allowed combinations of "many things" on your implementation: which micro-operations your target can do at the same time.

Here is a practical suggestion for extending RV32I:

• SBi (rd), rs: Store least significant byte of register rs to memory address specified by register rd, and increment rd by one.
• SBd (rd), rs: Store least significant byte of register rs to memory address specified by register rd, and decrement rd by one.
• SWi (rd), rs: Store register rs to memory address specified by register rd, and increment rd by four.
• SWd (rd), rs: Store register rs to memory address specified by register rd, and decrement rd by four.
• BNEi rd, rs, 1<<n, delta: Compare rd to rs, and increment rd by 1<<n.  If not equal, branch by delta.
• BNEd rd, rs, 1<<n, delta: Compare rd to rs, and decrement rd by 1<<n.  If not equal, branch by delta.

Note that BNEi and BNEd are really 2-5 instructions each, for at least n=0 (change by 1) and n=2 (change by 4).

If these are implementable without extra latencies or overheads compared to their non-autoincrement versions in RV32I, then these are one possible set that provide very close to the maximum throughput for block memory copies, but also allowing efficient implementations for the other memory/string operations.

But my point is, there are other such sets, depending on the implementation of the target processor.  Without knowing which micro-ops the implementation can do in parallel, it is useless to discuss such sets, because efficiency-wise they are equivalent.  We'd just be listing the possible sets.

For bulk RV32I memcpy(), unrolling the inner iterations using an immediate offset as brucehoult described earlier,
    .loop:
        lw    t1, 0(a1)
        sw    0(a2), t1
        lw    t1, 4(a1)
        sw    4(a2), t1
        addi  a1, a1, 8
        addi  a2, a2, 8
        bne  a3, a1, .loop
yields a copy rate of 4N/(2N+3) bytes per instruction with N copies per iteration (0.8, 1.143, 1.333, 1.455, ...), if the size is a multiple of 4N.  However,
    .loop:
        lw    t1, (a1)
        swi   (a2++), t1
        bnei  a1, a3, 1<<2, .loop
would yield a copy rate of 4/3 = 1.333 bytes per instruction for any size a multiple of 4, and
    .loop:
        lw    t1, 0(a1)
        swi   (a2++), t1
        lw    t1, 4(a1)
        swi   (a2++), t1
        bnei  a1, a3, 1<<3, .loop
would yield a copy rate of 4N/(2N+1) bytes per instruction with N copies per iteration (N=1: 1.333, N=2: 1.6, N=4: 1.778, N=8: 1.882, N=16: 1.939) bytes per instruction.  That is, unrolling the inner loop 16 times, copying 64 bytes per iteration, we'd reach 97% of the theoretical maximum copy rate. (You need to unroll the RV32I loop 48 times, copying 144 bytes at a time, to reach the same.)

For an example of the other possibilities, let's say you could implement lw rd, (rs1+rs2), i.e. load from an address that is the sum of two registers, and the store-autoinc/dec.  Then, you could use rs1 as the target address (autoinc/dec'd), and rs2 be a constant, the difference between the target and source addresses.  You'd get the same near-maximum copy rate as the last snippet above, using one more register:
        sub   a1, a1, a2
    .loop:
        lw    t1, (a2+a1)
        swi   (a2++), t1
        lw    t1, (a2+a1)
        swi   (a2++), t1
        bne  a2, a3, .loop

A yet another possible set is sum-of-two-register address loads and stores, and an autoadd/subtract branch-if-not-equal.

For alignment tests, a branch if any of the N least significant bits in a source register are nonzero, would be useful.
For string operations, a branch comparing each byte in first source register to the corresponding or least significant byte in the second source register, and taking the branch only if none are equal, would allow up to 4× speedup for many operations (with the caveat that internally, the function may access up to three bytes past the end-of-string nul byte).  (This is why I am partial to the autoinc/dec stores and conditional branches as an extension: many birds with few similar stones.)

[brucehoult]

Based on the above, the utter maximum theoretical copy rate is half a word (of native register size) per clock cycle, or equivalently two clock cycles per native register size word coped.  (For string operations, two cycles per byte copied, unless you have a branch instruction "branch if none of the bytes in the target register are zeroes".)

It's not that bad. The following will detect a null byte in a 64 bit register without any special instructions.

#define DETECTNULL(X) (((X) - 0x0101010101010101) & ~(X) & 0x8080808080808080)

Example

X = 'Hello\0xx' = 0x48454c4c4f007878
W = X - 0x0101010101010101 = 0x47444b4b4dff7777
V = ~X = 0xb7bab3b3b0ff8787
U = W & V = 0x700030300ff0707
T = U & 0x8080808080808080 = 0x0000000000800000

T is not 0, so some byte in X was 0.

This is only four instructions, or three instructions if your CPU has a BIC / ANDN / ANDC instruction (as RISC-V does in the B extension, and also ARM, MSP430, PDP-11 and VAX).

You can find the exact byte using CLZ (Count Leading Zeroes) if you have it, otherwise just iterate through that one register worth of data.

However I wanted to improve on this in the RISC-V B extension, but without doing something as crude as a special "strlen" function.

We already were considering a "Generalized Reverse" (GREV) instruction which takes a 64 bit value from a register and passes it through a 6-level network controlled by 6 bits from the 2nd operand (5 bits for a 32 bit machine):

- bit 0 controls whether pairs of bits in the 1st operand are swapped
- bit 1 controls whether bits 2 apart in each nybble are swapped
- bit 2 controls whether bits 4 apart in each byte are swapped
- bit 3 controls whether bits 8 apart in each short are swapped
- bit 4 controls whether bits 16 apart in each word are swapped
- bit 5 controls whether bits 32 apart are swapped

Some uses:

- a control value of 000000 does nothing
- a control value of 000111 reverses the bits in each byte
- a control value of 111000 reverses the bytes in a register, keeping each individual byte intact (i.e. reverse a string)
- a control value of 111111 reverses all the bits in the register


I realized that another useful instruction (which were are calling GORC for now) could reuse the same network, but instead of conditionally swapping pairs of bits, use another function. Specifically, GORC takes each pair of bits and either passes them through unchanged or else replaces both or them by their OR. You can get GREV+GORC for maybe 10% more than the cost of GREV alone.

- a control value of 000000 does nothing
- a control value of 000111 ORs together all the bits in each byte

Bingo!

Taking our X = 'Hello\0xx' = 0x48454c4c4f007878 example again, GORC X, 7 produces 0xffffffffff00ffff

If the result is not all 1s (-1) then one of the bytes was zero.

Because we cannot create an unrolled version for every single length, up to one cycle per iteration is taken by the loop branch.  As brucehoult showed earlier, that overhead depends on the number of unrolled copies per loop iteration – but then the block size needs to be at least as large as the copy step.

That leaves the address register updates.  With offset addressing (a small immediate constant, a multiple of the native register size, added to a register), that too boils down to one or two cycles per loop iteration (depending on whether updating a register value can be done in a single cycle or not).  If the register update can be done in parallel with a load or store or the loop branch, its "cost" vanishes.

It seems to me that both block-memcpy instruction and a normal assembly loops should be able to get arbitrarily close to two cycles per native word copied (using the above assumptions), and that anything better than this, you need e.g. wider single-cycle memory accesses, or something else outside the box here, so to speak.  If you agree, then shouldn't we look at which low-level operations can be done in parallel in the same clock cycle on your processor design, to see how to reach the two cycles per word copy rate?  And what kind of instructions would get there?

Seems all correct.

I think a dual issue pipeline will be the minimum within a few years, for all but the tiniest embedded cores, as it is *so* little added area/complexity/expense for a large gain in efficiency See ARM M7 / A7 / A8 / A9, SiFive 7-series, Western Digital SweRV (open sourced).

With a dual issue machine, you only need to unroll the loop once to completely hide the update of two pointers, a compare against a limit, and a conditional branch. (the compare and branch are one instruction on RISC-V)

Code: [Select]

add limit,src,size
loop:
  lw tmp, 0(src); addi src,src,8
  sw tmp 0(dst); addi dst,dst,8
  lw tmp -4(src); cmp src,limit
  sw tmp -4(dst); blt loop


[brucehoult]

For an example of the other possibilities, let's say you could implement lw rd, (rs1+rs2), i.e. load from an address that is the sum of two registers, and the store-autoinc/dec.  Then, you could use rs1 as the target address (autoinc/dec'd), and rs2 be a constant, the difference between the target and source addresses.  You'd get the same near-maximum copy rate as the last snippet above, using one more register:
        sub   a1, a1, a2
    .loop:
        lw    t1, (a2+a1)
        swi   (a2++), t1
        lw    t1, (a2+a1)
        swi   (a2++), t1
        bne  a2, a3, .loop

I have proposed pretty much this before, except my version was more like:

Code: [Select]

  addi a2,a2,-4
  sub a1,a1,a2
loop:
  lw t1,(a2,a1)
  sw! t1,4(a2)
  bne a2,a3,loop

It's cheaper to write back the effective address you already calculated. But it does require one more adjustment instruction before the loop.

This also extends naturally to code that steps through 2 or 3 or more arrays, loading data and doing some element-wise calculation on it, before writing a single result to another array. Which is pretty common. It's just that all the arrays need to have the same element size.

[Nominal Animal]

However I wanted to improve on this in the RISC-V B extension, but without doing something as crude as a special "strlen" function.

It is not just strlen()/strnlen(), but also for strcmp()/strncmp() and strcpy()/strncpy(), these being the three most used string functions.

If the branch does a byte-wise "branch only if none are equal" comparison between the 4 bytes in the two registers, you could also implement strchr()/strnchr(), and speed up strstr()/memmem().

If the branch does a byte-wise "branch only if none are equal" comparison between 4×4 bytes (in the two registers), you could also implement strpbrk()/strspn()/strcspn() with very low cost, since each register could hold up to four initial bytes in a matching sequence.

Other than this nitpick, I agree.  I don't like the idea of enhancing just one operation either; and I'd prefer to try to keep the patterns so simple there is hope of teaching the compilers to use them.

With a dual issue machine, you only need to unroll the loop once to completely hide the update of two pointers, a compare against a limit, and a conditional branch. (the compare and branch are one instruction on RISC-V)

Quite true, and I did not think of that (or rather, that it was pertinent here).

You see, in HPC, many AMD cores have two SSE/AVX ALUs, so that 128-bit vector operations are essentially dual issue.  I've exploited this a lot in my own code, using compiler intrinsics for the vector operations – perhaps not as efficient as hand-tuned and cycle-profiled assembly, but gets most of the speedup.

It's cheaper to write back the effective address you already calculated.

This!  This is exactly the kind of low-level µ-op details I wanted to know.  Your version is obviously superior to mine; how did I miss it earlier?

But it does require one more adjustment instruction before the loop.

It really depends on the function signature.  With known pointers/size, at least GCC will implement the copy loop itself, and avoid the adjustment by folding in the "constants".  It does the same for e.g. static inline assembly functions, where the arithmetic is done when supplying input register values, when the parameter values are known at compile time.  For unknown pointers/size, for standard C functions, there is at minimum an addition to calculate the limiting address, and possibly some validity checks (at least for the user-programmer facing functions), so one more adjustment is just noise there.

[SiliconWizard]

Not completely sure what Nominal Animal meant here: "I am talking about lowest-level operations, within the instruction pipeline; not about superscalarity or individual full instructions."
Any instruction can do many things at once as long as the logic path doesn't exceed your requirements.

The question is, what are the allowed combinations of "many things" on your implementation: which micro-operations your target can do at the same time.

Here is a practical suggestion for extending RV32I:

• SBi (rd), rs: Store least significant byte of register rs to memory address specified by register rd, and increment rd by one.
• SBd (rd), rs: Store least significant byte of register rs to memory address specified by register rd, and decrement rd by one.
• SWi (rd), rs: Store register rs to memory address specified by register rd, and increment rd by four.
• SWd (rd), rs: Store register rs to memory address specified by register rd, and decrement rd by four.
• BNEi rd, rs, 1<<n, delta: Compare rd to rs, and increment rd by 1<<n.  If not equal, branch by delta.
• BNEd rd, rs, 1<<n, delta: Compare rd to rs, and decrement rd by 1<<n.  If not equal, branch by delta.

I see absolutely no issue nor any required added latency for any of the instructions you suggest above.
The only difference with existing instructions is the additional inc/dec of a dest register. This can be done fully in parallel with the rest of what they have to do, so no problem.

[Nominal Animal]

I see absolutely no issue nor any required added latency for any of the instructions you suggest above.
The only difference with existing instructions is the additional inc/dec of a dest register. This can be done fully in parallel with the rest of what they have to do, so no problem.

Excellent; thanks. 

How wide are your µ-op memory accesses, then?  Native word sized, or larger?

(The above can reach very close to the theoretical maximum copy rate with one memory access per cycle, in a single-issue core, using native register sized words; with just the branch instruction as the loop iteration "overhead".  If you want faster, you need wider than native word memory accesses per cycle.)

[brucehoult]

However I wanted to improve on this in the RISC-V B extension, but without doing something as crude as a special "strlen" function.

It is not just strlen()/strnlen(), but also for strcmp()/strncmp() and strcpy()/strncpy(), these being the three most used string functions.

strlen() is implicit in those -- often checked in parallel, but on some machines it is better to explicitly calculate strlen() first and then use a counted loop for the copy or compare.

Better still if the *programmer* calculates the strlen() first, and uses memcpy()/memcmp(), and remembers the strlen() for later use.

If the branch does a byte-wise "branch only if none are equal" comparison between the 4 bytes in the two registers, you could also implement strchr()/strnchr(), and speed up strstr()/memmem().

That only requires an XOR and then the "is any byte zero" test.

A new branch instruction would fit, but reg + reg + 12 bit branch offset uses a *lot* of encoding space. That's ok for beq/bne/blt/bltu/ble/bleu because they are used absolutely everywhere in programs (~20% of all instructions). The same goes for new reg + reg + 12 bit immediate ALU operations. Personally I would probably remove (or never have added) XORI as it is used *so* seldom and when it is used it's usually with 0xffffffff so can be done as a subtract from -1 anyway. ORI is also very marginal whether its worth having, used a lot less than ANDI.

The advantage of src1+src2+dst register to register instructions is they use comparatively little opcode space, so you can have a ton of them (eventually). It takes 128 of them to use as much encoding space as a single conditional branch or immediate ALU instruction.

The immediate shift instructions SLLI, SRLI, SRAI use much less encoding space than the other immediate instructions because they only use a 6 bit immediate (5 for RV32), so you can have 64 of them for the same encoding space as a single normal 12 bit immediate instruction. So GREVI and GORCI and other "shift-like" instructions are easy to add.

If the branch does a byte-wise "branch only if none are equal" comparison between 4×4 bytes (in the two registers), you could also implement strpbrk()/strspn()/strcspn() with very low cost, since each register could hold up to four initial bytes in a matching sequence.

I didn't quite get that.

[brucehoult]

Not completely sure what Nominal Animal meant here: "I am talking about lowest-level operations, within the instruction pipeline; not about superscalarity or individual full instructions."
Any instruction can do many things at once as long as the logic path doesn't exceed your requirements.

The question is, what are the allowed combinations of "many things" on your implementation: which micro-operations your target can do at the same time.

Here is a practical suggestion for extending RV32I:

• SBi (rd), rs: Store least significant byte of register rs to memory address specified by register rd, and increment rd by one.
• SBd (rd), rs: Store least significant byte of register rs to memory address specified by register rd, and decrement rd by one.
• SWi (rd), rs: Store register rs to memory address specified by register rd, and increment rd by four.
• SWd (rd), rs: Store register rs to memory address specified by register rd, and decrement rd by four.
• BNEi rd, rs, 1<<n, delta: Compare rd to rs, and increment rd by 1<<n.  If not equal, branch by delta.
• BNEd rd, rs, 1<<n, delta: Compare rd to rs, and decrement rd by 1<<n.  If not equal, branch by delta.

I see absolutely no issue nor any required added latency for any of the instructions you suggest above.
The only difference with existing instructions is the additional inc/dec of a dest register. This can be done fully in parallel with the rest of what they have to do, so no problem.

Correct for pipeline design, except that post-increment and post-decrement need an adder which is not already present, and not used by anything else. Both the stores and the branches would fit better if they did the add/increment/decrement *before* the store or compare.

There is also the quibble that for consistency with everything else in the RV32I ISA rd should be changed to rs1 and rs to rs2.

Which brings me to opcode space usage :-)

If they can't have offsets then SBi, SBd, SWi, SWd are very very cheap on opcode space. There would be no reason to leave SH and SD versions out.

On the other hand BNEi and BNEd are very very expensive in opcode space, at least if delta has the same range as the other conditional branch instructions. If n can be 0..3 then BNEi and BNEd use 33% more opcode space than all the existing BNE, BEQ, BLT, BLTU, BGE, BGEU combined. At the very least delta should be shortened by three bits (to +/- 512 bytes instead of +/- 4k) to make room for 2 bits for n and 1 bit for i/d.

In the base ISA func3 (3 bits) is used to choose between BNE, BEQ, BLT, BLTU, BGE, BGEU with values 010 and 011 unused. Nothing else in the currently ratified extensions (MAFD) uses those. I don't know offhand whether one of the extensions in progress does.

My opinion is it might be worth using one of those for BNEi and BNEd, but maybe shortening delta by even one or two bits more, to allow room for other specialized "short conditional" branch instructions in future, and keep one func3 value completely free.

[Nominal Animal]

Better still if the *programmer* calculates the strlen() first, and uses memcpy()/memcmp(), and remembers the strlen() for later use.

It is still duplicated work; I'd like to avoid that.

Also, a lot of existing C code relies heavily on nul-terminated string operations (instead of known-length string operations); python3 (the standard CPython interpreter) in particular.   Based on ltrace -o log -e strlen python3 empty.py, python-3.6.9 on my machine does 15,509 strlen() calls on interpreter startup; about half of them of 9 characters and longer; over 3000 of them are on strings longer than 16 characters.

If the branch does a byte-wise "branch only if none are equal" comparison between 4×4 bytes (in the two registers), you could also implement strpbrk()/strspn()/strcspn() with very low cost, since each register could hold up to four initial bytes in a matching sequence.

I didn't quite get that.

Probably nobody did, it was such a poor description!

Consider registers a and b as four-byte arrays.  The instruction I was trying to describe is
    if (a[0] == b[0] || a[0] == b[1] || a[0] == b[2] || a[0] == b[3] ||
        a[1] == b[0] || a[1] == b[1] || a[1] == b[2] || a[1] == b[3] ||
        a[2] == b[0] || a[2] == b[1] || a[2] == b[2] || a[2] == b[3] ||
        a[3] == b[0] || a[3] == b[1] || a[3] == b[2] || a[3] == b[3]) take_branch;

Typical strspn(), strcspn(), strtok(), and strpbrk() delimiter sets are relatively small, typically 6 (ASCII whitespace characters).  If you have the above branch test instruction, a 32-bit register can describe up to four different delimiters, or four initial characters for a parallel multi-string strstr()/memmem() function, with a match jumping to a character-by-character test.

Let's say t1 contains the next four bytes in the string, and t2 and t3 contain 5 to 8 delimiters.  (If there are fewer, then some are just duplicated.)  If we call the above branch instruction blah, the inner loop would be something like
    .loop:   ; src=a1, end=a2, delimiters in t2 and t3
        lw    t1, (a1)
        blah  t1, t2, .check
        blah  t1, t3, .check   
        bnei  a1, a2, 1<<2, .loop
        return, no matches
    .check:
        byte-by-byte check at a1

The idea is that matches are relatively rare, and we can afford examining them one by one when we know a match exists; we just want to speed up the "no match" case.

However, string operations seem much less common as memcpy(), memmove(), and memcmp().   On my machine, python-3.6.9 does 43,435 of memcpy()/memmove()/memcmp() on startup.  Thus, I consider the string stuff secondary: wishlist kind of thing.  And this 4×4-byte register comparison operator, just an example of what could work from a programmer perspective.