Experiences with concurrent / multi-threaded step function for agents?

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Experiences with concurrent / multi-threaded step function for agents?

Jonas Andersen
Hi,

I have a simulation which is usually run with a few thousand agents. During the simulation run I noticed that the CPU utilization was around a low 13% (running on quad core with HT).

A quick and naive attempt to utilize the available CPU better was to schedule a simple proxy, which in the step method would get all the real agents and simply submit them to a fixed thread pool executor and wait for them all to terminate.

This gave an impressive boost to the simulation execution, now running with 80%+ CPU utilization.

It also resulted in some expected errors regarding concurrent modification of the context object (while looping through the agents to schedule them, as some agents are removing themselves from the context). This is something I can deal with, but was wondering if there are others on this list who have already made some experiences in concurrent agent steps?

Are the Repast objects generally thread safe (with a few rules) or is very broad and strict synchronization required? From initial observation the iterating through agents in the context and adding/removing agents is a no-no. What about for example moving agents within a projection (continuous space), would this also need synchronization?
I guess worst case, I'll need to synchronize all access to the Context and other Repast objects. Naturally, the data structures (simulation environment) used by the agents will need to properly handle the concurrent execution.

From other discussions, I get the impression I should randomize the list of agents before they are submitted to the executor service? I also think I read somewhere that the concurrent execution also impacts the reproducibility of the simulation (I assume since the CPU scheduling in not controlled by the random seed and thus the sequence will differ?).

Any suggestions, lessons learned, pointers, do's and don'ts, etc. will be much appreciated.

Best regards,

Jonas Andersen



------------------------------------------------------------------------------

_______________________________________________
Repast-interest mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/repast-interest
Reply | Threaded
Open this post in threaded view
|

Re: Experiences with concurrent / multi-threaded step function for agents?

rnick
Jonas,

You will need to synchronized any write access to shared resources such as contexts and projections. Depending on your model you should also randomize the agents before executing them. This is necessary to avoid situations like "first mover advantage”. For example, if your model has some idiom like “move to area X because it has the greatest concentration of  Y”, and the same agent always goes first then that agent has an advantage. Of course, this doesn’t always apply. As you say, in the concurrent case, the order is not under the control of the random seed.

I’ve found multi-threading to most useful when there’s is some relatively time consuming operation that each agent needs to do that doesn’t require any write-access. In order to find that it you may need to re-write part of the model. For example, if an agent behavior is something like “calculate what to do next and then do it”, you may be able to multi-thread the “calculate what to do next” part, but execute the “do it” part sequentially. Given enough agents this may be faster even though it typically requires two loops over the agents rather than one. This is also often faster than a single multi-threaded loop with synchronization. Of course, your mileage may vary, and profiling is important here.

Nick


> On Oct 19, 2015, at 11:12 AM, Jonas Andersen <[hidden email]> wrote:
>
> Hi,
>
> I have a simulation which is usually run with a few thousand agents. During the simulation run I noticed that the CPU utilization was around a low 13% (running on quad core with HT).
>
> A quick and naive attempt to utilize the available CPU better was to schedule a simple proxy, which in the step method would get all the real agents and simply submit them to a fixed thread pool executor and wait for them all to terminate.
>
> This gave an impressive boost to the simulation execution, now running with 80%+ CPU utilization.
>
> It also resulted in some expected errors regarding concurrent modification of the context object (while looping through the agents to schedule them, as some agents are removing themselves from the context). This is something I can deal with, but was wondering if there are others on this list who have already made some experiences in concurrent agent steps?
>
> Are the Repast objects generally thread safe (with a few rules) or is very broad and strict synchronization required? From initial observation the iterating through agents in the context and adding/removing agents is a no-no. What about for example moving agents within a projection (continuous space), would this also need synchronization?
> I guess worst case, I'll need to synchronize all access to the Context and other Repast objects. Naturally, the data structures (simulation environment) used by the agents will need to properly handle the concurrent execution.
>
> From other discussions, I get the impression I should randomize the list of agents before they are submitted to the executor service? I also think I read somewhere that the concurrent execution also impacts the reproducibility of the simulation (I assume since the CPU scheduling in not controlled by the random seed and thus the sequence will differ?).
>
> Any suggestions, lessons learned, pointers, do's and don'ts, etc. will be much appreciated.
>
> Best regards,
>
> Jonas Andersen
>
>
> ------------------------------------------------------------------------------
> _______________________________________________
> Repast-interest mailing list
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/repast-interest


