trixi-framework / trixi-framework/TrixiParticles.jl
Parallelized `update_system_buffer!`
Nobody has claimed this yet.
- Dominant language
- Julia
- Stars
- 83
- Forks
- 24
- Avg merge
- 8d 18h
- Merged PRs (30d)
- 3
Description
In #773, we use the findall function in update_system_buffer! to filter out the active indices. However, parallelizing findall efficiently is challenging. For CUDA vectors (see here), there is a “semi-parallel” version: cumsum is computed serially (?), and then the active indices are filtered in parallel. In the minimal working example below, I broke this down and benchmarked it. On the CPU, findall is much faster in serial, but my_findall_cpu should scale better in parallel. For now, I would keep findall in #773. This issue is just a reminder to possibly look for a parallel version of cumsum in the future.
(@efaulhaber please add or correct anything I missed or didn’t express clearly.)
using KernelAbstractions
using Metal
using Adapt
using Random
using Polyester
using BenchmarkTools
@kernel function mykernel!(active, active_indices, prefix)
i = @index(Global)
if active[i] == true
active_indices[prefix[i]] = i
end
end
function my_findall(active_indices, active)
prefix = cumsum(active)
# Afterwards used to iterate only over computed indices: `active_indices[1:total]`
total = Metal.@allowscalar prefix[end]
mykernel!(backend)(active, active_indices, prefix, ndrange=length(active))
return total
end
function my_findall_cpu(active_indices, active)
prefix = cumsum(active)
# Afterwards used to iterate only over computed indices: `active_indices[1:total]`
total = prefix[end]
Polyester.@batch for i in eachindex(active)
if active[i] == true
active_indices[prefix[i]] = i
end
end
return total
end
n = 100_000_000
backend = MetalBackend()
active_indices_cpu = rand(Int, n)
active_indices = Adapt.adapt(backend, active_indices_cpu)
Random.seed!(1)
active_cpu = rand(UInt32.(0:1), n)
active = Adapt.adapt(backend, active_cpu)
active_bool = map(x -> x == true, active)
@benchmark my_findall($active_indices, $active)
@benchmark my_findall_cpu($active_indices_cpu, $active_cpu)
f(x) = x == true
@benchmark findall($f, $active)
@benchmark findall($f, $active_cpu)
@benchmark findall($active_bool)
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with the update_system_buffer! use of findall described in issue #773, then run the provided Julia MWE and its benchmarks for my_findall, my_findall_cpu, and findall. Determine whether a parallel cumsum approach is viable and define completion by identifying a faster parallel implementation that preserves the active-index filtering behavior.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- julia
- Domain
- performance
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100