parallelizing log-sum-exp I have some approximate likelihoods: $L_1, \ldots, L_n$. Each is quite expensive to calculate. They're approximate because they use random numbers. Each of them is being calculated on the same data set of size $N$. Actually, what's really being calculated are the log-likelihoods: $\ell_i$ for $i=1,\ldots,n$, not the likelihoods.
I'd like to average together these likelihoods. If each likelihood is unbiased, then so is the sample mean. This is an important requirement when using the Pseudo-marginal Metropolis-Hastings sampler, for instance.
To avoid numerical underflow, from exponentiating numbers close to $-\infty$, I'd like to use the log-sum-exp trick:
$$
\log \left( \frac{1}{n}\sum_{i} L_i\right) = m + \log  \sum_{i}\exp[\ell_i - m] - \log n
$$
Question
Typically $m$ is set to $\max(\ell_1, \ldots, \ell_n)$. However,

*

*if one is using multithreading, calculating the maximum will require more thread communication or memory or locking, and

*I don't want to waste time calculating some example/pilot likelihoods (remember, they're expensive to compute).

Is there a good rule of thumb to use as a substitute? Perhaps $m := -.5N$? I reason that, if the data are iid, and each data point likelihood is approx. $r \approx .6$, then $L_i \approx r^N$ and $\ell_i \approx N \log r \approx -.5 N$. Another piece of relevant information: I expect these $\ell_i$ to be quite left-skewed.
The perfect answer is probably problem-specific, but I was wondering if anyone had some nice anecdotes or resources.
 A: I followed @jwimberley's advice. Here is a thread pool that

*

*uses a strict lock (i.e. a std::unique_lock<std::shared_mutex>)whenever writing individual approximations to the shared std::vector (e.g. here)

*uses a strict lock (i.e. a std::unique_lock<std::shared_mutex>) whenever writing the new input parameters to the log-likelihood function or refreshing the sum to begin accumulating again (e.g. here)

*uses atomic counters to count the number of calculations that have started and finished (e.g. here) . I needed both. If you use only one counter to count the number of approximations done, say, then the last thread that should do work might finish slowly enough so that an extra thread can start erroneously.

Because the bottleneck is the sampling-based approximations---not the intra-thread communication required for summing and maximum calculations---the reading from shared memory is only loosely protected using a shared lock (i.e. a std::shared_lock<std::shared_mutex>).
When all the work is done, the the standard log-sum exp trick is used for the final calculation. This uses the maximum $m$. See here.
If you wanted to visualize the whole process as a graph: first, one thread will write the new parameter input for the likelihood. Second, in parallel all the workers will calculate their approximation to the likelihood. When each thread is finished with a likelihood approximation, they grab the mutex and write to the output std::vector. Finally, when all threads are done, only one thread processes all these numbers with log-sum-exp and spits out the one floating point.
