Hacker News Reader

Having done quite a bit of HPC in my research career, the usually best approach is (IMO) to:

* decompose the problem data to the subsets handled by each machine

* within each node, use pushing. this allows walking the node-internal data structure sequentially, thus is very cache friendly

* for the boundary cells, use pulling

edit: I should add, it may also make sense to do pulling between the cores, otherwise you need locks which could hurt performance as well.

> You can do this without synchronization by exploiting the fact that all "lanes" of a SIMD vector execute simultaneously, e.g. by doing vector scatters "to the left" and then "to the right" those writes will not race with each other, and don't require locks or atomics.

Well, SIMD is implicit synchronization. Within a SIMD wavefront, all instructions have an implicit barrier between them (because all instructions begin, and finish, simultaneously).

This implicit synchronization may be all you need.

> Whether pull or push is faster heavily depends on the algorithm - there is no silver bullet here. To write efficient parallel algorithms you need to know how to do both.

I agree. The terminology in HPC seems to be "gather" and "scatter" operations.

It should be noted that "gather" can be converted into "scatter" with some tricks. But the programmer should be prepared in using both methods, depending on the circumstance.

Convolution is a great illustration of the difference between the push and pull approaches. You can implement (one-dimensional, but generalizes easily to any dimension) convolution either by assigning each point a weighted average centered at that point, computed over all points (pull), or by sliding the weight function along the interval and accumulating (summing) the weighted value of the current center of the weight function at each point (push). The push approach is optimized for reads (linear reads, quadratic writes), and the pull approach is optimized for writes (quadratic reads, linear writes).

What does push gain you over pull? Why would someone want to use it? Does it help with inplace updates vs having to duplicate storage?

The problem it solves is temporal cache locality, and whether pull or push is better often only depends on what is it that you want to keep in cache for the next operation.

For example, suppose you are doing a 3x3 convolution over a matrix, and you want to keep the result of the convolution in cache because the next operation consumes it.

So your cache is pretty much filled with the output matrix, and you only have space in cache to pull in one row from global memory for reading.

Now consider what happens if you process your input matrix row-by-row, first with the pull approach and then with the push approach.

With the pull approach you need to load 3 rows from memory into cache before you can push. No matter how you do this, as you advance through the input, you are going to be loading some rows twice. For example, suppose that from the 3x3 window, we load the rows in this order: top, bottom, mid (and then push the convolution to the mid row of the output). In one iteration we load rows 0, 2 (evicts row 0) and 1 (evicts row 2). The next iteration loads 1 (hit) and 3 (evicts 1), and then 2 (reloads 2!). That's bad!

With the push approach, you load one row, and push partial contributions to the 3 rows of the output matrix. Then you load the next row, and do the same. The output matrix is always in cache, so those writes always hit, and you never need to load a row from memory twice.

So in a sense, pull optimizes for bringing the rows of the output into cache once, which is good if you want to continue working with the input afterwards, while push optimizes for keeping the output in cache, which is good if you want to continue working with the output afterwards.

One isn't really better than the other. Which one to choose depends on what is it that you want to do. Maybe you have one input matrix, and multiple convolution windows, and want to compute multiple outputs that you don't need right away. In that case, you want to keep the input matrix in cache, and compute the rows of the output one by one, evicting them from the cache after each computation.

If you can't keep 3 rows of the input matrix in cache, why would you be able to keep 3 rows of the output matrix in cache? If the matrices are large enough that they don't fit in cache, shouldn't they be processed in squareish blocks recursively to maximize cache reuse (not in rows)?

> If you can't keep 3 rows of the input matrix in cache, why would you be able to keep 3 rows of the output matrix in cache? If the matrices are large enough that they don't fit in cache, shouldn't they be processed in squareish blocks recursively to maximize cache reuse (not in rows)?

Your cache size is fixed by the computer and you can't change it. If you are doing a convolution, you want "(N+1)xN = cache size" to determine the size of the "blocks" (NxN matrix, and an 1xN row) of the convolution you process. Those blocks are also matrices, so by decomposing your matrix into smaller matrices you don't avoid this problem.

So sure, you could also decompose your problem by doing "(N+3)xN = cache-size", but that means that the size of the "square blocks" that you can now properly fit in cache is smaller, and need to decompose your original problem into more sub-problems to get it done. You could also do: "2Nx2N = cache size", and just load a whole input block and an output block into cache.

In both cases, you are bringing memory into cache that you only touch once, yet continue occupying cache space after you don't need them anymore. You could have used that space to process larger matrices instead, and have to decompose your problem into fewer blocks.