GPU Programming with Vulkan Columnar

This guide introduces GPU programming through the lens of Vulkan Columnar, a GPU columnar compute library built on Vulkan 1.3 compute shaders. After reading it, you will understand every design decision, shader, and dispatch in the codebase well enough to contribute.

1. Why a GPU for Columnar Data?

GPUs execute thousands of threads in lockstep, trading single-thread latency for aggregate throughput. A modern GPU can have 3,000–16,000 arithmetic units running concurrently. Each thread is simple – no branch prediction, no out-of-order execution – but collectively they deliver 10–60 TFLOPS and 1–2 TB/s of memory bandwidth. By contrast, a high-end server CPU peaks at 2–3 TFLOPS and 100–200 GB/s.

Columnar data is the ideal GPU workload:

  • Regular element size. Every element in a U32 column is exactly 4 bytes. Threads read contiguous, aligned memory; no pointer-chasing or variable-length encoding.

  • No inter-element dependencies. Filtering row i does not depend on row i+1. Arithmetic on element i is independent of element j. Perfectly data-parallel.

  • Uniform control flow. Every thread applies the same operation. No per-element if divergence (except at null boundaries, handled by masking).

The trade-off is the PCI Express bus. Data must travel from host RAM to GPU VRAM and back. PCIe Gen 4 x16 provides ~25 GB/s in each direction – slow compared to the GPU’s 1 TB/s internal bandwidth. A single GPU operation shipping data over PCIe may break even or lose to a CPU. The win comes from chained operations: filter, then cast, then sort, then reduce – all while the data stays in VRAM between dispatches. This library targets that exact pattern.

2. The Vulkan Compute Pipeline (What You Actually Need)

Vulkan is a large API. Compute-only usage strips it down to six concepts:

Instance and Device

A VkInstance binds the library to the Vulkan loader. A VkPhysicalDevice represents one GPU. A VkDevice is the logical handle for submitting work. vc_create_context handles enumeration, queue-family selection, and optional feature detection.

Shader Module

GLSL source is compiled offline by glslc into SPIR-V, a binary intermediate representation. The SPIR-V byte array is embedded in the C++ binary via xxd -i and passed to vkCreateShaderModule. This eliminates runtime compilation and file I/O.

Pipeline

A VkPipeline binds a shader module to a pipeline layout. For compute, this is a VkComputePipelineCreateInfo with one stage. Pipelines are created once and cached. See vc_device.h vc_create_compute_pipeline. The layout declares which resources (descriptor sets, push constants) the shader expects.

Descriptor Sets

These bind GPU buffers to shader binding points. Each VkWriteDescriptorSet points a layout(binding=N) in the shader to a VkBuffer. The library uses up to six SSBO bindings per operation (input data, input validity, second input, output, output validity, etc.).

Push Constants

Small (<=128 bytes) values written directly into the command buffer, readable by the shader as layout(push_constant) uniform. Used for element counts, operation codes, element sizes, and flags. No descriptor allocation required.

Command Buffers

Recorded once, submitted to a VkQueue, and waited on. Pattern: reset, begin, bind pipeline, bind descriptors, push constants, dispatch, barrier, end, submit, wait.

Vulkan Memory Allocator (VMA)

The library uses VMA instead of raw vkAllocateMemory. Call vmaCreateBuffer with VMA_MEMORY_USAGE_AUTO and let VMA choose the best heap (device-local, host-visible, etc.).

3. The GPU Memory Model

GPU memory is a hierarchy, not a flat pool:

Global Memory (VRAM / HBM)

The large pool (4–48 GB) accessible by all threads. Bandwidth is high (~1 TB/s on modern GPUs) but latency is hundreds of cycles. Every SSBO binding in this library maps to global memory.

Shared Memory

Per-workgroup scratchpad, typically 32–100 KB. Accessed at register speed. Threads within a workgroup use it to communicate via barrier(). Used in filter (prefix sum), reduce (tree reduction), elementwise (sub-32-bit widening), and join (hash table).

Registers

Per-thread storage, the fastest memory. GLSL local variables (uint a_lo) map to registers when the compiler can fit them.

Host-Visible Memory

A window of VRAM mapped into the CPU’s address space. Used for read-back: vmaInvalidateAllocation makes GPU writes visible to the CPU. The HOST_ACCESS_RANDOM_BIT flag tells VMA to keep the buffer in a host-accessible heap.

