Look at the spinlocks in the linux kernel -- I believe they are much faster (though I 've never used them).  What sort of agents are you dealing with? What sort of time stepping strategy are you using? What sort of interactions do they engage in?

I've  built (with a team) human/ecosystem simulations which ran with around 14000 agents (if I recall correctly), but they werer fairly complex agents running with arbitrary times steps.

I really need more info before I can offer much substantive help.

I am not familiar with Monte Carlo computations but usually in a multithreaded application, you create a single mutex that is locked and unlocked by multiple threads in the critical(synchronization) region. Speaking IMHO, it seems like you need to rethink your synchronization logic.

Generally "Monte Carlo" means here that you choose randomly one agent, or pair of agents (for interaction), do update, then  choose another agent/pair etc.. For multi-threated implementation it is possible, that two threats choose the same agent concurrently.

Additionally I need portable implementation, which will work with any C++11 compiler.

In a simulation term, you have used the process interaction world view to model. Each agent has its own process. But in the large scale situation, this world view is not suitable. Because the number of threads or other resource are limited. You should try the event-schedule world view to model. 

Milions of Mutex with limited number of threads (e.g up to 32) is not the problem. It still can work well. 

You can try to use Poco C++. It has NotificationQueue, NotificationCenter, ThreadPool, etc. http://pocoproject.org/  It is a good C++ library with many design patterns.

Thanks for your advice. I have to implement few solutions and check which is the fastest.  But, for my program, I expect, that queue based ones are probably the worse, because single-threaded version spends half the CPU time around rand() functions - agents only rare do something really costly.

I did some tests. The first implementation use one std::mutex guarding critical section where agents are locked and unlocked. This work about 10 times SLOWER than single threated version! The second implementation use std::atomic_flag{s} guarding each agent, and work up to about 2.5 times faster (using 16 threads on 8-core CPU under Windows 7).  It looks like  this version is mostly limited by CPU-RAM transfer.

Hello,

If you could start a small GitHub project to share just a prototype version (just the threading and random number generation, not the whole ABM model) of your code, people could interact and bench variations of it with their own ideas.

Also, I'm a little concerned by you saying: "half the CPU time around rand() functions".  The rand() C/C++ function is not thread safe and does not generate good quality random numbers which is important if you are using Monte Carlo methods, even more so if you multi-thread them. See the first link.

A safe way to do this would be to construct a specific C++11 pseudo random number generators (PRNG) like Mersenne Twister (mt19937) object for each thread. Contrarily to the rand() function, these PRNG do not share states and can be used without any synchronization mechanism as they are different instances of the PRNG class. See the second link.

Please, keep us informed of your progress, your problem is very interesting!

http://stackoverflow.com/questions/6161322/using-stdlibs-rand-from-multiple-threads

http://stackoverflow.com/questions/8813592/c11-thread-safety-of-random-number-generators

https://en.wikipedia.org/wiki/Mersenne_Twister

Of course rand() was a "mind short-cut". I my work I use few different random generators depending of requirements (mostly size and time of particular simulation).

But Marsenne-Twister looks as the heaviest one (consuming a lot of CPU and considerable memory when you thinking also about CPU cache).

Now I can do even billion :-) of agents using "atomic writing" as semaphors.