← All repos

gpu_bitonic_sort

Browse cluster: Functional Programming & Type Theory
47commits
1contributors
3languages

Tech stack & purpose

GPU Bitonic Sort is a GPU parallel evaluator for recursive functional programs, demonstrated by implementing the bitonic sort algorithm as pure recursive functions on binary trees. The project serves as a runtime test case for a future compiler, where the algorithm is fixed and the GPU implementation must compute it exactly as written without algorithmic modifications. It's built in JavaScript, C, and CUDA, with the JavaScript version providing a clear reference implementation, the C version offering a single-threaded baseline (~2500ms for depth 20), and the CUDA version achieving approximately 64x speedup (~38ms for depth 20 on an RTX 4090). The GPU evaluator uses a SEED / GROW / WORK architecture running as a single cooperative kernel with grid synchronization, mapping independent recursive calls marked `PARALLEL` to concurrent GPU execution across blocks and threads.

Languages

Cuda
88.3%
C
8.0%
JavaScript
3.6%

Contributors