Critical optimization: memory coalescing. GPUs fetch 32–128 bytes per memory transaction. If 32 threads in a warp request 32 consecutive 4-byte words, the GPU satisfies this with one or two transactions (coalesced). If they request scattered addresses, 32 separate transactions are needed (up to 32x slowdown). All column buffers are stored as dense arrays to guarantee coalesced access.

4. Shader Design Patterns

All shaders in this library follow five rules:

  1. One workgroup = 256 threads. layout(local_size_x = 256) in;. Matches the typical warp/wavefront size (32/64) evenly.

  2. Push constants for parameters. Never use specialization constants for runtime values. Push constants change per dispatch without recompiling pipelines.

  3. SSBOs over UBOs. Storage buffers support arbitrary sizes and are the natural fit for column data. All bindings are std430.

  4. Barriers are cooperative. Every thread in a workgroup must reach a barrier() call. If some threads take an early return while others wait at the barrier, the GPU hangs. This is the most common shader bug.

  5. Validation layers in debug. VK_LAYER_KHRONOS_validation catches out-of-bounds access, mismatched pipeline layouts, and missing barriers. The debug build enables it automatically.

Example: the element-wise shader (elementwise.comp)

This is the library’s most complex shader and demonstrates several patterns:

layout(local_size_x = 256) in;
layout(std430, binding = 0) readonly buffer InBuf { uint in_data[]; };
layout(push_constant) uniform Params { uint element_count; uint op; ... };

void main() {
    uint gid = gl_GlobalInvocationID.x;
    if (gid >= params.element_count) return;

    // 64-bit arithmetic: load as (lo, hi) pairs
    uint a_lo, a_hi, b_lo, b_hi;
    load_elem(gid, false, a_lo, a_hi);
    load_elem(gid, true,  b_lo, b_hi);

    // ADD with carry chain
    uint s = a_lo + b_lo;
    uint r_lo = s;
    uint r_hi = a_hi + b_hi + ((s < a_lo) ? 1u : 0u);

    store_elem(gid, r_lo, r_hi);
}

Key design decisions in this shader:

Sub-32-bit widening via shared memory. U8, U16, I8, and I16 columns are stored as packed arrays (4 or 2 elements per u32 word). The shader reads packed data in phase 1 (“widen”), expanding each byte or half-word into a full u32 in shared memory. All 256 workgroup threads participate in the barrier. Phase 2 operates on widened values. Phase 3 packs results back (only for sub-32-bit output, e.g. U8+U8->U8). For U32 or U64 output from sub-32-bit input (e.g. U8 comparison produces U32 mask), phase 3 is skipped entirely.

Signed widening. I8 and I16 values are sign-extended during widening: if the high bit is set, the upper 24 or 16 bits are filled with 1s. This is controlled by an is_signed push constant. Comparisons use int() for signed comparison; arithmetic operates on widened unsigned values (modular arithmetic is correct).

Single-workgroup limit for sub-32-bit. The shared memory array is shared uint smem_lhs[256] – exactly one workgroup of elements. The C++ side rejects sub-32-bit operations with more than 256 elements. This is documented in api-reference.rst and will be lifted in v2 with workgroup-offset support.

5. Parallel Algorithms in the Library

Filter: Stream Compaction via Blelloch Scan

vc_filter is implemented as a three-pass Blelloch parallel prefix sum.

  1. Pass 1 (count valid): Each thread checks one mask element, writes 1 or 0 to a scratch buffer. Workgroup-level reduction via subgroup operations (subgroupAdd) when VK_KHR_shader_subgroup_arithmetic is available, falling back to shared-memory tree reduction.

  2. Pass 2 (exclusive scan): Builds a prefix sum of the counts. The scan gives each valid element its destination index in the compacted output.

  3. Pass 3 (scatter): Each thread with a valid mask element copies its data element to the output at the prefix-sum address.

The algorithm is work-efficient (O(n) total operations) and performs ~29x faster than single-threaded CPU at 1M elements – see performance-optimizations.rst.

Sort: LSD Radix Sort

vc_sort implements a least-significant-digit radix sort in four passes per 32-bit element (eight for 64-bit). Each pass:

  1. Histogram: Each thread counts occurrences of each radix digit (0-255) in shared memory, then atomically adds to a global histogram.

  2. Prefix-sum histogram: The CPU computes the exclusive prefix sum of the histogram. (A future optimization will move this to the GPU.)

  3. Reorder: Each thread reads its element, extracts the digit, and writes to output[histogram[digit] + local_offset].

