Aussie AI

Loop Strip Mining (Loop Sectioning)

  • Book Excerpt from "Generative AI in C++"
  • by David Spuler, Ph.D.

Loop Strip Mining (Loop Sectioning)

Loop strip mining is a loop optimization that scans or “mines” various “strips” of an array. It is related to “loop tiling” on arrays in two dimensions, but strip mining only applies to processing one-dimensional arrays. Loop strip mining is also called “loop sectioning” because it breaks an array up into sections that are operated on.

For a basic example, consider a simple array initialization:

    for (int i = 0; i < n; i++) {
        arr[i] = 0.0f;
    }

Let's assume we can parallelize this with 16 elements at a time (e.g. 512 bits total parallel processing, which is 16 separate 32-bit float variables). So, we want to process “strips” of length 16. For simplicity, let us assume that n is divisible exactly by 16, so there's no leftover work after the main loop.

    for (int i = 0; i < n; i += 16) {
        // Initialize arr[i]...arr[i+15] in parallel
    }

Obviously, this is a dummy example, where memset would do better for zeroing the array. Also, this really looks exactly like “vectorization” to me, where we are vectorizing 512 bits at a time (16 floats), and indeed the research mentions vectorization as one application. But loop strip mining and vectorization are not exactly the same techniques, because loop strip mining is a more general idea with other applications.

 

Next:

Up: Table of Contents

Buy: Generative AI in C++: Coding Transformers and LLMs

Generative AI in C++ 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++