# Threaded AD

**URL:** <https://discourse.mc-stan.org/t/threaded-ad/3697>\
**Category:** Developers\
**Tags:** math\
**Created:** [March 27, 2018, 8:25pm UTC](https://discourse.mc-stan.org/t/threaded-ad/3697 "2018-03-27T20:25:47Z")\
**Posts on this page:** 20\
**Page:** 2

<div class="post-metadata">

**Author:** ![ahartikainen](https://yyz2.discourse-cdn.com/flex030/user_avatar/discourse.mc-stan.org/ahartikainen/32/321_2.png) [@ahartikainen](https://discourse.mc-stan.org/u/ahartikainen)\
**Post date:** [April 1, 2018, 4:00pm UTC](https://discourse.mc-stan.org/t/threaded-ad/3697/21 "2018-04-01T16:00:40Z")

</div>

At least with PyStan one failing process will fail the other ones.

Also multiprocessing uses pickle with “wrong” protocol, so it will fail with large data.

Also multiprocessing needs special attention which is not a good thing.

In short cpu/gpu handling should go to C++ side and filesystem stuff to Python side.

---

<div class="post-metadata">

**Author:** ![Bob\_Carpenter](https://yyz2.discourse-cdn.com/flex030/user_avatar/discourse.mc-stan.org/bob_carpenter/32/9230_2.png) [@Bob\_Carpenter](https://discourse.mc-stan.org/u/Bob_Carpenter)\
**Post date:** [April 1, 2018, 6:18pm UTC](https://discourse.mc-stan.org/t/threaded-ad/3697/22 "2018-04-01T18:18:05Z")

</div>

> [@wds15](#):
>
> We can go with just async and chunk the incoming work into as many threads as we think at once.

Isn’t this controlled by the users’ invocation of `map_rect`? That is, aren’t all the map jobs run in parallel?

> [@wds15](#):
>
> map\_rect\_async is a great start.

I think `map_rect_concurrent` or `map_rect_threaded` would be a better name, as it’s not fully asynchronous. We’re waiting on a future at some point.

> [@wds15](#):
>
> Yes, we can also pack parameters in the lambda as long as these are just kept as references there.

The algorithms need to know what the parameters are, at least the `ode_integrate` does in order to be able to create the coupled system. How do we do that with closure-bound parameters?

> [@wds15](#):
>
> Juggling all these branches is tedious

Yup. I usually just wind up with multiple copies of `cmdstan` floating around, then never know where to find the one I want since I’m not used to multiple copies.

> [@wds15](#):
>
> I haven’t seen any noticeable slowdowns yet. We simply have an AD tape per thread. All what the C++ implementation has to do is to use the thread specific AD tape for the var creations - that’s it.

That’s all it ever did, but there used to be a pretty big slowdown just for doing that.

> [@wds15](#):
>
> What would be even more elegant is to create in the sub-threads operands\_and\_partials and then the build operation is called in the main thread (a delayed call of the build function).

Yes, and I hope we get there in the design. I think getting the API right and picking the low hanging fruit first is the right strategy for moving forward.

> [@wds15](#):
>
> I think we should replace the map\_rect\_serial with the asynchronous one.

I would prefer to have this configurable, too. We want people who run four parallel chains in parallel on a four-core machine to not also try to multi-thread four ways within each of those chains.

> [@wds15](#):
>
> detect Apples clang and then if-def-out the asynchronous thing

Sounds like the right thing to do.

> [@wds15](#):
>
> Right now the number of threads is controlled over an environment variable STAN\_THREADS. This needs to be set and it controls the number of threads which are spwaned at most simultaneously.

Is the idea that if we have only `STAN_THREADS = 4` and we have a `map_rect` call with 20 jobs, we make sure we only run 4 threads at a time?

> [@wds15](#):
>
> threaded AD was long thought to be impossible

Not at all. I designed for this from the very beginning. The reason we never turned it on before is that there wasn’t an easy way to do multi-threading cross-platform before C++11, we didn’t have the `map_rect` design with all the back-end work you did on a parallelizable function, and we were seeing big slowdowns while running multi-threaded. Then when I saw thread local was a thing in C++11 along with multi-threading, I made [this issue](https://github.com/stan-dev/math/issues/551) before I really knew the details for C++11. Sebastian then sorted it all out!

> [@ariddell](#):
>
> Models are not threadsafe.

Actually, the models are threadsafe now other than the line number counter. So that’s going to have to be made thread local, too, if we want reasonable error messages. If there is negligible overhead on this, then no big deal.

I’d still like all the thread-local declarations to be conditional on running multi-threaded code unless we can show there’s very low overhead to making thread-local declarations.

> [@wds15](#):
>
> if I compile things with -O0 then things work! Starting with -O1 I am getting segfaults

This is often a sign that you’re doing something like making access to illegal memory. The higher optimization levels are much better at reusing memory layout.

> [@wds15](#):
>
> mozilla licensed…no idea if that is ok or not

I’d rather avoid MPL if possible, as it’s a bit more restrictive than BSD.

> [@wds15](#):
>
> the motivation to make stan model classes thread safe?

If they’re not, running multi-threaded won’t work. They’ve been kept immutable after construction with one exception I’m aware of other than the line number.

> [@wds15](#):
>
> The branch now compiles and runs with g++ and clang++.

That’s great news.

> [@wds15](#):
>
> Our remaining code-base then needs to access the stack instead of using ChainableStack:: as prefix, we now just use ChainableStack::context(). as prefix.

This is a better approach to singletons in C++11 anyway. I’ve been meaning to reconfigure everything in math to do this anyway. Does the thread local work on local function static variables?

> [@wds15](#):
>
> So the extra function call is likely eliminated from the compiler such that there is no overhead incurred

The compilers are very good at inlining simple function calls.

> [@ariddell](#):
>
> there’s a lot more operating-system overhead associated with launching a new process than launching a new thread.

Absolutely. Multiple threads are way better when possible.

> [@wds15](#):
>
> There maybe additional overhead, but one gains a huge plus in terms of robustness as any failure will only affect a given process, but not all threads.

Exceptions that aren’t caught or seg faults are going to cause unrecoverable crashes in whatever we do unless we start engineering for failover.

---

<div class="post-metadata">

**Author:** ![wds15](https://yyz2.discourse-cdn.com/flex030/user_avatar/discourse.mc-stan.org/wds15/32/908_2.png) [@wds15](https://discourse.mc-stan.org/u/wds15)\
**Post date:** [April 2, 2018, 7:30am UTC](https://discourse.mc-stan.org/t/threaded-ad/3697/23 "2018-04-02T07:30:49Z")

</div>

> [@Bob\_Carpenter](#):
>
> Isn’t this controlled by the users’ invocation of map\_rect? That is, aren’t all the map jobs run in parallel?

The way I am suggesting to implement this new `map_rect_concurrent` is to divide the N jobs from the user into T chunks. All T chunks are then send of to be calculated in parallel at once using the async facility. So N will usually be a large number N \>\> T and T is something close to the number of cores.

> [@Bob\_Carpenter](#):
>
> The algorithms need to know what the parameters are, at least the ode\_integrate does in order to be able to create the coupled system. How do we do that with closure-bound parameters?

Like usual: Using the type of the variable. We can refer to `var` instances in other threads as long as we just read from them. That works fine.

> [@Bob\_Carpenter](#):
>
> I would prefer to have this configurable, too. We want people who run four parallel chains in parallel on a four-core machine to not also try to multi-thread four ways within each of those chains.

But do we really need to make it a compile time choice? What I am proposing is to make this a runtime choice. So if `STAN_THREADS` is not defined or is set to \<=1, then only a single thread will ever run (so no sub-threads). Whenever `STAN_THREADS` \> 1 we would start to queue multiple threads and run things concurrently. I haven’t noticed any slowdowns - and we should check that thoroughly. However, if we can avoid to keep a serial and a concurrent version around, we should just go with the concurrent version. Makes maintenance easier.

> [@Bob\_Carpenter](#):
>
> Is the idea that if we have only STAN\_THREADS = 4 and we have a map\_rect call with 20 jobs, we make sure we only run 4 threads at a time?

Correct.

> [@Bob\_Carpenter](#):
>
> Then when I saw thread local was a thing in C++11 along with multi-threading, I made this issue before I really knew the details for C++11. Sebastian then sorted it all out!

All I did is to find out what others do here. The `thread_local` thing is really magic and having seen some of the thread-nightmare codes of others I think there was a good reason to wait until C++11 brought all these wonderful high-level facilities (despite their limitations).

> [@Bob\_Carpenter](#):
>
> This is a better approach to singletons in C++11 anyway. I’ve been meaning to reconfigure everything in math to do this anyway. Does the thread local work on local function static variables?

Yes, the code right now relies on a thread local variable declared as static inside a static function. This is what seems to work for g++ and clang++.

As discussed, let me file a pull with the threaded AD stuff first. Once we get that merged we can turn `map_rect_serial` into `map_rect_concurrent`.

---

<div class="post-metadata">

**Author:** ![sakrejda](https://yyz2.discourse-cdn.com/flex030/user_avatar/discourse.mc-stan.org/sakrejda/32/845_2.png) [@sakrejda](https://discourse.mc-stan.org/u/sakrejda)\
**Post date:** [April 2, 2018, 8:31pm UTC](https://discourse.mc-stan.org/t/threaded-ad/3697/24 "2018-04-02T20:31:34Z")

</div>

> [@wds15](#):
>
> having seen some of the thread-nightmare codes of others I think there was a good reason to wait until C++11 brought all these wonderful high-level facilities (despite their limitations).

It’s not _that_ bad :)

---

<div class="post-metadata">

**Author:** ![Bob\_Carpenter](https://yyz2.discourse-cdn.com/flex030/user_avatar/discourse.mc-stan.org/bob_carpenter/32/9230_2.png) [@Bob\_Carpenter](https://discourse.mc-stan.org/u/Bob_Carpenter)\
**Post date:** [April 6, 2018, 7:47pm UTC](https://discourse.mc-stan.org/t/threaded-ad/3697/25 "2018-04-06T19:47:10Z")

</div>

> [@wds15](#):
>
> The way I am suggesting to implement this new map\_rect\_concurrent is to divide the N jobs from the user into T chunks. All T chunks are then send of to be calculated in parallel at once using the async facility.

That should be reasonable. The only cocnern is load balancing if one chunk winds up taking longer than others.

> [@wds15](#):
>
> We can refer to var instances in other threads as long as we just read from them. That works fine.

So you mean walking over the expression graph in the AST and fishing out any uses of variables and building up a container of those automatically to pass in?

> [@wds15](#):
>
> But do we really need to make it a compile time choice? What I am proposing is to make this a runtime choice. So if STAN\_THREADS is not defined or is set to \<=1, then only a single thread will ever run (so no sub-threads).

That’s great. I just saw an environment variable and thought it’d be static.

> [@wds15](#):
>
> The thread\_local thing is really magic

That’s one of the reasons the autodiff code’s set up the way it is. Back when we started Stan, I thought multi-threading would be very important. We just never had the `map_rect` infrastructure or portable C++11 threading lib before to make it useful.

> [@sakrejda](#):
>
> It’s not that bad :)

Posix threads for serious applications? It’s pretty rough. It’s like numerical analysis in that it’s full of fussy side conditions and it’s like going to higher dimensions in that none of your single-threaded intuitions hold any more. Oh, and it’s really really really hard to trap and debug race conditions and other memory corruptions.

---

<div class="post-metadata">

**Author:** ![sakrejda](https://yyz2.discourse-cdn.com/flex030/user_avatar/discourse.mc-stan.org/sakrejda/32/845_2.png) [@sakrejda](https://discourse.mc-stan.org/u/sakrejda)\
**Post date:** [April 6, 2018, 9:07pm UTC](https://discourse.mc-stan.org/t/threaded-ad/3697/26 "2018-04-06T21:07:55Z")

</div>

> [@Bob\_Carpenter](#):
>
> Posix threads for serious applications?

I was thinking a single threadpool for limited applications like we currently are planning with futures.

---

<div class="post-metadata">

**Author:** ![wds15](https://yyz2.discourse-cdn.com/flex030/user_avatar/discourse.mc-stan.org/wds15/32/908_2.png) [@wds15](https://discourse.mc-stan.org/u/wds15)\
**Post date:** [April 7, 2018, 7:27am UTC](https://discourse.mc-stan.org/t/threaded-ad/3697/27 "2018-04-07T07:27:25Z")

</div>

> [@Bob\_Carpenter](#):
>
> So you mean walking over the expression graph in the AST and fishing out any uses of variables and building up a container of those automatically to pass in?

Uhm… I think the answer is yes, but I am not sure. To my understanding if you pass into sub-threads `const var&` then you will be safe. Thus, you can read in the sub-threads from an AD stock of the main process, but not more.

> [@Bob\_Carpenter](#):
>
> That’s great. I just saw an environment variable and thought it’d be static.

No, static makes no sense here. We should probably go one step further and define a value of “0” to imply the use of all available cores. Once the thread AD pull is in, I will file the `map_rect` in a threaded version.

> [@Bob\_Carpenter](#):
>
> That’s one of the reasons the autodiff code’s set up the way it is. Back when we started Stan, I thought multi-threading would be very important. We just never had the map\_rect infrastructure or portable C++11 threading lib before to make it useful.

Yeah. It is funny that I had to embark on MPI to get a facility which works splendid with threads. Nice “side-product” which I never thought of before.

> [@sakrejda](#):
>
> I was thinking a single threadpool for limited applications like we currently are planning with futures.

We are not going for a threadpool to start with. A threadpool will probably be a good thing to implement at a later point. For the moment being I am suggesting to go with the `async` facility of C++11. What you get exactly with that is compiler/platform specific and is not under our control.

---

<div class="post-metadata">

**Author:** ![sakrejda](https://yyz2.discourse-cdn.com/flex030/user_avatar/discourse.mc-stan.org/sakrejda/32/845_2.png) [@sakrejda](https://discourse.mc-stan.org/u/sakrejda)\
**Post date:** [April 7, 2018, 11:28am UTC](https://discourse.mc-stan.org/t/threaded-ad/3697/28 "2018-04-07T11:28:19Z")

</div>

> [@wds15](#):
>
> We are not going for a threadpool to start with. A threadpool will probably be a good thing to implement at a later point

In no way am I suggesting complicating the current PR. I’ve implemented a threadpool a few times and it’s something I can do later to replace futures later.

---

<div class="post-metadata">

**Author:** ![wds15](https://yyz2.discourse-cdn.com/flex030/user_avatar/discourse.mc-stan.org/wds15/32/908_2.png) [@wds15](https://discourse.mc-stan.org/u/wds15)\
**Post date:** [April 7, 2018, 5:17pm UTC](https://discourse.mc-stan.org/t/threaded-ad/3697/29 "2018-04-07T17:17:18Z")

</div>

Threading just got merged, so you can try it for PyStan.

---

<div class="post-metadata">

**Author:** ![ariddell](https://avatars.discourse-cdn.com/v4/letter/a/57b2e6/32.png) [@ariddell](https://discourse.mc-stan.org/u/ariddell)\
**Post date:** [April 7, 2018, 6:36pm UTC](https://discourse.mc-stan.org/t/threaded-ad/3697/30 "2018-04-07T18:36:13Z")

</div>

Can you point me to the PR # or the commit? I didn’t spot it immediately.

---

<div class="post-metadata">

**Author:** ![ahartikainen](https://yyz2.discourse-cdn.com/flex030/user_avatar/discourse.mc-stan.org/ahartikainen/32/321_2.png) [@ahartikainen](https://discourse.mc-stan.org/u/ahartikainen)\
**Post date:** [April 7, 2018, 6:48pm UTC](https://discourse.mc-stan.org/t/threaded-ad/3697/31 "2018-04-07T18:48:10Z")

</div>

This?

> <https://github.com/stan-dev/math/pull/809>

So if PyStan uses `n_jobs` to choose how many cores are available for processes, should `n_threads` be same or not?

---

<div class="post-metadata">

**Author:** ![ariddell](https://avatars.discourse-cdn.com/v4/letter/a/57b2e6/32.png) [@ariddell](https://discourse.mc-stan.org/u/ariddell)\
**Post date:** [April 7, 2018, 6:59pm UTC](https://discourse.mc-stan.org/t/threaded-ad/3697/32 "2018-04-07T18:59:58Z")

</div>

The `n_jobs` parameter name is taken from scikit-learn. I don’t think  
we need to change the name.

Everything should be easy to change. We just stop using  
multiprocessing.Pool and start using the thread-based equivalent (maybe  
concurrent.futures.ThreadPoolExecutor ?).

It’s wonderful to be able to support all platforms. This is a great change.

---

<div class="post-metadata">

**Author:** ![bgoodri](https://yyz2.discourse-cdn.com/flex030/user_avatar/discourse.mc-stan.org/bgoodri/32/4451_2.png) [@bgoodri](https://discourse.mc-stan.org/u/bgoodri)\
**Post date:** [April 7, 2018, 10:03pm UTC](https://discourse.mc-stan.org/t/threaded-ad/3697/33 "2018-04-07T22:03:10Z")

</div>

@wds15 Can we use threads to fire off chains (that may or may not themselves use `map_rect`)?

---

<div class="post-metadata">

**Author:** ![syclik](https://yyz2.discourse-cdn.com/flex030/user_avatar/discourse.mc-stan.org/syclik/32/6_2.png) [@syclik](https://discourse.mc-stan.org/u/syclik)\
**Post date:** [April 7, 2018, 10:08pm UTC](https://discourse.mc-stan.org/t/threaded-ad/3697/34 "2018-04-07T22:08:33Z")

</div>

> [@bgoodri](#):
>
> Can we use threads to fire off chains

Yes!

We should be able to write c++ wrappers at the service level to do just that. I’m guessing this is the way we want to control threading going forward for both RStan and PyStan?

---

<div class="post-metadata">

**Author:** ![bgoodri](https://yyz2.discourse-cdn.com/flex030/user_avatar/discourse.mc-stan.org/bgoodri/32/4451_2.png) [@bgoodri](https://discourse.mc-stan.org/u/bgoodri)\
**Post date:** [April 7, 2018, 10:18pm UTC](https://discourse.mc-stan.org/t/threaded-ad/3697/35 "2018-04-07T22:18:52Z")

</div>

It saves many copies of the data, so if there is no downside, then I would think so.

---

<div class="post-metadata">

**Author:** ![wds15](https://yyz2.discourse-cdn.com/flex030/user_avatar/discourse.mc-stan.org/wds15/32/908_2.png) [@wds15](https://discourse.mc-stan.org/u/wds15)\
**Post date:** [April 8, 2018, 7:27am UTC](https://discourse.mc-stan.org/t/threaded-ad/3697/36 "2018-04-08T07:27:32Z")

</div>

Just to confirm: Yes, we can use threading for chains and this will work nicely together with a parallel `map_rect` version based on threads (although the MPI version should not be used in chains which are threaded).

One word of caution though: I have performed quick benchmarks for myself which confirmed me that there was no performance penalty due to threading. However, before we roll this into all the interfaces someone other than me should confirm that we do not see any performance hits. If we want to make the transition from 1 process per chain to threaded chains smoothly, then we should develop the threaded chain facility in parallel to what we have…otherwise our design choice to keep the no-thread option around (and as default) no sense.

---

<div class="post-metadata">

**Author:** ![wds15](https://yyz2.discourse-cdn.com/flex030/user_avatar/discourse.mc-stan.org/wds15/32/908_2.png) [@wds15](https://discourse.mc-stan.org/u/wds15)\
**Post date:** [April 8, 2018, 8:29am UTC](https://discourse.mc-stan.org/t/threaded-ad/3697/37 "2018-04-08T08:29:12Z")

</div>

The `map_rect_concurrent` pull is up! Within-chain parallelization is very close to land in develop.

---

<div class="post-metadata">

**Author:** ![syclik](https://yyz2.discourse-cdn.com/flex030/user_avatar/discourse.mc-stan.org/syclik/32/6_2.png) [@syclik](https://discourse.mc-stan.org/u/syclik)\
**Post date:** [April 8, 2018, 12:02pm UTC](https://discourse.mc-stan.org/t/threaded-ad/3697/38 "2018-04-08T12:02:59Z")

</div>

Just thinking that we might run into interactions with GPU. We’ll cross that bridge when we get there.

---

<div class="post-metadata">

**Author:** ![Bob\_Carpenter](https://yyz2.discourse-cdn.com/flex030/user_avatar/discourse.mc-stan.org/bob_carpenter/32/9230_2.png) [@Bob\_Carpenter](https://discourse.mc-stan.org/u/Bob_Carpenter)\
**Post date:** [April 8, 2018, 3:33pm UTC](https://discourse.mc-stan.org/t/threaded-ad/3697/39 "2018-04-08T15:33:51Z")

</div>

> [@wds15](#):
>
> To my understanding if you pass into sub-threads const var& then you will be safe.

The issue is that we need to know which parameters are being used so that we can construct the appropriate coupled system. I don’t know how else we could get it other than reading over the AST.

> [@wds15](#):
>
> We should probably go one step further and define a value of “0” to imply the use of all available cores.

That seems like an odd convention. Given that it’s underlyingly a string, can we choose something else, or is that going to be too awkward for the interface type checks? I take it we can dynamically check the number of threads, as we do in RStan.

> [@ariddell](#):
>
> We just stop using  
> multiprocessing.Pool and start using the thread-based equivalent (maybe  
> concurrent.futures.ThreadPoolExecutor ?).

This isn’t threading at the algorithm level, it’s at the `map` function level. But I can see there’s interest for the future in making this multi-threaded. That was my original design intent, but then we found that there was a heavy overhead from thread local autodiff and then found that we were almost never memory bound, so we just went with a much simpler design.

I’m all for opening up threading to the chains level. Mainly because that’ll open up the option for better cross-chain adaptation methods. I’d really like to massively parallelize adaptation. It’s all about exploring the typical set well to estimate mass matrices (metrics).

---

<div class="post-metadata">

**Author:** ![stevebronder](https://yyz2.discourse-cdn.com/flex030/user_avatar/discourse.mc-stan.org/stevebronder/32/17242_2.png) [@stevebronder](https://discourse.mc-stan.org/u/stevebronder)\
**Post date:** [April 8, 2018, 5:21pm UTC](https://discourse.mc-stan.org/t/threaded-ad/3697/40 "2018-04-08T17:21:31Z")

</div>

> [@syclik](#):
>
> Just thinking that we might run into interactions with GPU. We’ll cross that bridge when we get there.

I think it will be fine. To my understanding if a user ran a GPU function using map concurrent then that function + chunk of data is going to be placed in the GPU job queue and execute normally. It may actually be a pretty good way to make sure we keep the GPU busy.

[Previous page](https://discourse.mc-stan.org/t/threaded-ad/3697.md?page=1)