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. .. toctree:: :maxdepth: 2 ---- 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: .. code-block:: glsl 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//vc_.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//CMakeLists.txt``).** The build pipeline for every shader is: .. code-block:: glslc -O -o .spv .comp xxd -i .spv | sed ... -> _spv.h The ``sed`` step renames xxd symbols to stable names (``_spv``, ``_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: .. list-table:: :header-rows: 1 * - Artifact - Location - Validates * - Shader - ``shaders/.comp`` - GLSL correctness, SPIR-V validation * - Unit test - ``tests/ops/test_.cpp`` - GPU output matches CPU reference for 10+ cases * - Benchmark - ``benchmarks/ops/bench_.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//CMakeLists.txt`` and ``vc_.cpp``. 2. Write a GLSL compute shader in ``shaders/.comp``. 3. Add the shader embedding pipeline to ``CMakeLists.txt``. 4. Implement the public API function (e.g. ``vc_``) 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_.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_.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.