Supporting Techniques Of Multi-core Parallel Simulation For Stochastic Reaction And Diffusion Systems

Stochastic Reaction and Diffusion Simulation(SRDS)can help to understand molecular dynamics and messenger mechanism of the interior and exterior of cells,as well as behavior mechanism of a single cell and the whole biochemical system,and then supports verifying hypothesis on molecular dynamics and validating treatment methods.Characteristics of such simulation,e.g.zero lookahead,sensitive to neighborhood update,large scale,computation-intensive,and repetitive execution,propose high demand to the performance of simulation,which means Parallel Discrete Event Simulation(PDES)based on high performance computer an important way for addressing the challenges.Along with the fast development of multi-core processor,compared to the traditional process-based PDES,multi-threaded PDES achieves efficient communication among cores by sharing process space,which has been proved as a promising way to make better advantages of multi-core clusters.However,the overhead of event queuing,time management and load balancing remains high in the present multi-threaded PDES,which makes it difficult to make full advantages of multi-core clusters.Therefore,the research on Supporting Techniques of Multi-core Parallel Simulation for Stochastic Reaction and Diffusion Systems has noticeable theoretical significances and practical values for improving simulation efficiency,making full use of computation and communication resources of multi-core clusters,as well as satisfying increasing demands of real applications.To satisfy the demands in performance of stochastic reaction and diffusion simulation in multi-core clusters,the main work and contribution of this thesis covers multi-threaded PDES architecture,asynchronous Global Virtual Time(GVT)algorithm,self-adaptive load balancing and optimism control,and rollback optimization as follows.(1)Present multi-threaded PDES adopts symmetric and homogeneous architecture-threads simultaneously communicate with others and process events,resulting in high contention on communication service and event queuing,which constrains event-processing rate and scalability.To these problems,it proposes a Scalable and Configurable Multithreaded PDES Architecture SConMA which firstly designs a hierarchical and asynchronous event queuing mechanism in which an event queue is partitioned into thread,logic process(LP,i.e.simulation object)and input channel according to the characteristics of SRDS,forming top-down three-level queues,and lower level queues only submit urgent event to upper lever queues and maintain correct global queuing,in return probability at which a few threads concurrently access a single queue is reduced;meanwhile divides communication and event processing,and then assigns special threads to process communication,LPs that reside in threads within one process schedule events through sharing process space,in this way contention on communication is reduced.As experimental results show,SConMA exhibits superior performance and scalability-it shortens execution time by about 12% compared to centralized muti-threaded PDES architecture,and decreases the contention probability at thread event queue by 40% on average.(2)The present multi-threaded PDES adopts synchronous GVT algorithm,which brings in high overhead,while it is difficult to solve transient message and simultaneous reporting problems caused by inter-node messages using the Fujimoto multi-threaded asynchronous GVT algorithm.To these problems,it proposes a hybrid asynchronous GVT algorithm based on large scale multi-core cluster HAGVT in which local GVT within one process is computed by event-processing threads under the control of communication thread using improved Fujimoto algorithm,meanwhile transient message and simultaneous reporting problems among processes are solved by communication threads using Mattern algorithm,in this way the two algorithms cooperate to compute GVT within and among processes asynchronously in multi-core clusters.As theoretical analysis and experimental results show,HAGVT can compute GVT at any wallclock time during simulation,and computational cost and GVT delay is lower than the original Mattern and Fujimoto algorithms-compared to the runs that adopt the original Fujimoto algorithm,HAGVT shortens execution time by around 11%.(3)Heterogeneous distribution of molecules in the whole space leads to load imbalance among threads,and rollback is high in optimistic runs due to the zero lookahead property.Present approaches deal with either load balancing or optimism control separately,as a result threads cannot achieve optimal rate of processing effective events.To this problem,it propose a self-adaptive algorithm for load balancing and optimism control ALBW which operates in two steps: for the first run of a simulation,it uses the simulated annealing based algorithm for load balancing and optimistic window control SALBW to explore the optimal parameters for workload migration and optimism control in the whole parameter space in a self-adaptive pattern;for the successive runs of the same simulation,it uses the improved Q-Learning algorithm for load balancing QLB to explores the optimal parameters for a specific run based on the result of SALBW;in this way it adapts different application circumstance.As experimental results show,ALBW shortens the execution time of large scale calcium wave model by around 36% in a multi-core cluster.(4)The rollback mechanism based on message send time-stamp(STRB)uses the order-preserving characteristic of modern communication and achieves efficient rollback in optimistic simulation.However,molecules have various diffusion rates,as a result events may be processed before formerly-scheduled events,which makes STRB difficult to cancel invalid events.To this problem,it proposes a rollback mechanism based on message send and receive time-stamp SRTRB which determines the critical invalid event by the send time-stamp of message sent by rolled back LP,and then cancels invalid events using the send time-stamp of this critical event,after that computes the rollback time according to the receive time-stamp of this event,and finally recovers processed events by the rollback time,in this way it realizes correct rollback when molecules arrive in any order.As experimental results show,SRTRB can achieve correct rollback in SRDS,and exhibits better performance than anti-message based rollback mechanism-when using threads within one process the runs which adopt anti-message take as 1.42 times execution time as the runs that adopt SRTRB on average.Finally,a high performance PDES framework RD-PDES oriented to stochastic reaction and diffusion simulation and based on multi-core clusters is developed.The comprehensive test on large scale reinforced calcium wave model shows that RD-PDES achieves superior performance and scalability,and shortens execution time by 37% compared to the general-purpose PDES platform YH-SUPE.Moreover,RD-PDES exhibits apparent generality through testing on a bistable biochemical model.