Skip to content
xc

Data-parallel extraction

xcc finds the loops in a program that can run in parallel and makes each one a par block, with no annotations in the source. This is automatic parallelisation in three phases: acquisition, validation, and run-time device-under-test (DUT) measurement. It is on by default (--par-style=auto).

1. Acquisition compile time xc: the parser scans each loop C: the IR outliner walks clang's loops, outermost first every candidate becomes a par block beside the plain loop 2. Validation compile time, and before each run loop shape, reductions, calls GCD dependence test per array GPU-safety scan of the body unproven pairs: run-time guards failure: the plain loop runs 3. Runtime DUT measurement the first runs on each machine static cost: compute- or bandwidth-bound every device under test runs the real block, timed the winner is learned per size Later runs read the learned record and go straight to the winning device; a new size, machine or compiler version measures again.

1. Acquisition

Section titled “1. Acquisition”

Acquisition finds the candidate loops.

In xc, the parser looks at each for loop before it parses it. A candidate is an ascending counted loop, for (T i in a..b) or the C form for (T i = a; i < b; i++), whose body may:

  • assign its own locals freely;
  • write the outer program’s state only as a reduction: acc += e, acc *= e, &=, |=, ^=, acc++, or a minimum or maximum written as if (e < acc) acc = e;;
  • not return, goto or break out of the loop, use varargs, or take an outer name’s address.

A perfect two- or three-deep nest whose inner bounds do not depend on the outer index becomes one block over the whole grid. The loop is parsed twice, once as written and once as a block, and the program carries both: the block runs where it was proved safe, the plain loop everywhere else.

In C, xcc works on the IR it reads from clang. An IR outliner walks the natural loops, outermost first, and outlines each candidate into a function with a captured-variable record and reduction state. A loop that is declined has its inner loops judged on their own, so an outer loop that cannot run in parallel still gets its inner loops lifted.

Small loops stay as they are: a constant trip count below a threshold, with no inner work, costs more to launch than to run.

2. Validation

Section titled “2. Validation”

Validation proves each candidate safe, at compile time where it can and before each run where it must.

  • Loop shape. One entry, a top test against a loop-invariant bound, a positive constant step, and no other exit.
  • Reductions. Every value carried from one iteration to the next must be a reduction with an associative operator: integer +, *, &, |, ^, minimum and maximum, including if-converted conditional updates and chains like t = t + x1 + x2. A float sum is reassociated only when :goal(speed) is asked for explicitly, so by default a sum gives the plain loop’s result.
  • Dependence analysis. Each array index is reduced to an affine form k·i + c, or a symbolic one over captured integers, and every read is tested against every write to the same array with the GCD test. Pairs the compiler cannot settle become run-time guards, written into the block and checked before each run. A failed guard, or two arrays found to overlap at run time, runs the block serially.
  • GPU safety. The body and everything it calls is scanned for what a GPU cannot run: reference-counted objects, virtual and indirect calls, heap allocation, recursion, inline assembly, varargs, writes to global scalars, and calls outside the program other than math intrinsics.
  • Calls. Calls to the program’s own functions are followed; indirect calls and calls into libraries without a body are refused.

A lifted loop that fails any check is demoted, not rejected: the plain loop runs, and -Wpar-auto says what was lifted, what was demoted, and why. A block written with par by hand gets the same checks as errors and warnings.

3. Run-time device-under-test measurement

Section titled “3. Run-time device-under-test measurement”

The third phase happens on the user’s machine, the first times the block runs.

A static cost model comes first. The compiler writes each block’s instruction count, whether it loops inside, and each array’s footprint per item into the block. The runtime classifies the block as compute-bound or bandwidth-bound: a bandwidth-bound block is kept off a GPU across a bus without being timed, since the copies would cost more than the work.

Then each device under test runs the real block, and is timed:

  • the GPU;
  • remote GPUs, where an xcd daemon serves them;
  • every GPU together, tiled;
  • every CPU core;
  • one CPU thread;
  • every device together, GPUs and CPU cores.

The GPUs go first, while the card is still at speed, and each device’s first run, which builds its kernel, is a warm-up that is not counted. Every one of these runs is a real run of the program’s own work: nothing is repeated just to time it. Where CUDA and Vulkan reach the same card, CUDA is tried first. A device that cannot run a block, such as a GPU without 64-bit integers, leaves the comparison and the others finish.

The winner is learned per machine, per block and per problem size, as size bounds in the program’s own settings store. The key carries a hash of the hardware (the GPUs, the CPU and its thread count, the set of tile workers), a hash of the block’s code, and the compiler version, so a new machine, a changed block or a new compiler measures again, and old records are purged. Later runs read the record and go straight to the winning device; a size well outside what was measured is measured again.

The user’s settings and XC_PAR override all of this, and XC_PAR_REPORT=1 prints each decision.