POSE

Our PDES environment is built in CHARM++. CHARM++ supports the virtualization programming model, an approach we believe will give rise to great improvements in PDES performance. Virtualization involves dividing a problem into a large number $N$ of components that will execute on $P$ processors[1]. $N$ is independent of $P$, though ideally $N$$>>$$P$. The user's view of the program consists of these components and their interactions; the user need not be concerned with how the components map to processors. The underlying run-time system takes care of this and any subsequent remapping (see Figure 1).

Figure 1: Virtualization in CHARM++

In CHARM++, these components are known as chares. Chares are C++ objects with methods that may be invoked asynchronously from other chares. Since many chares can be mapped to a single processor, CHARM++ uses message-driven execution to determine which chare executes at a given time. This is accomplished by having a dynamic scheduler on each processor. The scheduler has a pool of messages, i.e. method invocations destined for a particular chare, and selects one of these, determines the object it is destined for, and then invokes the corresponding method on the object. At completion, the scheduler selects the next message. Different scheduling policies are available, as well as prioritized execution, which enables the user to attach priorities to messages. The advantage of this approach is that no chare can hold a processor idle while it is waiting for a message. Since $N$$>$$P$, there may be other chares that can do work in the interim.

The logical processes (LPs) of PDES can be mapped onto CHARM++'s chares in a straightforward manner. Similarly, we use timestamps on messages as priorities and thus the CHARM++ scheduler becomes an event list. Virtualization provides the simulation programmer with a view of the program consisting of the entities in the model and not the underlying parallel configuration.

Posers  In POSE, simulation entities, or posers are special types of chares that have a data field for object virtual time (OVT). This is the number of simulated time units that have passed since the start of the simulation relative to the object. Posers also have event methods similar to CHARM++ entry methods (invoked by sending messages from one object to another, possibly on a different processor), with the main difference being the presence of a data field for timestamp in all messages sent to invoke an event method.

Figure 2: Components of a poser.

Posers can pass simulated time in two ways. First is the elapse function. This is used to pass a certain amount of local time (presumably performing some activity). It advances the OVT of the poser in which it is called. The second means is by an offset added to event invocations. This can be used to schedule a future activity or to indicate transit time in a simulation. For example, suppose the event being invoked involves the movement of data such as a packet being sent over a network, and it takes $t$ time units to transmit it, we would schedule an event at the point receiving the packet at a time that is offset by $t$ from the current time.

Posers have plug-in behaviors for their underlying implementation. For the user, it is enough to know that the implementation involves the queuing of events, the synchronization of their execution, and access to and modification of poser state. We refer to these respectively as the wrapper behavior, the synchronization strategy behavior, and the representation behavior. Different approaches can be used for each. Figure 2 illustrates how these components fit together. The simulation developer concentrates on modeling entities (the representation). For more control over simulation behavior and performance, the developer can try different synchronization strategies.

Why encapsulate so much information in each entity, and then encourage the breakdown of the physical system into many such entities? Virtualization allows us to maximize the degree of parallelism. The scope of simulation overhead resulting from a synchronization error is limited to the entity on which the error occurs. Since different entities may have different behaviors, this limits the effects of those behaviors to a smaller scope.

Speculative Synchronization  POSE makes use of optimistic concurrency control which originated as Time-Warp[9]. When an object receives an event, it gets control of the processor. The object's synchronization strategy is then invoked and checks for any synchronization error corrections (rollbacks, cancellations) before it performs forward execution steps (events).

Here the opportunity to perform speculative computation[10] arises. All optimistic strategies perform some amount of speculative computation. In more traditional approaches, an event arrives and is sorted into the event list and the earliest event is executed. We know the event is the earliest available on the processor, but we do not know if it is the earliest in the entire simulation, thus executing it is speculative.

In our approach, the behavior is similar with some exceptions. First, we have a speculative window that governs how far into the future beyond the global virtual time (GVT) estimate an object may proceed. Speculative windows are similar to the time windows of other optimistic variants, except in how events within the window are processed.

In POSE, events are inserted into the event queue on the object for which they are destined. When the object gets control, it invokes the synchronization strategy to process events. Typically, the event just received will be the event processed, and no other events will exist on that object. However, some events may arrive slightly ahead of schedule and may be worthy candidates for speculative execution. Others may arrive with timestamps very far in the future and it may be unwise to execute them speculatively.

The synchronization strategy determines how to process the events within a speculative window. To avoid rescheduling overhead, we allow objects freedom to speculate once they get control. Event processing on the object follows this pattern: if there are events with timestamp $t\geq$GVT but within the speculative window, do all of them. The later events are probably not the earliest in the simulation, and it is very likely that they are not even the earliest on that processor. We allow the strategy to speculate that those events are the earliest that the object will receive. By handling events in bunches, we reduce scheduling and context switching overhead and benefit from a warmed cache, but risk additional rollback overhead.

POSE is a work in progress. We are developing an adaptive strategy that strives to execute more events at a time while minimizing rollbacks. This strategy will detect object behavior patterns and adjust to them by altering speculative window size and event processing behavior.