Saturday, July 04, 2009

Three Phase Update

I uploaded a new tutorial Concurrent Java Simulations Using Three Phase Update. Here is the abstract:

Computer games and simulations have a main loop which is divided into phases such as user input controller processing, updating model state, and rendering the view. Since the states of multiple simulated objects are determined by their interactions, each object must have the opportunity to access the current state of every other object during the update phase. To ensure that the next states of objects are independent of the order in which they are updated, all of these accesses must occur before the state of any one object mutates into its next state. This can be accomplished by dividing the update into two sub-phases, access and mutate, in which no object can mutate its state until every other object has completed accessing shared state. Beyond update order independence, this has an additional benefit in that this can increase the performance of multi-threaded concurrent applications because synchronization is not required to ensure the integrity of shared state. A further increase in performance for concurrent simulations can be had by the introduction of a third sub-phase, digest, in which processing is performed on data copied during the preceding access sub-phase but modifying shared state is delayed until the following mutate sub-phase. This tutorial demonstrates the use of the three sub-phases pattern, Three Phase Update (TPU), using example code in the Java programming language including classes from the Java concurrency library.