How PyTorch sums a tensor, and splits the work between threads
pgmesa · · 30 min read
Part of Rebuilding PyTorch (6 of 8)
- Why I rebuilt PyTorch's core from scratch
- What a PyTorch tensor really is
- Interlude: What the CPU does when your code reads memory
- How PyTorch walks a tensor of any shape
- How PyTorch prepares the loop of every operation
- How a PyTorch kernel uses the vector registers of every CPU
- How PyTorch sums a tensor, and splits the work between threads
- How PyTorch computes gradients
- How PyTorch runs the same operations on a GPU
Every operation so far wrote one output element for every input element: a + b reads one number of a and one of b, and writes one number. A reduction is the other kind: x.sum(), x.mean(1) or x.max(0) read many numbers and write one per group. It runs on the same machinery, the same iterator, the same 2-D loop and the same vector registers, but it brings two new problems. The additions depend on each other, so the simplest loop leaves most of the core idle. And every addition rounds, so the order in which the numbers are added changes the result. Once there are threads, that order depends on how the work is split, which leads to a question I did not expect when I started: does x.sum() give the same number with one thread and with eight?
Before you start. This article builds on the three before it: How PyTorch walks a tensor of any shape (the 2-D loop, and how the work is split between threads in its section 9), How PyTorch prepares the loop of every operation (strides of 0, the order of the dimensions and how they are merged) and How a PyTorch kernel uses the vector registers of every CPU (
Vectorized<T>and the two lambdas of a kernel). The hardware it relies on, latency, cache lines and cores, is in the interlude.
This is the path the article follows:
And at the end, the key takeaways.
All the timings are from a Ryzen 7 9700X, a Zen 5 with 8 cores, on one thread unless a table says otherwise. They come from raxisreductions.py, which also builds and runs a small C++ program for section 3. I ran it in November 2026, with NumPy 2.5.4, PyTorch 2.14.1 and Raxis 0.5.0, on Windows 11 25H2 (MSVC 19.44) and Ubuntu 24.04 under WSL2 (GCC 13.3), on the same machine. The tables are from Windows, and the text says where Linux differs.
1. What a reduction is
A reduction combines many numbers into one: a sum, a mean, a maximum, the position of the maximum. On a tensor it can combine all of its elements, or only those along some dimensions. Take a small one:
| Call | Adds together | Result | Shape |
|---|---|---|---|
x.sum() | all six | 21 | [] |
x.sum(0) | each column: 1 + 4, 2 + 5, 3 + 6 | [5, 7, 9] | [3] |
x.sum(1) | each row: 1 + 2 + 3, 4 + 5 + 6 | [6, 15] | [2] |
x.sum(1, keepdim=True) | the same | [[6], [15]] | [2, 1] |
The dimension passed to sum is the one that disappears: sum(0) reduces dimension 0, the rows, and leaves one number per column. With keepdim=True the reduced dimension stays, with size 1, which is useful when the result has to broadcast against x again, as in x - x.mean(1, keepdim=True).
So a reduction has an output with fewer elements than its input, and every output element is the result of many input elements. That is the only thing that changes with respect to a + b, and the next section shows how PyTorch turns it into something its iterator already knows.
2. A TensorIterator whose output does not move
The trick is a stride of 0, the same one that broadcasting uses for inputs, now on the output. sum first allocates its result with the reduced shape. Then it views that result with the input’s number of dimensions, where every reduced dimension comes back with size 1 and stride 0 (pytorchReduceOpsUtils.h, raxisreduce_ops_utils.h):
// From review_reduce_result: put the reduced dims back, with stride 0
for (int64_t dim = 0; dim < ndim; ++dim) {
if (mask.test(dim)) { // a reduced dimension
shape.push_back(1);
strides.push_back(0);
} else {
shape.push_back(result_shape[result_idx]);
strides.push_back(result_strides[result_idx]);
result_idx++;
}
}
For x.sum(0) on our 2 x 3 tensor, the result [5, 7, 9] is viewed as a 1 x 3 tensor with strides [0, 1], which the iterator broadcasts against the 2 x 3 input: moving down a row does not move in the output, so the two rows of a column land on the same output element. The iterator is built as for any other operation, with this view as its output and x as its input (TensorIterator::reduce_op, marked as a reduction). When the loop runs, each step does out += x[i] at an output position that stays still along the reduced dimension. The output is filled with 0 first, the identity of the sum, so that the first addition has something to add to.
There is one change in how the iterator orders the dimensions. In the article on TensorIterator the dimension with the smallest strides went inside, so that the inner loop reads memory in order. For a reduction, the reduced dimensions go inside first, whatever their strides (pytorchTensorIterator.cpp, raxistensor_iterator.cpp):
if (is_reduction_ && operands_[idx].is_output) {
// move reduced dimensions to the front
if ((stride0 == 0) != (stride1 == 0)) {
return stride1 == 0 ? 1 : -1;
}
}
So the inner loop, dimension 0, always runs along a reduced dimension, and the kernel can tell from one number that it is looking at a reduction: the output stride of dimension 0 is 0. These are the strides, in bytes, that the loop receives for a 1000 x 1000 float32 tensor, after the reordering and the merging of dimensions (dimension 0 first, as the iterator stores them):
| Call | Shape | Input strides | Output strides | Inner loop |
|---|---|---|---|---|
x.sum(1) | [1000, 1000] | [4, 4000] | [0, 4] | along a row, in order |
x.sum(0) | [1000, 1000] | [4000, 4] | [0, 4] | down a column, 4000 bytes per step |
x.sum() | [1000000] | [4] | [0] | all of x, in order |
x.sum() merges into one dimension, as a + b did, because both dimensions are reduced and the input is contiguous. x.sum(0) is the interesting one: its inner loop goes down a column, with a stride of 4000 bytes, which is exactly what the iterator avoids for elementwise operations. Section 6 shows how the kernel turns this around. First, the loop itself.
3. The obvious loop, and why it is slow
For x.sum() the loop is one line, the one anyone would write first:
float acc = 0.0f;
for (int64_t i = 0; i < n; i++) {
acc += x[i];
}
Each addition needs the result of the one before it. This is the chain of the interlude again, now made of additions instead of loads: the core cannot start addition i + 1 until addition i has finished. So the loop runs at the latency of one addition, not at the rate at which the core can start them.
The experiment (raxissum_loops.cpp) writes the loop in five ways and times them on 64Ki floats, 256 KiB. After the first run they sit in the L2, so the memory is not the limit. Each loop runs 2000 times in a row, and the table keeps the fastest of 5 such runs. The program is built with AVX2, and with the compiler told to add exactly in the order written (/fp:precise on MSVC, -ffp-contract=off on GCC):
| Sum of 64Ki float32 from the L2 | ns per element | Independent chains |
|---|---|---|
one float accumulator | 0.361 | 1 |
four float accumulators | 0.090 | 4 |
| one AVX2 vector of 8 accumulators | 0.045 | 8 |
| four AVX2 vectors, 32 accumulators | 0.016 | 32 |
one double accumulator | 0.401 | 1 |
The first row is about two cycles per element at this CPU’s clock, which is the latency of a floating-point addition on Zen 5. With four accumulators, acc[i % 4] += x[i], there are four chains that do not depend on each other, and the out-of-order core runs them side by side: four times faster. A vector register of eight floats is eight accumulators in one instruction, and four vectors are 32: 22 times faster than the first loop. At that point the additions are no longer the limit; how fast the L2 delivers the bytes is. With GCC on Linux the numbers are within a few percent of these.
You might wonder why the compiler does not do this by itself, since it vectorizes a + b without help. Because it would change the result. With four accumulators the numbers are added in another order, and for floats the order matters, as the next section shows. A C/C++ compiler may not reorder floating-point additions unless it is told that it may, with -ffast-math on GCC and Clang, or /fp:fast on MSVC. For integers the order does not change the result, and compilers do vectorize integer sums on their own.
So the kernel has to write the accumulators itself. PyTorch’s does: it keeps four vectors of accumulators, 32 for float32 with AVX2, the fourth row of the table. The last row, a double accumulator, is as slow as the first, and the next section explains why someone might still want it.
4. Why it is also wrong
A float32 has 24 bits for the digits of the number (the significand), so it can hold every integer up to , and from there only every second one. Now sum ones, about 33 million, with the first loop. When the accumulator reaches 16,777,216, adding 1 gives 16,777,217, which a float32 cannot hold, and the addition rounds back to 16,777,216. Each of the remaining 16 million additions does the same, and the loop returns 16,777,216, half of the right answer:
| Sum of ones | Result |
|---|---|
one float accumulator | 16,777,216 |
four float accumulators | 33,554,432 |
one vector, four vectors, one double | 33,554,432 |
With four accumulators each one only reaches about 8 million, so every addition is exact. That is the first lesson: more accumulators are not only faster, they also keep each partial sum smaller.
Ones are the extreme case, but every addition rounds. When the accumulator is large and the number added is small, the low bits of the small number fall off the end of the significand. With random numbers from [0, 1), the error grows with the number of elements, because the accumulator keeps growing and the numbers added do not. This is the relative error of each loop against the exact sum:
| Floats from [0, 1), relative error | 1M numbers | 16M numbers |
|---|---|---|
one float accumulator | 1.5e-05 | 9.9e-05 |
four float accumulators | 3.8e-07 | 1.2e-05 |
| one vector of 8 | 3.8e-07 | 4.4e-06 |
| four vectors, 32 | 7.3e-07 | 9.5e-07 |
one double accumulator | 1.9e-08 | 6.5e-09 |
An error of 1e-4 means the fourth significant digit is wrong, in a type that holds about seven. More accumulators help again, because each one stays smaller, but the error still grows with the size: at 1M the order of the middle rows is partly luck, at 16M the pattern is clear. A double accumulator has 53 bits and its error is tiny, but it is a single chain, and a vector register holds half as many doubles as floats. That is the trade-off a sum has to solve: accumulators that stay small, without losing the speed of 32 of them.
5. The cascade sum
The classical answer is pairwise summation: add the numbers in pairs, then add the sums of the pairs in pairs, and so on, like the rounds of a tournament. Every addition then combines two numbers of similar size, so few bits fall off, and the error grows with the logarithm of the number of elements instead of with the number itself. NumPy uses it. Done literally it needs a recursion, or a stack of partial sums, which does not fit well in a vector loop.
PyTorch uses a version of it that runs in one pass with a fixed amount of memory, the cascade sum (multi_row_sum, pytorchSumKernel.cpp, raxissum_kernel.cpp). It keeps four levels of accumulators. Level 0 adds a fixed number of elements, level_step; then it is added into level 1 and set back to zero. Once level 1 has received level_step such sums, it is added into level 2, and so on, the way a carry moves between the digits of a number:
const int64_t level_power = std::max(int64_t(4), ceil_log2(size) / num_levels);
const int64_t level_step = int64_t(1) << level_power; // 16 or more
const int64_t level_mask = level_step - 1;
for (; i + level_step <= size;) {
for (int64_t j = 0; j < level_step; ++j, ++i) { // level 0: level_step elements
for (int64_t k = 0; k < nrows; ++k) {
acc[0][k] += load(in_data + i * row_stride, col_stride, k);
}
}
for (int64_t lev = 1; lev < num_levels; ++lev) { // the carry
for (int64_t k = 0; k < nrows; ++k) {
acc[lev][k] += acc[lev - 1][k];
acc[lev - 1][k] = 0;
}
if ((i & (level_mask << (lev * level_power))) != 0) {
break; // this level is not full yet
}
}
}
The nrows accumulators of each level are independent sums, which gives the parallel chains of section 3. For a contiguous row, the kernel calls this function with nrows = 4 and with Vectorized<float> as the type of each accumulator: 4 vectors of 8, the 32 chains of the fastest loop, with a cascade in each one.
Follow x.sum() of a million floats. Each step of the loop reads 32 floats, one per chain, so there are 31,250 steps, and each chain adds 31,250 numbers. , and rounds down to 3, below the minimum of 4, so level_power is 4 and level_step is 16. In each of the 32 chains:
| Level | Receives | Adds before passing on | Holds, for numbers from [0, 1) |
|---|---|---|---|
| 0 | the elements | 16 | about 8 |
| 1 | sums of 16 elements | 16 | about 128 |
| 2 | sums of 256 elements | 16 | about 2,048 |
| 3 | sums of 4,096 elements | all the rest | about 15,600 at the end |
Every addition at levels 0 to 2 adds numbers of similar size. At the end the four levels of each chain are added together, then the four vectors, then the eight lanes of the last vector, and that is the sum. The carry runs once every 16 elements, so it costs almost nothing: x.sum() of a million floats takes 0.027 ms in Raxis, 0.027 ns per element, close to the four-vector loop of section 3 even though the data now comes from the L3.
And the error, now with the libraries, for 16M floats from [0, 1) in a row, and down the columns of the same numbers seen as a 2M x 8 matrix:
| Relative error | NumPy | PyTorch | Raxis |
|---|---|---|---|
sum() of 16M in a row | 7.1e-09 | 7.1e-09 | 7.1e-09 |
sum(0) of 2M x 8, worst column | 5.1e-05 | 1.2e-07 | 1.2e-07 |
sum() of ones | exact | exact | exact |
In a row, the three are as good as a double accumulator. Down the columns, NumPy is as bad as the single float accumulator, and this is documented: NumPy’s pairwise summation is “only used when summing along the fast axis in memory”, as its documentation of sum says. For sum(0) of a C-contiguous array, NumPy adds the rows one after another into the output, out[j] += x[i, j], so every column is a single chain of 2 million additions. PyTorch’s kernel runs a cascade per column, as the next section shows, and that is the factor of 400 in the second row. The three give the same numbers on Linux.
6. Rows and columns
The kernel receives the 2-D blocks of section 2, with the strides of the input and of the output, and picks one of its paths from them (pytorchSumKernel.cpp, raxissum_kernel.cpp):
- Contiguous inner reduction. The input stride of the reduced dimension is 4 bytes:
sum()andsum(1). Each row is summed with the four vectors and their cascade, as in the last section (vectorized_inner_sum), and the eight lanes are added together at the end of each row. - Contiguous outer reduction. The reduced dimension has a large stride and the other one is contiguous:
sum(0). Here the kernel does not walk down one column at a time. It takes 32 columns at once, four vectors of 8 consecutive floats of the same row, and walks down the rows: each step reads 128 contiguous bytes of one row, and each lane of each vector accumulates one column (vectorized_outer_sum, the samemulti_row_sumwith the columns as itsnrows). That turns the stride of 4000 bytes into reads of whole cache lines, and still gives every column its own cascade. - Neither is contiguous, for example a transposed view: the same two strategies with scalar accumulators.
This is the time of each sum on one thread, for a 1000 x 1000 float32 matrix (4 MB, in the L3 after the first run) and a 4000 x 4000 one (64 MB):
sum, ms, one thread | NumPy | PyTorch | Raxis |
|---|---|---|---|
1000 x 1000, sum() | 0.151 | 0.057 | 0.026 |
1000 x 1000, sum(0) | 0.039 | 0.070 | 0.035 |
1000 x 1000, sum(1) | 0.159 | 0.073 | 0.034 |
4000 x 4000, sum() | 7.60 | 1.05 | 0.78 |
4000 x 4000, sum(0) | 0.92 | 4.29 | 1.63 |
4000 x 4000, sum(1) | 9.82 | 1.21 | 0.89 |
Several things stand out, and each one has a reason:
- NumPy’s
sum()andsum(1)are 3 to 6 times slower than Raxis’s from the L3. Its pairwise sum adds blocks of 128 numbers with eight scalar accumulators, which is precise but runs at 0.1 to 0.15 ns per element on both systems, between the four-floatand the one-vector loops of section 3. At 4000 x 4000 it takes 7.6 ms on Windows and 2.0 ms on Linux. On Windows its time per element jumps between sizes (0.14 ns at 10M elements, 0.32 ns at 16M), and I did not find why. - NumPy’s
sum(0)is fast, because adding row after row into the output is an elementwise addition of contiguous rows: memory is read in order, and the output, one row of 16 KB at 4000 x 4000, stays in the L1. That is the same order that made its columns imprecise in the last section. It is a real trade-off, not a mistake: speed and precision ask for different orders. - PyTorch and Raxis lose at
sum(0)of the 4000 x 4000 matrix, 1.63 ms against 0.92. Their strip of 32 columns reads 128 bytes of a row and then jumps 16,000 bytes to the next one. That is a stride like the ones in the interlude’s section 6: the prefetcher follows it worse than reading in order, and with 64 MB almost every step lands on a different page. At 1000 x 1000, 4 MB, all three take the same time. - PyTorch on Windows is about twice as slow as Raxis whenever the data is in the caches, and 2.6 times at the 4000 x 4000
sum(0). On Linux the two take the same time in every row (0.025 ms for the 1000 x 1000sum(), 1.84 ms for the 4000 x 4000sum(0)), and Raxis runs the same algorithm, also compiled with MSVC on Windows. So it seems to be something in PyTorch’s Windows build of this kernel, and I did not find what, at least not yet.
7. Not only sums
A sum has an identity, 0, and one number of state. Other reductions need something else, and PyTorch has a path for each kind:
- Integer sums,
max,min,amax. Their result does not depend on the order (integer additions do not round, and a maximum is a maximum), so they need no cascade. They use a generic vectorized reduction with the same four vector accumulators (cpu_reduce_kernel_vec, raxisreduce.h), and the output is filled first with the identity: 0 for a sum, the lowest value of the type for a maximum. meanis the sum divided by the number of elements.argmaxneeds two numbers of state, the largest value so far and its position, and a rule for combining two of them. PyTorch writes such a reduction as a small struct of operations:reduce(acc, value, index)adds an element,combine(acc, acc)merges two partial results, andproject(acc)gives the final value (ArgMaxOps, pytorchSharedReduceOps.h).binary_kernel_reducethen runs it one output element at a time (pytorchReduce.h, raxisreduce.h).varandstduse the same structure with Welford’s algorithm, which keeps the running mean and the sum of squared differences in one pass (WelfordOps, pytorchSharedReduceOps.h). The obvious formula, the mean of the squares minus the square of the mean, subtracts two large numbers that are almost equal, and in float32 that can leave nothing but rounding.
The combine operation is what makes a reduction splittable: two threads can each reduce half of the elements, and one combination gives the result. That is where the threads come in.
8. parallel_for: splitting a range between threads
Every parallel loop in PyTorch’s CPU code, elementwise or reduction, goes through one function, parallel_for(begin, end, grain_size, f). It runs f(chunk_begin, chunk_end) on chunks of the range [begin, end), on as many threads as it decides (pytorchParallel-inl.h, raxisparallel_impl.h):
lazy_init_num_threads();
const int64_t num_iters = end - begin;
const bool use_parallel =
num_iters > grain_size && // enough work
num_iters > 1 &&
!in_parallel_region() && // not already inside a parallel loop
get_num_threads() > 1;
if (!use_parallel) {
f(begin, end); // the calling thread does everything
return;
}
invoke_parallel(begin, end, grain_size, f);
Three conditions keep the work on one thread:
- The grain size. Below it, starting the other threads would cost more than the work. The second article met it: elementwise operations pass
GRAIN_SIZE, 32,768 elements (pytorchTensorIterator.h, raxistensor_iterator.h). - No nested parallelism. If
fitself callsparallel_for, for example in a kernel that runs an operation per row, the inner call runs serially. Otherwise every thread would start a team of its own, and 8 threads would become 64, competing for 8 cores. - The number of threads. By default PyTorch uses one thread per physical core, 8 on this CPU, not one per hardware thread (16), as the interlude explains.
OMP_NUM_THREADSortorch.set_num_threadschange it. It is read the first time a thread callsparallel_for: that is thelazy_init_num_threads.
invoke_parallel is where the threads come from. With OpenMP, the default backend on Windows and Linux, it is a parallel region in which every thread computes its own chunk (pytorchParallelOpenMP.h, raxisparallel_openmp.h):
#pragma omp parallel
{
int64_t num_threads = omp_get_num_threads();
if (grain_size > 0) {
num_threads = std::min(num_threads, divup(end - begin, grain_size));
}
int64_t tid = omp_get_thread_num();
int64_t chunk_size = divup(end - begin, num_threads);
int64_t begin_tid = begin + tid * chunk_size;
if (begin_tid < end) {
f(begin_tid, std::min(end, begin_tid + chunk_size));
}
}
divup(a, b) is . There is one chunk per thread, but never so many chunks that one would be smaller than the grain size. All the threads of the team start even when some of them get no chunk: a comment in PyTorch’s code says that the num_threads clause of OpenMP, which would start fewer threads, is avoided because of a bug in GCC’s OpenMP runtime (pytorch#32008). With 8 threads:
| Elements | Threads that get work | Chunk | Ranges |
|---|---|---|---|
| 32,768 | none, serial | [0, 32768) on the calling thread | |
| 32,769 | 2 | 16,385 | [0, 16385), [16385, 32769) |
| 100,000 | 4 | 25,000 | [0, 25000), …, [75000, 100000) |
| 1,048,576 | 8 | 131,072 | [0, 131072), …, [917504, 1048576) |
What does starting the threads cost, and when does it pay? a + b into an existing output, float32, with 1 and 8 threads, in microseconds:
a + b (out=), us | PyTorch, 1 thread | PyTorch, 8 | Raxis, 1 thread | Raxis, 8 |
|---|---|---|---|---|
| 16,384 | 1.9 | 1.9 | 2.2 | 2.2 |
| 32,768 | 3.1 | 3.1 | 2.9 | 2.9 |
| 32,769 | 2.7 | 3.1 | 2.9 | 3.6 |
| 65,536 | 6.2 | 4.0 | 6.5 | 4.6 |
| 131,072 | 12.9 | 6.2 | 13.7 | 7.2 |
| 1,048,576 | 97.5 | 25.7 | 93.3 | 28.0 |
At 32,769 elements two threads do half of the work each, and the time does not go down: the work saved, about 1.5 microseconds, is what it costs to hand the second half to another thread and wait for it. From 65,536 elements the threads start to pay, and at a million the eight of them are 3.8 times faster, not 8, because the three arrays, 12 MB, come from the L3, which the cores share. These numbers move by a microsecond or so from run to run, and Linux gives the same picture. The grain size is one number for every elementwise operation, although an exp does much more work per element than an addition; some kernels pass a smaller one of their own.
One detail of the measurement: on Linux, PyTorch brings GCC’s OpenMP runtime and Raxis brings Intel’s, and in the same process the idle threads of one runtime keep spinning for a while, waiting for work, while the other one is timed. For this table the script measures each library in a process of its own. Raxis also has a backend without OpenMP, a thread pool of its own, which it uses on macOS (Apple’s compiler has no OpenMP); there invoke_parallel hands one task per chunk to the pool, and the calling thread runs the first one.
9. Splitting a reduction
A reduction cannot just cut its input into flat ranges, as a + b does: two threads that sum two halves of the same column would both add into the same output element at the same time, and one of the two additions could be lost. So parallel_reduce, the reduction’s version of for_each, picks one of three plans (pytorchTensorIteratorReduce.cpp, raxistensor_iterator_reduce.cpp):
if (numel < GRAIN_SIZE || get_num_threads() == 1 || in_parallel_region()) {
serial_for_each(loop, {0, numel}); // one thread
} else if (output.numel() == 1) {
two_pass_reduction(*this, loop); // a single output element
} else {
parallel_dim_reduction(*this, loop); // many output elements
}
Many output elements: split the outputs. parallel_dim_reduction picks a dimension that is not reduced, the outermost one with at least as many elements as there are threads (find_split_dim), and gives each thread a range of it with parallel_for. Each thread then runs the whole reduction for its own output elements, so no two threads ever write the same one (pytorchTensorIteratorReduce.cpp, raxistensor_iterator_reduce.cpp). For x.sum(1) of a 1000 x 1000 matrix it splits the rows: 125 rows per thread, each one summed whole by one thread.
For x.sum(0) it splits the columns, with one more step: when the columns are contiguous, it rounds the boundaries of each range down to a multiple of 128 bytes, 32 floats, the width of the strip of section 6 (round_columns). Two threads then never share a strip, nor write to the same cache line of the output. With 8 threads, parallel_for(0, 1000, 1, ...) first gives each thread 125 columns, and the rounding moves the boundaries:
| Thread | Before rounding | After | Columns |
|---|---|---|---|
| 0 | [0, 125) | [0, 96) | 96 |
| 1 | [125, 250) | [96, 224) | 128 |
| 2 to 6 | [250, 375) … [750, 875) | [224, 352) … [736, 864) | 128 each |
| 7 | [875, 1000) | [864, 1000) | 136 |
The end of the last range is not rounded, so all 1000 columns are covered.
A single output element: two passes. x.sum() has one output, and there is nothing to split but the input. two_pass_reduction allocates a small buffer with one output element per thread, and runs parallel_for over the whole input with the grain size: each thread reduces its chunk into its own slot of the buffer, with the same kernel and the same cascade. Then a second, tiny reduction adds the slots of the buffer together (pytorchTensorIteratorReduce.cpp, raxistensor_iterator_reduce.cpp). For 10 million elements and 8 threads, each thread sums 1,250,000 of them, and the second pass adds 8 numbers.
What the threads buy here, on Windows, in milliseconds:
sum, ms | PyTorch, 1 thread | PyTorch, 8 | Raxis, 1 thread | Raxis, 8 |
|---|---|---|---|---|
1000 x 1000, sum() | 0.087 | 0.018 | 0.028 | 0.011 |
1000 x 1000, sum(0) | 0.114 | 0.022 | 0.044 | 0.012 |
1000 x 1000, sum(1) | 0.105 | 0.018 | 0.044 | 0.010 |
4000 x 4000, sum() | 1.45 | 0.65 | 0.79 | 0.63 |
4000 x 4000, sum(0) | 4.36 | 1.58 | 1.65 | 0.76 |
4000 x 4000, sum(1) | 1.48 | 0.63 | 1.12 | 0.74 |
From the L3, eight threads are 2.5 to 5 times faster. From memory, with the 64 MB matrix, they add little to sum() and sum(1), which one core already reads close to the limit of the memory. (64 MB in 0.79 ms is 81 GB/s, more than the 76.8 GB/s the RAM can deliver, so part of the matrix is still in the L3 from the run before.) sum(0), whose strips read with a stride, gains twice as much: eight threads keep eight times as many reads on their way.
10. Does the result depend on the number of threads?
With many output elements, no: each output element is reduced by one thread, from its first element to its last, with the same cascade, whatever the number of threads. Only which thread does it changes.
With one output element, yes. The chunks of two_pass_reduction are divup(n, threads) elements long, so the number of threads decides where the partial sums start and end, and the floats are added in a different grouping. I measured sum() of 10 million float32 from a normal distribution, whose exact sum is 1820.9482, and sum(0) and sum(1) of a 1000 x 1000 matrix, with 1 to 16 threads:
| Threads | PyTorch sum() | Raxis sum() | sum(0) and sum(1) equal to 1 thread |
|---|---|---|---|
| 1 | 1820.9490 | 1820.9490 | yes |
| 2 | 1820.9486 | 1820.9486 | yes |
| 3 | 1820.9487 | 1820.9487 | yes |
| 4 | 1820.9486 | 1820.9486 | yes |
| 6 | 1820.9487 | 1820.9487 | yes |
| 8 | 1820.9492 | 1820.9492 | yes |
| 16 | 1820.9486 | 1820.9486 | yes |
The results differ in the last digits. Around 1820, two neighbouring float32 numbers are 0.000122 apart, so these are differences of two to five steps. None of them is the exact value, and one thread is not more exact than eight: they are all different roundings of 1820.9482. PyTorch and Raxis give the same bits at every thread count, because they split the work at the same places and add in the same order, and every sum(0) and sum(1) is identical to the one-thread result. On Linux the table is the same except for the first row, where both give 1820.9487.
This matters when you compare two runs. A training run on a machine with another number of cores, or with OMP_NUM_THREADS set differently, sums its losses and norms with other roundings, and its numbers drift apart in the last digits from the first step. For a model this is noise, but a test that compares two results bit for bit has to fix the number of threads. A fixed split, the same chunks whatever the number of threads, would make sum() independent of it too, at the cost of choosing that split; neither PyTorch nor Raxis does that today.
Key takeaways
- A reduction is a TensorIterator whose output does not move (section 2): a stride of 0 along the reduced dimensions.
- One accumulator is slow and imprecise (sections 3 and 4): 22 times slower than 32 accumulators, and ones add up to . The cascade sum fixes both (section 5).
- Threads have a cost (section 8): PyTorch does not split an operation below 32,768 elements, and on the 9700X an addition starts to gain from threads only at about twice that.
sum(dim)gives the same bits with any number of threads, andsum()does not (section 10), in PyTorch as in Raxis.
Further reading
- Nicholas J. Higham, “The Accuracy of Floating Point Summation”, SIAM Journal on Scientific Computing, 1993: the error bounds of the recursive, pairwise and compensated sums, and when each one wins.
- David Goldberg, “What Every Computer Scientist Should Know About Floating-Point Arithmetic”, ACM Computing Surveys, 1991: rounding, and why the order of the additions matters.
- Kahan summation, a compensated sum that carries the lost low bits along: more precise than pairwise, but four operations per element instead of one.
- The notes of NumPy’s
sumon pairwise summation and the fast axis. - The OpenMP specification, for
#pragma omp paralleland the variables that set the number of threads.
If something is not clear, or you think I got something wrong, leave a comment.