------------------------------------------------------------------------------
_______________________________________________
Repast-interest mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/repast-interest
Reply | Threaded
Open this post in threaded view
|

Re: Experiences with concurrent / multi-threaded step function for agents?

Tatara, Eric R.
I agree with Nick's suggestion in splitting up the code into parallel parts that only write to local agent fields, and a serial part that updates shared resources like contexts or projections.  The Repast Flock demo follows this design pattern.

Another way to "parallelize" execution with no coding is to just run multiple instances of Repast.  Both the GUI and batch mode can be launched separately and should not have a problem running on different CPU cores, assuming that there is not I/O conflict like trying to write to the same file.   I've used this approach to split up a batch run that originally had say 100 independent runs defined into four separately launched batch runs of 25-run length, and it does run about 4x faster on a CPU with four physical cores compared to running all 100 runs in a single batch.

eric

Eric Tatara, PhD, PE
Software Engineer
Global Security Sciences Division
Argonne National Laboratory

________________________________________
From: Nick Collier [[hidden email]]
Sent: Tuesday, October 20, 2015 8:10 AM
To: Jonas Andersen
Cc: [hidden email]
Subject: Re: [Repast-interest] Experiences with concurrent / multi-threaded step function for agents?

Jonas,

You will need to synchronized any write access to shared resources such as contexts and projections. Depending on your model you should also randomize the agents before executing them. This is necessary to avoid situations like "first mover advantage”. For example, if your model has some idiom like “move to area X because it has the greatest concentration of  Y”, and the same agent always goes first then that agent has an advantage. Of course, this doesn’t always apply. As you say, in the concurrent case, the order is not under the control of the random seed.

I’ve found multi-threading to most useful when there’s is some relatively time consuming operation that each agent needs to do that doesn’t require any write-access. In order to find that it you may need to re-write part of the model. For example, if an agent behavior is something like “calculate what to do next and then do it”, you may be able to multi-thread the “calculate what to do next” part, but execute the “do it” part sequentially. Given enough agents this may be faster even though it typically requires two loops over the agents rather than one. This is also often faster than a single multi-threaded loop with synchronization. Of course, your mileage may vary, and profiling is important here.

Nick


> On Oct 19, 2015, at 11:12 AM, Jonas Andersen <[hidden email]> wrote:
>
> Hi,
>
> I have a simulation which is usually run with a few thousand agents. During the simulation run I noticed that the CPU utilization was around a low 13% (running on quad core with HT).
>
> A quick and naive attempt to utilize the available CPU better was to schedule a simple proxy, which in the step method would get all the real agents and simply submit them to a fixed thread pool executor and wait for them all to terminate.
>
> This gave an impressive boost to the simulation execution, now running with 80%+ CPU utilization.
>
> It also resulted in some expected errors regarding concurrent modification of the context object (while looping through the agents to schedule them, as some agents are removing themselves from the context). This is something I can deal with, but was wondering if there are others on this list who have already made some experiences in concurrent agent steps?
>
> Are the Repast objects generally thread safe (with a few rules) or is very broad and strict synchronization required? From initial observation the iterating through agents in the context and adding/removing agents is a no-no. What about for example moving agents within a projection (continuous space), would this also need synchronization?
> I guess worst case, I'll need to synchronize all access to the Context and other Repast objects. Naturally, the data structures (simulation environment) used by the agents will need to properly handle the concurrent execution.
>
> From other discussions, I get the impression I should randomize the list of agents before they are submitted to the executor service? I also think I read somewhere that the concurrent execution also impacts the reproducibility of the simulation (I assume since the CPU scheduling in not controlled by the random seed and thus the sequence will differ?).
>
> Any suggestions, lessons learned, pointers, do's and don'ts, etc. will be much appreciated.
>
> Best regards,
>
> Jonas Andersen
>
>
> ------------------------------------------------------------------------------
> _______________________________________________
> Repast-interest mailing list
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/repast-interest


------------------------------------------------------------------------------
_______________________________________________
Repast-interest mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/repast-interest

------------------------------------------------------------------------------
_______________________________________________
Repast-interest mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/repast-interest
Reply | Threaded
Open this post in threaded view
|

