6 ms·

Back in the mid-2000s I worked at a company that made their own (MIPS-based) chips. NSA was one of our customers - supposedly the "defense" who could be conside

Back in the mid-2000s I worked at a company that made their own (MIPS-based) chips. NSA was one of our customers - supposedly the "defense" who could be considered the good side of NSA compared to the 10x larger "offense" but still. As we were planning for our second generation, they offered quite a bit of money if we'd implement a "sheep and goats" instruction. It would take two operands: an input and a mask. The masked-in bits of the input (the "sheep") would be packed toward the MSB of the output, while the masked-out bits (the "goats") would be packed toward the LSB. We had a lot of people on staff with serious chops in all sorts of math including cryptography, but none of them could identify an algorithm that would benefit from having such an instruction (as distinct from more conventional range-based bitfield instructions). Since the company went under shortly afterward, it remained a mystery. I still wonder about it.

less_less 5y ago
Half of this instruction is present in AMD64's BMI2 extension as PEXT, and the reverse operation as PDEP. Unlike "sheep and goats", PEXT just extracts the sheep into the LSB and ignores the goats. If I recall the Knuth lecture correctly, given a "sheep and goats" instruction where one of the sets is packed in reverse order, you can implement any n-bit permutation in something like log2(n) instructions. I don't remember if this is true if they're both packed in forward order. But it would be nice for some hardware crypto designs, like DES or more recently GIFT. PEXT has at least two additional use cases I know of: manipulating bit indices for databases, and binary (GF2) matrix manipulation. I've used it in a (non-crypto) project to select a subset of columns from a binary matrix, to convert it to systematic form. This subroutine also used popcount. What I really wanted in that project was another "NSA instruction": bit matrix multiply. Cray supercomputers can multiply two 64x64 binary matrices in one instruction, though I have no idea how many cycles it takes. With AVX2, the best I could do is 6 instructions plus precomputation for 8x8 x 8x32, which is 1/128'th the work.
- someguydave 5y ago
  indeed, Cray famously said "If you were plowing a field, which would you rather use: two strong oxen or 1024 chickens?" Unfortunately we only have 1024 chickens in modern computers.
  - CalChris 5y ago
    Yes, but those chickens now are as powerful as Cray's oxen were then.
    - flavius29663 5y ago
      so, do you want 2 modern oxen or 1024 modern chickens?
      - CalChris 5y ago
        Gimme dem modern wide supercalar OOO cached chickens, please. Cray was right back then but he is no longer right now. If he were, the market would say so.
        PhantomGremlin 5y ago
        Cray is still right. Today we know how to put 16 4 GHz CPUs on a single die. If we want, we can hook chips together to build a computer with 16,384 CPUs. But we can't build a single chip running usefully at 16x4 GHz. We can't build a single system running at 16384x4 GHz. If we could build that fast chip or system, all else being equal, the market would choose the single fast CPU over the pile of slow CPUs. Right now "the market can't say so". It's impossible to provide such a system to the market. We're forced to buy computers with so many CPUs because we've pretty much hit the wall in terms of frequency scaling. Intel Pentium 4, circa 2001, ran at about 1.4 GHz. Intel Core i9, circa 2021, runs at about 3.5 GHz, with turbo boost to about 5.2 GHz. That's about a 3x improvement in clock speed in 20 years. We simply can't make CPUs that run faster than that. (I had to use x to represent multiplication, HN formatting gets funny with asterisks).
        djmips 5y ago
        Thanks for the post but you can't in all fairness keep your "Cray is still right" opening statement when you go on to agree that in reality, which is what is important, we have to settle for lots of chickens.
- Enginerrrd 5y ago
  It's out of my depth, but my guess is on sething DES related. Here's a link to some possibly relevant discussion about it. http://www.icodeguru.com/Embedded/Hacker's-Delight/050.htm http://www.icodeguru.com/Embedded/Hacker's-Delight/050.htm
- thomasmg 5y ago
  Succinct (space-saving) data structures often need "rank" and "select" operations. Rank(n) is the number of 1 bits up to position n. Select(n) is the reverse: at which position is the n-th 1 bit. For "rank", the "popcount" instruction can be used. Interestingly, for "select", the "PDEP" instruction can be used: you can put the data array in the PDEP mask, and 1 << n in the value; basically flip the operands. I found this quite fascinating. For details, there is a short paper on this: "A Fast x86 Implementation of Select". I wonder if those succinct data structures are in any way related to what NSA is doing. I think not, but who knows.
  - Bayart 5y ago
    The paper, if anyone wants to save some clicks : https://arxiv.org/abs/1706.00990 https://arxiv.org/abs/1706.00990
  - yvdriess 5y ago
    I've seen it used for large-scale genomics. Saving a few bits if you're dealing with billions of a thing is very useful. They're also vital for being able to pack as much of a datastructure (e.g. a graph) on a single node. Some graph algorithms, e.g. random walks, are latency bound and scale really badly in a distributed system.
