Русский     English

Aivika - A Constructor of General-Purpose Simulation Libraries

Aivika - is a computer program platform consisting of simulation libraries. It is mainly focused on discrete event simulation, but it partially supports system dynamics and agent-based modeling too. It is written in the Haskell programming language. The choice of the programming language is related to the simulation method implemented, which has deep relations to functional programming.

Basic Version

The platform is divided into two parts. The first part is a basic version, which is suitable for solving the most part of simulation tasks. It is like other simulation libraries such as SimPy, but it often can do more than others can do.

The corresponding package is called aivika. You can install it from Hackage DB.

The main idea is that we represent modeling activities as abstract computations.

For example, a discrete event handler can be defined as the Event computation:

newtype Event a = Event (Point -> IO a)

It literally means that the Event computation is a function of the modeling time point mapped to some value calculated within the standard IO computation. Moreover, API is defined in such a way that the Event computation is always synchronized with the event queue, which provides us with some guarantees.

IO is also called an imperative computation. We can perform side effects within it. For example, we can mutate a reference value, read from file, save date in the file, plot charts and so on.

Every Haskell program is started within the IO computation. It would not be possible to perform any side effect without this. But the side effects are often namely those things, because of which we run the application.

The basic version of Aivika uses the IO computation. The generated code is rather efficient. It is relatively fast. The IO monad allows doing much. Therefore, API of the basic version has almost no any additional constraints.

For instance, the following function is key for the basic version. It enqueues the event handler that should be actuated at the specified modeling time. To pass in data to the event, we can use a closure.

enqueueEvent :: Double -> Event () -> Event ()

Here we see that the enqueueEvent function has no constraints. This is a general rule for the basic version of Aivika.

Generalized Version

Another part of the platform is based on a generalized version of Aivika. The main idea is that we can replace the standard IO computation with arbitrary computation m. Then Event becomes a monad transformer:

newtype Event m a = Event (Point m -> m a)

What can we gain from this in practice?

Computation m, by which we parameterize another computation Event m, can have some useful unique features. For example, it could be a computation with help of which we could efficiently create and run nested simulations, or run distributed simulations. These are things that are not inherent directly in the IO monad.

Furthermore, we could create almost completely a general-purpose simulation library operating on abstract computations like Event m and requiring only that computation m would satisfy some limited set of constraints. That implementation would be common for all possible instantiations of computation m, where m would be a library parameter.

The generalized version of Aivika is namely such an implementation. Is is very similar to the basic version on level of both the programming code and ideas. Here we indeed operate on generalized computations like Event m, where m is an arbitrary computation.

The corresponding package from Hackage DB is called aivika-transformers.

To define the constraints, which the arbitrary computation m should satisfy, we can use type classes:

class (Monad m, ...) => MonadSD m
class (Monad m, ...) => MonadDES m

The MonadSD type class defines computations based on which we can build a program library for system dynamics. In its turn, the MonadDES type class defines computations based on which we can automatically build a general-purpose library for discrete event simulation. It is sufficient to instantiate the type class for creating the corresponding library.

There are two main things that the MonadDES type class requires to implement:

The second requirement actually means that we have to define a function that would enqueue the event handler with the specified activation modeling time.

class EventQueueing m where

    enqueueEvent :: Double 
                    -> Event m () 
                    -> Event m ()

It has turned out that satisfying these requirements is mostly sufficient to allow us to operate on discontinuous processes, resources, queues, streams of transacts, servers, in other words, on all those things that are used to be associated with discrete event simulation.

Provided the MonadDES instance, we actually receive a general-purpose library for discrete event simulation. In other words, the generalized version can be realized as a constructor of simulation libraries.

Nested Simulation

In the basic version of Aivika the event queue is implemented as a binary heap based on arrays. The operation of enqueueing a new event handler or dequeueing the handler with minimal activation time are examples of destructive operations that mutate the state of the queue itself. They are efficient for the most part of simulations tasks, but they are not acceptable in some cases.

So, this method is not acceptable for nested simulation. We have to create efficiently branches of the current model state. For example, it would allow us to forecast the future of the model but then return to the present with the received information. It could be useful for financial modeling.

It is obvious that the basic version of Aivika does not allow implementing the nested simulation directly, but we can fortunately implement it with help of the generalized version. For that, we have to create such a computation that would be an instance of the MonadDES type class, but would also have the desired features.

In package aivika-branches this computation is called BrIO:

instance MonadDES BrIO

Its key feature is a function that allows running nested computation in the future and then return the result in the current computation, not changing in any way the current model state:

futureEvent :: Double 
               -> Event BrIO a 
               -> Event BrIO a

How can we achieve this?

While in the basic version of Aivika the reference was just a cell of memory, the reference is more complicated here. It must be a map of the simulation branches to cells of memory. When referencing to the cell for the first time, we initialize it by a value from the parent branch. In other words, the reference becomes a tree of memory cells.