Re: Experiences with concurrent / multi-threaded step function for agents?

Jonas Andersen
Thanks a lot for all the suggestions and comments. For the immediate needs, we can run multiple concurrent batch runs. When time allows, I'll be looking into the multi-threaded execution with the recommendations made here.

Best regards,

Jonas


On Tue, Oct 20, 2015 at 5:16 PM, Tatara, Eric R. <[hidden email]> wrote:
I agree with Nick's suggestion in splitting up the code into parallel parts that only write to local agent fields, and a serial part that updates shared resources like contexts or projections.  The Repast Flock demo follows this design pattern.

Another way to "parallelize" execution with no coding is to just run multiple instances of Repast.  Both the GUI and batch mode can be launched separately and should not have a problem running on different CPU cores, assuming that there is not I/O conflict like trying to write to the same file.   I've used this approach to split up a batch run that originally had say 100 independent runs defined into four separately launched batch runs of 25-run length, and it does run about 4x faster on a CPU with four physical cores compared to running all 100 runs in a single batch.

eric

Eric Tatara, PhD, PE
Software Engineer
Global Security Sciences Division
Argonne National Laboratory

________________________________________
From: Nick Collier [[hidden email]]
Sent: Tuesday, October 20, 2015 8:10 AM
To: Jonas Andersen
Cc: [hidden email]
Subject: Re: [Repast-interest] Experiences with concurrent / multi-threaded step function for agents?

Jonas,

You will need to synchronized any write access to shared resources such as contexts and projections. Depending on your model you should also randomize the agents before executing them. This is necessary to avoid situations like "first mover advantage”. For example, if your model has some idiom like “move to area X because it has the greatest concentration of  Y”, and the same agent always goes first then that agent has an advantage. Of course, this doesn’t always apply. As you say, in the concurrent case, the order is not under the control of the random seed.

I’ve found multi-threading to most useful when there’s is some relatively time consuming operation that each agent needs to do that doesn’t require any write-access. In order to find that it you may need to re-write part of the model. For example, if an agent behavior is something like “calculate what to do next and then do it”, you may be able to multi-thread the “calculate what to do next” part, but execute the “do it” part sequentially. Given enough agents this may be faster even though it typically requires two loops over the agents rather than one. This is also often faster than a single multi-threaded loop with synchronization. Of course, your mileage may vary, and profiling is important here.

Nick


> On Oct 19, 2015, at 11:12 AM, Jonas Andersen <[hidden email]> wrote:
>
> Hi,
>
> I have a simulation which is usually run with a few thousand agents. During the simulation run I noticed that the CPU utilization was around a low 13% (running on quad core with HT).
>
> A quick and naive attempt to utilize the available CPU better was to schedule a simple proxy, which in the step method would get all the real agents and simply submit them to a fixed thread pool executor and wait for them all to terminate.
>
> This gave an impressive boost to the simulation execution, now running with 80%+ CPU utilization.
>
> It also resulted in some expected errors regarding concurrent modification of the context object (while looping through the agents to schedule them, as some agents are removing themselves from the context). This is something I can deal with, but was wondering if there are others on this list who have already made some experiences in concurrent agent steps?
>
> Are the Repast objects generally thread safe (with a few rules) or is very broad and strict synchronization required? From initial observation the iterating through agents in the context and adding/removing agents is a no-no. What about for example moving agents within a projection (continuous space), would this also need synchronization?
> I guess worst case, I'll need to synchronize all access to the Context and other Repast objects. Naturally, the data structures (simulation environment) used by the agents will need to properly handle the concurrent execution.
>
> From other discussions, I get the impression I should randomize the list of agents before they are submitted to the executor service? I also think I read somewhere that the concurrent execution also impacts the reproducibility of the simulation (I assume since the CPU scheduling in not controlled by the random seed and thus the sequence will differ?).
>
> Any suggestions, lessons learned, pointers, do's and don'ts, etc. will be much appreciated.
>
> Best regards,
>
> Jonas Andersen
>
>
> ------------------------------------------------------------------------------
> _______________________________________________
> Repast-interest mailing list
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/repast-interest


------------------------------------------------------------------------------
_______________________________________________
Repast-interest mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/repast-interest


------------------------------------------------------------------------------

_______________________________________________
Repast-interest mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/repast-interest