Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Using the most unhinged AVX-512 instruction to make fastest phrase search algo

gab-menezes.github.io

Post reply on HN
Print view View original

31–40 of 62 posts

Re: Using the most unhinged AVX-512 instruction to make fastest phrase search algo

#31

Post by kccqzy »

adrian_b wrote: post #26
Aurornis wrote: post #16

Earlier quoted context omitted.

> It's a shame that Intel seemed to really not want people to use it AVX-512 was never part of the specification for those CPUs. It was never advertised as a feature or selling point. You had to disable the E cores to enable AVX-512, assuming your motherboard even supported it. Alder Lake AVX-512 has reached mythical status, but I think the number of people angry about it is far higher than the number of people who e…

They had to disable AVX-512 only because Microsoft was too lazy to rewrite their thread scheduler to handle heterogeneous CPU cores. The Intel-AMD x86-64 architecture is full of horrible things, starting with the System Management Mode added in 1990, which have been added by Intel only because every time Microsoft has refused to update Windows, expecting that the hardware vendors must do the work instead of Microsoft…

> the P-cores of Alder Lake will continue to support any instruction subset that had been supported by Rocket Lake and Tiger Lake and Ice Lake and Cannon Lake

Wait. I thought the article says only Tiger Lake supports the vp2intersect instruction. Is that not true then?

Re: Using the most unhinged AVX-512 instruction to make fastest phrase search algo

#32

Post by LarsKrimi »

pclmulqdq wrote: post #29
LarsKrimi wrote: post #28

Earlier quoted context omitted.

It has a fixed polynomial, so not really that useful for anything but AES The only case where I've had use of GF(2^8) inverses is in FEC algorithms (Forney's algorithm) and then you need some kind of weird polynomial. But all of those needs are rarely in the hot-path, and the FEC algo's are way outdated

I think the AFFINE and AFFINEINV instructions are specifically for FEC and maybe compression algorithms. I also think they smell like something requested by one of the big customers of Intel (e.g. the government).

Hmm of course erasure codes would always need to solve these problems. Not sure what modern applications need that in the X86 world

I really think it's only AES since thats the only place I've seen that polynomial used. But of course maybe there's an obscure tape backup FEC algo used somewhere in datacenters?

Re: Using the most unhinged AVX-512 instruction to make fastest phrase search algo

#33

Post by mananaysiempre »

pclmulqdq wrote: post #22
mrandish wrote: post #7

Earlier quoted context omitted.

From my 1980s 8-bit CPU perspective, the instruction is unhinged based solely on the number of letters. Compared to LDA, STA, RTS, that's not an assembler mnemonic, it's a novel. :-)

"Load accumulator" (LDA) vs "Galois Field 2^8 affine transform on quad binary words" (GF2P8AFFINEQB) The compression factor isn't quite the same on character count, but it's still abbreviated. :)

Incidentally, how is it a GF(2^8) affine transform? As best as I can tell, it’s a GF(2)^8 affine transform, i.e. an affine transform of vectors of bits with normal XOR addition and AND multiplication, and the polynomial defining GF(2^8) just does not enter anywhere. It does enter into GF2P8AFFINEINVQB, but I’m having difficulties finding a geometric description for that one at all.

Re: Using the most unhinged AVX-512 instruction to make fastest phrase search algo

#34

Post by pclmulqdq »

mananaysiempre wrote: post #33
pclmulqdq wrote: post #22

Earlier quoted context omitted.

"Load accumulator" (LDA) vs "Galois Field 2^8 affine transform on quad binary words" (GF2P8AFFINEQB) The compression factor isn't quite the same on character count, but it's still abbreviated. :)

Incidentally, how is it a GF(2^8) affine transform? As best as I can tell, it’s a GF(2)^8 affine transform, i.e. an affine transform of vectors of bits with normal XOR addition and AND multiplication, and the polynomial defining GF(2^8) just does not enter anywhere. It does enter into GF2P8AFFINEINVQB, but I’m having difficulties finding a geometric description for that one at all.

I believe that the polynomial for GF2P8AFFINEQB is user-defined. One argument is an 8x8 matrix in GF(2) and the result is [A.x + b] in GF(2)^8 for each 8-bit section. Don't quote me on this, but I believe that matrix multiply in GF(2)^8 gets you a transform in GF(2^8).

Re: Using the most unhinged AVX-512 instruction to make fastest phrase search algo

#35

Post by ack_complete »

Aurornis wrote: post #16
Namidairo wrote: post #14

Earlier quoted context omitted.

It's a shame that Intel seemed to really not want people to use it, given they started disabling the ability to use it in future microcode, and fused it off in later parts.

