How quickly can we use brute force to guess a 64-bit number? The short answer is, it all depends on what resources are available. So we’re going to examine this problem starting with the most naive approach and then expand to other techniques involving parallelization.
We’ll discuss parallelization at the CPU level with SIMD instructions, then via multiple cores, GPUs, and cloud computing. Along the way we’ll touch on a variety of topics about microprocessors and some interesting discoveries, e.g., adding more cores isn’t always an improvement, and not all cloud vCPUs are equivalent.
64 bits ought to be enough for anybody!
2019-12-02 Privacy, Security 8 Comments
Searching large spaces becomes easier if you compress that space with hashing or binary search, etc. His analysis only considered the most naive & trivial algorithm and disregarded high level algorithmic optimizations that a real programmer would employ to improve performance dramatically. Normally one does not do low level optimization without first optimizing the high level algorithm, but he only did the former, so I’m a bit iffy about the way he approached this.
I don’t want to miss his point, I know he disregarded better search algorithms in order to deliberately force it to be a brute force solution, but I kind of wish he had picked a more meaningful/realistic problem, even if he made it up himself. It could have been interesting to see how various types of GPUs/clusters perform then rather than an extremely subpar counting algorithm to begin with. Something that fits the bill could be factoring primes, or searching for patterns in digits of pi. Oh well.
It’s interesting to see in the graph how closely digital ocean’s and google’s virtual cpu units perform, though I don’t know why he omitted the macbook and core i3 from the graph. He should have plotted them even though they did not scale well. Anyways, these nitpicks aside, it does highlight just how much of an advantage GPUs have over CPUs for massively parallel workloads. You’d need hundreds of CPU cores to approach a GPU’s performance, and that would be nowhere close to the GPU’s efficiency. FPGAs could be interesting too.