Re: Byte Addressability And Beyond

Terje Mathisen <terje.mathisen@tmsw.no> writes:

Anton Ertl wrote:

Anyway, such instructions can be done in a RISCy way (pure
register-to-register instructions) or in a CISCy way
(memory-to-memory).
=20
A RISCy way to do UTF-8 -> UTF-32 would be to have the first 4 bytes
of the remaining string in a register and producing an UTF-32 code
point in another register and a length in a third register (or in the
high part of the destination register to reduce write port
requirements).  Similarly for UTF-32->UTF-8, with the length
specifying the length of the result; that would need to be combined
with a length masked store to make it easy to store the result.
=20
This approach can also be SIMDified, converting regbits/32 code points
in one representation to the same number of code points in the other
representation plus a length of the UTF-8 representation.
=20
The disadvantage of this approach exists particularly for
UTF-8->UTF-32: this is a very sequential approach full of dependences:
each use of the conversion instruction is followed by a dependent load
of the next input fragment, and the next use of the conversion
instruction depends on that load.

>
Rather the opposite:
>
UTF8->UTF32 looks a _lot_ like an easier example of a byte-oriented=20
variable length (x86?) instruction decoder, but with the big=20
simplification that the first byte directly tells you how long the=20
sequence is.

The SIMD version of the RISCy instruction is no problem.  So you can
process regbits/32 code points in one go.  But what I wrote above
still applies: You use this instruction in a loop like

# s* are SIMD registers, g* are GPRs
l: s0= load(g0)
   s1,g1= cu14(s0)
   store (g2)<-s1
   g0 = g0+g1
   g2 = g2+SIMD_width
   if g0>=input_end goto end
   if g2<output_limit goto l
end:

(probably some fine tuning of the last iteration and the termination
is necessary).

And here you have a dependence chain from load to cu14 to the g0+g1 to
the load of the next iteration.  With cu14 and the addition as
single-cycle operations and the load taking 5 cycles as for D-cache
hits on recent Intel CPUs, that's 7 cycles per iteration, limiting the
throughput of your conversion routine to 1/7th of what your cu14 and
your load/store unit would be capable of in throughput-limited code.

With a byte-stream buffer as architectural feature, and a CU14 that
takes its utf-8 input from that and automatically advances the stream,
this could be quite a bit more efficient.  Something like:

... set up stream buffer ...
l: s1 = cu14(stream-buffer)
   store (g2)<-s1
   g2 = g2+SIMD_width
   if streambuffer empty goto end
   if g2<output_limit goto l
end:

(again with some fine-tuning for the last iteration and termination).

For a technically unnecessary marketing gimick like CU14 one probably
won't add a stream buffer, but, e.g., compression and decompression
are probably more relevant and may also benefit from such a feature.

Doing a SIMD version corresponds to a superscalar x86 in that the=20
decoder needs to grab a variable number of bytes for each instruction,=20
starting the next immediately after.

The instructions are fetched into a stream buffer rather than waiting
for the decoder to produce a length result before starting the next
instruction fetch (and of course the instruction fetcher also has to
deal with branches).

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
  Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>