# String Distance Calculations on GPU
**URL:** https://discourse.julialang.org/t/string-distance-calculations-on-gpu/57549
**Category:** Performance
**Tags:** gpu, cuda, distances
**Created:** [March 19, 2021, 3:32pm UTC](https://discourse.julialang.org/t/string-distance-calculations-on-gpu/57549 "2021-03-19T15:32:03Z")
**Posts on this page:** 5
**Page:** 1
### Author:  [@mthelm85](https://discourse.julialang.org/u/mthelm85)
#### Post date: [March 19, 2021, 3:32pm UTC](https://discourse.julialang.org/t/string-distance-calculations-on-gpu/57549/1 "2021-03-19T15:32:03Z")
How difficult would it be to do this in Julia?
It looks like it might be possible to do this with PyTorch:
> **[GitHub - 1ytic/pytorch-edit-distance: Levenshtein edit-distance on PyTorch...](https://github.com/1ytic/pytorch-edit-distance)**
>
> Levenshtein edit-distance on PyTorch and CUDA. Contribute to 1ytic/pytorch-edit-distance development by creating an account on GitHub.
And here are some papers on the topic:
[https://www.researchgate.net/publication/300042590\_Using\_GPUs\_to\_Speed-Up\_Levenshtein\_Edit\_Distance\_Computation](https://www.researchgate.net/publication/300042590_Using_GPUs_to_Speed-Up_Levenshtein_Edit_Distance_Computation)
> **[A parallel approximate string matching under Levenshtein distance on graphics...](https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5634649/)**
>
> Approximate string matching with k-differences has a number of practical applications, ranging from pattern recognition to computational biology. This paper proposes an efficient memory-access algorithm for parallel approximate string matching with...
I currently use [StringDistances.jl](https://github.com/matthieugomez/StringDistances.jl) but I occasionally need to do comparisons across really large data sets so I’ve started looking into the possibility of accelerating these calculations on a GPU.
Has anyone else explored this? I’m not sure I would know where to start to be honest but I would certainly be willing to invest some time into this.
Is it just a matter of finding a CUDA implementation and then writing a Julia wrapper around it?
---
### Author:  [@Soren](https://discourse.julialang.org/u/Soren)
#### Post date: [February 13, 2022, 3:20pm UTC](https://discourse.julialang.org/t/string-distance-calculations-on-gpu/57549/2 "2022-02-13T15:20:31Z")
Hi!
Did you manage to find a good solution? I’m working on a similar problem.
Soren
---
### Author:  [@mthelm85](https://discourse.julialang.org/u/mthelm85)
#### Post date: [February 13, 2022, 3:33pm UTC](https://discourse.julialang.org/t/string-distance-calculations-on-gpu/57549/3 "2022-02-13T15:33:49Z")
Unfortunately I did not achieve a GPU-based solution. The solution I settled on involved building a vantage point tree with one data set ([VPTrees.jl](https://github.com/JuliaNeighbors/VPTrees.jl)) and then looping through the second data set in parallel to search for matches. This has worked well enough for me so I haven’t explored any alternatives. I would still be very interested in working on a GPU solution though…
---
### Author:  [@ToucheSir](https://discourse.julialang.org/u/ToucheSir)
#### Post date: [February 13, 2022, 9:16pm UTC](https://discourse.julialang.org/t/string-distance-calculations-on-gpu/57549/4 "2022-02-13T21:16:47Z")
It seems the most straightforward (but not easy) approach would be to port the kernels in [https://github.com/1ytic/pytorch-edit-distance/blob/master/edit-distance.cu](https://github.com/1ytic/pytorch-edit-distance/blob/master/edit-distance.cu) to CUDA.jl.
---
### Author:  [@maxfreu](https://discourse.julialang.org/u/maxfreu)
#### Post date: [February 17, 2022, 3:38pm UTC](https://discourse.julialang.org/t/string-distance-calculations-on-gpu/57549/5 "2022-02-17T15:38:42Z")
Actually it’s not that hard to translate the stuff. The good thing is that in julia you just need half the code. Just go through it line by line, remove the type annotations, edit the indexing appropriately to account for 0/1 based indexing and take care to get the block/thread indices right. Then go ahead and adjust the data layout for column major, which means that you have to reverse the indexing order. After you have the first pass running, you can adapt one based indexing and try to make it more “julian”.