13 ms·
WebAssembly techniques to speed up matrix multiplication
- toolslite 5y ago[dead]
- VHRanger 5y agoThis'll end up inevitably as a WASM BLAS library Which wouldn't be a bad thing
- injidup 5y agohttps://www.google.com/search?q=wasm%20blas&ie=utf-8&oe=utf-8&client=firefox-b-m https://www.google.com/search?q=wasm%20blas&ie=utf-8&oe=utf-...
- LeanderK 5y agoWhat can't we just compile BLAS to WASM? Isn't this the point of WASM?
- brandmeyer 5y agoThe BLAS have historically relied on a wide range of microarchitecture-specific optimizations to get the most out of each processor generation. An ideal solution would be for the browser to provide that to the application in such a way that it is difficult to fingerprint. See also the history of Atlas, GotoBLAS, Intel MKL, etc.
- bee_rider 5y agolibflame/BLIS might be a good starting point, they've created a framework where you bring your compute kernels, and they make them into a BLAS (plus some other nice functionality). I believe most of the framework itself is in C, so I guess that could somehow be made to spit out wasm (I know nothing about wasm). Then, getting the browser to be aware of the actual real assembly kernels might be a pain.
- phkahler 5y agoAnother technique is to transpose the left matrix so each dot product is scanned in row-order and hence more cache friendly. Another one I tried ages ago is to use a single loop counter and "de-interleave" the bits to get what would normally be 3 distinct loop variables. For this you need to modify the entry in the result matrix rather than having it write-only. It has the effect of accessing like a z-order curve but in 3 dimensions. It's a bit of overhead, but you can also unroll say 8 iterations (2x2x2) which helps make up for it. This ends up making good use of both caches and even virtual memory if things don't fit in RAM. OTOH it tends to prefer sizes that are a power of 2.
- dralley 5y agoThe compiler will sometimes do this transpose for you, but as with all compiler optimizations it might sometimes break.
- melissalobos 5y agoThat sounds very interesting, is the anywhere I can read more about this optimization? I didn't know any compiler could do optimizations like that.
- kanaffa12345 5y agothere is no way a general purpose compiler will figure this out. op is probably talking about something like halide or tvm or torchscript jit.
- deleted 5y ago[deleted]
- astrange 5y agohttps://polly.llvm.org https://polly.llvm.org is a research project that could possibly maybe do this.
- 5y ago
- wheelerof4te 5y agoI admire people who can read and understand this.
- Kilenaitor 5y agoWhich parts are you unable to read and understand? I'm sure some of us here could help explain if you have specific questions or hangups.
- wheelerof4te 5y agoThe math stuff :) JavaScript code is readable, at least.
- Kilenaitor 5y agoIs "the math stuff" all the optimizations being performed e.g. vectorizing multiplication? Not trying to sound dismissive here but the core math the post is working with is actually a pretty straightforward matrix multiplication. The bulk of the discussion focuses on optimizing the execution of that straightforward multiplication algorithm [triple-nested for loop; O(n^3)] rather than making algorithmic/mathematic optimizations. And again, specific questions are easier to answer. :)
- djur 5y agoMatrix multiplication isn't exactly intuitive if you've never worked with it before.
- bruce343434 5y agoI don't understand the naming and notation of this article because the author is assuming context that I don't have. Section baseline: What are N, M, K? 3 matrices or? Laid out as a flat array, or what? `c[m * N + n] += a[m * K + k] * b[k * N + n];`, ah, apparently a b and c are the matrices? How does this work? Section body: What is the mathy "C′=αC+A⋅B"? derivative of a constant is the angle times the constant plus the dot product of A and B???
- marginalia_nu 5y agoIt's kind of bizarre how it's an accomplishment to get your code closer to what the hardware is capable of. In a sane world, that should be the default environment you're working in. Anything else is wasteful.
- Kilenaitor 5y agoThere's always been a tradeoff in writing code between developer experience and taking full advantage of what the hardware is capable of. That "waste" in execution efficiency is often worth it for the sake of representing helpful abstractions and generally helping developer productivity. The real win here is when we can have both because of smart toolchains that can transform those high-level constructs and representations into the most efficient implementation for the hardware. Posts like this demonstrate what's possible with the right optimizations so tools like compilers and assemblers are able to take advantage of these when given the high-level code. That way we can achieve what you're hoping for: the default being optimal implementations.
- AnIdiotOnTheNet 5y ago> That "waste" in execution efficiency is often worth it for the sake of representing helpful abstractions and generally helping developer productivity. That's arguable at best. I for one am sick of 'developer productivity' being the excuse for why my goddamned supercomputer crawls when performing tasks that were trivial even on hardware 15 years older. > The real win here is when we can have both because of smart toolchains that can transform those high-level constructs and representations into the most efficient implementation for the hardware. That's been the promise for a long time and it still hasn't been realized. If anything things seem to be getting less and less optimal.
- nicoburns 5y ago> I for one am sick of 'developer productivity' being the excuse for why my goddamned supercomputer crawls when performing tasks that were trivial even on hardware 15 years older. The problem here is developer salaries. So long as developers are as expensive as they are the incentive will be to optimise for developer productivity over runtime efficiency.
- zwieback 5y agoVery cool! My question: will this kind of thing become more mainstream? I've seen the web emerge, go from static pages to entire apps being delivered and executed in the browser. The last bastion of native apps and libraries seems to be highly optimized algorithms but maybe those will also migrate to a deliver-from-the-web and execute in some kind of browser sandbox. Java promised to deliver some version of native code execution but the Java app/applet idea never seemed to take off. In some ways it seems superior to what we have now but maybe the security concerns we had during that era held Java back too much. Or am I misunderstanding what WebAssembly can bring to the game?
- halpert 5y agoThe web always feels terrible compared to a native app, especially on a phone. Some of the difference is due to Safari being a bad browser (probably intentional), but a bigger part is that the threading model makes it really difficult to have a responsive UI. Not to mention the browser’s gestures often clash with the application’s gestures.
- jsheard 5y agoWASM threads are available in all modern browsers now, including Safari. It's very early days in terms of ecosystem but we're steadily getting there.
- danielvaughn 5y agoAlso aren't service workers technically multi-threading? That's been a thing for a while in the browser now.
- jsheard 5y agoTechnically yeah, but the threads could only communicate through message passing which isn't ideal for performance. The more recent major improvement is for workers to be able to share a single memory space similar to how threading works in native applications.
- riddleronroof 5y agoThis is very cool
- bertman 5y agoVery cool writeup! Unfortunately, the bar graphs at the bottom of the article have different y-axis scaling, but even so: It's sad how Firefox' performance pales in comparison to Chrome.
- deleted 5y ago[deleted]
- LeanderK 5y agoI was hopeful WebAssembly will speed up the web. What's missing? Native Browser APIs? Native IO Apis? Let's say I want to interactively plot some complicated function without slowing down the rest. Can I do this in WebAssembly now?
- onion2k 5y agoLet's say I want to interactively plot some complicated function without slowing down the rest If you can draw your plot in a shader then you can do it in WebGL very easily. You'd only need to update the input uniforms and everything else would happen on the GPU.
- sharikous 5y ago> Let's say I want to interactively plot some complicated function without slowing down the rest. Can I do this in WebAssembly now? Yep, with a Web Worker for the secondary thread. However the environment is still young and its' difficult to use heavy computation libraries. Besides for some reason SIMD instructions are present only for 128 bit units (2 doubles or 4 floats). Another problem is no matter what to do it is a layer over the hardware, so it will be slower than specialized machine code (if what you do is not in the JS API)
- LeanderK 5y ago> difficult to use heavy computation libraries what do you mean? What's the blocker? Something like numpy for js would fill this role, calling wasm in the background. Just the missing SIMD-instructions? Some quick googling shows that one can't compile BLAS for wasm yet. This might be due to wasm64 not being available yet, i think? So would this help to tap into the existing ecosystem of optimised mathematical routines? Ideally...I would leave js and just use python ;) It has the whole ecosystem at hands with numpy, scipy, statsmodels etc. But nobody is doing it and idk why. I think it might be due to fortran not compiling to wasm.
- sharikous 5y agoYes I forgot about wasm64 not being available still. Yes, that's a big block. About numpy for js I believe js is still not comfortable enough for this kind of use, especially with the lack of operator overloading. Anyway there are some builds of BLAS (or equivalents) to wasm and even of python. Check out pyodide and brython
- ausbah 5y agoshouldn't compilers handle stuff like this?
- brrrrrm 5y agoIn an ideal world, absolutely! It's a hard problem and there are many attempts to make that happen automatically including polyhedral optimization (Polly[1]) and tensor compiler libraries (XLA[2] and TVM[3]). I work on a project called LoopTool[4] which is researching ways to dramatically reduce the representations of the other projects to simplify optimization scope. [1] https://polly.llvm.org https://polly.llvm.org [2] https://www.tensorflow.org/xla https://www.tensorflow.org/xla [3] https://tvm.apache.org https://tvm.apache.org [4] https://github.com/facebookresearch/loop_tool https://github.com/facebookresearch/loop_tool
- visarga 5y agoIf they worked so well AMD would not be in such a bad position with their GPUs in ML. They would just need to compile to their arch.
- wdroz 5y agoSince wasm supports threads, I wonder if you can speed up these operations further more by using multiple threads.
- brrrrrm 5y agoThat's a good point: you certainly could. There's some fun exploration to be done with atomic operations. The issue is that threaded execution requires cross-origin isolation, which isn't trivial to integrate. (Example server that will serve the required headers: https://github.com/bwasti/wasmblr/blob/main/thread_example/server.py https://github.com/bwasti/wasmblr/blob/main/thread_example/s...)
- magoghm 5y agoI tested it on my M1 Mac and it reached 46.78 Gigaflops, which is quite amazing for a CPU running at 3.2 GHz. Isn't that like an average of 14.6 floating point operations per clock cycle?
- microtonal 5y agoI hate to post this multiple times, but the M1 has a dedicated matrix co-processor, it can do matrix multiplication at >1300GFLOP/s if you use the native Accelerate framework (which uses the standard BLAS API). The M1 Pro/Max can even do double that (>2600 GFLOP/s) [1]. 46.78 GFLOP/s is not even that great on non-specialized hardware. E.g., a Ryzen 5900X, can do ~150 GFLOP/s single-threaded with MKL. [1] https://github.com/danieldk/gemm-benchmark#1-to-16-threads https://github.com/danieldk/gemm-benchmark#1-to-16-threads
- lostmsu 5y agoIf you look at the comment above about the regular GEMM implementation, M1 actually can do that at 1.6 Teraflops.
- owlbite 5y agoHow does this compare to the native BLAS in the Accelerate library?
- conradludgate 5y agoAccelerate on the M1 is ridiculously fast (thanks to its special core set and specific instructions). Some benchmarks I've done has it beating out CUDA on my RTX 2070. I have to got a proper gflops number though
- microtonal 5y agoIt's going to absolutely blow this away. Here are some of my single precision GEMM benchmarks for the M1 and M1 Pro: https://github.com/danieldk/gemm-benchmark#1-to-16-threads https://github.com/danieldk/gemm-benchmark#1-to-16-threads tl;dr, the M1 can do ~1300 GFLOP/s and the M1 Pro up to ~2700GFLOP/s. On the vanilla M1, that's 28 times faster than the best result in the post. The difference (besides years of optimizing linear algebra libraries) is that Accelerate uses the AMX matrix multiplication co-processors through Apple's proprietary instructions.
- deleted 5y ago[deleted]
- deleted 5y ago[deleted]
- bruce343434 5y agoI don't understand the naming and notation of this article because the author is assuming context that I don't have. Section baseline: What are N, M, K? 3 matrices or? Laid out as a flat array, or what? `c[m * N + n] += a[m * K + k] * b[k * N + n];`, ah, apparently a b and c are the matrices? How does this work? Section body: What is the mathy "C′=αC+A⋅B"? derivative of a constant is the angle times the constant plus the dot product of A and B??? Please, if you write a public blog post, use your head. Not everybody will understand your terse notes.
- engmgrmgr 5y agoNot to be too snarky, but perhaps the onus is on you to do some homework if you want to understand a niche article for which you lack context? Laying out matrices like that is pretty standard, especially for a post about vectorization.
- bruce343434 5y agoyou're probably right, but at least a small prelude explaining the single character variable names would not be out of place.
- ginko 5y agoIsn't the idea of webassembly to compile native C/C++/Rust/Whatever code to be able to run in the browser? Why not just compile OpenBLAS or another computer numerics library like that to WA?
- remus 5y agoI'm by no means an expert but my understanding is that a lot of the performance from libraries like openBLAS comes from targeting specific architectures (e.g. particular instruction sets on a series of processors). You can probably milk some more performance by targeting the web assembly architecture specifically (assuming openBLAS hasn't started doing similar themselves).
- brrrrrm 5y agothat's exactly how TF.js does it: https://github.com/google/XNNPACK/blob/master/src/f32-gemm/MRx2c4-wasmsimd.c.in https://github.com/google/XNNPACK/blob/master/src/f32-gemm/M...
- bee_rider 5y agoPeople are asking about BLAS already in various threads, but if they know the size of their matrices beforehand, it might be interesting to try EIGEN. EIGEN also has the benefit that it is an all-template C++ library so I guess it should be somehow possible to spit out the WASM (I know nothing about WASM). Of course usually BLAS beats EIGEN, but for small, known-sized matrices, it might have a chance.
- MauranKilom 5y agoCan you specify what "small" constitutes for you?
- bee_rider 5y agoSmall enough that MKL doesn't optimize for it. Since GEMM is important, 16x16 or something silly like that I guess.
- pcwalton 5y agoI really like this writeup. Note that it may not be worth using the SIMD in this way (horizontal SIMD) if you know you will be multiplying many matrices that are the same size. It may be better to do vertical SIMD and simply perform the scalar algorithm on 4 or 8 matrices at a time, like GPUs would do for vertex shaders. This does mean that you may have to interleave your matrices in an odd way to optimize memory access, though.
- juloo 5y agoAn other way is WebGL.