Normally I would do this in C++. I stumbled across OpenAI Triton on the GPU MODE discord. Curious about it, I thought this would be a good time to try it out.
The Triton compiler does automatic optimizations that usually a CUDA programmer would do by hand. So I decided to write these algorithms in Triton to learn more about it. I will explore triton and test the runtime of the parallel algorithms with their single-threaded counterpart on the CPU.
I am simplifying the runtimes for readability, in reality they are much more complex. For further reading check out this paper for parallel algorithms
- Finding the End of a Linked List
- Runtime:
$O(log(n))$ (paper) - Results: End Of Linked List
- Run:
python src/End_of_Linked_List.py
- Runtime:
- Vector sum (e.g.
sum([1,2,3,4,5]) = 15)- Runtime:
$O(log(n))$
- Runtime:
- pytorch
- Quick install with
pip install pytorch
- Quick install with
- triton
- Quick install with
pip install triton
- Quick install with
source code is located in src/[algorithm].py