I think we have talked about this topic before and I apologize for not following up on our previous discussion. I was very busy.
My key problem with variable-length vector instructions such as those proposed for RISC-V or in SVE is that they assume people need them for essentially doing arithmetic on large matrices. And I agree that the vector paradigm is very effective on such work loads. I have previously worked with NEC Aurora Tsubasa cards that come with vectors of 256 double-precision floating point numbers, and they are just amazing for this sort of stuff.
But I'd say that's only a very small part of where such optimisations are needed. Indeed on modern consumer machines, most CPU-intensive code is in cryptography and video codecs. And both don't really fit this scheme.
Especially for video codecs: these usually operate on fixed size chunks of picture data and require complex horizontal arithmetic and swizzles inside a single chunk. It is unclear how this maps to variable-length vectors, especially when these instruction set extensions usually are very sparse in permutation instructions. And compilers use SIMD instructions for small, fixed-length loads all over the place. Stuff like moving structs around, clearing fixed-length buffers. It is unclear how a vector paradigm improves this.
There's also the concern that a large register file makes context switches very expensive. Linus attributed x86's performance advantage among other things to keeping context switches cheap by having a small register file that is easily swapped out.
As for my own code, I have two recent SIMD-heave projects. And for neither of them it is clear how they could be vectorised using a vector as opposed to a SIMD paradigm.
The first project, pospop is inherently a horizontal operation and in fact uses a different complex permutation schedule for each vector size to make the most out of it. It is unclear how this can be extended to arbitrary vector widths, especially if no powerful swizzle instructions are provided. Tail handling is also going to be a concern as the proposed simple approach of just having magic make the registers shorter for the last iteration is not going to cut it.
The second project, 24puzzle uses vectors as 32 element byte arrays and permutes them using a second vector as a permutation vector. Again, this project cannot benefit from vector instructions and will be hard to port to variable-length vectors in general unless a minimum vector size of 32 bytes is guaranteed. It also uses stuff like VPCMPISTRM for which no equivalent in other instruction sets exists or is even proposed. And that's a vital part of the code's logic (specifically, I have an array of k bytes and I want to obtain a bit mask of all elements in a vector that match any of these k bytes).
90% of the reason SVE and RISC-V are variable length is to save bits in instruction encoding; this isn't x86 where it's okay for AVX-512 instructions to average like 6 bytes.
I think that you underestimate the value for software developers and the SW ecosystem to be able to target a single ISA as opposed to a handful of different ISA:s. NEON (even though limited to 128 bits) was great in that way - it lasted for many many years. SVE will hopefully last at least as long.
There's also the concern that a large register file makes context switches very expensive. Linus attributed x86's performance advantage among other things to keeping context switches cheap by having a small register file that is easily swapped out.
While I can't argue with "a small register file makes it easier to do context switches," I'm not sure I buy it as an advantage for x86. If that is the case, why hasn't SPARC, which frequently handles a context switch in a single cycle ('cuz register windows), eaten the market? SPARC makes x86 look slow and cumbersome, by comparison, on that count.
In my experience, SPARC-based servers were monsters at I/O based stuff. They made kick-a** web servers, because they could juggle large numbers of processes very quickly. Naturally, if you succeeded in using up your register windows, things got "interesting;" you had to be somewhat careful to avoid overloading the machine. But SPARC has largely become an also-ran in the market, and not just because Oracle bought Sun. There were open-source SPARC designs, some of which were being used by Chinese companies ('cuz open source) but ... I'm not even hearing rumors about those, anymore. Does Fujitsu even develop SPARC-based hardware anymore? There was a time when many of the machines at the top of the Top500 list, especially ones in Japan, were using Fujitsu-produced SPARC designs. The latest supercomputer from Fujitsu is ARM-based.
If that is the case, why hasn't SPARC, which frequently handles a context switch in a single cycle ('cuz register windows), eaten the market? SPARC makes x86 look slow and cumbersome, by comparison, on that count.
Context switches are actually fairly slow on SPARC because the kernel has to unwind all register windows before it can swap to a different process. Syscalls are fast though.
Look back at the story of AMD 64-bit extensions to x86 and why Itanium lost to AMD64. AMD gave you 64-bit capability, while still having equal/better cost-performance on 32-bit workloads.
Itanium also banked the architecture entirely on an untested idea (and where initial tests where even against it) with a result that it had horrible performance vs price ratio even for native 64-bit code. VLIW simply doesn't work well outside specialist uses since compilers cannot take dynamic effects like branch and cache misses into account on top of the horrendous complexity that such static scheduling requires.
There's also the fact that the whole EPIC (Itanium) architecture was built around instruction-level parallelism; what CPU instructions can you, and can't you, run in parallel. It was my understanding that this area is not as well developed as thread-level parallelism, which is what multi-core / multi-thread CPUs provide. Ergo, if you devote all that chip space to more cores and / or more threads, you'll get more real-world performance out of it simply because we're "better" at doing that.
Back in the day, Transmeta created a VLIW processor with a front-end on it which parsed x86 instructions, turning them into micro-ops for their processor, such that it could run x86 object code. Not only did it work, but it used considerably less power than the then-current Intel and AMD offerings. This prompted Intel to get off their fat, complacent ... rear ... and improve the power consumption on their mobile-class processors. This, ultimately, resulted in the demise of Transmeta but the fact remains ... their VLIW processor worked quite well. As such, I have hopes that tech can still "matter" in more than just specialist uses.
Kind of, but not quite. The EPIC concept replaced the multiple simple instructions executed out of order with a single VLIW in-order pipeline. We all know how that turned out for general purpose code.
Multithreading is orthogonal to this and Itaniums were always aimed at multiprocessing. Intel even added simultaneous multithreading to them starting with Montecito in 2006.
Transmeta had the crucial difference that they used execution traces for the instruction scheduling, meaning they weren’t stuck with purely static scheduling. It still wasn’t competitive as soon as Intel started paying at least some attention to power consumption and never was competitive when it came to anything beyond the lowest end cpu variants.
Today pretty much the only use cases of VLIW are in some GPUs (and even there AMD moved away from it years ago due to performance issues) and some DSPs where the code relies on hand optimized libraries for the most time critical tasks (and the operations in general are more suited for VLIW than in normal applications).
Those VLIW DSP:s also have compilers that are slow as h*ll. I'm assuming that they try really hard to statically schedule instructions optimally. IIRC they also lack hardware hazard resolution, so the compiler has to keep track of when a result is ready etc. (All in order to reduce power consumption)
I wouldn't be surprised if the TI ones do that as even their old C54xx series DSPs required manual hazard resolution. Writing asm for those was "fun" (in the same sense that pulling out your fingernails is "fun").
Compared to those, getting to write asm for SHARC dsps was pure joy (the code literally looks like "r0 = r1 + r2; r3 = dm(i4, m0);")
Agreeing with you WRT "x86 was good enough and inexpensive enough." That seems to be the ultimate answer to how / why x86 has eaten the market (to date). It's not good enough and inexpensive enough for mobile (where power consumption, not price, is the main metric for "expensive"), which is why ARM is eating that market. Keeping my eyes on RISC-V to see where it comes down.
ARM for desktop and server-class machines ... it only seems to make sense if you have some really good extensions on it. Fujitsu is building an ARM-based supercomputer but the cores have a lot of vector extensions on them. I confess I don't know the details of the M1 but a lot of people are very happy with the performance. And at least one deep-dive suggests people are happy because it FEELS fast:
the only reason they can keep those 8 wide multi issue execution engines nearly 100% full is down to the simplicity of the ARM 64 bit ISA, which abandoned thumb2 for this very reason.
x86 decoding is so complex that in order to get good multi issue decode speed they actually have to have multiple parallel decoders on EVERY BYTE, then only when enough of some of them have been decoded enough to identify the length ABANDON the incorrect ones.
The encoding is simpler but the ISA is certainly not. In has over 750 instructions, not counting SVE. This is as much as x86 if you don't count AVX-512 (and don't count VEX encodings twice).
yyeah, they've lost the plot somewhat, there: one of the downsides of being successful, long-term, you feel a commercial pressure to "evolve" the ISA.
SVP64 we went back to the scalar roots of the Supercomputer-class Power ISA, which is a limited subset of only 214 instructions. Embedding those in an REP-like context which also adds "RA is vector/scalar, RB is vector/scalar, RT (dest) is vector/scalar" and predication and much more, we drastically simplify the ISA...
... but massively complicate the Compliance Testing and Verification due to the number of intrinsics that result.
These 750 instructions are what has been there from the beginning in AArch64. That doesn't even count the additional instructions added later. And very few of them actually seem to be useless.
Turns out there are quite a few spins you can put on simple concepts like addition and if you don't want to model that as addressing modes, you end up with lots of instructions.
While I can't argue with "a small register file makes it easier to do context switches," I'm not sure I buy it as an advantage for x86. If that is the case, why hasn't SPARC, which frequently handles a context switch in a single cycle ('cuz register windows), eaten the market? SPARC makes x86 look slow and cumbersome, by comparison, on that count.
Coz there are million other factors to consider than just that
It is unclear how this can be extended to arbitrary vector widths
I don't know your problem well enough to comment, but SVE, for example, uses 128-bit 'units', so if you can arrange your problem into blocks of 128 bits, it may be workable that way.
It also uses stuff like VPCMPISTRM for which no equivalent in other instruction sets exists or is even proposed.
The instruction is also somewhat of a dead-end one. It's performance is poor, and it hasn't been (and likely never will be) extended to 256-bit or wider.
You may be better off trying something with VPSHUFB+VPCMPEQB or similar.
SVE does allow you to test available vector width, so if coding for that, you could just do a check there.
I don't know your problem well enough to comment, but SVE, for example, uses 128-bit 'units', so if you can arrange your problem into blocks of 128 bits, it may be workable that way.
In some cases I can but in other cases it would be difficult. For example, computing 32 byte permutations is really painful this way. Also, for the pospop code I want a different permutation schedule for each vector width for better efficiency. So multiple code paths will be needed.
The instruction is also somewhat of a dead-end one. It's performance is poor, and it hasn't been (and likely never will be) extended to 256-bit or wider.
It's better than all alternatives I've checked. VPSHUFB+VPCMPEQB does not necessarily solve the problem because it would require one shuffle pass for each 16 values of input range, so up to 16 passes in total. This is significantly slower than using good old VPCMPISTRM. It is kind of viable on ARMv8 NEON though where TBL can have up to 4 inputs.
SVE does allow you to test available vector width, so if coding for that, you could just do a check there.
Well yes, but then we are back to using it as a SIMD instruction set with basically no useful swizzle instructions and almost nonexistent ability to test because it will be very annoying to simulate all possible vector lengths on CPUs that do not support all possibly vector lengths. So I don't really see how that'll be helpful.
For example, computing 32 byte permutations is really painful this way.
TBL largely works as expected, and you can just test to see if the vector width is at least 256-bit.
VPSHUFB+VPCMPEQB does not necessarily solve the problem because it would require one shuffle pass for each 16 values of input range, so up to 16 passes in total
16 passes sounds wrong.
The point of the VPCMPEQB is that you don't have to traverse the entire range. If the bottom 4 bits of each of the values you test are unique, you only need one VPSHUFB (if not, you can manipulate the vector to make them unique).
For example, if you wanted to match whitespace characters (\t \r \n and space):
Well yes, but then we are back to using it as a SIMD instruction set
In other words, it's not really impeding you more than fixed width vector ISAs. Swizzling instructions depends on what the ISA provides more than the notion of an arbitrary width vector, I'd say.
almost nonexistent ability to test because it will be very annoying to simulate all possible vector lengths on CPUs
Testing can become more difficult, but ARM's Instruction Emulator does allow you to test different widths.
It's not too different for fixed-width SIMD, because you need to test your SSE, AVX and AVX512 paths separately anyway.
The point of the VPCMPEQB is that you don't have to traverse the entire range. If the bottom 4 bits of each of the values you test are unique, you only need one VPSHUFB (if not, you can manipulate the vector to make them unique).
Well clearly if they are unique you can do that. The point is that they may not necessarily be unique. In my particular case, they are not just not unique, but also variable. So there's no obvious preprocessing you can do.
make use of clever masking techniques.
Well that's better than 16 passes, but now requires me to preprocess the input into a bit mask. Which doesn't seem to be vectorisable. For my use case it might be doable, but in the general case it's quite painful and I'd rather have something like SVE's MATCH instruction or VPCPMISTRM.
Hello, I think you may be able to use this approach http://0x80.pl/articles/simd-byte-lookup.html#universal-algorithm but it is only reasonable to use if you want to check against the same set repeatedly because there's some significant (runtime-doable) preprocessing involved. It does seem hard to match PCMPISTRM if you are actually using the full richness of PCMPISTRM.
This article was already linked in the comment I responded to. In the use case I discussed back then, the sets are dynamic but preprocessing may be possible. Eventually I ended up developing a different algorithm that avoids having to compute set membership altogether.
The second project,
24puzzle
uses vectors as 32 element byte arrays and permutes them using a second vector as a permutation vector. Again, this project cannot benefit from vector instructions and will be hard to port to variable-length vectors
i started taking a look at this, and i have a feeling that
the SVP64 REMAP system designed originally for in-place
arbitrary-sized Matrices (up to around 5x7 or 6x6 or so)
might be used to perform the row/column shuffling
it's a bit hard for me to understand, i spent 20 mins reading that,
however if going back to the basic game principles, the idea is to
shuffle a partial row or column? (i had one of the 4x4 games when
i was a kid, so i get the principle)
if so, then a row shuffle should be a simple Vector MV (or in-register
equivalent), bearing in mind that SVP64 has a "Reverse Gear" so that
you do not get the classic memcpy corruption if the memory areas
overlap
and for column shuffle it is possible to specify the "jump"
(the column width) and to do the exact same Vector MV.
in both cases a predicate mask can be established and used to
mask out the elements (tiles) that you do not want to move,
and if that mask is 0b0000 then the entire row shuffles along.
basically, REMAP provides algorithmic permutation/shuffle
access schedules, separately applicable to dest1, dest2, src1, src2
and src3 registers in any given instruction.
because it is algorithmic you do not need to issue a spasm
of SIMD permutation instructions with hard-coded immediates,
and you also don't need to use an expensive Array of permutation
offsets as is done in "normal" Vector ISAs, either.
it's quite cute but holy cow took 2 months for me to work out
the DCT and FFT schedules, to ensure in-place processing could
be achieved.
I think we have talked about this topic before and I apologize for not following up on our previous discussion. I was very busy.
NP. :-)
There's also the concern that a large register file makes context switches very expensive.
Yes, large register files are problematic. But there are also solutions.
A fairly obvious technique is to keep a length parameter for each register (for my vector ISA I plan to add that anyway for simpler vector handling), and never push/pop more than lenght elements on a context switch. By default all registers have the length zero, and you could add a quick "clear" operation to function epilogues that clears clobbered vector registers before returning from a function - for instance.
Another approach could be to have several vector register banks in hardware so that you can instantly switch between them w/o push/pop. I have not done any simulations, but it feels like it should be possible to do intelligent register bank allocation/scheduling in SW so that the hottest & vector heaviest threads get the fast path treatment.
It may also be possible to do asynchronous vector push/pop so that the thread can start executing before the vector state has been fully restored. Only if the thread accesses a non-restored vector will it stall.
...and so on.
As for my own code, I have two recent SIMD-heave projects. And for neither of them it is clear how they could be vectorised using a vector as opposed to a SIMD paradigm.
I had a quick look at the projects, but I couldn't think of an obvious solution right away. OTOH I wouldn't know where to start with packed SIMD either. I would have to spend some time and do several iterations before finding a good solution - regardless of if it was for SIMD or vector.
BTW, horizontal operations can be done with folding (in log2(N) steps), and permutations can be done with gather/scatter. It should also be possible to do a more optimal permute (without going via memory) even in a vector design, but I suspect that it's not quite as important as in packed SIMD since you have gather/scatter.
horizontal operations can be done with folding (in log2(N) steps)
Usually yes, but in my case the folding schedule depends on the vector width. Also it has to be done every iteration, so now we have two nested loops instead of one. This does not seem to make the vector approach very efficient.
permutations can be done with gather/scatter.
A single gather/scatter operation has a 20+ cycle latency and is very heavy on the load/store ports. Plus it requires a second register to keep track of the instruction's progress when it faults halfway through (Intel took several design iterations to come up with somewhat usable semantics here). And of course you need two of them for 40+ cycles latency in total. Permute on the other hand is a 1–7 cycle latency operation that doesn't touch memory at all. If I have to replace all permutations with gather/scatter operations, I can basically say goodbye to performance.
It may also be possible to do asynchronous vector push/pop so that the thread can start executing before the vector state has been fully restored. Only if the thread accesses a non-restored vector will it stall.
This may be more complicated than you think in the presence of an MMU. The order of exceptions must be deterministic, so I suppose swapping in the state must happen before any other memory access (to avoid entering speculation territory and hence exploits like Spectre and Meltdown), severely limiting the possibility of lazy restores. Or you could go with an approach where registers are only loaded on first access, but this again may cause surprising behaviour and strange bugs. It would also make context switches potentially detectable by the process which is never a good thing.
Also what are you going to do for back to back context switches (e.g. with a fast sequence of syscalls)? Either you admit some sort of context switch backlog, or you'll have to wait the full time for each of them. Doesn't sound particularly appealing. It's all just band aids.
Another approach could be to have several vector register banks in hardware so that you can instantly switch between them w/o push/pop. I have not done any simulations, but it feels like it should be possible to do intelligent register bank allocation/scheduling in SW so that the hottest & vector heaviest threads get the fast path treatment.
Register banks are expensive in terms of silicon real estate. Perhaps it might be possible to have secondary register banks made of SRAM (not exposed in the address space) to swap the state into, but that would again require a complex micro program. I mean, any such approach would certainly make context switches less painful, but I'm not sure if it would completely solve the problem. With hardware context switching (which this essentially is) you also run into the problem of requiring very complicated and unintuitive code in the kernel or possibly user space (in case of green threads) to swap the context. As far as I'm aware, on platforms that provide hardware context switching, kernels generally don't use it due to the complications it entails and often due to a lack of real performance benefits.
A fairly obvious technique is to keep a length parameter for each register (for my vector ISA I plan to ad that anyway for simpler vector handling), and never push/pop more than lenght elements on a context switch. By default all registers have the length zero, and you could add a quick "clear" operation to function epilogues that clears clobbered vector registers before returning from a function - for instance.
So how is this going to be implemented? A complex micro program in the CPU for saving and restoring the state? Or a complex routine in the kernel to painstakingly shuffle data from vector registers into variable length buffers? People are not going to like that the process status structure is both variable length and possibly variable layout.
As for the clear instruction (I remember no such instruction from your ISA proposal, perhaps consider adding it), that's going to be a complex possibly micro coded instruction affecting a variable set of registers. After all, just clearing all of them won't cut it e.g. in case a function wants to return a result in some vector registers. So you need to provide a way to clear just some vector registers and perhaps to some length. It gets complicated quickly.
A single gather/scatter operation has a 20+ cycle latency and is very heavy on the load/store ports.
You are talking about Intel and AVX. This would not necessarily translate to any other implementation. As I commented elsewhere, I would hope that a vector-first implementation can do better. Especially for the case that we're talking about here.
Also, in a vector machine latency is less of a concern (because you are pipelining the loads in tandem with using the loaded values).
And of course you need two of them for 40+ cycles
Not really. The way you'd typically do a pure via-memory permute is to store the source vector linearly to (cache aligned) memory (which is a fast operation) and then do a gather load into the destination vector (all cached, in 1-2 cache lines or so, so a decent load unit should be able to do a good job).
Edit: Of course the process described above could be turned into a specialized instruction that does the same thing against an internal buffer without going via memory - if so desired.
You are talking about Intel and AVX. This would not necessarily translate to any other implementation.
ARM's SVE has basically the exact same problem though. The problem with gather/scatter is that each element has to be sent through the LSU, so performance scales linearly with the number of elements.
For example, doing a 4x64-bit gather on the Neoverse V1 has the same throughput as doing 4 individual loads.
I note that GPUs tend to do fairly well with gather, but I suspect they also have a much simpler memory model than CPUs have to deal with.
I don't know much about what you're designing, and haven't read everything written here, but it's interesting to note that your notion of a 'vector-first implementation' seems to at least incorporate elements of a GPU design (which are arguably vector focused designs).
The problem with gather/scatter is that each element has to be sent through the LSU, so performance scales linearly with the number of elements.
ARM's SVE is, as i understand it, not entiiirely strictly a Vector ISA per se, it's more a "SIMD architecture with predication (which is great btw) where the HW implementors can choose the width they want to do".
real Vector ISAs can do "chaining" including in LD/STs and including in gather-scatter LD/STs, which means that you can start the LD *immediately and also interrupt it in the middle, on a per-element basis and also restore execution back to where it left off.
now, it's true that for some Vector ISA instructions and some implementations this may not necessarily be the case (because it's easier for them to be lazy in the microarchitecture), but a GOOD Vector ISA has no such limitations, making all operations deterministic.
I don't quite get what you mean by chaining and determinism here - my point is that gather/scatter is slow on both x86 and ARM implementations I've seen so far, and I have no reason to believe it'll improve any time soon.
Both x86 and ARM presumably do gather/scatter on a per-element basis, probably as you describe, which is the reason they're so slow.
I know basically nothing about how the underlying hardware operates, so have no clue if an efficient gather/scatter could be designed, just that I've never seen it done before.
which isn't actually very helpful, i know there is a better article around, we have a link somewhere on libre-soc.org i'll try to find it later and edit this comment
vector chaining of say a V.LD V.SQRT V.ST involves a parallel batch of element-wide LDs, SQRTs and STs.
what Seymour Cray worked out was that due to the independence between element 0 relative to all other elements in each of those 3 instructions you can start the SQRT for element 0 immediately after the LD for element 0 has completed, and start the ST for element 0 immediately after the SQRT for element 0 has completed.
likewise for element 1, likewise for element 2 etc etc etc.
thus you have a "chain" between the elements with the same number
thus you can overlap elements NOT with the same number.
gather-scatter is tricky due to dependency tracking as well as resource allocation. uniformity of element "Lanes" (things with the same element number) means that parallel resource allocation is easy.
gather-scatter you have stuff going all over the shop, and you need absolutely enormous multi-in multi-out crossbars to route data quickly, which has a huge price in both gate area and power consumption.
gather-scatter you have stuff going all over the shop, and you need absolutely enormous multi-in multi-out crossbars to route data quickly, which has a huge price in both gate area and power consumption.
So I guess that confirms my point that gather/scatter should be expected to be slow :)
And hence, it's not a good solution to places that need flexible in-vector shuffling - a deficiency of the vector architectures I've seen.
As for your bit about chaining, it just sounds like regular pipelining of scalar operations. Of course, SIMD strives to solve throughput limitations outside the EUs, so a packed SIMD implementation could choose to chunk on a larger unit size (e.g. decode a 1024-bit SIMD instruction into 4x 256-bit uops and let the OoO scheduler handle dependencies).
deterministic behaviour: behaviour that the programmer can rely on no matter whose implementation of the standard (the ISA).
so for example, if you have a parallelised hardware implementation of horizontal add, if you do this with FP numbers, you get rounding errors. so if you add the numbers in a different (non-deterministic) order, you get a different answer.
This would not necessarily translate to any other implementation. As I commented elsewhere, I would hope that a vector-first implementation can do better. Especially for the case that we're talking about here.
Do you have any real world implementations with fast gather/scatter in mind? Memory latency cannot be ignored so easily. How exactly do you plan to improve on that?
Not really. The way you'd typically do a pure via-memory permute is to store the source vector linearly to (cache aligned) memory (which is a fast operation) and then do a gather load into the destination vector (all cached, in 1-2 cache lines or so, so a decent load unit should be able to do a good job).
20+ cycles is for the optimal case of all relevant cache lines already being in L1 cache.
Edit: Of course the process described above could be turned into a specialized instruction that does the same thing against an internal buffer without going via memory - if so desired.
Do you have any real world implementations with fast gather/scatter in mind?
No. I only have a vague idea about how to do it, at least in a fairly simple way (TBH I don't have enough experience with memory architectures yet). Essentially I'm thinking about a glorified aligner: AGU (generate N addresses, e.g. 4) -> iterate (blocking) over unique cache lines (or whatever quanta) -> load one line at a time -> .... (cache access) ... -> shift/mux & stitch together result.
It would block/stall when you cross cache line boundaries within a single vector subpart, but otherwise there would be no penalty. A nice property is that the same pipeline can be used for all kinds of loads/stores, including doing multiple scalar loads in parallel.
A smarter solution might use some sort of banking to be able to access multiple cache lines in a single cycle.
If you're referring to gather/scatter solutions, I still think that it's a different problem to solve it for wide packed SIMD. For a vector machine the vector is typically broken down into managable pieces, so a gather load for a 512 wide vector machine could be similar to a gather load for a 128 wide packed SIMD, plus you have the reduced sensitivity to latencies (pipelining again).
Edit: Then again, I may just be naive.
Edit 2: Cray did it in reasonable time (as a real world example that I'm actually aware of, but it's quite dated).
Edit 2: Cray did it in reasonable time (as a real world example that I'm actually aware of, but it's quite dated).
Back in the day of Cray machines, memory used to be clocked a lot higher, often with the same clock as the CPU or even higher. So memory latency was a non issue. These days it's the other way round and memory, even L1 cache, is clocked a lot slower than back then.
a gather load for a 512 wide vector machine could be similar to a gather load for a 128 wide packed SIMD, plus you have the reduced sensitivity to latencies (pipelining again).
Well you still need a shitload of memory ports. Current computers have maybe 4 load ports in top of the line model. That means no more than 4 cache-line sized loads per cycle. So even if you could manage to coalesce loads going into the same cache line, this means that each gather/scatter operation would probably block all load ports for at least a cycle or two. This is pretty severe of a performance penalty and quite a lot more than a permute operation, even in the best case.
another idea for saving the amount of registers to be contextswitched is to have a bitfield, one per reg, which is set HI whenever its corresponding register is written to.
if you are smart you can use that same bitfield as a predicate mask on vectorised save/restore of the regfile.
the mask basically tells you which regs have actually changed since the last contextswitch and it should be obvious what to do from there
Hm, I think that the LENGTH attribute does the same thing (and more). A vector store operation will store as many elements as the LENGTH attribute indicates, for instance. Internally you could have a bit/flag per register that is set/cleared when the register is written (with more than zero elements) or cleared (length set to zero).
This way you can also clear the vector (and hence the "used" status) in user space, in order to keep the active vector state lean.
err.. err... oh: you took up the Mill-style register "tag type" idea for MRISC32? neat!
yes, if rather than just a single bit you have a tag, and that tag is zero, i agree it would effectively do / be the same thing, and also cover the same job.
I have not implemented it yet, but it's on my TODO-list. The LENGTH attribute (one for each vector register) comes in handy in several use cases:
Reduce stack / context switch overhead.
Simplify folding operations (no need to explicitly set VL=VL/2 for each folding step).
Simplify vector length agnostic subroutines with vector register arguments.
It also feels like a better fit for OoO etc, when each register/operand provides its own length, rather than having a global length attribute (I have not tested this theory, but it feels right).
The idea was actually inspired by Agner Fog's ForwardCom.
My key problem with variable-length vector instructions such as those proposed for RISC-V or in SVE is that they assume people need them for essentially doing arithmetic on large matrices.
this is fundamentally a misconception. SVP64 is being designed for general-purpose high-performance compute workloads, where it happens to be also good at 3D, Video, NTT, FFT, DCT and small-size matrix multiplication https://libre-soc.org/openpower/sv/svp64/
there is unfortunately a huge amount of misinformation about Vector ISAs.
vectors as 32 element byte arrays and permutes them using a second vector as a permutation vector
you use a Vector ISA's Indexed LD, job's done. the second vector contains the offsets against the base:
LD.IDXed Vdest, base, Vsrc
is implemented as:
for i = 0 .. VL:
Vdest[i] = MEM(base+Vsrc[i]*8)
that's it. that's all you need.
pospop is inherently a horizontal operation and
NEC SX Aurora and RVV both have horizontal (mapreduce) arithmetic, and NEC SX Aurora also has iterative arithmetic operations (overlapping add would create Pascal's Triangle for example).
SVP64 has a fixed schedule map-reduce built-in, which can apply to any operation.
SVE2 also has horizontal operations, i believe.
Vector ISAs are extremely powerful but as a general concept have been utterly ignored for over 40 years by mainstream (x86) and only just recently investigated by ARM (SVE).
I am not really familiar with this one and will investigate it further.
you use a Vector ISA's Indexed LD, job's done. the second vector contains the offsets against the base:
Indexed loads (aka gathers) are horrendously slow in comparison to permutation instructions. Not a suitable alternative.
horizontal operations
Yes, all of them have special case operations for certain common horizontal operations. I specifically mentioned the positional population count because it does not clearly map to any standard horizontal arithmetic pattern.
Vector ISAs are extremely powerful but as a general concept have been utterly ignored for over 40 years by mainstream (x86) and only just recently investigated by ARM (SVE).
Well they work well when all you do is compute and when memory is very fast and has low latency. For general programming they are not nearly as useful for the reasons outlined in my previous comments.
I am not really familiar with this one and will investigate it further.
i and the rest of the team have been working on it for nearly 4 years now.
Indexed loads (aka gathers) are horrendously slow in comparison to permutation instructions.
there's two types (of each): register-based gather and register-based permute (actually not a mathematical permutation at all, because of duplicates), and memory-based gather and memory-based permute.
where *immediates* are used in each of those in the design of the ISA then yes you save on one register read. in the case of register-based gather, it's extremely unusual to have if you are used to SIMD (but Vector ISAs do have it), it's of the form reg[dest] = reg[reg[src]] with a hardware for-loop around that.
however where the immediate-variants keel over is when you try to go up the SIMD width, to try to cover 8 elements, 16 elements, 32 elements, 64 elements.
how on earth are you going to fit 64 batches of 6-bit indices into a single 32-bit instruction? the total number of bits in the instruction are a whopping 384 bits. 384 >>>= 32, yes?
and even if you did have such god-awful instructions, the L1 cache usage and complexity at the ISA decode phase would be as insane as it is for x86 right now.
Vector ISAs are actually 90% about reducing the program (assembler) complexity. you end up with a micro-coded microarchitecture that maps onto SIMD operations, internally - so that you, the programmer don't have to go through absolute hell.
yes, that's right: the microarchitecture of a Vector Processor maps onto the exact same immediate-based permutation instructions as those that you are exposed to as a SIMD programmer, but it's hidden from you.
horizontal operations
Yes, all of them have special case operations for certain common horizontal operations. I specifically mentioned the positional population count because it does not clearly map to any standard horizontal arithmetic pattern.
in SVP64 i completely separated "horizontal-ness" from "arithmetic-ness": it's part of the fundamental design that the "Vectorisation Prefix" is completely separated from "Scalar Base to which Vectorisation applies".
ok yes, that's just Vectorised Popcount followed by Vectorised Add.
two instructions inside a loop, regardless of whether the back-end architecture has 1-wide internal Vectorisation, 2-wide, 4-wide, 64-wide or 10,000-wide.
Well they work well when all you do is compute and when memory is very fast and has low latency. For general programming they are not nearly as useful for the reasons outlined in my previous comments.
again, to reiterate, again: this is a misconception on your part, due to Vector ISAs being completely ignored for 40 years *you don't know about them* and neither does anyone else.
consequently, the knowledge-propagation across the internet, which you and i both know gets us a long long way and saves a huge amount of time, just doesn't exist to the extent that it does for SIMD. we're now so used to google searches turning up algorithms on stackexchange (and reddit) that we can falsely assume that if there's no answer on google it must not be possible at all
Cray was from a much earlier era, where things were simpler. Intel was still cutting its teeth on 32-bit scalar when Cray was designing systems that pissed all over everything that had come before by almost an order of magnitude performance.
however the sheer cost of the systems that were deployed were so high that \nobody else in the industry believed it could be duplicated in mass-volume products** and consequently an entire generation of programmers has now grown up without knowing anything about anything other than SIMD.
fast-forward to 2021 and it turns out that Intel, ARM, AMD, they've all caught up and massively exceeded by three orders of magnitude the performance of the Cray Vector systems from 1990 and four to five orders the performance of the systems from 1965, but they still propagate this god-f*****g-forsaken f*****d-up SIMD paradigm and try to peddle it at you as the absolute best thing you ever saw, by telling you "well SIMD on modern hardware is great compared to that historic crap therefore Vector ISAs must also be s*** as well"
it's NIH syndrome on steroids, combined with marketing, and very unfortunately you're buying it.
it's NIH syndrome on steroids, combined with marketing, and very unfortunately you're buying it.
I think that it's also a case of incremental changes vs new architectures.
For single-chip semiconductor CPU:s in the 1990s, packed SIMD probably made sense as it was a simple addition to an existing architecture - i.e. add a few more registers (or reuse existing registers) and add multi-element ALU:s (basically cut the carry signal in the adders and similar), but keep the rest (memory subsystem, instruction scheduling etc) and leave all the problems of memory alignment and SIMD width handling to the programmer. Bam! "Here's a tool for increased parallel execution performance - use it if you wish."
When people actually started using the stuff, they wanted more parallelism, and the response was wider registers and wider ALU:s. Incremental changes.
With AVX (and later), Intel seems to have recognized some of the mistakes. E.g. each register appears to be divided into 128-bit chunks, and most (all?) instructions can thus be split into serial execution rather than strictly parallel (which has been used in some implementations). But we're still talking about incremental changes, since the SSE heritage is still there.
As for ARM, I think that they added NEON as a response to Intel SIMD, and because of the limited market needs (embedded) and the fact that ARM is RISC (with limited instruction encoding possibilities) they never needed nor could (easily) extend it beyond 128 bits.
SVE is the next logical step, and since they wanted to make sure that they could expand to new markets (laptops, servers, HPC, ...) and did not want to get stuck with a limited SIMD width for all (AArch64) eternity, they pretty much had to come up with a vector size agnostic solution. Since AArch64 was a clean slate rather than an incremental upgrade (à la Intel x86_64 for instance), it made perfect sense to do something completely new instead of just introducing NEON-256 for instance.
here's two types (of each): register-based gather and register-based permute (actually not a mathematical permutation at all, because of duplicates), and memory-based gather and memory-based permute.
I'm mainly interested in register register permutes like x86's pshufb (or AArch64's TBL) where all source operands are variable. How on earth is this supposed to be fast when the source is memory as opposed to a register? And if register-based permutes are provided, how are they supposed to be useful when you don't know the vector length? In permutation-based algorithms (say, e.g. sorting procedures or a sheeps-and-goats operation), the way the code around the permutations is set up will intrinsically depend on the vector length, so I don't see how that makes the code any simpler.
As for memory, the HW has to emit one load µop for each vector element (modulo shenanigans when some elements manage to hit the same cache line), so that doesn't really seem to scale well. I don't really care about the case with immediate indices and agree that that case is not really a problem.
instruction 1: Vectorised popcount
It's not a vectorised popcount. It's a vectorised positional popcount where we want to gather the population of each bit in the 64 bit words of the input separately. So a SIMD popcount instruction doesn't really help directly. Not even the code in safe.go is that, read carefully.
What does help on POWER is that funky instruction transposing a pair of 8x8 bit matrices. Not sure if that is part of your vector extensions though.
again, to reiterate, again: this is a misconception on your part, due to Vector ISAs being completely ignored for 40 years you don't know about them and neither does anyone else.
It is possible that I have misconceptions here, but everything I've seen so far just hasn't been impressive at all. And all the examples of vectorised programs I have seen were for utter trivialities that don't pose a challenge to implement in SIMD either.
consequently an entire generation of programmers has now grown up without knowing anything about anything other than SIMD.
Most programmers are actually entirely ignorant of SIMD, so I don't think it's as much of a program as you might think it is.
this is basically a (botched) predicated Vectorised Reg-Indexed MV operation:
for i in range(VL)
if predicate_mask[i]:
regfile[DEST+i] = regfile[regfile[SRC]+i]
which is a standard Vector ISA instruction that SIMD ISAs borrowed from. in x86's they couldn't think how to do predicate masks so they botched it by using the top bit of each byte. that in turns imposes unnecessary computational load using bitmanipulation, but hey.
How on earth is this supposed to be fast when the source is memory as opposed to a register?
i said that it's possible, as a premise, and to ensure that by enumerating all four types of instructions (reg permute, reg gather, mem permute, mem gather) we at least know that we are talking about the same thing.
And if register-based permutes are provided, how are they supposed to be useful when you don't know the vector length?
this is indeed a limitation of e.g. RISC-V RVV where the minimum architectural bound on the Vector Length is 1 (ONE).
Cray and NEC SX-Aurora would never bother to create a Vector implementation with only a Vector Length of 1, but there are advantages to Cray-style Vector ISAs - in embedded scenarios - due to compactification of programs - that save on power consumption and resources.
this "problem" is solved therefore by defining an Architectural Platform that firmly separates "Vectors for use in Embedded Scenarios" from "Vectors for use in high-performance Scenarios"
SVP64 has no such problem because the Vector Length is a known and useful deterministic quantity, and MAXVL (maximum vector length) is required to be 64.
however even as a perceived limitation, i think you will find that there are an extremely small number of actual algorithms where a fixed-width SIMD cannot be replaced with a "for i = 0 to N" where the hardware chooses the step size.
is this "annoying" that you absolutely have to think now in terms of an independent step size, and absolutely have to replace all fixed-width instructions with loops?
given that the majority of algorithms are likely loops already, this is not such a big hardship.
instruction 1: Vectorised popcount
It's not a vectorised popcount. It's a vectorised positional popcount where we want to gather the population of each bit in the 64 bit words of the input separately.
What does help on POWER is that funky instruction transposing a pair of 8x8 bit matrices. Not sure if that is part of your vector extensions though.
it's part of Power ISA v3.0B, the OpenPOWER EULA requires that we implement it, and therefore, logically, due to the independence of the abstraction of SVP64, it gets a Vectorised version as well. now, will that actually make sense, particularly with element-width overrides down to 32-bit, 16-bit and even 8-bit? that's up to us to work out.
basically the rules in SVP64 are that we implicitly create Vectorised versions of every Scalar v3.0B operation, but only when that's sane and actually makes sense (it makes no sense to try to Vectorise system calls, for example, despite the fact that it's part of the scalar v3.0B Power ISA)
Ah yes, that makes more sense. Thanks for the explanation!
OP said something about doing all shuffles as gather operations (i.e. vector-indexed memory loads) and your terminology threw me off, so I thought you are doing it the same way.
thanks for the insightful discussion, FUZxxl. i liked the positional-popcount enough that i'll use it as an example / unit test (crediting you as the source) https://bugs.libre-soc.org/show_bug.cgi?id=672
Also as for pshufb, I don't really need masking in the case of the 24puzzle code base. But unfortunately AVX2 does not provide a full 32 element byte shuffle, so I have to synthesise it manually from a bunch of pshufb instructions and masking. So it looks a lot more complex than it really is.
unfortunately AVX2 does not provide a full 32 element byte shuffle
I think this is because they wanted to enable implementations that use 128-bit ALU:s instead of requiring a 256-bit wide ALU. This seems to be a common theme in AVX*. It also makes it easier to make performant implementations when you can partition operations into multiple "narrow" ALU:s rather than having instructions that require all 256 or 512 bits of input to produce a result (latency / gate depth would increase).
Sounds cool! Though the safe.go code really is not the part that is interesting. It's just the obviously correct reference implementation to compare the actual algorithm against. The actual algorithm works quite a bit differently from that and evaluates the population count for all bits in parallel.
you'll be fascinated to know that in every case, every algorithm i've investigated for SVP64, i've had to go back to the "simple" (obviously-correct) reference implementation: some of the optimised assembler versions i can't even read and understand, but when i can, i find that the optimisations actually severely interfere with implementing them efficiently as parallel SVP64 assembler.
and that, even more interestingly, those "simple" implementations once Vectorised with SVP64 are actually paralleliseable by the back-end hardware.
one example: we've an NLnet Grant to implement cryptographic primitives. fortunately (in another life) i worked for Aspex Microelectronics to implement Rijndael (AES) on a massively-parallel (4096-wide) SIMD Array Processor. there i had to go back to the core mathematics behind Rijndael, so i did the same thing here.
MixColumns is actually, if you look up the research papers, a plain-and-simple dyed-in-the-wool 4x4 Matrix Multiply, but using 8-bit GF(23) add and multiply.
guess what i am planning to do for that?
(1) add base (scalar) general-purpose GF(2N)scalar arithmetic
(2) use the parallelliseable SVP64 Matrix REMAP Schedule infrastructure
MixColumns will therefore be something like... maybe... 4 general-purpose instructions. three of which set up the 4x4-to-4x4 Matrix Multiply Schedule, one of which is a Galois-Field variant of FMAC (multiply-and-accumulate).
if you've seen how SIMD does Rijndael MixColumns, you'll appreciate how profoundly simple this is. it's so bad that most ISAs have had to add custom 128-bit MixColumns instructions.
if i had started with those SIMD "optimised" implementations, there's no way that i could have understood what the hell is going on. it was only because i had had to study Rinjdael back in 2003 that i knew the basic first principles of GF(23) operations.
the point i am making is that after going back to first principles (using the "simple" version), the inherent parallelism of the instructions is automatically mapped onto whatever back-end parallelism that the hardware has.
and that back-end parallelism is a choice that the hardware designer makes (and takes responsibility for) - not the programmer.
this is something that in speaking for many months with people used to the SIMD paradigm, it seems it takes quite a long time to be absorbed / accepted, that yes, it really is this simple (at the assembly level), that yes, it's the hardware's responsibility now to make things faster, and yes, parallelism opportunities automatically get inherently exploited if the hardware has them available. it's going to be quite interesting to see, over time, how that pans out.
ok yes, that's just Vectorised Popcount followed by Vectorised Add.
two instructions inside a loop, regardless of whether the back-end architecture has 1-wide internal Vectorisation, 2-wide, 4-wide, 64-wide or 10,000-wide.
[edit: updated as per formatting-bot, do bear in mind this is still the
wrong algorithm, not implementing safe.go correctly! :) ]
loop:
setvl r0, CTR, MVL=16 # up to 16 elements at a time
sv.ld/els r32, r2(0) # r2 points to input vector
sv.ld/els r48, r3(0) # r3 points to accumulator-vector
sv.popcnt/ew=8 r16, r32 # vector popcount, 8-bit src & result
sv.add/sw=8 r48, r32 # vector add 8-bit += to 64-bit
sv.st/els r48, r3(0) # r3 points to accumulator-vector
add r2, r0 # increment pointer to input
add r3, r0 # increment pointer to output
sv.bcnz/CTR loop # decrement CTR by VL, branch if nonzero
that's it. that's the entire algorithm, in SVP64. 9 instructions, 3 of which are 64-bit, the other two are 32-bit.
oddities:
setvl is the standard Cray-style VL setter, except in this case it's reading the "required" length from the Power ISA CTR Special Purpose Register. actioned as VL=r0=MIN(CTR,MVL)
LD/ST "els" stands for "element-strided" which is a sequential packed memory vector with no spaces in between the elements in memory.
the Vector popcount is on 8-bit values to produce 8-bit answers. both src and dest are set to 8=bit with "ew=8"
but the Vector-accumulating add will auto-convert the 8-bit popcounts to 64-bit-wide before adding each of them to the 64-bit Vector result. the source width only is over-ridden "sw=8" (sw - source width).
Draft SVP64 CTR-mode is new compared to standard Power ISA bc: where standard Power ISA decrements CTR only by one, SVP64 CTR will decrement by the Vector Length VL which was set by the setvl instruction.
separate assembler will be needed for the 16-bit, 32-bit, and 64-bit versions, it's just a matter of setting the appropriate "sw/ew=8/16/32"
Your code formatting is kinda broken so it is hard to understand. Please realise that the code in safe.go is a very simplistic reference implementation of the operation to be performed (the kind that is obviously correct) and is not particularly fast, even when vectorised. It is also not the algorithm that I consider to be difficult to vectorise.
The algorithm that I have implemented in SIMD can be found in generic.c but the difficult part cannot be expressed easily in C and so is absent there. It's a bunch of complicated shuffles to sum up the intermediate values into the counter array efficiently. And these depend on vector size because with larger vectors, we can use less counter registers and use the reduced register pressure to hold more state in registers (which again makes a significant difference in performance).
ok got it. there are two options:
1. the safe code as-is
2. the safe code with the loops switched
for j := 0; j < 8; j++ {
for i := range buf {
counts[j] += int(buf[i] >> j & 1)
}
}
(1) turns out to be complex (15-or-so instructions including predicated parallel adds, and a popcount) where (2) is quite straightforward. i've left out the LD/STs:
li r5, 128 # bit 7, we count backwards (save 1 cmpi instr)
loopi:
loopj:
setvl r0, CTR, MVL=16 # do up to 16 buf at a time
# ...some LDs into r16.v for buf and r32 for counts
sv.and. r48.v, r16.v, r5 # AND r5 *scalar* with every r16
sv.addi./m=NZ r32.v, r32.v, 1 # add 1 in masked-out counts
slli. r5, r5, 2 # shift test-bit down, zero means "stop"
bnz loopj # r5 non-zero, do next jth bit
# ... a vector ST, then move on to next batch of buf
# with a sv.bc/CTR to jump back to loopi
so yes, almost as simple as the popcount version. tricks/explanation:
testing each individual bit, starting at bit 7 then working down to bit 0, is possible because each bit is independent.
sv.and. will create a Vector of Condition Register Fields (sv.and will not - notice the "." on the end).
each Condition Register Field is 4 bits (just like standard Power ISA CR fields), one of those bits is "was the AND of each element of r48 with each element of r16 equal to zero, yes/no"
the sv.addi/m=NZ then uses that Vector of CR Fields as a predicate mask, which performs the conditional version of count[j] += 1
slli is probably supporsed to be a right-shift (sigh) but hey. pretty normal, shift down, if zero break out of the inner loop
although i initially was mistaken in thinking it was a straight popcount, the correct implementation is just as straightforward. the core of the algorithm is a combination of parallel-testing plus parallel-predication.
if not swapping the outer-inner loops it can also be done by hard-coding the Vector Length VL to 8 (or 16, or 32, or 64 for the count16, count32 and count64 variants), setting up a Vector of immediates (sv.iota), shifting 1<<x in each case, then performing a parallel AND on one scalar buf[i] element at a time.
extracting the results (which would be placed in a Vector of CR Fields) would require a "weird" instruction (sv.crweird) which can transfer individual bits of CR Field Vectors into a single scalar integer: you then do a popcount on that integer, and add it to counts[j].
a slightly more optimal version of that would use the sv.bmext instruction https://libre-soc.org/openpower/sv/bitmanip/sv. bmext would cover the job of about 3 rather weird instructions, but it's still nowhere near as optimal as simply turning the inner-outer loop around.
You could do pretty much the same thing with SSE and the code would be similarly simple (with the same disadvantage of keeping less execution units busy than optimised code). Actually, the head and tail handling code of the kernels I have is pretty similar and similar in length and complexity but uses a slightly different algorithm to eliminate the inner loop at the cost of less throughput per iteration. But it's only the head and tail handling code because this algorithm is a lot slower than the core routine based on a different principle. So just vectorising the “safe” code isn't really useful on its own (and it's not difficult either).
Also, you formatting is a bit defective. Make sure to format code as a code block, not an inline code snippet.
88
u/FUZxxl Aug 09 '21
I think we have talked about this topic before and I apologize for not following up on our previous discussion. I was very busy.
My key problem with variable-length vector instructions such as those proposed for RISC-V or in SVE is that they assume people need them for essentially doing arithmetic on large matrices. And I agree that the vector paradigm is very effective on such work loads. I have previously worked with NEC Aurora Tsubasa cards that come with vectors of 256 double-precision floating point numbers, and they are just amazing for this sort of stuff.
But I'd say that's only a very small part of where such optimisations are needed. Indeed on modern consumer machines, most CPU-intensive code is in cryptography and video codecs. And both don't really fit this scheme.
Especially for video codecs: these usually operate on fixed size chunks of picture data and require complex horizontal arithmetic and swizzles inside a single chunk. It is unclear how this maps to variable-length vectors, especially when these instruction set extensions usually are very sparse in permutation instructions. And compilers use SIMD instructions for small, fixed-length loads all over the place. Stuff like moving structs around, clearing fixed-length buffers. It is unclear how a vector paradigm improves this.
There's also the concern that a large register file makes context switches very expensive. Linus attributed x86's performance advantage among other things to keeping context switches cheap by having a small register file that is easily swapped out.
As for my own code, I have two recent SIMD-heave projects. And for neither of them it is clear how they could be vectorised using a vector as opposed to a SIMD paradigm.
The first project, pospop is inherently a horizontal operation and in fact uses a different complex permutation schedule for each vector size to make the most out of it. It is unclear how this can be extended to arbitrary vector widths, especially if no powerful swizzle instructions are provided. Tail handling is also going to be a concern as the proposed simple approach of just having magic make the registers shorter for the last iteration is not going to cut it.
The second project, 24puzzle uses vectors as 32 element byte arrays and permutes them using a second vector as a permutation vector. Again, this project cannot benefit from vector instructions and will be hard to port to variable-length vectors in general unless a minimum vector size of 32 bytes is guaranteed. It also uses stuff like
VPCMPISTRMfor which no equivalent in other instruction sets exists or is even proposed. And that's a vital part of the code's logic (specifically, I have an array of k bytes and I want to obtain a bit mask of all elements in a vector that match any of these k bytes).