51–60 of 98 posts
Earlier quoted context omitted.
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.
Yes, but those chickens now are as powerful as Cray's oxen were then.
Earlier quoted context omitted.
Yes, but those chickens now are as powerful as Cray's oxen were then.
so, do you want 2 modern oxen or 1024 modern chickens?
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 ma…
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 rememb…
Obviously using a dedicated instruction is fastest in normal cases. But if you need to implement popcount or many other bit manipulation algorithms in software, a good book to look at is "Hacker's Delight" by Henry S. Warren, Jr, 2003. "Hacker's Delight' page 65+ discuss "Counting 1-bits" (population counts). There are a lot of software algorithms to do this. One approach is to set each 2-bit field to the count of 2…
Faster Population Counts Using AVX2 Instructions, Computer Journal, Volume 61, Issue 1, 2018 https://arxiv.org/abs/1611.07612
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 ma…
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...
It is possible that the "population count" instruction has been included in the instruction sets of most American supercomputers at the request of NSA, which was an important customer for them. Nevertheless, the first computer having this instruction was a British computer, the Ferranti Mark I (February 1951). The name used by Ferranti Mark I for this instruction was "sideways add". Also notable was that Ferranti Mar…
Moreover, Ferranti Mark I included a hardware random number generator, another feature useful for cryptography, which was reintroduced only recently in modern CPUs.
[1] https://web.archive.org/web/20180611180213/https://plus.goog...
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 ma…
Did representatives of the “NSA” have a New Zealand accent?
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 ma…
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 rememb…
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 I wonder if those succinct data structures are in any way related to what NSA is doing. I think not, but who knows.
Earlier quoted context omitted.
Moreover, Ferranti Mark I included a hardware random number generator, another feature useful for cryptography, which was reintroduced only recently in modern CPUs.
Hardware random number generators do have some security issues though. Linux devs were opposed to solely relying on them, because they can be compromised by the vendor [1]. So they are at best used in algorithms that they can not compromise (still in [1], but lower, in the comments). [1] https://web.archive.org/web/20180611180213/https://plus.goog...
Discrete hardware RNG's, like that of the Ferranti Mark I, are perfectly secure.
For a modern device, the best way to implement a hardware RNG is to just include an ADC (analog-digital converter) input. Then you may connect externally on the PCB some noisy analog amplifier, e.g. one which has a noisy resistor or diode at its input. Digitizing the noise with the ADC will provide the random numbers and the ADC input can be isolated and tested separately at any time, so the user can verify that there is no hidden functionality.
Most microcontrollers have ADC inputs, so it is easy to add a secure hardware RNG for them. The same could be done for a personal computer by making a noisy amplifier that can be plugged in the microphone input, or by making a USB device with a microcontroller.