- Sniffnoy 5y ago
  Heh, so it's an instruction for INTERCAL's "select" (~) operator...
pbsd 5y ago
That sounds like a decent primitive to accelerate arbitrary bit permutations in software. It's known as GRP in, e.g., [1]. [1] http://palms.ee.princeton.edu/PALMSopen/shi00bit.pdf http://palms.ee.princeton.edu/PALMSopen/shi00bit.pdf
- notacoward 5y ago
  Very interesting. This was published in 2000, and the people we worked with were near Princeton, so this result - the specific utility of such an instruction, if not the semantics themselves - might very well be something that was known to some relevant people but not yet widely enough for any of our people to recognize it. Thanks!
dboreham 5y ago
I have also been around in a company that made CPUs that initially had no bit count instruction. Then at some point the instruction was added. At the time I heard that "men in black with mirrored sunglasses" had shown up and demanded that the instruction be added. Whether or not this was an accurate description of events, you can see the note on page 74 in this document (section 8.2) : http://www.transputer.net/iset/pdf/tis-acwg.pdf http://www.transputer.net/iset/pdf/tis-acwg.pdf recording the instruction having been added. Edit, I see Roger Shepherd (one of the people in the know at above mentioned company) commented in the comp.arch thread (which I vaguely remember reading at the time) but no mention of MIB...
coolspot 5y ago
Is it possible that by some mistake the NSA your company was working with was National Sheepfarmers Association? Did representatives of the “NSA” have a New Zealand accent?
devit 5y ago
That's equivalent to !0 << popcount(!(x & mask)) (where left shift must saturate and not truncate the shift count, otherwise you need to special case x = 0) and seems much less useful than popcount.
- notacoward 5y ago
  I think you're misunderstanding what the instruction (or similar ones that others have mentioned) would do. It's a specialized permutation function; every bit in the input is preserved, just in a different position. Your version doesn't have that property at all, and would indeed not be very useful.
mjevans 5y ago
The 'and goats' part leads me to conceptualizing the instruction more like: Bit Scrambler / Chutes - shuffle bits around in a way that divides a stream. This might also be useful in pre-filters for compression (entropy reduction) if you knew the content of the message. E.G. for ASCII text the upper 2-3 bits of each letter could be ranked to the side for better compression and a reduction of message size. As others have pointed out, modern CPUs ended up with 'half' that instruction, so I wonder if there were any other reasons for the full instruction.
jhallenworld 5y ago
Compress and expand (from Hackers Delight) are like this, but only the selected bits are kept. These are quite useful instructions. One use is the hash function for perfect hash tables. The hash table includes a mask which picks the bits of the keys which actually change (between all keys) and compresses them all to the right as the hash index. Disclaimer: I contributed the "expand" algorithm shown in Hacker's Delight.

less_less 5y ago

Half of this instruction is present in AMD64's BMI2 extension as PEXT, and the reverse operation as PDEP. Unlike "sheep and goats", PEXT just extracts the sheep into the LSB and ignores the goats. If I recall the Knuth lecture correctly, given a "sheep and goats" instruction where one of the sets is packed in reverse order, you can implement any n-bit permutation in something like log2(n) instructions. I don't remember if this is true if they're both packed in forward order. But it would be nice for some hardware crypto designs, like DES or more recently GIFT. PEXT has at least two additional use cases I know of: manipulating bit indices for databases, and binary (GF2) matrix manipulation. I've used it in a (non-crypto) project to select a subset of columns from a binary matrix, to convert it to systematic form. This subroutine also used popcount. What I really wanted in that project was another "NSA instruction": bit matrix multiply. Cray supercomputers can multiply two 64x64 binary matrices in one instruction, though I have no idea how many cycles it takes. With AVX2, the best I could do is 6 instructions plus precomputation for 8x8 x 8x32, which is 1/128'th the work.

someguydave 5y ago
indeed, Cray famously said "If you were plowing a field, which would you rather use: two strong oxen or 1024 chickens?" Unfortunately we only have 1024 chickens in modern computers.
- CalChris 5y ago
  Yes, but those chickens now are as powerful as Cray's oxen were then.
  - flavius29663 5y ago
    so, do you want 2 modern oxen or 1024 modern chickens?
    - CalChris 5y ago
      Gimme dem modern wide supercalar OOO cached chickens, please. Cray was right back then but he is no longer right now. If he were, the market would say so.
      - PhantomGremlin 5y ago
        Cray is still right. Today we know how to put 16 4 GHz CPUs on a single die. If we want, we can hook chips together to build a computer with 16,384 CPUs. But we can't build a single chip running usefully at 16x4 GHz. We can't build a single system running at 16384x4 GHz. If we could build that fast chip or system, all else being equal, the market would choose the single fast CPU over the pile of slow CPUs. Right now "the market can't say so". It's impossible to provide such a system to the market. We're forced to buy computers with so many CPUs because we've pretty much hit the wall in terms of frequency scaling. Intel Pentium 4, circa 2001, ran at about 1.4 GHz. Intel Core i9, circa 2021, runs at about 3.5 GHz, with turbo boost to about 5.2 GHz. That's about a 3x improvement in clock speed in 20 years. We simply can't make CPUs that run faster than that. (I had to use x to represent multiplication, HN formatting gets funny with asterisks).
        djmips 5y ago
        Thanks for the post but you can't in all fairness keep your "Cray is still right" opening statement when you go on to agree that in reality, which is what is important, we have to settle for lots of chickens.
