4 ms·

Parallelism with the computing units in GPU permeates the entire computing model. For the longest time I don't get how partial derivative instructions like dFd

by ww520 5y ago

Parallelism with the computing units in GPU permeates the entire computing model. For the longest time I don't get how partial derivative instructions like dFdx/dFdy/ddx/ddy work. None of the doc helps. These instructions take in a number and return its partial derivative, just a generic number, nothing to do with graphic, geometry or function. The number could have been the dollar amount of a mortgage and its partial derivative is returned. It turns out these functions tied to how the GPU architecture runs the computing units in parallel. The computing units are arranged to run in parallel in a geometric grid according to the input data model. The computing units run the same program in LOCK STEP in parallel (well at least in lock step upon arriving at the dFdx/dFdy instructions). They also know their neighbors in the grid. When a computing unit encounters a dFdx instruction, it reaches across and grabs its neighbors' input value to their dFdx instructions. All the neighbors arrive at dFdx at the same time with their input value ready. With the neighbors' numbers and its own number as the mid point, it can compute the partial derivative using gradient slope.

anonymous532 5y ago
I don't sign in often, thank you for this amazing reveal.
bigdict 5y ago
So the function F is implicitly defined to have value F(x,y) = v, where x and y are coordinates of the core, and v is the input value to the dFdx/dFdy instruction? Then the output of the instruction running on the x,y core (take dFdx for example) is supposedly equal to (F(x+1,y)-F(x-1,y))/2?
- ww520 5y ago
  Yes. That's the idea. Though not exactly sure how the GPU uses the neighboring values to interpolate the partial derivative. It's probably GPU dependent.
  - corysama 5y ago
    Pretty much all of them work in 2x2 quads. DyDx is calculated within a quad. But, not across them. This is an imperfect approximation to the derivative that needs to be accounted for. But, it’s useful and very cheap and trivially easy.
  - Jasper_ 5y ago
    It's defined to work on a 2x2 grid called a quad. If you're the top left pixel, then dFdX(v) = v(x+1,y) - v. If you're the top right pixel, then it's dFdX(v) = v(x-1,y) - v
deleted 5y ago
[deleted]
bla3 5y ago
That sounds like a useful mental model. But it can't be quite right, can it? There aren't enough cores to do _all_ pixels in parallel, so how is that handled? Does it render tiles and compute all edges several times for this?
- ww520 5y ago
  That's correct. There aren't enough physical cores to do all cells in parallel. A 1000x1000 grid would have 1M cells. These are virtual computing units. Conceptually there are 1M virtual computing units, one per cell. The thousands of physical cores take on the cells one batch at a time until all of the cells are run. In fact multiple cores can run the code of one cell in parallel. E.g. for-loop is unrolled and each core takes on a different branch of the for-loop. The scheduling of the cores to virtual computing units is like the OS scheduling CPUs to different processes. Most instructions have no inter-dependency between cells. These instructions can be executed by a core as fast as it can on one computing unit until an inter-dependent instruction like dFdx is encountered that requires syncing. The computing unit is put in a wait state while the core moves on to another one. When all the computing units are sync'ed up at the dFdx instruction, they're then executed by the cores batch by batch.
  - Jasper_ 5y ago
    No, multiple cores can't run the code of the same cell in parallel. The key here is that these cores run in lockstep, so the program counter is the is the exact same for all cells being run at once. In practice, each core supports 32 (or sometimes 64) cells at a time. There is also no syncing required for dFdX! Since the quads ran in lockstep, the results are guaranteed to be computed at the same time. In practice, these are all computed in vector SIMD registers, and a dFdX simply pulls a registers from another SIMD lane. If you want to execute more tasks than this, throw more cores at it.
    - ww520 5y ago
      All the computing units running in lockstep is what appears to the program. They don't have to run in lockstep for every single instruction in reality. SIMT works in a warp with up to 32 threads [1]. Different thread warps working on different cell regions can run with different program counters. Also the newer Volta architecture (section 3.2 in [1]) allows independent thread scheduling of threads across warps such that each thread can have its own program counter and stack. There're certainly sync. See how barrier is used (9.7.12.1 in [1]) to synchronize threads. [1] https://docs.nvidia.com/cuda/parallel-thread-execution/index.html https://docs.nvidia.com/cuda/parallel-thread-execution/index...

by ww520 5y ago

anonymous532 5y ago

I don't sign in often, thank you for this amazing reveal.

bigdict 5y ago

So the function F is implicitly defined to have value F(x,y) = v, where x and y are coordinates of the core, and v is the input value to the dFdx/dFdy instruction? Then the output of the instruction running on the x,y core (take dFdx for example) is supposedly equal to (F(x+1,y)-F(x-1,y))/2?

ww520 5y ago
Yes. That's the idea. Though not exactly sure how the GPU uses the neighboring values to interpolate the partial derivative. It's probably GPU dependent.
- corysama 5y ago
  Pretty much all of them work in 2x2 quads. DyDx is calculated within a quad. But, not across them. This is an imperfect approximation to the derivative that needs to be accounted for. But, it’s useful and very cheap and trivially easy.
- Jasper_ 5y ago
  It's defined to work on a 2x2 grid called a quad. If you're the top left pixel, then dFdX(v) = v(x+1,y) - v. If you're the top right pixel, then it's dFdX(v) = v(x-1,y) - v

deleted 5y ago

[deleted]

bla3 5y ago

That sounds like a useful mental model. But it can't be quite right, can it? There aren't enough cores to do _all_ pixels in parallel, so how is that handled? Does it render tiles and compute all edges several times for this?

ww520 5y ago
That's correct. There aren't enough physical cores to do all cells in parallel. A 1000x1000 grid would have 1M cells. These are virtual computing units. Conceptually there are 1M virtual computing units, one per cell. The thousands of physical cores take on the cells one batch at a time until all of the cells are run. In fact multiple cores can run the code of one cell in parallel. E.g. for-loop is unrolled and each core takes on a different branch of the for-loop. The scheduling of the cores to virtual computing units is like the OS scheduling CPUs to different processes. Most instructions have no inter-dependency between cells. These instructions can be executed by a core as fast as it can on one computing unit until an inter-dependent instruction like dFdx is encountered that requires syncing. The computing unit is put in a wait state while the core moves on to another one. When all the computing units are sync'ed up at the dFdx instruction, they're then executed by the cores batch by batch.
- Jasper_ 5y ago
  No, multiple cores can't run the code of the same cell in parallel. The key here is that these cores run in lockstep, so the program counter is the is the exact same for all cells being run at once. In practice, each core supports 32 (or sometimes 64) cells at a time. There is also no syncing required for dFdX! Since the quads ran in lockstep, the results are guaranteed to be computed at the same time. In practice, these are all computed in vector SIMD registers, and a dFdX simply pulls a registers from another SIMD lane. If you want to execute more tasks than this, throw more cores at it.
  - ww520 5y ago
    All the computing units running in lockstep is what appears to the program. They don't have to run in lockstep for every single instruction in reality. SIMT works in a warp with up to 32 threads [1]. Different thread warps working on different cell regions can run with different program counters. Also the newer Volta architecture (section 3.2 in [1]) allows independent thread scheduling of threads across warps such that each thread can have its own program counter and stack. There're certainly sync. See how barrier is used (9.7.12.1 in [1]) to synchronize threads. [1] https://docs.nvidia.com/cuda/parallel-thread-execution/index.html https://docs.nvidia.com/cuda/parallel-thread-execution/index...