Floating-point columns are bit-flipped (sign-bit complement) so that the unsigned radix sort produces correct signed/float ordering.

Reduce: Tree Reduction

vc_reduce performs sum, min, max, mean, count, first, and last operations via a workgroup-local tree reduction:

  • Each thread loops over stride-sized chunks of data (to handle inputs larger than one workgroup).

  • A shared-memory binary tree reduction collapses 256 values to 1 per workgroup.

  • Multiple workgroups write their partial results to an intermediate buffer.

  • The CPU merges partial results in O(num_workgroups) time.

Group-By: Sort + Segment Reduce

vc_groupby sorts the key-value pair by key (GPU radix sort), then uses a GPU shader to find segment boundaries and reduce each segment. The multi-WG merge runs on the CPU as a simpler first implementation.

Join: Shared-Memory Hash Join

vc_inner_join loads the right key column into shared memory, builds an open-addressing hash table with MurmurHash3, then probes with left keys. The current implementation is limited to 1,664 right-side keys per workgroup (join_hash.comp: 2,048 shared u32 / 3 slots per entry). A future global hash table extension will partition on hash prefix for larger tables.

6. Cross-Vendor Architecture

The library runs on any GPU with a Vulkan 1.3 driver - AMD, NVIDIA, Intel, Apple Silicon (MoltenVK), and software renderers (lavapipe). Four mechanisms ensure this:

Feature Detection

At vc_create_context, the library queries optional features:

  • VK_KHR_push_descriptor – enables vkCmdPushDescriptorSet, eliminating per-dispatch descriptor pool allocation.

  • VK_KHR_shader_subgroup_arithmetic – provides subgroupAdd and friends for fast workgroup-wide reductions.

  • Subgroup size query (VkPhysicalDeviceSubgroupProperties).

Results are stored in VcContext::has_push_descriptors and has_subgroup_arithmetic. Operations check these flags and take the accelerated path when available, falling back to portable implementations.

No Vendor ID Hardcodes

VcContext does not store a vendor ID. Shaders use portable GLSL with no vendor-specific extensions. When an AMD-specific optimization is applied (e.g. subgroup-based filter pass 1), it is guarded by a feature check, not if (vendor == AMD).

Single-Workgroup Dispatch

All operations dispatch one-dimensional workgroups (vkCmdDispatch(wgs, 1, 1)). No multi-dimensional grids, no workgroup ID-dependent logic that could expose scheduling differences.

lavapipe as Minimum Bar

Every change is tested against lavapipe (Vulkan software renderer). If it passes there, it will pass on any conformant Vulkan driver.

7. Library Architecture

```mermaid graph TD

A[Polars / DataFusion / Spark] –> B[C ABI] B –> C[vc_arith / vc_filter / vc_sort / …] C –> D[dispatch_elementwise / vc_submit_and_wait] D –> E[Vulkan Queue] E –> F[GPU] D –> G[VMA] C –> H[SPIR-V shaders] H -. embedded via xxd -i .-> C

```

The architecture has three layers:

C ABI (``include/vulkan_columnar/vc_context.h``). Every function takes a VcContext* as its first argument and returns opaque handles (VcColumn*, VcGroupByResult*). No C++ types, no exceptions, no STL in the public surface. This makes the library bindable from Rust, Python (cffi), Go (cgo), and Zig.

Operation Layer (``src/ops/<name>/vc_<name>.cpp``). Each operation is a single translation unit with:

  • A PipelineCache struct holding VkShaderModule, VkPipeline, and VkDescriptorSetLayout objects. Created once, reused across calls.

  • A dispatch function that allocates scratch buffers, binds descriptors, sets push constants, dispatches workgroups, inserts barriers, and reads results.

  • Public functions that validate inputs and call the dispatch function.

Core Layer (``src/core/vc_context.cpp``). vc_create_context, vc_create_column, vc_read_column, and vc_export_arrow. Column buffers are VMA-allocated with VK_BUFFER_USAGE_STORAGE_BUFFER_BIT | TRANSFER_SRC | TRANSFER_DST. Host data is uploaded via staging buffer (vkCmdCopyBuffer).

Shared Helpers (``include/vulkan_columnar/vc_device.h``). Static inline functions: vc_create_shader_module, vc_create_compute_pipeline, vc_submit_and_wait, vc_begin_command_buffer, vc_end_command_buffer, vc_allocate_descriptor_set, vc_bind_descriptor_binding. Every operation links against this header; no duplicated Vulkan boilerplate.

