CHP 1.2.0, now with Clocks

March 27, 2009 – 11:00 am

The announcement is slightly delayed due to setting up the blog, but last week I released version 1.2.0 of the Communicating Haskell Processes (CHP) library.  CHP is a Haskell library with explicit, monad-based concurrency and synchronous message-passing (see the original paper on CHP).  Alongside various small changes, version 1.2.0 adds an implementation of Adam‘s ideas for clocks.

A clock is a synchronisation primitive somewhere between a barrier and a timer.  A clock has the notion of enrollment, so that at any time a certain number of processes are enrolled on the barrier.  Each of these processes may then wait for a time, T (we say: offer T).  Once all enrolled processes have made an offer, these times are sorted, and the clock’s time advances to the next-soonest of all the offers.  So if there are four processes enrolled on a clock with current time 1, and they wait for times 3, 7, 3 and 4, the time will advance to 3, and two processes will wake up, while the other processes will remain sleeping (waiting for times 4 and 7).  There is more information in the documentation.

This is an efficient way of implementing logical-time (rather than real-time) in simulations.  Previously we would use a barrier, synchronising at the end of each time-step, but this was time-consuming if not every process needed to act every time-step, and we had a lot (perhaps hundreds of thousands) of processes/agents.

Adam originally implemented clocks as a process in occam — processes would send time offers via a channel, and wait to hear back on a different channel when their offer became the latest clock time.  I implemented clocks in CHP on top of Software Transactional Memory (STM).  The implementation was straightforward once Adam and I realised that we did not need choice on clocks.  Once all processes offer on the clock, time will advance — if one process later retracts its offer, it was hard to come up with a sensible and useful semantics for what should happen.

When it came to implement the API for clocks, it was apparent (especially in Haskell) that time should not have to be an integer.  The nice thing about Haskell and its type-classes is that it makes explicit the requirements on your type-parameters.  It turns out that for times in clocks, all you need is Ord (i.e. the ability to compare two times).  No arithmetic is required on times, nor Enum (to advance time by one unit).  The processes using the clock determine the next time, so all that is required is to find the next-soonest of the offered times.  We even added in the ability for time to wrap around; if the current time is 8 and the offers are 1, 3, 4, the new time will be 1.  This does not need Bounded (to find bounds), only Ord.  This is particularly useful combined with a Haskell type such as:

data Phase = Discover | Movement | Render deriving (Ord)

One can code passive agents in a simulation that only render by continually waiting for the Render time.  If these are the only agents in your simulation (perhaps temporarily at the beginning of the simulation), the Discover and Movement times will continually be skipped over.  If there are other processes, they will act on all three phases while your passive agents continue to only act in the Render phase.

Neil.

Report post

Leave a Reply

Protected by Akismet. Blog with WordPress.