Compiling models to megakernels(blog.luminal.com)
35 pointsby jafioti3 days ago2 comments
  • measurablefunc2 days ago
    There are only 4 optimizations in computer science: inlining, partial evaluation, dead code elimination, & caching. It looks like AI researchers just discovered inlining & they already knew about caching so eventually they'll get to partial evaluation & dead code elimination.
    • imtringued2 days ago
      Your list is so short it doesn't even include the basics such as reordering operations.

      It also feels incredibly snarky to say "they knew about caching" and that they will get to partial evaluation and dead code elimination, when those seem to be particularly useless (beyond what the CUDA compiler itself does) when it comes to writing GPU kernels or doing machine learning in general.

      You can't do any partial evaluation of a neural network because the activation functions are interrupting the multiplication of tensors. If you remove the activation function, then you end up with two linear layers that are equivalent to one linear layer, defeating the point of the idea. You could have trained a network with a single layer instead and achieved the same accuracy with a corresponding shorter training/inference time.

      Dead code elimination is even more useless since most kernels are special purpose to begin with and you can't remove tensors without altering the architecture. Instead of adding useless tensors only to remove them, you could have simply used a better architecture.

      • torginus2 days ago
        I think you can. If you have a neuron whose input weights are 100,-1,2, with threshold 0, you can know the output of the neuron if the first input is enabled, as the other 2 dont matter, so you can skip evaluating those.

        I'm not enough of an expert to see if there's any actualy merit to this idea, and if you can skip evaluating huge parts of the network and keeping track of such evaluations, is actually worth it, but it intuitively makes sense to me that making an omelette has nothing to do with the Battle of Hastings, so when making a query about the former, the neurons encoding the latter might not affect the output.

        Afaik, there's already research into finding which network weight encode which concepts.

        MOE is a somewhat cruder version of this technique.

    • johndough2 days ago
      Which categories do algorithmic optimizations fall under? For example:

      Strassen algorithm for matrix multiplication https://en.wikipedia.org/wiki/Strassen_algorithm

      FFT convolution https://dsp.stackexchange.com/a/63211

      Winograd convolution https://www.cv-foundation.org/openaccess/content_cvpr_2016/p...

      And of course optimization algorithms themselves.

      • torginus2 days ago
        Don't know about the others, but FFT is the classic case of common subexpression evaluation (its mathematically equivalent), which I think by OPs definition would fall under caching.
      • j-pb2 days ago
        Partial evaluation on the symbolic structure of the problem.
    • fragmede2 days ago
      Dead code elimination is already a technique in AI when someone takes an MoE model and removes an unused "E" from it.
    • mxkopy2 days ago
      AI actually has some optimizations unique to the field. You can in fact optimize a model to make it work; not a lot of other disciplines put as much emphasis on this as AI
      • tossandthrow2 days ago
        Can you list these optimizations?
        • mxkopy2 days ago
          RLHF is one that comes to mind
          • tossandthrow2 days ago
            Well, this is an entirely other category of optimizations - not program performance but model performance.
            • lucrbvi2 days ago
              Yes, in "runtime optimization" the model is just a computation graph so we can use a lot of well known tricks from compilation like dead code elimination and co..
              • tossandthrow2 days ago
                We are getting closer!

                What other optimizations are there that can be used than what explicitly falls into the 4 categories that the top commenter here listed out?

                • mirekrusin2 days ago
                  For inference assorted categories may include vectorization, register allocation, scheduling, lock elision, better algos, changing complexity, better data structures, profile guided specialization, layout/alignment changes, compression, quantization/mixed precision, fused kernels (goes beyond inlining), low rank adapters, sparsity, speculative decoding, parallel/multi token decoding, better sampling, prefill/decode separation, analog computation (why not) etc etc.

                  There is more to it, mentioned 4 categories are not the only ones, they are not even broad categories.

                  If somebody likes broad categories here is good one: "1s and 0s" and you can compute anything you want, there you go – single category for everything. Is it meaningful? Not really.

    • jafioti2 days ago
      That's a bit trite tbh. We all know of these techniques, but actually implementing them on GPUs in a low-overhead manner that maintains the model's fidelity is challenging. It's much more than just breaking out the old CS book and picking the next idea from there.
    • direwolf202 days ago
      Model pruning is dead code elimination
  • geremiiah2 days ago
    So if I'm understanding correctly, you decompose kernels into their per_sm_workload, then you figure out per_sm_data_dependency and then you can schedule sm_workloads from the next kernel to start running as soon as the data dependency is satisfied, not needing to wait for the other sms from the previous kernel to finish.

    In this case are you're strickly fusing pre defined kernels or are you also optimizing them? Is this complimentary to your earlier work on search-based compilers?

    • jafioti2 days ago
      Thats reasonably accurate, we're fusing both pre-defined operations as well as codegenned operations. Block-level operations live inside the search space, as do kernel, warp and thread level operations. Since it's a unified search space, we can look through tons of combinations of kernel, block, warp, and thread level ops. When we go to compile them to runnable code, thread ops get compiled to warp ops, warp ops get compiled to block ops, block ops get compiled to kernel ops (megakernels live here!), so at the end of the day everything that gets ran is a kernel.

      In other words, very complimentary to our search-based approach.