Shader Embedding (``src/ops/<name>/CMakeLists.txt``). The build pipeline for every shader is:

glslc -O -o <name>.spv <name>.comp
xxd -i <name>.spv | sed ... -> <name>_spv.h

The sed step renames xxd symbols to stable names (<name>_spv, <name>_spv_len) instead of path-derived names. The C++ code includes the generated header and passes the byte array to vc_create_shader_module.

8. Optimization Principles

Memory Bandwidth is the Bottleneck

Almost every operation in this library is memory-bound, not compute-bound. A U32 addition has one arithmetic op per 12 bytes of I/O (read A, read B, write result). At 1 TB/s bandwidth, that is ~80 billion operations/second – far below the GPU’s compute capacity. Optimizations focus on:

  • Reducing transfers: chaining operations in VRAM.

  • Coalescing: contiguous array access.

  • Avoiding atomics: shared-memory reduction followed by a single global write, instead of per-element global atomics.

Descriptor Overhead Matters

vkAllocateDescriptorSets + vkUpdateDescriptorSets costs ~0.01 ms per dispatch. With hundreds of dispatches per operation (sort uses 4–8 radix passes), this adds up. VK_KHR_push_descriptor replaces pool allocation with a command-buffer call, saving 10–30%.

Pipeline Reuse

vc_filter_pipeline_cache_create creates shader modules and pipelines once. Subsequent vc_filter calls bind the cached pipelines. The cache is stored in VcContext and destroyed at context teardown.

Prefetching

Where possible, shaders load data into shared memory early (phase 1 of elementwise), then compute in phase 2. This overlaps global memory latency with computation across threads.

9. Testing and Benchmarking

Every operation has three artifacts:

Artifact

Location

Validates

Shader

shaders/<name>.comp

GLSL correctness, SPIR-V validation

Unit test

tests/ops/test_<name>.cpp

GPU output matches CPU reference for 10+ cases

Benchmark

benchmarks/ops/bench_<name>.cpp

Wall time, kernel time, bandwidth, speedup vs CPU

Tests always compare GPU output to CPU reference. They cover valid inputs, null handling, edge cases (zero-length, single-element, dtype mismatch), and error returns. See tests/ops/test_elementwise.cpp for 32 tests spanning all 10 dtypes, arithmetic, comparison, null ops, and boolean ops.

Benchmarks report four numbers:

  • Wall time: clock_gettime around the Vulkan submit+wait (includes PCIe transfer for single operations).

  • Kernel time: GPU timestamp queries (vkGetQueryPoolResults).

  • Bandwidth: bytes_read + bytes_written / kernel_time.

  • CPU reference: single-threaded std:: equivalent.

The 2x speedup requirement applies to chained operations only (data stays in VRAM between dispatches). Single-operation speedup is allowed to be modest due to PCIe tax.

Vulkan validation layers are enabled in debug builds. A validation error is a broken build. The layer prints to stderr; tests fail if any error appears.

ASan + UBSan must be clean: -fsanitize=address,undefined in debug.

clang-tidy enforces modernize-*, bugprone-*, performance-*, readability-* rules. Clang-format enforces Chromium style at 100 columns.

10. Contributing a New Operation

Use src/ops/filter/ as the canonical template. Steps:

  1. Create src/ops/<name>/CMakeLists.txt and vc_<name>.cpp.

  2. Write a GLSL compute shader in shaders/<name>.comp.

  3. Add the shader embedding pipeline to CMakeLists.txt.

  4. Implement the public API function (e.g. vc_<name>) with input validation.

  5. Implement the dispatch function: pipeline creation (reuse across calls), scratch buffer allocation, descriptor binding, push constants, dispatch, barrier, read-back.

  6. Write tests in tests/ops/test_<name>.cpp. Test at least: empty input, single element, maximum single-WG size, multi-WG, nulls (if applicable), dtype mismatch, and error returns.

  7. Write benchmarks in benchmarks/ops/bench_<name>.cpp.

  8. Update docs/api-reference.rst with: the API function signature, Status line, Vulkan primitives used, algorithm description, and edge case behavior.

  9. Update docs/performance-optimizations.rst when optimized.

  10. Run ctest --output-on-failure before submitting.

The vc_device.h header provides all Vulkan boilerplate. Avoid raw vkCreate* calls; use the helpers. Every dispatch pattern is demonstrated in an existing operation – pick the closest match.