Enginerrrd 5y ago
It's out of my depth, but my guess is on sething DES related. Here's a link to some possibly relevant discussion about it. http://www.icodeguru.com/Embedded/Hacker's-Delight/050.htm http://www.icodeguru.com/Embedded/Hacker's-Delight/050.htm
thomasmg 5y ago
Succinct (space-saving) data structures often need "rank" and "select" operations. Rank(n) is the number of 1 bits up to position n. Select(n) is the reverse: at which position is the n-th 1 bit. For "rank", the "popcount" instruction can be used. Interestingly, for "select", the "PDEP" instruction can be used: you can put the data array in the PDEP mask, and 1 << n in the value; basically flip the operands. I found this quite fascinating. For details, there is a short paper on this: "A Fast x86 Implementation of Select". I wonder if those succinct data structures are in any way related to what NSA is doing. I think not, but who knows.
- Bayart 5y ago
  The paper, if anyone wants to save some clicks : https://arxiv.org/abs/1706.00990 https://arxiv.org/abs/1706.00990
- yvdriess 5y ago
  I've seen it used for large-scale genomics. Saving a few bits if you're dealing with billions of a thing is very useful. They're also vital for being able to pack as much of a datastructure (e.g. a graph) on a single node. Some graph algorithms, e.g. random walks, are latency bound and scale really badly in a distributed system.
Sniffnoy 5y ago
Heh, so it's an instruction for INTERCAL's "select" (~) operator...

pbsd 5y ago

That sounds like a decent primitive to accelerate arbitrary bit permutations in software. It's known as GRP in, e.g., [1]. [1] http://palms.ee.princeton.edu/PALMSopen/shi00bit.pdf http://palms.ee.princeton.edu/PALMSopen/shi00bit.pdf

notacoward 5y ago
Very interesting. This was published in 2000, and the people we worked with were near Princeton, so this result - the specific utility of such an instruction, if not the semantics themselves - might very well be something that was known to some relevant people but not yet widely enough for any of our people to recognize it. Thanks!

dboreham 5y ago

I have also been around in a company that made CPUs that initially had no bit count instruction. Then at some point the instruction was added. At the time I heard that "men in black with mirrored sunglasses" had shown up and demanded that the instruction be added. Whether or not this was an accurate description of events, you can see the note on page 74 in this document (section 8.2) : http://www.transputer.net/iset/pdf/tis-acwg.pdf http://www.transputer.net/iset/pdf/tis-acwg.pdf recording the instruction having been added. Edit, I see Roger Shepherd (one of the people in the know at above mentioned company) commented in the comp.arch thread (which I vaguely remember reading at the time) but no mention of MIB...

coolspot 5y ago

Is it possible that by some mistake the NSA your company was working with was National Sheepfarmers Association? Did representatives of the “NSA” have a New Zealand accent?

devit 5y ago

That's equivalent to !0 << popcount(!(x & mask)) (where left shift must saturate and not truncate the shift count, otherwise you need to special case x = 0) and seems much less useful than popcount.

notacoward 5y ago
I think you're misunderstanding what the instruction (or similar ones that others have mentioned) would do. It's a specialized permutation function; every bit in the input is preserved, just in a different position. Your version doesn't have that property at all, and would indeed not be very useful.

mjevans 5y ago

The 'and goats' part leads me to conceptualizing the instruction more like: Bit Scrambler / Chutes - shuffle bits around in a way that divides a stream. This might also be useful in pre-filters for compression (entropy reduction) if you knew the content of the message. E.G. for ASCII text the upper 2-3 bits of each letter could be ranked to the side for better compression and a reduction of message size. As others have pointed out, modern CPUs ended up with 'half' that instruction, so I wonder if there were any other reasons for the full instruction.

jhallenworld 5y ago

Compress and expand (from Hackers Delight) are like this, but only the selected bits are kept. These are quite useful instructions. One use is the hash function for perfect hash tables. The hash table includes a mask which picks the bits of the keys which actually change (between all keys) and compresses them all to the right as the hash index. Disclaimer: I contributed the "expand" algorithm shown in Hacker's Delight.