5 ms·

> If we’re using concurrency, that means multiple threads of execution may be mutating the same cell, which requires synchronization — locks, atomics, etc. That

> If we’re using concurrency, that means multiple threads of execution may be mutating the same cell, which requires synchronization — locks, atomics, etc. That much synchronization is the death knell of performance. 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. 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. The author only appears to know how to do pull (if that's wrong, they didn't really do push any justice in the article), so from their POV push just doesn't work. The article does show something very important though: pull does give you reasonable performance and is quite easy to reason about and get right. In contrast, push is quite hard due to the write-write data-races the author mentions, so I don't blame the author from arriving at their conclusion that one should always do pull. It might not always be true, but it is definitely a safe place to start, particularly if you aren't super familiar with the algorithm yet and don't know how or if push would work well. For example, many of the convolutions that neural networks use are actually implemented using the "push" approach because that's more efficient, and they are quite similar to what the blog post author is doing.

m_mueller 6y ago
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.
sitkack 6y ago
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?
- fluffything 6y ago
  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.
  - grogers 6y ago
    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)?
dragontamer 6y ago
> 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.
senderista 6y ago
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).

m_mueller 6y ago

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.

sitkack 6y ago

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?

fluffything 6y ago
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.
- grogers 6y ago
  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)?

dragontamer 6y ago

> 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.

senderista 6y ago

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).