Monday, May 19, 2014

Benchmarking Discrete Event Simulation Software

Introduction

Over the last several months Harvey Harrison and Matt Chudleigh have been working hard to increase JaamSim's execution speed. With the release this week of JaamSim2014-20, I am pleased to say that JaamSim is now faster than both Arena and Simio.

Before starting our optimisation process, we searched the internet for any information on benchmarks for discrete event simulation software. Surprisingly, there are no published benchmarks of any kind that compare the execution speeds of the various simulation packages. Some articles compare the features and design of the software packages, but provide no quantitative data. To the best of my knowledge, this blog post is the first to give numerical results.

The first step in any optimisation effort is to decide what to measure. For discrete event software, there are three activities that are likely to be slow enough to bottleneck execution speed:
  1. Event scheduling and processing.
  2. Creating and destroying entities.
  3. Executing blocks that do not involve simulated time.

Event Scheduling and Processing Benchmark

This post focuses on the first of these activities -- scheduling and executing events. The following model was devised to measure this time.
Benchmark Model
In this model, N entities are created at time zero and fed into a delay activity whose duration is selected randomly from the range 0 to 2N seconds (uniformly distributed). On completion of the delay, each entity is routed back to re-execute the delay again. This design results in an average of one entity per second completing the delay and an average of N events on the future event list. The use of the uniform distribution ensures that each new event is inserted in a random position in the future event list.

The average time to create, schedule, and execute an event was measured by running the model for 60 seconds of real time (using a stopwatch) and counting the number of times the delay activity was completed. The effect of the computer speed was allowed for by converting the calculated time into clock cycles. All measurements were made using my laptop computer which has a second generator (Sandybridge) Core i5 processor running at 2.5 GHz.

Performance Results

We began by benchmarking the initial version of JaamSim (2014-11) and comparing the results to those for Arena and Simio. The following graph shows the execution time per event for the three software packages over a range of future event list sizes. This is the "Before" picture for the simulation weight loss clinic.
Before Optimisation
Clearly, JaamSim2014-11 was quite a lot slower than both Arena and Simio for event scheduling and processing. This slowness was caused by its use of system threads to control simulated time. Each event required two context switches -- passing control from one thread to another -- a relatively time consuming process for the computer.

Next we began optimising. The following graph shows the performance of two subsequent releases of JaamSim.
After Optimisation
The biggest gain came from re-designing the event processing engine so that events could executed without context switching. This was no small task and preparations had been made for this change over several previous months. Jaam2014-16 was the first release to implement the new system and the event processing time immediately dropped from 67,000 clock cycles per event to 1,200 clock cycles per event (with an empty future events list). For comparison, Simio required 1,800 clock cycles per event.

The next step was to improve performance when there are a large number of events on the future events list. JaamSim2014-16 used a simple array structure that required O(N) clock cycles to insert a new event. This worked well up to about 100 events on the future event list, but became very inefficient for larger numbers of events. JaamSim2014-18 (not shown) improved this design enough to extend the range of efficient operation up to 1,000 future events, but became too slow at 10,000 events.

Finally, in JaamSim2014-20, we replaced the future events array with a new data structure called a "red-black tree" that requires only O(logN) clock cycles to insert a new event. With this change, JaamSim provides excellent performance to at least 10,000 future events.

Concluding Remarks

As of JaamSim2014-20, we have improved event scheduling and processing to the extent that it is no longer a significant factor in model execution speed. As subsequent posts will show, the execution time for a JaamSim delay block is now about the same as that for any of the other blocks in the Basic Objects palette.

So far, we have only benchmarked Arena and Simio, but more will come over the next 6 months. In particular, I'd like to see how well AnyLogic, FlexSim, and ExtendSim perform. Assistance from any readers who are familiar with these software packages would be most welcome. The hardest part of benchmarking other software is to learn enough to implement the various benchmarks in way that gets the best from the software. In the case of Simio, I am grateful to Alan Sagan for providing an implementation that performed ten times faster than my first attempt.

Tuesday, May 13, 2014

The Birth of JaamSim

JaamSim has its origin in the simulation models we prepare for the oil & gas and mining industries. These models simulate the movement of products such as crude oil, LNG, coal, and iron ore from production through marine terminals and ships to their final destinations. You can view some videos of these models using the link from the JaamSim webpage or at our YouTube channel: JavaSimulation.

Long before JaamSim, we wrote our models in commercial off-the-shelf software.  In the early 1980's, we used GPSS, followed a few years later by SLAM. In the 1990's, we used Audition, a simulation package developed in part by the National Research Council of Canada. When Audition came to the end of its life a decade later -- it was incompatible with Windows 2000 and NT -- we had several large models that needed to be converted to a new simulation platform. What to do?

We started by reviewing the lessons we had learned from our previous simulation packages:
  • Most of our modelling effort goes into writing custom simulation objects. With SLAM, we had a small framework that was built from its standard components and a very large body of FORTRAN code that did the real work.  SLAM did little more that manage the simulation clock and execute events.
  • A non-standard programming language is a bad idea. Audition was quite an advanced programming language in its day -- basically Smalltalk with extensions to do discrete-event simulation. As good as it was, it had a small user base and lacked many basic features. We spent a huge amount of effort writing code to do things that would already be provided in a standard programming language.
  • Simulation packages tend to become obsolete after ten or so years. Newer, more capable software appears on the scene and the old software becomes a legacy product that receives only token development. This is a healthy process for the simulation industry, but it leaves the model developer with a lot of software to rewrite.
As a result of this experience, we decided to adopt a mainstream object-oriented programming language and build our own simulation engine. We chose Java over C++ because it is simpler language and has a more productive programming environment. This proved to be a good decision. In eight months, we had constructed our simulation engine, written a compiler to translate Audition code into Java, and had converted and verified all our models.

Our new simulation program, the "Transportation Logistics Simulator" (TLS), was still an application-specific model for product transportation. TLS evolved with each new project and over the years acquired all the features of a modern simulation package.

JaamSim was born in 2010 when we separated TLS into a general purpose simulator and a set of application-specific components. In 2011, we released JaamSim as free, open source software and in 2013 introduced it to the simulation community with a Winter Simulation Conference paper.

JaamSim now consists of over 50,000 lines of executable code and Ohloh estimates that it represents about 13 years of effort, or about one million dollars of programmer time. It is one of the most active open-source projects that they track.

Enjoy!

Wednesday, May 7, 2014

Why is JaamSim free?

The first question most people ask me about JaamSim is "Why are you doing this?" This is a good question. We are going to a lot of trouble to develop and promote software that generates no revenue for us.

There is a personal reason and a business reason for JaamSim.  I'll start with the personal one. I've been a simulation consultant for more than thirty years now, and I would like to make a lasting contribution to the field. Over the years, I've developed strong opinions on how simulation models should be constructed and on the role simulation technology should play in the world. I'll say more about these topics in future posts, but suffice it to say that the present generation of commercial off-the-shelf simulation software is not suitable for this vision and that JaamSim is designed to fill this gap. JaamSim embodies all our ideas on how simulation software should work.

The business reason for JaamSim is simple. We want to be recognized as a leader in simulation technology to help us sell our consulting services. It's no good for us to claim that our software is the most sophisticated because everyone else does this too. Clients have no way to make a technical evaluation and simply assume that the most popular software is the best and safest choice. The only way for us to prove the value of our software is for it to be widely used by other simulation professionals. We have made JaamSim free and open source so that more people will try it out and hopefully adopt it as their preferred software. At the end of the day, our reputation is more important to us than any money that JaamSim might have generated as a commercial offering.