The most subtle and technically difficult issue is related to the fact that we have to automatically erase the tree from unachievable cells. The vast number of simulation branches can be created. The branches can be short-lived. Therefore, we have to know how to free the unachievable cells after usage. Aivika uses so called weak references for this purpose.

Regarding the event queue implementation, the following method is applied, which is widely used in functional programming.

The event handler queue is based on using an immutable data structure, which is put in a mutable cell of memory. Each time we enqueue a new event handler or remove the handler with minimal activation time, we create a new version of the event queue, which actually can share up to 99.99% of the old queue, being a completely different and independent object. The existent algorithms allow doing it quite efficiently, requesting for some memory allocation though. After we create the new event queue, we put it in the memory cell instead of the old queue.

Now when creating a branch of the current model state, we take the immutable event queue value from the memory cell and put it in a new memory cell that will correspond to the new branch. Whatever we will do in the branch, whatever event handlers we will enqueue or dequeue there, we cannot change the current state of the event queue, for it is immutable.

Thus, the operation of creating a new branch for running nested simulation can be quite efficient and relatively cheap. Because of using special data structures for implementing references and storing the event queue, the performance degrades some in comparison to the basic version of Aivika, but the degradation of speed seems to be constant asymptotically. The tests show that the speed slows down no more than in 5-6 times in comparison to the basic version, but we can run nested simulations instead.

Parallel Distributed Simulation

A method of using the immutable event queue can be successfully applied to parallel distributed simulation too. Here the simulation is distributed among nodes of the cluster or supercomputer. The nodes can send to each other and receive asynchronous messages that have timestamps.

In Aivika it will be package aivika-distributed. It implements an optimistic strategy based on the Time Warp method. If we receive an outdated message, that is the local modeling time is greater than the time at which the incoming message had to be processed, then a transparent rollback occurs till that time at which we could process the specified message. When rolling back, all invalid messages that were sent by the node are canceled. The rollbacks can be cascading and affecting many nodes.

As before, here we implement a computation that satisfies the requirements of the MonadDES type class. The corresponding computation is called DIO:

instance MonadDES DIO

To send messages to other nodes, we can use the following functions:

sendMessage :: forall a. P.Serializable a 
               => P.ProcessId a 
               -> a 
               -> Event DIO ()

enqueueMessage :: forall a. P.Serializable a 
                  => P.ProcessId a 
                  -> Double 
                  -> a 
                  -> Event DIO ()

Here prefix P means an import from package distributed-process. The second function allows setting the exact modeling time at which the message should be received. The first function defines that the message should be received precisely at that time at which it was sent, which potentially may lead to an infinite loop when rolling back. Therefore, it is recommended to use the second function, at least with a small time delay.

We can subscribe to a signal that will inform us about receiving the incoming message of the specified type:

messageReceived :: forall a. P.Serializable a 
                   => Signal DIO a

Each node has a log of operations. When updating, now every reference will write in the log such an operation so that we could revert the last changes and restore the previous reference state for the specified modeling time.

In case of the event queue, we write in the log such operations that will use the immutable queue values so that we also could restore fast the event handler queue for the specified modeling time. Here the immutable values are very useful without doubt.

Nevertheless, the operation log can bloat. Therefore, we have to know how to synchronize the global modeling time calculated for all nodes of the cluster so that we could erase the old records from the operation log, but this is a separate subject.

Also in case of distributed simulation, the messages may come unordered. In other words, we can initially receive the first message saying that we have to release the resource, but then we can receive with less modeling time the second message saying that we have to acquire the resource. When receiving the first message, such a situation may happen that we cannot proceed with the simulation, that we have to wait for the next external message that would reorder the simulation.

For that, the generalized version of Aivika defines the following function.

retryEvent :: MonadException m 
              => String 
              -> Event m a

It can be called with the DIO computation. Here we pass in a message that will be displayed in case of failure, when we will not be able to retry the computation within the specified time-out.

The I/O operations are another difficult case for distributed simulation. We should perform these operations synchronously, when the local modeling time of the node equals to the global modeling time.

The good news is that we can safely use the event queue to synchronize the global time before performing I/O operations. If a rollback occurs in the course of synchronizing the global time, nothing worse happens as we did not yet start the I/O operations, but the event can be repeated. In case of successful synchronization, we can safely perform the I/O operations. If the modeling time cannot be synchronized within the specified time-out and there was no rollback, then the error is raised.

The corresponding function is defined in the generalized version of Aivika. It enqueues the event handler that will be actuated at the specified modeling time after the local time of the node equals to the global modeling time. In other words, we can safely perform I/O operations within the event handler.

class EventIOQueueing m where

    enqueueEventIO :: Double 
                      -> Event m () 
                      -> Event m ()

This function can be used with the DIO computation that instantiates the corresponding type class.

Although the parallel distributed simulation is a difficult subject, we see that here we can apply the generalized version of Aivika too, which demonstrates again that this version is a flexible constructor of general-purpose simulation libraries.