Loop Perforation

Loop Perforation

The intentional introduction of randomness to code is known as a “stochastic” algorithm. Personally, I'm more familiar with the unintentional introduction of randomness, otherwise known as a “bug,” but now when it happens you can tell your boss that you were adding “stochastic functionality.”

Various research has shown that AI models have some resilience to the introduction of randomness. Paradoxically, “stochastic” algorithms can even be beneficial to accuracy when used during training. Another intentional use of random numbers occurs in AI inference where the top-k decoding algorithm can randomly pick from several candidate output tokens.

Code perforation is an optimization technique that trades accuracy for speed, by randomly (ahem, I mean, stochastically) skipping some computations. Essentially, using loop perforation is similar to an approximation with a random element, but in a generalized way for any iterative code. It's kind of like how teenage children randomly skip their homework.

Loop perforation skips iterations of a loop in a probabilistic manner. Randomly skipping some percentage of the loop bodies doesn't sound like a good plan, but it has its merits. In an AI inference computation, there's so much going on that no-one's going to notice a few missed beats. Apparently it can even be useful. Well, at least it's faster to do nothing.

Example: Loop Perforation: Here is an example of adding loop perforation to a vector dot product computation. This is an incredibly slow version, and is not recommended, but is just to give the idea of skipping a percentage of the iterations:

    float aussie_vecdot_perf(float v1[], float v2[], int n, int pc)   
    {
        // Loop perforation -- vector dot product
        float sum = 0.0;
        for (int i = 0; i < n; i++) {
            if ( ( rand() % 100 ) + 1 <= pc) {
                // This iteration is perforated...
                continue; // Skip it...
            }
            sum += v1[i] * v2[i];
        }
        return sum;
    }

• Next: • Up: Table of Contents • Buy: Generative AI in C++: Coding Transformers and LLMs

The new AI programming book by Aussie AI co-founders: AI coding in C++ Transformer engine speedups LLM models Phone and desktop AI Code examples Research citations Get your copy from Amazon: Generative AI in C++