Has any work/thought been given to parallelizing the sampler itself? For instance, assuming I shuffle gradient evaluation out of Stan to somewhere else (with e.g. MPI) then the sampler itself presents some overhead (10s to 100s of ms), especially for larger numbers of parameters (1M+). Is there a …

[image] nhuurre: you need to know the previous gradient before you can decide where to evaluate the next gradient Thanks, I was wondering more in terms of parallelizing the symplectic integrator over unconstrained parameters or perhaps more general issues such as memory allocations if there w…

[image] maedoc: I was wondering more in terms of parallelizing the symplectic integrator over unconstrained parameters Symplectic integrators are also sequential up to the gradient evaluation, but that just reduces to parallelizing the target density function. [image] maedoc: For instanc…

[image] betanalpha: There’s a decent amount of allocation in the dynamic trajectory evaluation, but the actual memory footprint at any give time is quite small. The cost of those memory allocations is unlikely to substantial relative to the gradient evaluations themselves, We were just discus…

There’s some relevant discussion in a systems paper published a while ago: ispass19.pdf 396.85 KB The paper shows that Stan models become L3 cache bound as the number of chains increases. The paper also proposes prefetching-based fixes to this problem, but I…

Thanks, @Red-Portal . I hadn’t seen this paper, but I’ll take a look. I’m not surprised we’re L3 cache bound. One of the things that’s improved over time is that we can now use shared data with multi-threading rather than copying data in multiple processes. I’m not entirely sure how much that’s f…

[image] betanalpha: but the actual memory footprint at any give time is quite small. I think when we start talking about 1M+ parameters like @maedoc is saying above there are no small footprints :) It’s def possible to implement a small local allocator for nuts. The most bare bones version w…

[image] betanalpha: Symplectic integrators are also sequential Since we are tossing ideas around, I should point out being sequential can be orthogonal to parallelism. For numerical integration there is parallel-in-time (e.g. Parallel-in-Time (PinT) Algorithms · GitHub ), with parareal being t…

[image] stevebronder: I think when we start talking about 1M+ parameters like @maedoc is saying above there are no small footprints :) Sure, but one also has to consider the relative footprint compared to other computations. Allocating memory for vectors will a million elements will certainl…

[image] betanalpha: almost all of which are built from sequential updates that don’t afford much opportunity for parallelization beyond the gradient evaluation. Other than the fact that MCMC overall is embarrassingly parallel. Run N chains and get N times the expected ESS. The serial bottl…

Parallelizing the sampler (not the model)

Developers

nhuurre February 3, 2022, 4:28pm 2

The HMC sampler is inherently sequential, you need to know the previous gradient before you can decide where to evaluate the next gradient. Only a little bit of parallelism is possible, the most recent discussion is in

Topic		Replies	Views
Evaluating parallelization performance Developers	23	2191	October 1, 2019
Parallel dynamic HMC merits Developers features	41	3869	March 27, 2026
Within-chain parallelization idea (maybe crazy) Developers	35	3367	February 24, 2022
What is the main bottleneck in parallelizing Stan? Developers	6	1037	September 27, 2019
Multicore Speedups are different between models Algorithms	25	5092	September 11, 2017

Parallelizing the sampler (not the model)

Related topics