trixi-framework / trixi-framework/TrixiParticles.jl

Parallelized `update_system_buffer!`

Open
#810 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

discussion gpu performance
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

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.