> It's a shame that Intel seemed to really not want people to use it AVX-512 was never part of the specification for those CPUs. It was never advertised as a feature or selling point. You had to disable the E cores to enable AVX-512, assuming your motherboard even supported it. Alder Lake AVX-512 has reached mythical status, but I think the number of people angry about it is far higher than the number of people who e…

The problem with the validation argument is that the P-cores were advertising AVX-512 via CPUID with the E-cores disabled. If the AVX-512 support was not validated and meant to be used, it would not have been a good idea to set that CPUID bit, or even allow the instructions to be executed without faulting. It's strange that it launched with any AVX-512 support at all and there were rumors that the decision to drop AVX-512 support officially was made at the last minute.

As for the downsides of disabling the E-cores, there were Alder Lake SKUs that were P-core only and had no E-cores.

Not all workloads are widely parallelizable and AVX-512 has features that are also useful for highly serialized workloads such as decompression, even at narrower than 512-bit width. Part of the reason that AVX-512 has limited usage is that Intel has set back widespread adoption of AVX-512 by half a decade by dropping it again from their consumer SKUs, with AVX10/256 only to return starting in ~2026.

Re: Using the most unhinged AVX-512 instruction to make fastest phrase search algo

#36

Post by LoganDark »

nine_k wrote: post #20

What a post. It should have taken a week just to write it, never mind the amount of time it took to actually come up with all this stuff and overcome all the obstacles mentioned. What a dedication to improving the performance of phrase search.

I think you meant to write "it must have" rather than "it should have"?

Re: Using the most unhinged AVX-512 instruction to make fastest phrase search algo

#37

Post by nine_k »

LoganDark wrote: post #36
nine_k wrote: post #20

What a post. It should have taken a week just to write it, never mind the amount of time it took to actually come up with all this stuff and overcome all the obstacles mentioned. What a dedication to improving the performance of phrase search.

I think you meant to write "it must have" rather than "it should have"?

Let's agree on "It likely has".

Re: Using the most unhinged AVX-512 instruction to make fastest phrase search algo

#38

Post by tpm »

bri3d wrote: post #8
nxobject wrote: post #2

Spoiler if you don’t want to read through the (wonder but many) paragraphs of exposition: the instruction is `vp2intersectq k, zmm, zmm`.

And, as noted in the article, that's an instruction which only works on two desktop CPU architectures (Tiger Lake and Zen 5), including one where it's arguably slower than not using it (Tiger Lake). Meaning... this entire effort was for something that's faster on only a single kind of CPU (Zen 5). This article is honestly one of the best I've read in a long time. It's esoteric and the result is 99.5% pointless object…

Presumably Zen 5 cores will also get used in Threadripper and EPYC processors.

Re: Using the most unhinged AVX-512 instruction to make fastest phrase search algo

#39

Post by adrian_b »

kccqzy wrote: post #31
adrian_b wrote: post #26

Earlier quoted context omitted.

They had to disable AVX-512 only because Microsoft was too lazy to rewrite their thread scheduler to handle heterogeneous CPU cores. The Intel-AMD x86-64 architecture is full of horrible things, starting with the System Management Mode added in 1990, which have been added by Intel only because every time Microsoft has refused to update Windows, expecting that the hardware vendors must do the work instead of Microsoft…

> the P-cores of Alder Lake will continue to support any instruction subset that had been supported by Rocket Lake and Tiger Lake and Ice Lake and Cannon Lake Wait. I thought the article says only Tiger Lake supports the vp2intersect instruction. Is that not true then?

Tiger Lake is the only one with vp2intersect, but before Alder Lake there had already been 3 generations of consumer CPUs with AVX-512 support (Cannon Lake in 2018/2019, Ice Lake in 2019/2020 and Tiger Lake + Rocket Lake in 2020/2021).

So it was expected that any future Intel CPUs will remain compatible. Removing an important instruction subset has never happened before in Intel's history.

Only AMD has removed some instructions when passing from a 32-bit ISA to a 64-bit ISA, most of which were obsolete (except that removing interrupt on overflow was bad and it does not simplify greatly a CPU core, since there are many other sources of precise exceptions that must still be supported; the only important effect of removing INTO is that many instructions can be retired earlier than otherwise, which reduces the risk of filling up the retirement queue).

Re: Using the most unhinged AVX-512 instruction to make fastest phrase search algo

#40

Post by janwas »

nextaccountic wrote: post #13
suzumer wrote: post #12

Earlier quoted context omitted.

According to this [1] wikipedia article, the only feature Sapphire Rapids doesn't support is VP2INTERSECT. [1]: https://en.wikipedia.org/wiki/Advanced_Vector_Extensions

It seems that there are faster alternatives to it https://arxiv.org/abs/2112.06342 https://www.reddit.com/r/asm/comments/110pld0/fasterthannati...

Note that the article mentions using both outputs of the instruction, whereas the emulation is only able to compute one output efficiently.
Post reply on HN