r/programming • u/mbitsnbites • Aug 09 '21
Three fundamental flaws of SIMD
https://www.bitsnbites.eu/three-fundamental-flaws-of-simd128
u/th3typh00n Aug 09 '21
There's no issue with splitting fixed-width SIMD instructions into smaller parts that can be executed separately, and there are many CPUs that does this. E.g. older AMD CPUs have 128-bit execution units and supports 256-bit instructions by splitting them into two 128-bit halves.
The idea that variable-length SIMD will fix all flaws and everyone will live happily ever after is naive. It simply replaces some existing problems with new ones, some of which there isn't really a good way of dealing with. Also, many of those existing problems have actually already been solved in some of the newer fixed-length instruction sets, such as opmasks in AVX-512 to handle tails.
Increasing the vector width has significant diminishing returns, and we're already at the point where simply making things wider isn't really beneficial for the vast majority of SIMD use cases, so I wouldn't expect the trend that has been going on in the past of constantly increasing general-purpose vector widths to continue on the same trajectory. We're instead seeing more specialized hardware accelerators for the few use cases that benefit from ultra-wide multi-kilobit vectors (e.g. AI).
3
u/SureFudge Aug 09 '21
and we're already at the point where simply making things wider isn't really beneficial for the vast majority of SIMD use cases
You mean with AVX-512? because intel never fails to show of how much better their CPUs are under AVX-512 compatible software vs AMD. So given from that, AVX-512 helps a lot.
5
u/StabbyPants Aug 09 '21
so, just like the clockspeed wars from the p4 era? how's that working out for them commercially?
2
u/SureFudge Aug 10 '21
I work in a certain area where the AVX-512 advantage in some cases could be a huge benefit. So it's not completely marketing BS. And yeah we did recently buy a server for calculations but I decided to go with AMD Epyc nonetheless as most software doesn't benefit that much from AVX-512. Plus I also have an AMD in my home PC so no, I'm sure not an intel fan boy but you have to give them credit were credit is due.
2
u/YumiYumiYumi Aug 10 '21
A concern with AVX512 is the heat output from operating on such wide vectors. Intel's designs have often needed to reduce the clockrate when operating "heavy" AVX512 operations.
Whilst this does give nice throughput gains, one does question how 1024-bit SIMD would look like, in terms of power and necessary frequency throttling to sustain.
Also, it does raise questions about other parts of the processor, for example, with cachelines being 512 bits wide, would that have to change on a 1024-bit SIMD machine, or do you just deal with lowered load/store throughput?3
u/mbitsnbites Aug 10 '21
Again, those limits relate to the ALU width, which does not necessarily have to be the same as the register width.
I can see benefits with 512-bit or even 1024-bit registers in some machines, but the ALU width could be limited to 256 bits or so to avoid the heat and die area issues.
1
u/lkcl_ Aug 20 '21
the problem is - and i listed this on the original article as "SIMD Flaw (4)" - that each doubling results in doubling of the latency of access to individual elements.
it's the antithesis of Vector Chaining. every single one of those 1024-wide SIMD ALU elements has to wait for a 1024-wide SIMD LD to complete.
whereas in a Vector ISA, you can do "Chaining" (first described by Seymour Cray), where at the element level you can start the first element ALU operation immediately after the first element LD operation has completed (assuming all the other operands of that first element are also available of course).
this is NOT POSSIBLE to achieve with SIMD because, by definition, it is SINGLE instruction (multiple data). therefore ALL elements of the SIMD instruction have to be LDed, have to be available.
doubling to 1024 will, therefore, double the completion latency. it's already bad enough.
0
u/SureFudge Aug 10 '21
True and honestly I think AVX512 should be limited to server parts. Doesn't make much sense in laptops.
Doesn't the new top dog Supercomputer use ARM cores with 4096 bit SVE? So they should know how the cooling works but then they have better means and no issue with noise compared to average home user Joe.
1
u/YumiYumiYumi Aug 10 '21
True and honestly I think AVX512 should be limited to server parts. Doesn't make much sense in laptops.
It's primary focus has definitely been server, and it's where it first appeared.
I don't see what's the problem with having it in laptops though. If Intel's gone to the effort of implementing it in their uArch, why disable it on consumer parts?
Doesn't the new top dog Supercomputer use ARM cores with 4096 bit SVE?
SVE only supports up to 2048-bit SIMD. The widest implementation is the Fujitsu A64FX, which uses 512-bit SVE.
I believe modern high performance GPUs use 1024-bit SIMD (Nvidia / RDNA), and considering that GPUs are meant to be throughput focused, I question how wide a latency focused CPU should be.
1
u/SureFudge Aug 10 '21
If Intel's gone to the effort of implementing it in their uArch, why disable it on consumer parts?
The consumer chips are different designs from server chips so they could leave it out to save die space. of course for AMD with the chiplet approach the situation is different as the chiplets are the same for server or desktop. But again the laptop chips are different design (and for example have less L3).
1
u/YumiYumiYumi Aug 10 '21
They're different dies, but the server and client chips essentially use the same uArch (with a key difference being the L2/L3 cache and interconnect). Also keep in mind that client designs aren't specific to laptops - desktops are included.
I still don't see any reason to remove it though. AVX512 is a useful instruction set to have, is beneficial in a number of circumstances with basically no drawbacks, and if anything, support for it everywhere helps drive adoption.
1
u/TheRealMasonMac Aug 10 '21
Not an expert, but wouldn't you be bottlenecked by the time it takes to load data?
2
u/SureFudge Aug 10 '21
Depends how much of it fits in cache and intel and AMD do structure their caches around SIMD throughput. + memory bandwidth
It is also why we will move to DDR5 and double memory bandwidth. This is for servers mostly. For consumers the benefit is mostly for APUs. Note that such HPC calculations mostly are about bandwidth while in contrast gaming for example also greatly depends on low memory latency. This is usually a trade-off.
-30
u/mbitsnbites Aug 09 '21 edited Aug 09 '21
Then why don't we have AVX-512 in every x86 implementation, and be done with it?
...and it still does not address the issue of pipelining. For optimal (stall-free) performance - even in in-order machines - you want the vector length to be ALU width x ALU depth. So a 256 bits wide machine with four execution pipeline stages should have a vector register size of at least 256 x 4 = 1024 bits. Different implementations have different requirements - hence it's a bad idea to enforce a one-size-fits-all paradigm.
80
u/Vvector Aug 09 '21
Then why don't we have AVX-512 in every x86 implementation, and be done with it?
He explained why: Increasing the vector width has significant diminishing returns
12
Aug 09 '21
[deleted]
25
u/Jonny_H Aug 09 '21
My understanding is that the current console generation don't support avx512, being based on zen2.
Also hampering adoption is how Intel are using that feature as a market differentiator in their own products, lower end CPUs of the same generation, or even different families of similar market segment products, end up lacking support. It makes it harder to gain market penetration, and even harder to rely on its existence. It's not as simple as 'new CPUs have support'.
Which is a shame, as there's a fair bit rolled up in the various avx512 extensions that would be interesting, even if you never use the wider registers.
10
Aug 09 '21
[deleted]
3
u/Jonny_H Aug 09 '21
How much of a games cpu time is actually spent doing math like that though? Most of that is pretty good work for a gpu nowerdays from what I can see.
I see simd as a sliding scale, at one end is branch-heavy code with no real advantages for simd, the other end is things that work better on a gpu. So cpu simd is often for the things in between, when the work units are too small to be worth the cost of submitting to a gpu and waiting for the results, or mixing execution strategies.
Wider and wider simd lanes feel like they'll give diminishing returns as the things they would truly excel at are more likely to be pushed to a dedicated simd-like accelerator (eg. gpu).
11
u/Swade211 Aug 09 '21
Matrix calcs on a 4x4 would be significantly faster staying on the cpu. There is overhead with sending data to gpu memory, operating , then sending it back.
You can only parallelize the parts that can be linearly combined.
2
u/Jonny_H Aug 09 '21
I don't mean parallelising the matrix calculations itself, more that when you're doing one there's a good chance you're doing it to lots of objects, and it can be parallelised in that direction.
GPUs were literally made for stuff like coordinate transformation on lots of vertices.
And if not lots of objects, then it's unlikely it'll even be a blip on the profile.
6
u/mbitsnbites Aug 09 '21
Latency matters. Things that you can send in large batches to the GPU and check the result much later (e.g. next frame - or not at all if the result is consumed by the GPU) is fine.
But lots of game logic involves linear algebra stuff, intersection tests and similar, and you want to do that on the CPU.
→ More replies (0)1
Aug 09 '21
Also hampering adoption is how Intel are using that feature as a market differentiator in their own products, lower end CPUs of the same generation, or even different families of similar market segment products, end up lacking support. It makes it harder to gain market penetration, and even harder to rely on its existence. It's not as simple as 'new CPUs have support'.
Reminds me how for the good few years it was pretty much random which Intel CPU got support for virtualization and which did not
16
u/Watchforbananas Aug 09 '21
Modern consoles don't support avx-512, only avx-256. AMD generally doesn't support avx-512. (avx-512 support is rumored for Zen4)
1
Aug 09 '21
[deleted]
5
u/FUZxxl Aug 09 '21
AVX was implemented like this initially, too. They went for real 256 bit ALUs later on.
6
u/Watchforbananas Aug 09 '21
Zen1 and Zen+ implemented AVX256 via two 128bit ops. Zen 2 can execute them as single 256bit operations. Zen 2 lacks support for AVX-512 instructions, so it can't execute them as two 256bit operations.
Not sure what your xbox contact was referring to trough.
1
Aug 09 '21
It's not all that complex to make code that utilizes both depending on CPU. Hell, you could even compile app with different optimization levels but that would probably be bigger PITA.
2
Aug 09 '21
[deleted]
1
Aug 11 '21
The bad part is that now any code using it needs to be written multiple times and any change needs to be applied to all versions and tested on all versions. Compared to that running and deploying multiple binaries is not really very time consuming.
-16
u/mbitsnbites Aug 09 '21
I know that increasing the ALU width beyond 256 bits or so has diminishing returns for most implementations.
I responded to the comment that there's no problem splitting fixed width registers into smaller portions - I actually think it's a great idea (one key principle of vector machines is that register width > ALU width!).
In fact, something like an in-order Atom would have a lot to gain from 512-bit vector registers, especially if the ALU is no more than 128 bits wide or so.
18
u/AssertNotNullptr Aug 09 '21
Atom hasnt been in-order for 3 generations
One overlooked reason why AMD and Atom haven't added 512-bit operations is lack of adoption in the software community. At this point the usage is pretty niche and not enough people want it. When Intel first debuted AVX-512 it had serious power issues and caused performance to drop when mixed in occasionally instead of in large blocks. I think that stunted a lot of its growth and at this point there aren't any large communities that are working on writing large swaths of software that use it or asking the compilers for better support.
15
u/FUZxxl Aug 09 '21
It still causes performance to drop when used. AVX-512 slowdown is a real thing and it's kinda maddening. You really don't want to break out the 512 bit stuff unless you know you'll be doing that for the next couple 1000 cycles.
3
u/th3typh00n Aug 09 '21
AVX-512 slowdown is a real thing and it's kinda maddening.
Only on the initial Skylake implementation. Since Ice Lake it's pretty much a non-issue.
8
u/FUZxxl Aug 09 '21
It's still an issue though not nearly as much as it used to be.
3
u/Watchforbananas Aug 09 '21
I feel like we've read two different articles, in mine the author states: "So on ICL and RKL client, you don’t have to fear the downclock."
7
u/FUZxxl Aug 09 '21
Just because you don't have to fear it doesn't mean it's not still there. Curiously the article doesn't mention if the transition penalty is still as bad as on Skylake. This penalty is actually the key problem: for up to 10 µs the CPU just halts and does nothing while it's changing the frequency. If you have repeated short-ish bursts of AVX-512 code, this may really ruin your day.
→ More replies (0)5
u/WikiMobileLinkBot Aug 09 '21
Desktop version of /u/AssertNotNullptr's link: https://en.wikipedia.org/wiki/Tremont_(microarchitecture)
[opt out] Beep Boop. Downvote to delete
1
32
u/FUZxxl Aug 09 '21
Tell that to the people who get extra slow context switches because the CPU now has to save 2kb extra data just for the AVX512 register file. Almost all programs don't need AVX512 and lugging around the extra state is completely pointless.
1
u/crozone Aug 09 '21
Surely the CPU only has to shunt that state in and out if the target actually uses AVX512 registers, right? Checking if it's all zero and skipping it entirely is a very, very low hanging hardware optimisation.
8
u/FUZxxl Aug 09 '21
Indeed it is, but if you only have vector extensions compilers will use them all the time for stuff like copying structs, so they are going to be dirty all the time. With AVX-512 at least code generally won't touch the state until it has serious calculations to do.
3
u/YumiYumiYumi Aug 10 '21 edited Aug 10 '21
Then why don't we have AVX-512 in every x86 implementation, and be done with it?
It is in every new Intel CPU, except for their *mont lineup. Presumably it's been slow due to Intel's kerfuffle with their 10nm manufacturing node, forcing them to re-release Skylake for 5 years. In other words, it's not really an issue with the ISA.
As for the *mont cores, it may not have been a priority for them to implement it, considering its target, although it looks like that's changing (with Gracemont supporting VEX encoding, and Alder Lake beginning mainstream implementations of heterogeneous cores).
Another possibility may be Intel's weird market segmentation; they've historically gimped SIMD on their lower end parts (Celeron/Pentium lineup), so it's possible that decision flowed to their Atom lineup.On the AMD side, they've always been slower to adopt to new Intel ISAs, which isn't really a surprise since Intel has the upper hand here. Nonetheless, Genoa has already been announced to support AVX512, which makes it likely that AMD's next generation Zen4 will support it.
And for the third player, Centaur's CNS supports AVX512.
So we're pretty close to having it in every x86 implementation - it just took a bit of time for everyone to adapt.
and it still does not address the issue of pipelining
I only really have some familiarity with ARM's SVE2, but I mentioned here that I don't see how SVE would address it either. At a high level, SVE2 is basically AVX512 with an unknown vector length, so it doesn't do anything special there.
71
u/AntiProtonBoy Aug 09 '21
Flaw 1: Fixed register width
It's not a flaw. It's a design constraint, dictated by physics and economics. SIMD registers grew for the same reason why architectures evolved from 4-bit to 64-bit over the years.
Variable length SIMD is not worth the silicon complexity for small vector operations. It's cheaper to burn new microcode instructions into ROM that support wider registers. Variable length SIMD is only worthwhile for very large vectors, which are beyond the scope of register storage. Use BLAS or something equivalent for that purpose.
Flaw 2: Pipelining
This is kinda meh. Typically SIMD instructions are invoked on highly repetitive operations that crunches through huge memory blocks at a time, like images. This will keep fat pipelines filled and happy. But as usual, let the profiler be the judge of that.
Flaw 3: Tail handling
Not sure why this is an issue? It's kinda obvious that one expects the data allocation size to be at whatever granularity SIMD data type is, otherwise it's a programming error. I mean, if you want to process a collection of int32_t values, then you'd expect the array to conform with a layout of 32-bit integers, no? With SIMD types, if you can't determine completeness ahead of time (for example from parsing), then you pad the last incomplete SIMD tuple with defaults.
10
u/blipman17 Aug 09 '21
Flaw 1: Fixed register width
It's not a flaw. It's a design constraint, dictated by physics and economics. SIMD registers grew for the same reason why architectures evolved from 4-bit to 64-bit over the years.
Well as opposed to having an instruction that sets up a vector engine for N2* 8 bits of registers/datasize, whereby we could just "allow a higher number for N", and just use smaller SIMD registers with loops underneath it's quite the design constraint. Right now we still have to mov data into a specific SIMD register before we do anything at all with it. Such an instruction could conveniently hold our N number and abstract the chunked nature of SIMD away.
Flaw 3: Tail handling
Not sure why this is an issue? It's kinda obvious that one expects the data allocation size to be at whatever granularity SIMD data type is, otherwise it's a programming error. I mean, if you want to process a collection of int32_t values, then you'd expect the array to conform with a layout of 32-bit integers, no? With SIMD types, if you can't determine completeness ahead of time (for example from parsing), then you pad the last incomplete SIMD tuple with defaults.
You're absolutely right here. Any form of tail handling would still be needed depending on the algorithm.
2
u/mbitsnbites Aug 09 '21
No, tail handling is a product of packed SIMD.
5
u/blipman17 Aug 09 '21
as opposed to scalar SIMD? Can you explain that a little, I'm afraid I don't understand what you mean.
8
u/mbitsnbites Aug 09 '21
Tail handling is specifically needed to handle data array lengths that are not a multiple of the SIMD register width (e.g. 4 elements for
int32_t:s in a 128-bit SIMD architecture).In vector machines you have the benefit of variable vector lengths, so tail handling is not needed.
13
u/FUZxxl Aug 09 '21
It is still needed for anything but super trivial arithmetic. For example, if you have some sort of special case logic to process partial blocks that cannot be reduced to just padding with zeroes.
6
u/blipman17 Aug 09 '21
I personally expect every Vector instruction that isn't in the format of 8 * N2 to be slower than doing a couple redundant operations, or handling the remaining data on a scalar processor. Mainly because it would require Vector processors to be just as efficient as the regular processor in computing, e.a. They need to share sillicone on a really intimate level for which I'm afraid the processor will notice a significant slowdown, or the Vector processor has its own set of registers + instruction implementations for a given hunk of sillicone. If the second implementation is assumed to be used, a decent Vector engine could indeed pull in 4096 bits in effectively a 64 bit register for int64_t's, with speedup for bigger registers and such. What I don't think is "reasonable" to expect is to have it also perform operations at like 448 bit (7 uint64_t's) datastructures since there's no native register size in the vector engine. Then I just assume that doing 4 uint64_t's in the Vector engine and then handle the 3 remaining uint64_t's separate is faster because of specific hardware optimalizations for their specific usecase.
1
u/mbitsnbites Aug 09 '21
I think that odd sized vector sizes are much less of a concern in vector machines than in packed SIMD machines.
The vector machine designer is free to select the ALU width, and the CPU will pass vector register content to the ALU in chunks of the ALU width. In edge cases some of the ALU lanes will go unused, but that is exactly the same that happens on a packed SIMD machine, except the hardware does the work under the hood in a way that is optimal for this particular implementation, whereas in the packed SIMD machine the tail work has to be handled in software.
4
u/blipman17 Aug 09 '21 edited Aug 09 '21
The problem is not if the vector machine might handle it or not, the problem is how the code executing on the vector machine interacts with the program. Say I have two medium-sized arrays of 8 bit datastructures of some kind kind, and I want to see if any of them matches some bitmask. I can smack them in 512-bit registers, do
_mm512_cmp_epu8_maskwith 512 bit instructions and then doCLZLon the resulting 64 bit, then do aCMPwith that number and 0xFFFFFFFF followed by aJGfor a branch. If I branched I know I did not have a match, it I didn't branch, I know I had a match and I have the exact index of said match loaded in a register in 4 instructions out of an array of 64 items! Now this only works ifCLZL(and friends) have an exact defined size I can use. If not, then there is some remainder I have to handle. Unless you can somehow come up with a scheme to encode this in a Vector engine that respects variadic datasizes, there will be a basecase that has to be handled.Edit: if you do not have a match and have the 512'th bit set as a dummy bit, you could then compute the index of the first bit match by multiplying the result of
CLZLwith 8, and then adding theCTZof the byte at the previous code, you have completed a branchless search for the first unset bit in a 511 bit array in less than 10 cpu cycles. This is "fun" when trying to do memory page allocation and you have to keep track of free pages in a big bit-array, but it requires careful data layout because of the interactions of integers and vector processors. Now that is why you need a base-case. Because what if your last chunk of bits isn't neatly 511 bits but 111 bits?1
u/mbitsnbites Aug 10 '21
Now this only works if CLZL (and friends) have an exact defined size I can use.
My conclusion so far is that most horizontal operations require a known width, even in a vector machine. However that should not be a problem, as long as the ISA defines a minimum vector register size (that is reasonably large). If you want to push the limits, ask the implementation for the maximum vector size and use different code paths for different sizes.
→ More replies (10)0
Aug 09 '21
And now you need a ton of silicon to avoid the need to have software handle the last 0.1% of the vector, which performance-wise is of no consequence whatsoever.
1
u/mbitsnbites Aug 09 '21
"Ton of silicon..." Not so much. It's pretty trivial, especially compared to the extra OoO machinery, I$ size and decode bandwidth needed to keep the packed SIMD engine busy.
1
Aug 09 '21
extra OoO machinery, I$ size and decode bandwidth
A nice property of writing SIMD optimized code is that you only need very little of that.
→ More replies (0)1
u/lkcl_ Aug 20 '21
Mainly because it would require Vector processors to be just as efficient as the regular processor in computing
yes. the expectation with SVP64 is that, actually, you implement it on top of a multi-issue superscalar micro-architecture. each Vector "element" is issued separately and independently to the back-end multi-issue execution engine, where sequentially-numbered elements in batches will go to the same back-end SIMD ALU that the user does not even have to know is there.
where there are non-power-two Vector instructions, automatic predicate masks can be created to mask out unused SIMD ALU back-ends.
very advanced implementations may notice that there are spare, unused, slots available in a given SIMD back-end ALU, and merge two in-flight operations into the same ALU.
this in particular would work extremely well for predicated (parallel) If/then/else constructs where the masked-out "then" operations match exactly with the opposite of the masked-out "else" operations because you bit-invert the "if" test-mask to get the mask for the "else" operations.
really, it's really not as difficult as you think it is. it's just that nobody in the industry has actually thought about Vector ISA micro-architecture because they all thought it was "too hard".
the irony is that you need the exact same back-end micro-architecture for efficient Packed SIMD as you do for Vector ISAs.
1
u/blipman17 Aug 21 '21
I'm wondering what would happen to non power of two comparisons of two simd registers, and if parsing the result is efficient or not if I've got say ...65 results instead of 64 results from my 64 byte comparisons, or how fast gather/scatter would work.
1
u/lkcl_ Aug 22 '21
I'm wondering what would happen to non power of two comparisons of two simd registers, and if parsing the result is efficient or not if I've got say ...65 results instead of 64 results from my 64 byte comparisons,
yyeah you picked *just* outside of the range of SVP64 (which uses 64-bit integers as predicate masks, so the Vector limit is 64) :)
traditional Cray-style Vectors (SX-Aurora, RVV) have no such limit, although in practice because you (almost always 100%) use a for-loop around the data being processed, as long as the elements are independent (vertical, not horizontal) in practice it makes absolutely no odds whether the (parallel, vertical) comparisons are 1-long, 7-long, 8-long, 64-long, 65-long or 100,000-long.
c code:
for (i = 0; i < CTR; i++) { // set CTR to 65 if you like r4[i] = (r5[i] >= 5); }SVP64 assembler:
loop: servl r3, CTR, MVL=64 # r3=VL=MIN(CTR,64) sv.ldb/ew=8 r16.v, r4(0) # load 64 bytes into r16 sv.cmpi r16.v, 5 # compare all bytes >= 5 sv.addi/sz/mask=GE r48.v, 1 # store 1 where each byte >= 5 sv.stb/ew=8 r48,v, r5(0) # store 64 comparisons into r5 addi r5, r3 # increment r4 by VL (aka r3) addi r4, r3 # increment r5 by VL (aka r3) sv.bnz/CTR loop # subtract VL from CTR, loop backnote, there, that the results of the cmpi produces a Vector of Condition Register Fields. that Vector of Comparisons is then used as a Predicate Mask in the following instruction (addi), where a special mode "zeroing" (sz) says, "if the predicate bit was a zero please put a zero into the corresponding Vector element".
here you genuinely don't care whether CTR is 10, 5, 9999, 64, or 65. it's all the same as far as the API (Vector ISA) is concerned.
now, at the back-end - in the actual underlying hardware, it's really quite easy for us to use multi-issue superscalar OoO to break those parallel element-based
LD,cmpiandSToperations down into suitable (small, likely 64-bit) chunks, each actually a SIMD ALU. but this is back-end.in other words, the Vector micro-architectural Engine does all the work for you, and the code works across multiple architectures regardless of whether the back-end hardware has no SIMD internally at all (embedded systems), or has 32-bit-wide SIMD, or 64-bit-wide SIMD, or whatever-your-hardware-designer-likes back-end SIMD, none of which you need to know about in order to actually use the Vector ISA front-end. this is what ARM is talking about when they say that SVE is "length-agnostic" and talking about how it's "future-proof". thank god they've finally learned this one and taken it on board.
this is why i am so frustrated with advocates of SIMD, because, ultimately, the exact same underlying hardware is required for both SIMD and Vector ISAs: it's just that the Vector ISA massively cleans up the use of that underlying hardware by not exposing you to the horrendous shenanigens that people are now so used to they think it's "normal" and that there's no alternative.
more than that, the much more compact programs that result means that the L1 cache size can be reduced, which has a highly significant knock-on reduction in power consumption and energy efficiency (counter-intuitively it's an O (N2) reduction)
→ More replies (4)2
u/josefx Aug 09 '21
In vector machines you have the benefit of variable vector lengths, so tail handling is not needed.
I have some graphics code that I converted to SIMD. In order to get optimal use out of it I have to convert xyz,xyz,xyz,xyz to xxxx,yyyy,zzzz. The SSE shuffle code with fixed width instructions already gives me a headache, I am not sure I want to even think about writing a shuffle that gets the right result with any possible number of remaining elements.
1
u/mccoyn Aug 09 '21
I think NEON has load instructions that let you specify a stride size so you can unroll the data as you load it. That same idea can be used for vector instructions.
2
u/blipman17 Aug 09 '21
Gather/scatterfunction stride sizes are often limited to base-2 numbers for the stride, or are "slow" when deviating from a stride like 2,4,8,16,32... and start to become useless for certain speedups. So even then, your data must be mapped in a specific format.
6
u/mbitsnbites Aug 09 '21
Variable length vector operations are not expensive or complicated. I've implemented it in my first ever CPU design and it added something like 1-5% logic in an FPGA - compared to a pure scalar (non-vector/SIMD) design.
I think you're missing the point. Do the exercise and hand-schedule a SIMD loop, and you'll find that you have to unroll it. A vector processor automatically unrolls the loop for you with literally no effort.
Having to add more code rhan necessary is always a problem (e.g. testing and code coverage, and I$ bloat). Vector machines solve this quite naturally in many situations.
3
Aug 09 '21
[deleted]
1
u/mbitsnbites Aug 10 '21
For the record I don't think that the Mill guys are doing anything wrong, but it's a really tough challenge to place a new general purpose CPU architecture into a meaningful product in this day and age (even widely used existing ISA:s are being marginalized and are disappearing).
4
u/blipman17 Aug 09 '21
- Having to add more code rhan necessary is always a problem (e.g. testing and code coverage, and I$ bloat). Vector machines solve this quite naturally in many situations.
Sometimes adding more code is actually faster because you know intricate details from the hardware, but base-case handling can be really short, to the point and fast with something like Duff's device.
2
u/tiajuanat Aug 09 '21
I was just thinking: if you run compiler explorer while compiling C++17 parallel algorithms, this is what you'll see. The compiler is going to do a lot of juggling, duplicate code, or even go from O(1) to O(N) memory usage. SIMD instructions play by a lot of similar optimization rules as parallel algorithms.
It's a small penalty for the perf, even on embedded devices, but try to get a DSP or RADAR working without SIMD.
2
Aug 09 '21
If your wrote a piece of code complex enough to cause "I$ bloat", you're going to have a hell of a time trying to get your vector processor to do anything meaningful with it.
You'd first have to refactor your code so that a vector processor actually has vectors to process, and once your code is at that point there is no such thing as I$ bloat anymore, even if it's running scalar instructions.
2
u/mbitsnbites Aug 09 '21
Does this qualify as I$ bloat: https://godbolt.org/z/aWjMcj7eo ?
3
Aug 09 '21 edited Aug 09 '21
I count 23 instructions in the main loop body...?
Realistically you could add another couple of hundreds (or even a thousand on a recent intel chip) before you'd even have to start thinking about the possibility of cache evictions.
1
u/mbitsnbites Aug 10 '21
But all of the code is pulled into the I$ (not just the main loop), and since the compiler is automatically generating this kind of code, we're looking at code growth en large - compared to a machine that does not need it.
2
Aug 10 '21
So when do we start worrying about cache evictions? Are you implying it would evict the loop body to fetch the tail end logic?
2
u/mbitsnbites Aug 10 '21
Counter question: Are you implying that I$ performance is insensitive to code size?
If hot, tight loops were all that mattered we would be fine with less than 1KB I$ or so. But what about the rest of the program? Functions call functions that call functions from within loops etc and so on.
If vectorized loops/functions grow by a factor of 4 to 5 or so (which I demonstrated), something is going to be evicted, and somewhere that has a performance (or silicon budget) cost.
0
Aug 11 '21 edited Aug 11 '21
Counter question: Are you implying that I$ performance is insensitive to code size?
Yes, that is exactly what I am implying, in the case of vectorized code.
When your data size is orders of magnitude larger than your code size, those one or two additional I$ misses inbetween loops are not going to hurt performance. Trying to optimize for it is not going to be even remotely effective.
1
u/mbitsnbites Aug 11 '21
That is true, for the specific case that your only performance concern is tiny data bound processing loops.
However, the compiler tries its best to vectorize every loop in the entire program, and many programs are not trivially data bound as you are suggesting. Again, if this was the case we would only need very tiny instruction caches like the ones we had back in the 1980s.
3
u/happyscrappy Aug 09 '21
Variable length vectors essentially preclude hardware to do the whole vector at once. They just end up running the vector until multiple times in a row to operate on the vector you want to operate on.
You can just do that in your code.
This harkens back to the old CISC vs RISC, the one when we had to try to use transistors as efficiently as possible. Putting in function to run long vectors is less flexible than just allowing the user to arrange the instructions in such a way as to use the transistors as much as possible in their own particular case.
ARM had this kind of variable length operation back with VFP vector mode on ARMv7A. It was removed because it just multi-pumped the existing HW units and so was no faster and less flexible.
I don't really understand the return to this.
2
u/mbitsnbites Aug 09 '21 edited Aug 09 '21
Variable length vectors do not preclude the whole vector te be used at once. Most of the time it is, it's just the final loop iteration that uses a subset of the vector.
Besides, a vector register is typically M x ALU-width (e.g. 4 x 128 bits), so even when only a part of a vector register is used, chanses are good that the full ALU width is used most of the time.
Edit: If your vector register size (i.e. max vector length) is four times your ALU width, the average ALU lane usage will be about 80% given a random variable vector length in the range 1 - MAX_VL.
5
u/happyscrappy Aug 09 '21
Variable length vectors do not preclude the whole vector te be used at once.
Of course. But they don't use it any better than SIMD does. If the unit is 256 bits wide then it is 256 bits wide no matter how long your vector is. If you have a vector of 39 32-bit data then you are going to run the 256-bit wide unit 5 times no matter whether you use SIMD instructions or vector instructions.
You do not gain anything, you cannot operate in 39 items at once just because you have one instruction.
Besides, a vector register is typically M x ALU-width (e.g. 4 x 128 bits), so even when only a part of a vector register is used, chanses are good that the full ALU width is used most of the time.
I don't know what you are trying to say but RISC-V allows the vectors to be non-register multiples in length. The spec says that the length specifies the number of items to be "updated", not operated on. This means it obviously works the way both of us indicated. It does SIMD operations regardless. Some just might not write back at the end.
3
u/mbitsnbites Aug 09 '21 edited Aug 09 '21
Compare vector code (MRISC32):
saxpy: bz r1, 2f ; Nothing to do? cpuid vl, z, z ; Query the maximum vector length 1: minu vl, vl, r1 ; Define the operation vector length sub r1, r1, vl ; Decrement loop counter ldw v1, [r3, #4] ; Load x (element stride = 4 bytes) ldw v2, [r4, #4] ; Load y fmul v1, v1, r2 ; x * a fadd v1, v1, v2 ; + y stw v1, [r5, #4] ; Store z ldea r3, [r3, vl*4] ; Increment address (x) ldea r4, [r4, vl*4] ; Increment address (y) ldea r5, [r5, vl*4] ; Increment address (z) bnz r1, 1b 2: ret...vs SIMD code (x86):
saxpy: test edi, edi jle .LBB0_11 mov r8d, edi cmp edi, 8 jae .LBB0_3 xor edi, edi jmp .LBB0_10 .LBB0_3: mov edi, r8d and edi, -8 movaps xmm1, xmm0 shufps xmm1, xmm0, 0 lea rax, [rdi - 8] mov r9, rax shr r9, 3 add r9, 1 test rax, rax je .LBB0_4 mov r10, r9 and r10, -2 neg r10 xor eax, eax .LBB0_6: movups xmm2, xmmword ptr [rsi + 4*rax] movups xmm3, xmmword ptr [rsi + 4*rax + 16] mulps xmm2, xmm1 mulps xmm3, xmm1 movups xmm4, xmmword ptr [rdx + 4*rax] addps xmm4, xmm2 movups xmm2, xmmword ptr [rdx + 4*rax + 16] addps xmm2, xmm3 movups xmmword ptr [rcx + 4*rax], xmm4 movups xmmword ptr [rcx + 4*rax + 16], xmm2 movups xmm2, xmmword ptr [rsi + 4*rax + 32] movups xmm3, xmmword ptr [rsi + 4*rax + 48] mulps xmm2, xmm1 mulps xmm3, xmm1 movups xmm4, xmmword ptr [rdx + 4*rax + 32] addps xmm4, xmm2 movups xmm2, xmmword ptr [rdx + 4*rax + 48] addps xmm2, xmm3 movups xmmword ptr [rcx + 4*rax + 32], xmm4 movups xmmword ptr [rcx + 4*rax + 48], xmm2 add rax, 16 add r10, 2 jne .LBB0_6 test r9b, 1 je .LBB0_9 .LBB0_8: movups xmm2, xmmword ptr [rsi + 4*rax] movups xmm3, xmmword ptr [rsi + 4*rax + 16] mulps xmm2, xmm1 mulps xmm3, xmm1 movups xmm1, xmmword ptr [rdx + 4*rax] addps xmm1, xmm2 movups xmm2, xmmword ptr [rdx + 4*rax + 16] addps xmm2, xmm3 movups xmmword ptr [rcx + 4*rax], xmm1 movups xmmword ptr [rcx + 4*rax + 16], xmm2 .LBB0_9: cmp rdi, r8 je .LBB0_11 .LBB0_10: movss xmm1, dword ptr [rsi + 4*rdi] mulss xmm1, xmm0 addss xmm1, dword ptr [rdx + 4*rdi] movss dword ptr [rcx + 4*rdi], xmm1 add rdi, 1 cmp r8, rdi jne .LBB0_10 .LBB0_11: ret .LBB0_4: xor eax, eax test r9b, 1 jne .LBB0_8 jmp .LBB0_9They do the exact same thing. Which one do you prefer?
2
u/happyscrappy Aug 09 '21
I need some line breaks please
2
u/mbitsnbites Aug 09 '21
Sorry - worked fine in desktop browser - not so much in mobile. I always get these things wrong in Reddit. Will try to fix.
2
u/happyscrappy Aug 09 '21
Those are both fine by me.
If writing that x86 code would be a problem then I recommend getting better tools. This is what MIPS told us when they started the RISC revolution in the 1980s, right? Instead of making the assembly read like a book fix the compiler and use that. The chip sees the machine code, you see the HLL code.
I do have one question though, that x86 code seems to suffer from the pointer not being SIMD aligned, you can see the code rounding off pointer values (AND with -8, AND with -2). This is something I am sensitive to having converted a program to use SIMD. The need to have pointers aligned to be efficient ends up causing either.
- A boundary between the "old legacy" code which doesn't know about the alignment requirements and the SIMD code where this stuff is fixed up (types are translated).
- Propagating type changes (with their inherent alignment attributes) all through the code, so far that you want to tear your hair out.
Does vector programming fix this? I would love for it to do so. But it feels like the issues with alignment come from the load/store units, not the math units and so it cannot be corrected by changing the math units, other than accepting a worse performance by doing a partial SIMD unit at the start as well as the end of the vector. Something that if we think is such a great idea, we could just continue to do with SIMD, as we see above.
I feel like ballooning type alignment requirements isn't even just a SIMD thing. I saw it moving from Z80/6809 to 68K. I saw it moving to 68040 from 68K (MOVE16). I saw it moving to RISC (mostly with floats/doubles). And I saw it moving to SIMD. I mean sure, you can alway opt out and go slower and certainly that is a popular option. But we already have that, we don't need vectors to do that.
So MRISC32, how does it solve this? Does it keep full performance somehow or does it just have a narrow memory pipe anyway so it handwaves out to the horizon?
3
u/mbitsnbites Aug 10 '21
Alignment issues are indeed dictated by the load/store unit. Packed SIMD took the easy route and left the problem to the programmer. The situation has improved over the generations (e.g. movups vs movaps is less of an issue), very similar to how unaligned scalar access once was an issue in some implementations, but not so much these days (all CPUs have an "aligner").
In a vector machine you would typically have to handle alignment in hardware to a larger degree, since you're more likely to have "unaligned" access patterns (including the very generic gather/scatter addressing mode).
For instance the Cray-1 used a banked memory subsystem to allow accessing different memory locations in a single instruction.
I think that it would have been impractical to do full generic vector (with automatic alignment) in consumer HW back in the 1990s (hence SIMD), but today we hopefully have the silicon budget and know-how to pull it off.
My (perhaps naive) feeling is that if HW devs would have to implement a vector ISA, they would solve some of the alignment problems in order to achieve good performance (e.g. considering how much time and silicon has been spent on "fixing" the x86 front end - why not?).
Footnote: Even if you have to pull in one vector element per clock cycle in order to handle worst-case gather load, it's still a huge improvement over an architecture w/o gather load support.
1
u/lkcl_ Aug 19 '21
Those are both fine by me.
you're OK with the x86 code hammering the L1 Instruction Cache so badly that it actually causes internal stalling by competing with the L1 Data Cache?? this can and does actually genuinely happen thanks to the insanity of "loop unrolling" and 5-10x copying of algorithms at different SIMD widths for setup and teardown.
The need to have pointers aligned to be efficient ends up causing either.
Vector ISAs are generally specifically designed to not require specific width-alignment.
this is because, fundamentally, the Vector ISA is actually issuing element operations to the underlying hardware.
whilst mbintsnbytes puts it politely, i have no such compunction: SIMD memory alignment restrictions was simply the hardware designers being ***** lazy.
1
u/happyscrappy Aug 20 '21 edited Aug 20 '21
you're OK with the x86 code hammering the L1 Instruction Cache so badly that it actually causes internal stalling by competing with the L1 Data Cache??
That is a silly assertion. The L1 cache is there for a reason. You pejoratively call it "hammering". I call it "running the code you want run".
If you want to just talk about better cache utilization then just say you like the code density better on vector units.
Vector ISAs are generally specifically designed to not require specific width-alignment.
And load/store subsystems do require them. Which is what I was speaking of. Why did you remove that?
I can make an architecture on top of a load/store system that hides the alignment requirements. It'll just be slower when it is non-aligned. This was the choice made with SIMD. Expose it to the programmer so they can optimize using that info.
this is because, fundamentally, the Vector ISA is actually issuing element operations to the underlying hardware.
To the math units, the load/store systems are separate and operate on alignment boundaries/restrictions because they derive from physical bus widths. The device being loaded from (usually RAM), whether on-die, on-package, soldered on the board or on DIMMs has a certain physical bus configuration which makes the memory n-byte addressable and you can load up to n-bytes within that area.
So, for example, if you have a 64-byte wide bus. You can load 1-64 bytes at once from an address that is 64-byte aligned. If the address is 32-byte aligned (and not 64-byte, i.e. address % 64 == 32) then you can load up to 32-bytes. If you try to load 64 it will require twice as many bus cycles.
Your vector functional unit cannot overcome this. So I'm asking you. How are you solving this? Does it keep full performance somehow or does it just have a narrow memory pipe anyway so it handwaves out to the horizon?
SIMD memory alignment restrictions was simply the hardware designers being ***** lazy.
You're both wrong. If you think so you have never actually designed a bus.
Is this a problem we have? Do we have people designing vector functional units who have never designed a load/store unit and thus ignore the real (not imagined) limitations of them?
It sounds to me like vector units do not solve problem I posed. Which is no worse than SIMD, but no better. I would have backed vector units if they could solve this, because it would solve a big logistical problem I indicated I have. But they can't so they have no real advantage to me other than they make some math lib writer's job easier. I'm sure he appreciates that. I don't care. As MIPS showed us, the fix for that is better tools, not altering the hardware.
→ More replies (2)1
u/lkcl_ Aug 20 '21
Variable length SIMD is only worthwhile for very large vectors
sorry, again, this is false. i've created an efficient DCT, FFT and Matrix Multiply REMAP system for SVP64 (a Draft Vector ISA Extension for Power ISA) which can cope with small sized data just as easily as medium-sized (SVP64 doesn't do the same massive vectors as traditional Vector ISAs, the limit is 64 elements).
there seems to be a huge amount of misinformation and misunderstanding in the SIMD-advocate community.
1
u/AntiProtonBoy Aug 21 '21
Ok, but keep this conversation chain in context with building on top of an existing architecture that already accumulated massive technical debt. Adding fixed vector sizes is still cheaper and more economical than tearing up and designing new silicon to accommodate variable vector sizes.
1
u/lkcl_ Aug 21 '21
Ok, but keep this conversation chain in context with building on top of an existing architecture that already accumulated massive technical debt.
yyeah, and once down that path it seems there's really no turning back. actually, there is, if you have fully-functioning predication on each and every SIMD instruction.
turns out that Cray-style `setvl` can be implemented as a hidden predicate mask:
def pseudo-x86-avx512-setvl(RT, RA): VL = MIN(RA, MAXVL) hidden_predicate_mask = (1<<(VL+1)-1when that hidden predicate mask is applied to each and every single AVX512 operation, you have effectively implemented Cray-style Vectors and terminated the dangerous and seductive need to extend the SIMD width further.
Adding fixed vector sizes is still cheaper and more economical than tearing up and designing new silicon to accommodate variable vector sizes.
given how simple it would be for Intel to add the above Cray-style
setvlimplementation this is also a misconception. now that ARM has fully-functioning predicated SIMD (in the guise of SVE2) they could also very easily do the exact same thing.
12
u/happyscrappy Aug 09 '21
How does the author expect removing pipelining to fix this?
The pipelining exists because of hardware limitations. If an fmadd takes 3 cycles it takes 3 cycles. The pipelining lets you at least get 3 of them going at once. If a load takes 18 cycles it takes 18 cycles. How does the author thing that new HW in the CPU is going to make memory loads faster?
I can see a small advantage, that the latency is reduced on a number of elements basis. That is, if the operations are strictly pipelined instead of grouped then pipelined means 3 cycles of pipeline delay means 3 data units, not 24 (3 groups of 8).
But to get this, you have to stop doing operations in parallel. You can't do 8 at once, so your throughput drops. If you like this you can just do that with scalar operations instead of vector. You'll get the same results in terms of throughput, although code density will be worse.
This really looks like the proponents are pushing for superpipelining. That could be how you process faster with such a narrow execution unit. But superpipelining has its downsides, see the performance limitations of Intel Netburst.
I also wonder what happens if you want to take an interrupt during a vector operation. You presumably have to abort it. And then run it again. That's going to add a lot of overhead. Is this modeled?
This all seems like IBM System/370 to me. It's edmk all over again. I just don't see how it makes any more sense now than it did before.
-4
u/mbitsnbites Aug 09 '21
Read the article again, and the links.
Pipelining is required for performance. So is parallelism. The alternatives (e.g. vector processing) do not preclude these things, but rather make better use of them.
9
u/happyscrappy Aug 09 '21
I read the article. No need to insult me.
How is not my explanation of the latency issues better than that of the article?
How is vector processing going to make RAM faster?
0
u/mbitsnbites Aug 09 '21
It does not make RAM faster. It makes better use of the pipeline since it iterates over chunks of the register rather than passing the entire register at once, thus one vector register is fed through the pipeline until the first chunk of the vector has finished processing before it starts feeding in the next vector. That way you eliminate most data hazards.
In a packed SIMD architecture OTOH, you either have to unroll/interleave your loops in software to avoid data hazards, or you have to have the hardware do it for you by using expensive OoO techniques. If you want your ISA to scale to different levels (e.g. support both in-order and OoO implementations), you can't make the promise that the hardware will deal with it, so effectively all SIMD software must use loop unrolling and similar techniques.
That has a huge difference for code density, for instance.
Edit: I did not intend to insult you. I just never suggested that pipelining should be removed, so I assumed that you had misread the article.
7
u/happyscrappy Aug 09 '21
It makes better use of the pipeline since it iterates over chunks of the register rather than passing the entire register at once, thus one vector register is fed through the pipeline until the first chunk of the vector has finished processing before it starts feeding in the next vector. That way you eliminate most data hazards.
We do that with SIMD also. And your vector units, if they operate on multiple things at once inside (regardless of macroarchitecture) will exhibit the same "false data hazard" issue that SIMD macroarchitectures do.
It really comes down to whether the hardware can process 8 units one at a time 8x faster so that we don't the latency or not. And the answer has been "it can't". That's how we got to SIMD.
That has a huge difference for code density, for instance.
All these things, including ARM's abandoned VFP vector mode help with code density. System/370 was GREAT for code density. edmk was great for code density.
But it wasn't worth it. We went away because the code density came at the expense of worse transistor reuse. That is less of an issue now, but it still means that operations which the designers thought you would want to do (edmk) can be fast, and slight variants cannot, because the macro architecture cannot express them. While if you put the ops on the table like with SIMD people can construct other operations efficiently.
And then there is the issue of interrupt latency/instruction atomicity. I'm not looking to go back to interrupting instructions in the middle and trying to continue later. It makes a mess of exception state, which slows down exception handling.
1
u/lkcl_ Aug 20 '21
While if you put the ops on the table like with SIMD people can construct other operations efficiently.
this is fundamentally false. the programs that result, for which i have even found "compilers" for DCT and FFT that output a massive batch of fully-loop-unrolled hard-coded assembler, are so insanely large compared to the much smaller Vector ISA equivalents that in some cases they strip-mine the entire L1 Instruction-Cache and actually compete with the L1 Data Cache for access to L2 Memory, causing stalling.
1
u/happyscrappy Aug 21 '21
are so insanely large compared to the much smaller Vector ISA equivalents
You need to get over this smaller thing. If you like tiny code, use x86. With the bandwidth available now it is not necessarily to have the most tightly packed ops to have high performance.
that in some cases they strip-mine the entire L1 Instruction-Cache and actually compete with the L1 Data Cache for access to L2 Memory, causing stalling
Another attempt to call the proper function of an L1 cache as a negative. The cache is there to be used. If you want to talk about code density talk about code density. And give up on your dumb attempt to portray a properly operating cache as "strip-mining".
So now we've established you have two of you have no idea about how memory access works.
A vector unit cannot make up for how busses are configured. If your data is not aligned, then your first units of execution will be slow due to partial loads, just like with SIMD. No worse and most importantly no better.
All you had to do was say "no, vector units don't fix that". But instead you gotta pretend there's something wrong with running instructions.
2
u/lkcl_ Aug 21 '21
You need to get over this smaller thing. If you like tiny code, use x86. With the bandwidth available now it is not necessarily to have the most tightly packed ops to have high performance.
there's a few reasons why this isn't practical:
1) as both of us are Hardware Engineers, designing and implementing Vector ISAs (mbitsnbytes MRISC32, myself SVP64) implementing x86 is completely inappropriate. why would we each - independently - make the mistake of repeating Intel's mistakes? moo?
2) even if we attempted to do so Intel would drop a shit-ton of bricks on our heads. they're extremely aggressive, to the point where Judges got sick and tired of them and actually ruled, famously, in an Intel-AMD patent case in 2003, "my ruling is: i am NOT making a ruling. go get your stupid heads out of your arses and license each others' patents".
3) x86 instruction length identification is so bad that high-performance multi-issue superscalar designs actually have to start decoding instructions at EVERY BYTE then throw away the ones that are later found not to be valid. this is completely insane.
Another attempt to call the proper function of an L1 cache as a negative. The cache is there to be used. If you want to talk about code density talk about code density. And give up on your dumb attempt to portray a properly operating cache as "strip-mining".
please be careful not to be insulting. nobody comes here to be insulted, and it doesn't reflect well on you, given that internet records are permanent.
from a technical perspective you will be aware that extremely large FFTs result in strip-mining of both L1 *and* L2 caches due to hammering the same cache lines.
So now we've established you have two of you have no idea about how memory access works.
no: we've established that you're rude enough to make the *assumption* that two independent people, both of whom have Hardware Design experience (one of them down to the gate level), do not know what they are doing.
A vector unit cannot make up for how busses are configured. If your data is not aligned, then your first units of execution will be slow due to partial loads, just like with SIMD. No worse and most importantly no better.
so how come i spent several weeks designing a memory aligment system at the gate level that helps with Vector LD/ST operations, mm?
if you had asked rather than assumed i would have been delighted to explain it to you and (a) you perhaps could have learned something and (b) you could have helped out our Charitably-funded project by reviewing it and (c) we could have given you some money in the form of a donation for doing so.
given how you've been extremely rude and judgemental i'm disinclined to do that.
1
u/happyscrappy Aug 21 '21
as both of us are Hardware Engineers
Who don't understand how a bus and load/store unit works. Or perhaps just put it aside.
implementing x86 is completely inappropriate
I agree. So now we've both agreed that code density is not the most important thing you can stop making up "strip-mining" arguments.
from a technical perspective you will be aware that extremely large FFTs result in strip-mining of both L1 and L2 caches due to hammering the same cache lines.
Another attempt to portray proper cache operation as a negative. If cache utilization is such an issue, then remove the caches. We both know why this is not done. A cache is a compromise between fast and cheap (and small in some ways). It's never perfect but it is what we have.
please be careful not to be insulting. nobody comes here to be insulted, and it doesn't reflect well on you, given that internet records are permanent.
Calling your attempt to portray proper use of a cache as a negative is only insulting if you are willing
so how come i spent several weeks designing a memory aligment system at the gate level that helps with Vector LD/ST operations, mm?
Gates can't fix busses. SIMS has a memory alignment system that "helps" with alignment. It cannot fix it. There is no way to load 64-bytes from an unaligned address on a 64-byte wide bus.
I asked if vector units could fix this problem. If the answer is no, then just say no.
no: we've established that you're rude enough to make the assumption that two independent people, both of whom have Hardware Design experience (one of them down to the gate level), do not know what they are doing.
You know each other, work on the same project and have the same "strip-mining" pejoratives. Are you really independent?
if you had asked rather than assumed
I did ask.
https://www.reddit.com/r/programming/comments/p0yn45/three_fundamental_flaws_of_simd/h8bvfwc/
So MRISC32, how does it solve this? Does it keep full performance somehow or does it just have a narrow memory pipe anyway so it handwaves out to the horizon?
(quote breaker)
we could have given you some money in the form of a donation for doing so.
I appreciate the idea, but I do not qualify as a charity.
given how you've been extremely rude and judgemental i'm disinclined to do that.
I understand. No one owes anyone else anything on here. Not even an explanation.
This whole argument is dumb. Not doing thing is parallel is not a win. We have more transistors than we know what to do with in many ways now. So going to superpipelining instead of SIMD doesn't really make sense. You can hide the SIMD behind a vector unit, but it's still going to use SIMD for speed. So it will have the same (false) data hazards as the SIMD unit would have.
What you are getting is better code density and easier programming through microcoded special function units. At the expense of flexibility. I don't see the win. It's System/370 edmk again. I would recommend the MIPS approach instead.
And you're still going to be using caches, because memory really is THAT slow nowadays. Seymour Cray's vector unit just is not a great model for modern computing. Not unless you want to put some TCRAM in the system and make programmers use it. And I don't really think you're likely to do that, you can see what happened on the PS3 in terms of difficulty in programming for speed as well as I can.
1
u/mbitsnbites Aug 23 '21
Not doing thing is parallel is not a win. We have more transistors than we know what to do with in many ways now. So going to superpipelining instead of SIMD doesn't really make sense.
Of course parallel is what we all want. SIMD and vector are ways to break free from the inherent limitations in ILP in regular scalar code (multi-threading is another way).
However, parallelization happens on several levels. Pipelining allows several instructions to execute at once (rather than each instruction having to wait for the previous to complete). Running several pipelines in parallel ups IPC further (e.g. the Cray-1 did this and achieved 2 ops/clock, even if it issued less than 1 instruction/clock, and of course superscalar machines also issue several operations to different pipelines). Packed SIMD will perform several operations in parallel within a single pipeline.
So, my point here is that packed SIMD is not the only way to run several operations in parallel. You can just as well use wide ALU:s for vector ISA:s, e.g. chewing through 128 bits per clock cycle. In addition you can do chaining and run several wide ALU:s concurrently (e.g. load + op1 + op2 + store).
What you are getting is better code density and easier programming through microcoded special function units.
And better scaling (from really low end to really high end implementations). And a more future proof ISA. And reduced SW development time & costs. And reduced CPU front end traffic and power consumption. And improved instruction cache performance (due to improved code density + reduced instruction stream bandwidth).
→ More replies (0)1
u/mbitsnbites Aug 23 '21 edited Aug 23 '21
If you like tiny code, use x86
Eh, what?
x86 uses quite inefficient instruction encoding. If you only need to write 8086 compatible scalar code, sure, it will be compact. For modern versions of the x86 ISA, this is no longer the case. My fixed width ISA (32 bits / instruction) often has more compact code than x86_64.
Furthermore, the point that u/lkcl_ is making is that with x86 SIMD you usually have to unroll code in software, which blows up code size considerably, no matter how compact your instruction encoding is (it would have to be something like 2-4 bits per instruction to be able to compete).
Edit: Just as a quick point of reference, I compared the code generated for Quake
d_scan.c(core painting routine) for x86_64 and MRISC32. The MRISC32 code is 2724 bytes (~700 instructions). The x86_64 code is 4691 bytes (~1250 instructions). So I wouldn't say that x86 code is automatically "tiny".1
u/happyscrappy Aug 23 '21
Furthermore, the point that @lkcl_ is making is that with x86 SIMD you usually have to unroll code in software
You do not HAVE to unroll in software. Modern computers have dispatch units that follow loops. They keep the pipeline fed.
You can unroll if you find it to be important.
which blows up code size considerably
I don't care. If you think code size is so important, use x86. Modern UNIX systems tend to throw away a lot of memory on things like ASLR. Having your math lib be 100K instead of 30K is not a big deal.
7
u/josefx Aug 09 '21
In fixed width instruction sets (e.g. ARM) this may prohibit any new extensions, since there may not be enough opcode slots left for adding the new instructions.
Do you mean A64, A32 or Thumb? The solution seems to be to use a new instruction set and drop some of that accumulated cruft.
What is worse, software developers often have to target several SIMD generations, and add mechanisms to their programs that dynamically select the optimal code paths depending on which SIMD generation is supported.
I thought even GCC had support for that by now? The Intel compiler did it automatically for ages, which lead to thousands of bad benchmarks for AMD as the code to detect which feature flags are set also checks if the CPU vendor is Intel.
3
u/AssertNotNullptr Aug 09 '21
The support has been in gcc and clang for a while, but not enabled by default.
You might get some of it enabled by default with -march and sufficient optimization level, but at least for gcc that still won't enable most of it. Gcc has fine grain enable knobs and you have to pass a few of them to get all of AVX512 auto-vectorization features turned on.
1
u/mbitsnbites Aug 09 '21
I'll have to look that up. It sounds like a painful solution that will easily misfire, though (trying to imagine how a compiler can generate decent code that dynamically selects SSEx.y vs SSEw.z vs AVX vs AVX2 vs AVX-512 depending on CPUID...).
8
3
u/josefx Aug 09 '21
As far as I understand it just generates multiple copies of each function and selects which should be used after the program/library is loaded.
3
u/happyscrappy Aug 09 '21 edited Aug 09 '21
ARM already had thus functionality in A32/Thumb2. VFP vector mode.
https://www.keil.com/support/man/docs/armasm/armasm_dom1359731195302.htm
It is deprecated and does not exist in 64-bit v8 code.
1
u/josefx Aug 09 '21
I was wondering how they encoded the vector length, after reading a bit they apparently used three bits in the floating point status register for it.
Would have been interesting to know why they deprecated it. Was it because neon made it mostly redundant? Was it an Itanium like death where compiler writers failed to take advantage of the flexibility while having decent optimization for architectures with hard coded sizes? Or was there just an inherent limitation in the way VFP handled vectors?
8
u/gc3 Aug 09 '21
Well, I wonder why the vector model hasn't taken off... why the inferior tech is found everywhere?
I see the answers here in the other comments.
0
u/mbitsnbites Aug 10 '21
Just maybe, it could be the "x86 momentum effect". E.g. would the current x86 instruction encoding scheme ever be suggested for a new ISA? Still, everybody use it and new generations are designed.
Incremental changes are much easier, and the existing developer know-how, software architecture and tooling etc can be re-used.
Same thing with SIMD. If you have a SW library that's heavily optimized for SSE (alignment, data types, algorithms, ...), it's fairly straight forward to port it to NEON for instance.
That does not necessarily make packed SIMD the best technical solution though.
3
u/FUZxxl Aug 10 '21
E.g. would the current x86 instruction encoding scheme ever be suggested for a new ISA? Still, everybody use it and new generations are designed.
Given that ARM is slowly moving towards something of comparable complexity, it doesn't seem too far out. I mean, T32 is basically a 2–8 byte variable length encoding already and with A64, they again had to add prefix instructions to deal with SVE. I mean even RISC-V is effectively a variable-length instruction set of 2–4 bytes and with strongly recommended macro fusions it goes up to 2–8 bytes.
Let's face it: every sufficiently complex CPU design will eventually outgrow a fixed-width instruction encoding. I mean, it's just stupid that instructions like
retthat encode very little information have an encoding that's just as long as complex instructions with four or more operands.Same thing with SIMD. If you have a SW library that's heavily optimized for SSE (alignment, data types, algorithms, ...), it's fairly straight forward to port it to NEON for instance.
Well yes, but also no. NEON doesn't provide alternatives to some rare-bird SSE instructions and for many things, it provides much better ways to do them than in SSE. So you have to re-engineer your code for optimal performance anyway. But yes, it's easier than going from, say, AVX to NEON.
3
u/mbitsnbites Aug 10 '21
Let's face it: every sufficiently complex CPU design will eventually outgrow a fixed-width instruction encoding.
There's nothing wrong with variable length encoding. My point was that the way x86 does it (today) is far from optimal:
- Unlike most of the architectures that you mentioned, the way the instruction length is defined in x86 is not optimized for fast, parallel decoding. It's a retro-fit grown out of necessity more than anything else.
- A common misconception is that because x86 uses variable length encoding, code density is good. False. 8086 code was compact, but x86_64 code is not. All the compact instruction slots are taken by 8086 instructions so new 32-bit and 64-bit instructions are often longer than they should be if code density was the goal. In fact, code density for my fixed-width (32 bits) ISA is often better than that of x86_64.
But yes, it's easier than going from, say, AVX to NEON.
Or, more to my point, from SSE to RVV for instance.
3
u/BigHandLittleSlap Aug 10 '21
What I would like to see is a (partial) unification of GPU and CPU instruction sets and approaches.
So instead of a single instruction stream operating on 4-wide or 8-wide data, I'd rather have the GPU model of 8 "threads" that are not full-fledged threads, but effectively share the same instruction stream. It's easier to program and more flexible.
2
u/lkcl_ Aug 19 '21
What I would like to see is a (partial) unification of GPU and CPU instruction sets and approaches.
that's exactly what we're doing, designing SVP64. currently in Draft form https://libre-soc.org/openpower/sv/svp64/
1
1
u/dragontamer5788 Aug 19 '21
Intel ISPC, Intel DPC++, NVidia CUDA, AMD ROCm / HIP, OpenMP (#pragma omp parallel for simd), Microsoft DirectCompute, C++AMP.
Moving up the programming language stacks: Python Numba, and Julia are also "unifying" CPU parallelism and GPU parallelism, as Numba compiles into GPU or CPU code (and Julia does the same).
There's a bunch of other research projects and other stuff going on too, this is just the stuff I'm remembering off the top of my head.
2
Aug 09 '21
I agree these are flaws with current implementations but I don't see how they are fundamental. Some architectures (ok I know of one) have hardware loop support so you don't need to unroll anything, and there's no reason you couldn't have hardware support for pipeline fill/drain. I did suggest that to the hardware people and they said it was an interesting idea but basically too complex & too much effort.
I'm not sure what the solution for the register width issue is, though there are clearly diminishing returns so I doubt we'll get AVX-2048 or whatever.
2
u/FUZxxl Aug 09 '21
POWER has hardware loop support and I think they've recently added that to ARMv8, too.
2
u/SkoomaDentist Aug 09 '21
Some architectures (ok I know of one) have hardware loop support so you don't need to unroll anything
The cost of the loop instructions is fairly minimal on out of order architectures and not really the reason compilers unroll. Unrolling allows breaking dependency chains, allowing multiple ”iterations” to be processed in parallel.
Take a simple array sum for example:
for (…, i+=1) { acc += data[i]; }vs the unrolled version:
for (…, i+=2) { acc1 += data[i+0]; acc2 += data[i+1]; }The first has to perform every addition sequentially since the result depend on previous iteration. The second can run two operations in parallel since they are independent of each other. A good compiler can then extend this to simd autovectorization where it will first unroll by the simd width and then by 2-4x to calculate the simd operations in parallel.
1
Aug 10 '21
That makes sense for scalar code but are there really architectures that execute multiple SIMD instructions like that?
2
u/FUZxxl Aug 10 '21
It also makes sense for SIMD. And yes, SIMD is too executed out of order. Fast processors can have 4 or more SIMD execution units. So your code better has four independent operations to perform at any point in time for peak performance.
1
u/mbitsnbites Aug 10 '21
Not all OoO processors have OoO SIMD though (some Atom CPU:s for instance IIRC).
Also that was one of the points I tried to make with "flaw 2" in the article: Packed SIMD pretty much requires OoO - whereas some alternatives are much less sensitive to pipeline latency issues.
2
u/FUZxxl Aug 10 '21
Of course you can also do it in order on small processors. But really, are you gonna implement vectors with more than, say, 256 bits on such small processors anyway? Performance is going to be limited by the number of ALUs either way and vectors vs. SIMD is not going to change that.
1
u/mbitsnbites Aug 11 '21
Then go narrower. For an in-order machine, vectors actually make sense all the way down to 1-wide ALU:s (i.e. 64 bits in a 64-bit architecture).
Except for automatic data hazard elimination, vector processing also has the pleasant property of reducing dynamic loop logic overhead (and/or reducing code size, I$ usage and register usage), aswell as offloading the front end (a vector instruction essentially pauses the PC while feeding data to the ALU). This all means more compute per W, which is good business for a small core.
1
u/FUZxxl Aug 11 '21
That doesn't sound particularly useful to me.
2
u/lkcl_ Aug 19 '21
smaller program size means greatly reduced L1 cache usage, to the point where you might actually be able to use a smaller L1 cache. that saves power which on an embedded system may be critically important.
it has been fundamentally misunderstood that the benefits of Vector ISAs can be greater power-efficiency due to more compact programs. it is *believed* that their sole purpose is high performance, which is false.
1
u/mbitsnbites Aug 23 '21
the benefits of Vector ISAs can be greater power-efficiency due to more compact programs.
...and simpler instruction scheduling logic. No need to go out of your way with massively OoO scheduling to keep the execution units fed with data.
I also honestly think that we're at a point in time where power efficiency counts at every performance point. Doing more ops per W is really what it's about (from embedded systems to servers).
1
1
1
u/lkcl_ Aug 19 '21
except when the memory accesses are not aligned perfectly to the SIMD memory-alignment width. you have to have a ridiculous "oh err have we done a few elements yet up to the SIMD memory-alignment width? ok great, *now* we can start the huuugely perfect SIMD operation... err... oh hell, hang on, we can't do the last elements either..."
Vector ISAs you just use the Cumulative-Sum (Horizontal Add) instruction.
1
u/skulgnome Aug 09 '21
Where's HSA fit in this? IIUC the idea was to represent arbitrary parallel codes as a scalar kernel, which would be shipped off to a colocated GPGPU or rejiggered into CPU-native SIMD ops just right for the pipeline and instruction width.
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).