CPU-based algorithm trains deep neural nets up to 15 times faster than top GPU
techxplore.com
techxplore.com
Code: https://github.com/keroro824/HashingDeepLearning
Edit: Here is the new paper referred to https://arxiv.org/abs/2103.10891
Here is the new code: https://github.com/RUSH-LAB/SLIDE
The paper I linked above was the first paper of which this is supposed to be an improvement.
As a result, saying it's a toy implementation is making people think you mean the speedup is a result of simply handling a simple portion of the problem, rather than thinking you mean even a naive implementation is quite fast.
This one hundred percent, the original has very few optimizations over a completely naive implementation. It uses MPI and huge pages, that's essentially it.
I hope that this research group can make more headway into training on CPUs, but I also would like to (naively) see less hyperbolic titles. This paper is not just particularly relevant to wide networks - it's only relevant to wide networks.
Does that mean it can / will?
https://research.fb.com/publications/applied-machine-learnin...
Table 1 shows News Feed service uses fully connected networks model, and table 3 shows this workload dominates all other workloads.
Their approach should also be readily adaptable to RNNs, including LTSMs.
Certainly worth investigating as an alternative for efficiently running and training giant networks on less expensive hardware.
1) any input vector can be represented by a "similar" another vector, e.g. [.4, -.3, .1] => [+1, -1, 0]
INIT:
2) generate a set of random input vectors using only {+1, 0, -1} numbers
3) for every neuron: compute a set of activations for every random input vector
4) combine those sets producing a large hash table where keys are random vectors and values are indices of active neurons
FEED-FORWARD:
5) for every input vector, find its nearest neighbor, e.g.: [.4, -.3, .1] => [+1, -1, 0]
6) use this vector as hash key to get indices of neurons
7) compute activations for only these neurons using only their weights and the input vector
8) repeat for all layers
etc.
This way, you avoid lots of computations, but the key is to have a good hash function and a lot of memory.
"The whole industry is fixated on one kind of improvement—faster matrix multiplications," Shrivastava said. "Everyone is looking at specialized hardware and architectures to push matrix multiplication. People are now even talking about having specialized hardware-software stacks for specific kinds of deep learning. Instead of taking an expensive algorithm and throwing the whole world of system optimization at it, I'm saying, 'Let's revisit the algorithm.'"
Shrivastava's lab did that in 2019,
recasting DNN training as a search problem that could be solved with hash tables.
Their "sub-linear deep learning engine" (SLIDE) is specifically designed to run on commodity CPUs, and Shrivastava and collaborators from Intel showed it could outperform GPU-based training when they unveiled it at MLSys 2020."
PDS: Quote: "All programming is an exercise in caching." - Terje Mathisen
From the previous paper:
We choose the standard fully connected neural
network with one hidden layer of size 128.It's like saying we have a super fast fibonacci algorithm, but we can only show it for n=1.
Yes. They describe a general algorithm, but show results for shallow nets. So it's unclear if this works well in general.
EDIT: orginial work afaik https://arxiv.org/abs/1903.03129
So yes and no - if you are correct and that paper is indeed the first claim (not up on the literature), this one is also the same first claim, or at least, an extension to it
So I don't see the clickbaitiness here, it's the central claim of the paper.
It's a fundamentally different programming style, which makes comparisons extremely difficult.
Furthermore: you hide latency on the GPU by running more and more parallel instances. Yeah, there is a 5 to 10 microsecond delay in all CPU to GPU comms and back, but just double, triple, or 100x fold the parallelism and batch up more tasks (aka Gustafson's law).
Don't run one SLIDE. Run 100x of them in parallel to hide the latency. AMD Vega 64 has 16384 hardware threads (one instruction every 4 clock ticks across 4096 hardware SIMD cores) with up to 10 occupancy. That's 163840 max hardware SIMD threads of conceptual execution. (Occupancy is similar to hyperthreads/SMT).
In practice, you run out of VRAM before running out of threads typically. 1000x instances uses 1000x the RAM.
---------
Anyway, I've seen an entire generation of programmers try to make CPU only algorithms and only fail year after year. The cryptocoin community would generally prefer CPU mining rather than GPU or ASIC mining.
But time and time again, the algorithms adapt and someone is brilliant enough to make the new alleged CPU algorithm work really well on a GPU.
Ex: GPUs have a bit-reverse instruction, but x86 is missing that instruction. I've invented hash algorithms that only work well on GPUs (or really, architectures with single-cycle bit-reverse) and will run poorly on CPUs.
----------
But when I run the idea on a CPU, I don't do bitreverse. I use bswap64 instead. Because x86 has single-cycle bswap. Its technically a different algorithm with a different result, but bswap shuffles the bits around enough that the hash-algorithm is still really fast and really good (passes a lot of randomization tests I've done).
----------
We're looking at instruction-level differences between two grossly different platforms. Anyone who is an expert at both systems will tell you that optimization and tuning for both systems are so grossly different, that its pretty much non-sensical to try to compare them in "black-box" manners. You need to put some level of effort into processor-level tuning if you want the results to stand.
I imagine this could work for more layers easily,and using other than fully connected layers could be done by partitioning data (for each set of inputs).
The next obvious question is, can their hashing function run even faster on a GPU?
They say: >In particular, SLIDE uses recently proposed DTWA hashing which works nicely on sparse data. If we represent the data vector as a list of indices and values. DTWA operation computes a random hash map of every non-zero index in the list. Then the map is partitioned into a fixed number of bins. Finally, the index with the maximum coordinate value in each bin is the hash value.
What is the "coordinate value"? And how does the above map to find instances where data and weights values would result in a value above the activation threshold?
They themselves mention it "works well on sparse data".
If they detect irrelevant data by simple value comparison(wrapped in that hashing function) couldn't GPU algorithm be sped up by skipping those multiplications too? How about instead of running matrix multiplication on entire data and all weights we "preprocess" data and weights finding specific indices where they are both above a certain value and multiply just those. It would be interesting to try that. How expensive would running such comparison, then data copy (or create a map of indices to process), then process only those chosen be in comparison with multiplying everything every time?
I'm guessing that it really depends on what percentage of data is actually relevant.
Another idea to make GPU AI faster is improving scheduling of those matrix multiplication. Multiplication by zero, another small number or a power of 2 should be able to execute faster than multiplication of high values (assuming it is implemented in hardware by addition and bit shifting if multiplying by powers of 2). I don't know if current GPU algorithms make any use of that, or if they simply divide the data by number of cores and run all chunks in parallel for however long the longest chunk takes to complete?
I think GPUs are pretty far from being dead in AI as a result of this.
I don’t think this statement means what he thinks it means. I think “cannot be overstated” is what is desired.
Array Languages Make Neural Networks Fast: https://arxiv.org/abs/1912.05234
I can train a neural network on the GPU in my laptop but it has only 8 cores.
Also, I'm pretty sure the goal of this research was not that you can train a DNN on your laptop, but that there is more democratization in the distribution of training power. Maybe some day a mid sized organization will be able to train a competitive model on a buch of off the shelf (or rented) servers...
I don't see any particular reason why we wouldn't see a similar speedup with the GPU version.
This really isn't true in general. Maybe in select subfields of AI like language model pertaining this is true.
All of that being said, I've heard from a few PS3 devs that the simple PPEs didn't really do a great job with that kind of AI code either, due to their extremely simple core designs including their branch predictors. So it didn't end up being a concern and a lot of AI ended up running on the SPEs just because they could be laying around with nothing better to process.
At the end of the day, game AI wasn't really held back by a particular console's design.
A great case of half of the industry riding into a concrete wall following the trendsetter.
There's a lot yet to learn about neural networks and the state of the art is still biological evolution.
Or room heating
Turning back to nineties, it's easy to see that almost all ventures into specialty hardware ended up with mainstream consumer CPUs catching up, and swallowing the niche in a few years time as computer science, and logic design advanced.
Very few computing tasks came out to be truly brute force demanding as people learned how things really work.
Multi-channel audio, and sound effects on CPUs — once thought to be impossible, are now everywher, even smartphone chips.
Getting there was very tough though. Very few people can write a software DSP, and accoustically correct mixers with real time performance even today.
In fact, there is already real world use for neural networks that only optimized for CPU: an chess engine. More specifically, chess engine that use NNUE (Efficiently Updated Neural Networks) [1] like Stockfish 12 [2]. It run much faster while consuming less watts compared to GPU, can be run on average CPU, and managed to beat GPU based neural networks! [3]
This model (NNUE) already exist far earlier than the model discussed in this thread, yet there is almost no discussion about it on HN nor Reddit's r/MachineLearning
[1] https://www.chessprogramming.org/NNUE
[2] https://www.chessprogramming.org/Stockfish_NNUE
[3] https://www.chess.com/blog/the_real_greco/evolution-of-a-che...
To be fair, they do want to embed it into a consumer friendly application, and the integration for embedding TF or something that can run pytorch models on a GPU without python is non-trivial.
If someone ported it to a GPU, it almost certainly would be faster. See http://www.talkchess.com/forum3/viewtopic.php?f=7&t=76986
There is a PyTorch port available, but no benchmarks unfortunatly. It does seem to be fairly widely used for training though, which is indicative of the speed gains available.
Engines like LC0 that do use the GPU work by searching fewer positions but with a heavier eval function. This makes the latency less relevant because it is a smaller percentage of the GPU time.
This seems like a solvable problem.
So it needs to load the comparatively tiny game state (chess board) into the GPU for each evaluation. The more game states it can evaluate per move, the better it is. It can be in the order of millions.
All except for... 3D rendering, image compositing, video encoding, and video decoding?
I'm really struggling to see what you're trying to argue, because we do have multiple meaningful brute-force tasks that most computers today ship with dedicated silicon for.
Yes we can do more real-time audio processing I guess, but that's mainly because CPU speeds increased, not because "people learned how things really worked", or am I missing something?
And 80s (consider Britton-Lee).
And the opposite too: "mainframes are too complicated; we'll write an OS that does all IO in the kernel (e.g. Unix) and run it on minis that don't have channel controllers". Come the 2000s and every disk drive and even keyboard has a processor it it.
And edge-vs-core computing in the network...
The best part is hardly anyone reads the literature much less history, so if you've lived through a couple of cycles you can see the pendulum starting to swing back and, to mix metaphors, "skate to where the puck will be"
So the real race is between how good you can be at batching vs. parallel dispatch when reading disk from I/O. As parallel dispatch is a more general problem it tends to get more attention.
At my first job we used some special SAS product to handle data larger than memory without getting much parallelism, then it was Hadoop, then Spark. Now I can write Julia code that is agnostic over the CPU or GPU and vastly outperforms for the same types of jobs, and where I can run the same code on my laptop or a cluster. It's a huge advance for my domain! I agree it probably doesn't apply to most engineers though.
Some of this overhead is language specific, and some is due to shitty code. Never the less I'd bet if I didn't need to shuttle memory to GPU or could do multiple things at a time I'd crush my perf number. ( noting of course that the 40% gpu util is roughly 10x better than a CPU )
Which all means there's a bunch of CPU bound stuff between your job and the GPU/Cuda kernels. How fast your app can deal with the above will influence overall GPU utilization.
We go to all this effort to build and write stuff in this optimising, fancy framework only for the whole process to be bottlenecked by some silly performance limitation in Python.
Wut? Modern GPUs(ahem, Nvidia) can pipeline very effectively. You can copy to and from the GPU while the GPU is busy working on something already loaded into memory. True, host copies suck, but you can hide them behind compute delays in many workloads.
With GPUDirect, you can even skip the CPU and DMA straight between the GPU and I/O(storage or network controller).
AMD has been shipping unified architectures since August 2011. Nobody cares.
The problem is that while a small low power CPU and a small low power GPU living on the same die and sharing the same memory controller will happily share memory, a big honkin' CPU and a big honkin' GPU don't like to share a memory controller. Some of the big advancements in absolute performance in recent years stems from making the memory controller closer and closer to the relevant processor. In recent AMD systems, the pins on the CPU are directly wired to the pins on the RAM DIMMs. Relatively old mother boards shipped when DDRx memory was the standard, and were still compatible with DDR(x+1) CPUs and RAM when those became the new standard; the motherboard has no RAM logic. If you wanted a unified architecture, you're either going to make the CPU talk to RAM through the GPU, or the GPU talk to RAM through the CPU, or go back to the early 2000s and put a north bridge on the motherboard.
In addition to all that, the bottlenecks are different. The bottleneck on a GPU is always, 100% of the time, memory bandwidth. Latency is mostly irrelevant. The bottleneck on a CPU is usually (95%? 99%?) the memory latency. There's no such thing as RAM that will perform well for both a CPU and a GPU.
At least, it's computationally better. But it won't allow scaling the processing power and memory size independently, so it might require a different commercial model.
* GPUs invest more chip real-estate in integer and floating point crunching (ALU, FP).
* CPUs invest more chip real-estate in control logic, prediction and speculation.
Not that these are the only hardware differences of course, like how caching works, and larger vs higher-bandwidth memory etc.
Maybe future CPU and GPU and TPU will merge as a new kind of compute unit.
We only got here because Microsoft was afraid of one vendor, Creative, monopolizing positional audio market. This led to killing off audio hardware acceleration in Vista and leveling the playing field.
This really makes sense in a way. I once read in a paper that the best thing to have when faced with the task of performing an arbitrary calculation with maximal speed is 1) one core that's a fast as possible (for stuff that must be calculated sequentially) and 2) as many as possible slower cores (for stuff that can be calculated in parallel).
I do think that GPUs are here to stay for a long time though.
Once I bought a separate i387 chip for floating point. Later it was inside the main CPU.
It is however curious how CPU and GPU become more similar over time, with CPUs getting ever wider SIMD instructions and GPUs becoming better over time with branching code, integer performance, etc.
You don’t need to do that for them to share a single memory address space. Putting them together would be useful if sharing caches between them made sense, but it doesn’t.
Similarly, an integrated GPU has a meaningful price advantage at low enough price tiers.
But GPU price and power budgets have been pretty steady for a long time, so I wouldn't expect a major shift any time soon.
In my game, I have a complex procedural generation process that occurs while loading a game. It's not a graphics process, so I originally did it on the CPU. It originally took about three seconds to build the data in parallel across seven background CPU threads on my quad-core processor. But testers who were using low-end dual-core i5s only had one background thread to do that same calculation, and typically reported that the procgen took multiple minutes to complete.
After spending a week refactoring the algorithm to do the same calculation on the GPU instead of the CPU (basically by pretending it was a rendering calculation and writing results out into a "texture" that we could read the results from), calculation times dropped from seconds or even minutes to just fractions of a millisecond, even on low-spec machines.
The calculation that I previously had to hide behind a loading screen was now quick enough that I could freely do it at runtime without even causing a blip to the frame rate. If you've got a problem that they can handle, GPUs are kind of astonishingly fast; even the (by modern standards) low-end ones.
If you look at what most graphic pipelines for 1 pixel the amount of calculations for that 1 pixel is not very much maybe a few dozen instructions. But at 1080 that is a lot more (about 2million times more). GPUs are exceedingly good at doing semi small programs over and over across 2000+ compute units. At best in a CPU you may get 64 if you have a super nice top of the line CPU (reality is 2 or 4). The graphs where that change over happens is going to vary considerably across workloads and instructions used. In most cases currently it heavily favors the GPU. Throw in branching or something like that and CPU might become more favorable. But you still have to try it out.
In the case of this article. They are using hashing/caching which, yeah, should produce a fairly nice speedup. Basically the old speedup trick of do the work once and keep the result. But that probably might not translate very nicely GPU. Oh you could get it to run but it may not be as performant. In the game world it would be like what we used to do with sin/cos and just have a lookup table instead of calling the instruction. We just precalled it and had a copy laying around in an array for the most common cases. So it was just a memory lookup and very little compute and keeping the cached result. BUT that does come at a cost if you have to branch on miss.
Now if you could combine the two ideas. Maybe with some sort of mask to the GPU to say 'do not do any work here as it is done already and work on something else' and pre fill stuff in this could be an even more interesting idea.
In their marketing terminology, the jesters at NVidia are calling SIMD lanes "cores".
For F32 operations, 50 AVX512 cores have 60*(512/32)=800 SIMD lanes. And of course there are about 64 cores per x86 server CPU now at the high end.
(SIMT for NVidia seems to be just a programming model that compiles to SIMD instructions[2], a bit like what you get with ispc on CPUs)
[1] https://images.nvidia.com/content/volta-architecture/pdf/vol... pages 17 and 10
[2] https://www.realworldtech.com/forum/?threadid=195094&curpost...
Given the increasing sizes of framebuffers and textures it makes sense to localize that, although many CPUs now include a GPU equivalent on the same die and many of the same sort of instructions.
A lot of it comes down to how big and independent the working sets are as opposed to strict advantage in computation as well.
[1] https://wccftech.com/why-apple-m1-single-core-comparisons-ar...
They argue that we should be benchmarking saturated single-core performance, but then show in their chosen benchmarks that the M1 is very competitive, benchmarking just below an i9 9880and above a Ryzen 7 4750.
That's a super-fast chip! No excuses like "oh it's Apple's first CPU" are needed - it's right up there.
And in real world usage it's kind of a useless thing to benchmark. See their note on how they had to wrestle with our Cinebench R23 program to get it to accept the load (threads locked to 2, affinity needed to be set after initiating the run but before the benchmark actually started and needed to be reapplied after the first pass) and a cleaner execution would almost certainly be welcome. It would also allow us to test cores working at their full potential.
It kind of shows how these micro-benchmarks aren't very reflective of real-world use.
RISC = Reduced Instruction Set Computer. Reduced instructions result in (supposedly) reduced complexity per instruction (which has failed over time). While each instruction is "simpler" it takes more instructions to accomplish a task. It would stand to reason that it would take more clock cycles to accomplish the same goal on ARM than x86. [1]
ARM processors regularly outperform x86 in terms of instructions per cycle. They have to in order to do the same amount of work. That is literally the whole idea of RISC. Simpler instructions executed quickly. [2]
But this is not why they are fundamentally not as capable. The reason for that is the pipeline. Or relative lack of pipe-lining. [3]
But again, you are comparing a Civic to a Lambo. You have a 3.5w CPU which, per watt, you have the more efficient processor. But that's not good enough. ARM folks love to stand on the efficiency soapbox and preach about performance. You want to have the flexibility of out-of-order execution but don't want to admit the shortcomings that come with it. You have the best performance per watt but you want best overall performance. Which, if you skew every metric in favor of sliced up processors and non-real world benchmarks then sure... Your phone is almost as fast as an entry level laptop when running native code on a single core. If x86 appears slower than ARM it's only because ARM fans have thrown everything but the kitchen sink into their test bench and found the absolute most favorable conditions possible. Anything but admit that their $1200 cell (which was never designed to be faster than your laptop) is "faster per watt per core per thread" than a $150 x86 processor.
[1] https://www.androidauthority.com/arm-vs-x86-key-differences-...
[2] https://www.extremetech.com/computing/318020-flaw-current-me...
[3] http://www.csbio.unc.edu/mcmillan/Comp411F17/Lecture26.pdf
What other optimizations would you like to see? I would expect the tensorflow team to already pay pretty close attention to performance in cpu and gpu implementations, not to mention CUDNN and such...