6 ms·
Prefix sum: 20 GB/s (2.6x baseline)
- tonetegeatinst 1y agoWonder if PTX programming for a GPU would accelerate this.
- almostgotcaught 1y agoLol do you think "PTX programming" is some kind of trick path to perf? It's just inline asm. Sometimes it's necessary but most of the time "CUDA is all you need": https://github.com/b0nes164/GPUPrefixSums https://github.com/b0nes164/GPUPrefixSums
- ashtonsix 1y agoIf the data is already in GPU memory, yes. Otherwise you'll be limited by the DRAM<->VRAM memory bottleneck. When we consider that delta coding (and family), are typically applied as one step in a series of CPU-first transforms and benefit from L1-3 caching we find CPU throughput pulls far-ahead of GPU-based approaches for typical workloads. This note holds for all GPU-based approaches, not just PTX.
- _zoltan_ 1y agowhat is a typical workload that you speak of, where CPUs are better? We've been implementing GPU support in Presto/Velox for analytical workloads and I'm yet to see a use case where we wouldn't pull ahead. The DRAM-VRAM memory bottleneck isn't really a bottleneck on GH/GB platforms (you can pull 400+GB/s across the C2C NVLink), and on NVL8 systems like the typical A100/H100 deployments out there, doing real workloads, where the data is coming over the network links, you're toast without using GPUDirect RDMA.
- ashtonsix 1y agoBy typical I imagined adoption within commonly-deployed TSDBs like Prometheus, InfluxDB, etc. GB/GH are actually ideal targets for my code: both architectures integrate Neoverse V2 cores, the same core I developed for. They are superchips with 144/72 CPU cores respectively. The perf numbers I shared are for one core, so multiply the numbers I gave by 144/72 to get expected throughput on GB/GH. As you (apparently?) have access to this hardware I'd sincerely appreciate if you could benchmark my code there and share the results.
- _zoltan_ 1y agoGB is CPU+2xGPU. GH is readily available for anybody at 1.5 dollars per hour on lambda; GB is harder and we're just going to begin to experiment on it.
- ashtonsix 1y agoEach Grace CPU has multiple cores: https://www.nvidia.com/en-gb/data-center/grace-cpu-superchip https://www.nvidia.com/en-gb/data-center/grace-cpu-superchip This superchip (might be different to whichever you're referring to) has 2 CPUs (144 cores): https://developer.nvidia.com/blog/nvidia-grace-cpu-superchip-architecture-in-depth https://developer.nvidia.com/blog/nvidia-grace-cpu-superchip...
- tmostak 1y agoEven without NVLink C2C, on a GPU with 16XPCIe 5.0 lanes to host, you have 128GB/sec in theory and 100+ GB/sec in practice bidirectional bandwidth (half that in each direction), so still come out ahead with pipelining. Of course prefix sums are often used within a series of other operators, so if these are already computed on GPU, you come out further ahead still.
- ashtonsix 1y agoHaha... GPUs are great. But do you mean to suggest we should swap a single ARM core for a top-line GPU with 10k+ cores and compare numbers on that basis? Surely not. Let's consider this in terms of throughput-per-$ so we have a fungible measurement unit. I think we're all agreed that this problem's bottleneck is the host memory<->compute bus so the question is: for $1 which server architecture lets you pump more data from memory to a compute core? It looks like you can get a H100 GPU with 16xPCIe 5.0 (128 GB/s theoretical, 100 GB/s realistic) for $1.99/hr from RunPod. With an m8g.8xlarge instance (32 ARM CPU cores) you should get much-better RAM<->CPU throughput (175 GB/s realistic) for $1.44/hr from AWS.
- _zoltan_ 1y agoGH200 is $1.5/hr at lambda and can do 450GB/s to the GPU. seems still cheaper?
- bassp 1y agoYes! There’s a canonical algorithm called the “Blelloch scan” for prefix sum (aka prefix scan, because you can generalize “sum” to “any binary associative function”) that’s very gpu friendly. I have… fond is the wrong word, but “strong” memories of implementing in a parallel programming class :) Here’s a link to a pretty accessible writeup, if you’re curious about the details: https://developer.nvidia.com/gpugems/gpugems3/part-vi-gpu-computing/chapter-39-parallel-prefix-sum-scan-cuda https://developer.nvidia.com/gpugems/gpugems3/part-vi-gpu-co...
- ashtonsix 1y agoMm, I used that exact writeup as a reference to implement this algorithm in WebGL 3 years ago: https://github.com/ashtonsix/webglc/blob/main/src/kernel/scan.ts https://github.com/ashtonsix/webglc/blob/main/src/kernel/sca... It even inspired the alternative "transpose" method I describe in the OP README.
- TinkersW 1y agoYour average none shared memory GPU communicates with the CPU over PCIe which is dogshit slow, like 100x slower than DRAM. I can upload about an average of 3.7 MBs per millisecond to my GPU(PCIe gen 3, x8), but it can be spiky and sometimes take longer than you might expect. By comparison a byte based AVX2 prefix scan can pretty much run at the speed of DRAM, so there is never any reason to transfer to the GPU.
- nullbyte 1y agoThis code looks like an alien language to me. Or maybe I'm just rusty at C.
- ashtonsix 1y agoThe weirdness probably comes from heavy use of "SIMD intrinsics" (Googleable term). These are functions with a 1:1 correspondence to assembly instructions, used for processing multiple values per instruction.
- mananaysiempre 1y agoSIMD intrinsics are less C and more assembly with overlong mnemonics and a register allocator, so even reading them is something of a separate skill. Unlike the skill of achieving meaningful speedups by writing them (i.e. low-level optimization), it’s nothing special, but expect to spend a lot of time jumping between the code and the reference manuals[1,2] at first. [1] https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html https://www.intel.com/content/www/us/en/docs/intrinsics-guid... [2] https://developer.arm.com/architectures/instruction-sets/intrinsics/ https://developer.arm.com/architectures/instruction-sets/int...
- ack_complete 1y agoThis is partially due to the compromises of mappingvector intrinsics into C (with C++ only being marginally better). In a more vector-oriented language, such as shader languages, this: s1 = vaddq_u32(s1, vextq_u32(z, s1, 2)); s1 = vaddq_u32(s1, vdupq_laneq_u32(s0, 3)); would be more like this: s1.xy += s1.zw; s1 += s0.w;
- mananaysiempre 1y agoTo be fair, even in standard C11 you can do a bit better than the CPU manufacturer’s syntax #define vaddv(A, B) _Generic((A), int8x8_t: vaddv_s8((A), (B)), uint8x8_t: vaddv_u8((A), (B)), int8x16_t: vaddvq_s8((A), (B)), uint8x16_t: vaddvq_u8((A), (B)), int16x4_t: vaddv_s16((A), (B)), uint16x4_t: vaddv_u16((A), (B)), int16x8_t: vaddvq_s16((A), (B)), uint16x8_t: vaddvq_u16((A), (B)), int32x2_t: vaddv_s32((A), (B)), uint32x2_t: vaddv_u32((A), (B)), float32x2_t: vaddv_f32((A), (B)), int32x4_t: vaddvq_s32((A), (B)), uint32x4_t: vaddvq_u32((A), (B)), float32x4_t: vaddvq_f32((A), (B)), int64x2_t: vaddvq_s64((A), (B)), uint64x2_t: vaddvq_u64((A), (B)), float64x2_t: vaddvq_f64((A), (B))) while in GNU C you can in fact use normal arithmetic and indexing (but not swizzles) on vector types.
- yogishbaliga 1y agoWay back in time, I used delta encoding for storing posting list (inverted index for search index). I experimented with using GPUs for decoding the posting list. It turned out that, as another reply mentioned copying posting list from CPU memory to GPU memory was taking way too long. If posting list is static, it can be copied to GPU memory once. This will make the decoding faster. But still there is a bottle neck of copying the result back into CPU memory. Nvidia's unified memory architecture may make it better as same memory can be shared between CPU and GPU.
- Certhas 1y agoAMD has had unified memory for ages in HPC and for a while now in the Strix Halo systems. I haven't had the chance to play with one yet, but I have high hopes for some of our complex simulation workloads.
- ashtonsix 1y agoOh neat. I have some related unpublished SOTA results I want to release soon: PEF/BIC-like compression ratios, with faster boolean algebra than Roaring Bitsets.
- hughw 1y agoThe shared memory architecture doesn't eliminate copying the data across to the device. Edit: or back.
- yogishbaliga 1y agoIf it is unified memory, CPU can access the result of GPU processing without copying it to CPU memory (theoretically)
- hughw 1y agoIf the CPU touches an address mapped to the GPU doesn't it fault a page into the CPU address space? I mean the program doesn't do anything special, but a page gets faulted in I believe.
- Galanwe 1y agoWhile the results look impressive, I can't help but think "yeah but had you stored an absolute value every X deltas instead of just a stream of deltas, you would have had a perfectly scalable parallel decoding"
- ashtonsix 1y agoI just did a mini-ablation study for this (prefix sum). By getting rid of the cross-block carry (16 values), you can increase perf from 19.85 to 23.45 GB/s: the gain is modest as most performance is lost on accumulator carry within the block. An absolute value every 16 deltas would undermine compression: a greater interval would lose even the modest performance gain, while a smaller interval would completely lose the compressibility benefits of delta coding. It's a different matter, although there is definitely plausible motivation for absolute values every X deltas: query/update locality (mini-partition-level). You wouldn't want to transcode a huge number of values to access/modify a small subset.
- zamadatix 1y agoI think what GP is saying is you can drop an absolute value every e.g. 8192 elements (or even orders of magnitude more if you're actually processing GBs of element) and this frees you to compute the blocks in parallel threads in a dependency free manor. The latency for a block would still bound by the single core rate, but the throughput of a stream is likely memory bound after 2-3 cores. It still hurts the point of doing delta compression, but not nearly as bad as every 16 values would. Even if one is willing to adopt such an encoding scheme, you'd still want to optimize what you have here anyways though. It also doesn't help, as mentioned, if the goal is actually latency of small streams rather than throughput of large ones.
- ashtonsix 1y agoOh right. That's sensible enough. Makes total sense to parallelise across multiple cores. I wouldn't expect a strictly linear speed-up due to contention on the memory bus, but it's not as bad as flat-lining after engaging 2-3 cores. On most AWS Graviton instances you should be able to pull ~5.5 GB/s per-core even with all cores active, and that becomes less of a bottleneck when considering you'll typically run a sequence of compute operations between memory round-trips (not just delta).
- jasonthorsness 1y ago"We achieve 19.8 GB/s prefix sum throughput—1.8x faster than a naive implementation and 2.6x faster than FastPFoR" "FastPFoR is well-established in both industry and academia. However, on our target platform (Graviton4, SIMDe-compiled) it benchmarks at only ~7.7 GB/s, beneath a naive scalar loop at ~10.8 GB/s." I thought the first bit was a typo but it was correct; the naive approach was faster than a "better" method. Another demonstration of how actually benchmarking on the target platform is important!
- coolThingsFirst 1y agoI had the opportunity(misfortune) to click on that resume and it could some aesthetic improvements. :) Fun project btw, HPC is always interesting.