6 ms·

So glad to see this coming along. If any of the project team are reading, what I'd like to see most is GPU-accelerated point-in-polygon lookups in postGIS, ST_

So glad to see this coming along. If any of the project team are reading, what I'd like to see most is GPU-accelerated point-in-polygon lookups in postGIS, ST_Contains and so forth.

trentnelson 12y ago
Yeah this is a problem well suited to parallelism. Oracle 12c's spatial stuff can be configured to leverage AVX for these sorts of problems. And let's admit it, writing SQL statements with `vector group by ...` make you feel like a bad-ass.
7952 12y ago
Point in polygon is difficult in GIS because the polygon can have a very large number of verticies that all have to be checked. Does a GPU have sufficient bandwidth to load large polygons quickly? Do GPU's have to sample each vertex every time? Often the best way is to divide polygons into tiles that have a limited number of verticies (this also makes indexing much more effective).
vardump 12y ago
It's likely GPUs are slower than CPUs for spatial data structures. Getting the data to GPU and results back takes just too long. Point in polygon is also very branchy in general case. GPUs are really bad with branchy code, so it's very unlikely you could even GPU accelerate such query, if it operates on point coordinates and a set of polygon vertexes. At least it would be very hard. Edit: right, after thinking about it, the branches can be optimized out. It could be fast if there are a set of sorted segments, just parallel compares and some boolean logic. Which leaves the problem of getting the data to GPU. Because you can definitely stream same comparisons on the CPU much faster (memory bandwidth limited) than you can stream the data to GPU over PCIe. So 2 CPU socket system, such as Xeon E5, I'd bet on the CPU. PCIe 4.0, 16 lanes would give 30 GB/s (not sure if PCIe 4.0 is supported anywhere), vs. aggregate CPU bandwidth of up to 150-200 GB/s. Dual socket Xeon E5 supports at least 1 TB of RAM (16x 16 GB buffered DDR4). 32 GB DDR4 memory modules exist as well, I think, and larger DIMM banks than 16 slots can be supported. It's just the number of slots on typical 2 socket mainboards. With more realistic setting, CPU would be even more ahead. All of this is ignoring GPU latency issues, which can be anywhere from microseconds to tens of milliseconds in pathological cases. Unless the data was on the GPU in the first place... I think currently a single GPU can have up to 12 GB of RAM. Maybe larger GPUs exist too. That's just not much RAM compared to what is typical for CPUs. Currently smallest amount of RAM a dual socket Xeon E5v3 standard server can have is 64 GB, if all memory channels have at least one DIMM.
- bhouston 12y ago
  If the data can stay on the GPU, then it is likely a win. GPU have 8GB or more now. Thus it depends on how much polygon data one has.
  - berkut 12y ago
    Not necessarily: even if the data's on the GPU so doesn't have to pay the PCI-E transfer penalty, GPUs still have cache hierarchies and these have latencies as well, and they can be worse than for CPUs as the branch-predictors and pre-fetchers of GPUs are still fairly primitive in comparison to what CPUs are capable of, meaning access patterns on a GPU can actually matter quite a bit - you end up having to change block-size per GPU type and code which works on one very well doesn't work as well on another GPU. However, point-in-polygon is a fairly simple algorithm, and if each polygon was mostly < 40 vertices, I suspect a GPU might be faster. However, for more complex algorithms, GPUs don't do as well and with many more vertices I suspect GPUs won't do as well for point-in-polygon tests. In terms of raw theoretical FP processing power, GPUs look good - but when you start to do more complex things with them - i.e. when branching happens a lot, say with path tracing, they don't look as good. E.g. a dual Xeon 3.5 Ghz quad i7 (costing ~£950 each) is as fast at path tracing as a single NVidia K6000 costing ~£4100.
    - bhouston 12y ago
      Here is a production quality path tracer that for most users runs noticeably faster than competing CPU-based renderer: https://www.redshift3d.com/ https://www.redshift3d.com/ Pragmatically, it produces results of similar quality quicker than CPU-based competitors. It is really taking the high end rendering world by storm this year.
      - berkut 12y ago
        Erm??... That's a biased renderer that uses all sorts of caching and approximations that there's no CPU-based renderer that supports (VRay's closest with it's ability to configure primary and secondary rays using different irradiance cache methods), and as Redshift doesn't support CPU rendering, it's hardly a comparison worth talking about as you'd be comparing different algorithms. The pure brute-force without any caching numbers I've seen for it don't look any better than the other top CPU renderers doing brute-force MC integration. Also, a quibble, but I guess by "high-end rendering world" you mean archviz (where VRay and 3DSMax are dominant) and a few small VFX studios who happen to be running Windows?
sitkack 12y ago
You should submit data and queries that you would like accelerated.
rcpt 12y ago
About a year ago there was a lot of press about a GPU database called MapD. It's not released yet but most of their demos involve spatial data cf http://blogs.nvidia.com/blog/2013/11/20/juicing-big-data-startup-builds-gpu-database-to-visualize-the-world-on-twitter/ http://blogs.nvidia.com/blog/2013/11/20/juicing-big-data-sta...

