Parallel stochastic simulation of neuronal reaction-diffusion equations

We demonstrate the use of a parallel discrete event simulation to simulate a stochastic reaction-diffusion model of chemical reactions involving calcium. The method is based upon the next sub-volume method, NSM, an outgrowth of the Gillespie algorithm. Parallel simulation is used because the Gillespie algorithm is computationally very expensive for a large number of molecules. We modified our XTW (Xu Time Warp) algorithm, an optimistic parallel simulator originally developed for handling connections in network-level simulations. XTW makes use of clusters corresponding to a group of sub-volumes used in NSM. It uses a multi-level queue to schedule events and has an O(1) complexity, a significant improvement over existing methods, including splay-tree, heap and red-black tree. XTW uses rollback messages to annihilate messages sent prior to the arrival of a straggler, instead of sending individual anti-messages as is done in other algorithms. This feature is made possible by the first come first serve (FCFS) property inherent to reaction-diffusion models. We utilized the Lotka-Volterra (LV) predator-prey model to test the scalability of the algorithm. This classic problem has the advantage of being readily expressed in either deterministic or stochastic form. It can be grossly analogized to a situation of 2 auto-catalytic substances, where fox enzyme can terminally degrade rabbit substrate, and where rabbit breakdown provides a critical cofactor for fox function. Load balancing and determination of window size are fundamental to the efficiency and stability of the simulation for large reaction-diffusion models. The simulation process can accept messages from other processes. The messages contain events. In an optimistic (Time Warp) simulation, the events are processed as they come in, regardless of the timestamps on the messages. This means that you can get a message from the past (i.e. with a lower timestamp then the messages already processed) and you have to set things straight. You do this by (1) sending out anti-messages to hunt down and kill messages with timestamps larger then the arrival with the small timestamp and (2) re-instantiating processing from the last safe state. The window size controls the optimism of Time Warp, preventing an excessive number of rollbacks. A number of load-balancing algorithms can be used with XTW: simulated annealing, multi-state Q-learning and genetic algorithms. We compare efficiency of these algorithms in the LV reaction-diffusion context.