So glad to see this coming along. If any of the project team are reading, what I'd like to see most is GPU-accelerated point-in-polygon lookups in postGIS, ST_Contains and so forth.

trentnelson 12y ago

Yeah this is a problem well suited to parallelism. Oracle 12c's spatial stuff can be configured to leverage AVX for these sorts of problems. And let's admit it, writing SQL statements with `vector group by ...` make you feel like a bad-ass.

7952 12y ago

Point in polygon is difficult in GIS because the polygon can have a very large number of verticies that all have to be checked. Does a GPU have sufficient bandwidth to load large polygons quickly? Do GPU's have to sample each vertex every time? Often the best way is to divide polygons into tiles that have a limited number of verticies (this also makes indexing much more effective).

vardump 12y ago

It's likely GPUs are slower than CPUs for spatial data structures. Getting the data to GPU and results back takes just too long. Point in polygon is also very branchy in general case. GPUs are really bad with branchy code, so it's very unlikely you could even GPU accelerate such query, if it operates on point coordinates and a set of polygon vertexes. At least it would be very hard. Edit: right, after thinking about it, the branches can be optimized out. It could be fast if there are a set of sorted segments, just parallel compares and some boolean logic. Which leaves the problem of getting the data to GPU. Because you can definitely stream same comparisons on the CPU much faster (memory bandwidth limited) than you can stream the data to GPU over PCIe. So 2 CPU socket system, such as Xeon E5, I'd bet on the CPU. PCIe 4.0, 16 lanes would give 30 GB/s (not sure if PCIe 4.0 is supported anywhere), vs. aggregate CPU bandwidth of up to 150-200 GB/s. Dual socket Xeon E5 supports at least 1 TB of RAM (16x 16 GB buffered DDR4). 32 GB DDR4 memory modules exist as well, I think, and larger DIMM banks than 16 slots can be supported. It's just the number of slots on typical 2 socket mainboards. With more realistic setting, CPU would be even more ahead. All of this is ignoring GPU latency issues, which can be anywhere from microseconds to tens of milliseconds in pathological cases. Unless the data was on the GPU in the first place... I think currently a single GPU can have up to 12 GB of RAM. Maybe larger GPUs exist too. That's just not much RAM compared to what is typical for CPUs. Currently smallest amount of RAM a dual socket Xeon E5v3 standard server can have is 64 GB, if all memory channels have at least one DIMM.

bhouston 12y ago
If the data can stay on the GPU, then it is likely a win. GPU have 8GB or more now. Thus it depends on how much polygon data one has.
- berkut 12y ago
  Not necessarily: even if the data's on the GPU so doesn't have to pay the PCI-E transfer penalty, GPUs still have cache hierarchies and these have latencies as well, and they can be worse than for CPUs as the branch-predictors and pre-fetchers of GPUs are still fairly primitive in comparison to what CPUs are capable of, meaning access patterns on a GPU can actually matter quite a bit - you end up having to change block-size per GPU type and code which works on one very well doesn't work as well on another GPU. However, point-in-polygon is a fairly simple algorithm, and if each polygon was mostly < 40 vertices, I suspect a GPU might be faster. However, for more complex algorithms, GPUs don't do as well and with many more vertices I suspect GPUs won't do as well for point-in-polygon tests. In terms of raw theoretical FP processing power, GPUs look good - but when you start to do more complex things with them - i.e. when branching happens a lot, say with path tracing, they don't look as good. E.g. a dual Xeon 3.5 Ghz quad i7 (costing ~£950 each) is as fast at path tracing as a single NVidia K6000 costing ~£4100.
  - bhouston 12y ago
    Here is a production quality path tracer that for most users runs noticeably faster than competing CPU-based renderer: https://www.redshift3d.com/ https://www.redshift3d.com/ Pragmatically, it produces results of similar quality quicker than CPU-based competitors. It is really taking the high end rendering world by storm this year.
    - berkut 12y ago
      Erm??... That's a biased renderer that uses all sorts of caching and approximations that there's no CPU-based renderer that supports (VRay's closest with it's ability to configure primary and secondary rays using different irradiance cache methods), and as Redshift doesn't support CPU rendering, it's hardly a comparison worth talking about as you'd be comparing different algorithms. The pure brute-force without any caching numbers I've seen for it don't look any better than the other top CPU renderers doing brute-force MC integration. Also, a quibble, but I guess by "high-end rendering world" you mean archviz (where VRay and 3DSMax are dominant) and a few small VFX studios who happen to be running Windows?

sitkack 12y ago

You should submit data and queries that you would like accelerated.

rcpt 12y ago

About a year ago there was a lot of press about a GPU database called MapD. It's not released yet but most of their demos involve spatial data cf http://blogs.nvidia.com/blog/2013/11/20/juicing-big-data-startup-builds-gpu-database-to-visualize-the-world-on-twitter/ http://blogs.nvidia.com/blog/2013/11/20/juicing-big-data-sta...