New features in KRoC

November 15, 2009 – 8:20 pm

We’re all back from a very successful Communicating Process Architectures conference in Eindhoven, and we’ve just added most of the new things that we’ve been working on this summer to the stable version of KRoC. Changes this time include:

  • The Transterpreter (our occam-pi runtime for small devices) can now run on the Arduino, and other devices that use an Atmel AVR microcontroller — see our CPA 2009 fringe presentation. We’re working on making it easier to set up at the moment, but if you want to try it out now, there are some preliminary instructions available already.
  • Work on the CCSP scheduler to improve performance on multicore systems continues — see our paper from COORDINATION 2009 for a description of the scheduler’s algorithms and scalability benchmarks against a selection of other concurrent runtimes.
  • The occam compiler now has initial support for automatically generating CSP models of processes, so you can use external tools to analyse and model-check your occam programs — see our paper from PLOS 2009.
  • The occam compiler now recognises SIGNAL as a new built-in variant protocol, with the single case SIGNAL — useful for channels that are only used for notification, and don’t need to carry a value.
  • We’ve added time.module, with several useful PROCs and FUNCTIONs for working with time in occam — for example, you can now write seconds (3) rather than specifying everything in microseconds.
  • We’ve also added random.module, which provides a flexible random number generator suitable for games and simulations.
  • We’ve made lots of little changes to make it easier to build packages of KRoC for various operating systems, and to cross-build KRoC for a different operating system or architecture.
  • … and, of course, we’ve fixed several bugs reported by KRoC users. Thanks very much — please let us know when you find something that’s broken!

For more information on KRoC and how to install it, see the KRoC home page.

In other recent concurrency news: the new Go programming language uses the process-oriented model of concurrency, and those of you working with concurrent Haskell programs will want to check out Neil’s new Communicating Haskell Processes blog…

Adam (on behalf of all the KRoC developers)

Report post

New mailing lists for process-oriented programming

May 27, 2009 – 2:47 pm

We’ve just set up two new public mailing lists for discussing process-oriented programming:

  • pop-users is for people using, or learning to use, process-oriented
    programming techniques. It aims to give users somewhere where they can
    discuss occam-pi, the Transterpreter, JCSP, CHP and other
    process-oriented technologies, and get help with problems they’re
    having.
  • pop-dev is for people who’re working on the languages and tools
    themselves; it aims to replace most of our low-traffic development lists
    like kroc-dev and tvm-dev.

Adam

Report post

New features in KRoC

March 30, 2009 – 3:07 pm

KRoC is our suite of open-source software for occam-pi development, including compilers, runtime systems, libraries and example programs. We’ve made some significant changes to KRoC recently that are likely to be of interest to users.

First, KRoC now includes the Transterpreter. The Transterpreter is a highly-portable virtual machine for running occam-pi programs; it makes occam-pi available on architectures other than IA32, and particularly on embedded devices. The Transterpreter was originally developed as a separate project, but it has now been integrated into the KRoC source tree: you can specify when configuring KRoC whether you want a toolchain based on IA32 native code generation or on the Transterpreter. This means that the KRoC suite should now be much easier to get running on new architectures. In addition, platforms already supported by the Transterpreter now have access to all the KRoC standard libraries and utilities.

Second, we’ve been reworking KRoC’s build system. Previously, KRoC consisted of a number of small packages which had to be installed in a specific order by the “build” script. Now, KRoC is one large automake project, and can be installed and packaged using the standard “./configure; make; make install” sequence. This makes KRoC development more straightforward, and makes it much easier to package KRoC for operating system distributions. Regular users can continue to use the “build” script (now much simplified).

Finally, we’ve added several new libraries recently that will be of use to occam-pi programmers:

  • graphics3d provides a pure-occam 3D rendering engine, including a recreation of the INMOS butterflies demo.
  • selector allows occam programs to wait efficiently for events on file descriptors.
  • trap is a low-overhead asynchronous network messaging framework aimed at distributed complex systems simulations.
  • ttyutil provides facilities for curses-style terminal displays.
  • useful offers a number of general utilities missing from the existing libraries, including string formatting, debug tracing and vector mathematics.
  • video provides access to Linux video capture devices.

These facilities are now available in the stable version of KRoC from Subversion. For more information about installing KRoC — and the new options available — please see the Installation page on the KRoC wiki.

Adam, Carl and Fred.

Report post

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

Usage-checker feedback

March 27, 2009 – 9:00 am

This week I have been trying to get some real occam code (as opposed to benchmark suites) compiling in Tock, our new occam compiler written in Haskell. One of the things that the old compiler, KRoC, was missing was the ability to check dynamically-sized PARallel blocks for safety, because its original code (before these dynamic PARs were allowed) checked everything statically. Tock implements Pugh’s Omega Test (see my slides for an explanation), which allows us to check these things. And so, I found a piece of unsafe code that KRoC had let slip, but Tock flagged up:

PROC mixer ( [ ] CHAN SIGNAL in ? , VAL [ ] REAL32 level , CHAN SIGNAL out )
   WHILE TRUE
     INITIAL SIGNAL sum IS signal ( [ i = 0 FOR BLOCK.SIZE | 0.0 ] ) :
     SEQ
       PAR i = 0 FOR SIZE in
         SIGNAL s :
         SEQ
           in [ i ] ? s
           SEQ j = 0 FOR BLOCK.SIZE
             sum [ j ] := sum [ j ] + ( s [ j ] * level [ i ] )
       out ! sum
:

For those not so familiar with occam, this code takes a list of reading/input channel ends, and loops around: it reads from each channel in parallel, then (still in parallel) merges the results of the channel communication into a shared variable. After that it sends out the merged results. The race hazard here is that two (or all of) the processes might update the merged array at once. This can be fixed by changing the PAR to a SEQ, or by reading to separate arrays and merging afterwards. What I became slightly interested in (after fixing a bug) was the error message we give. At our disposal is a list of equalities and inequalities giving an example of when the code can be unsafe. In the latest code, the full list would be:

(SIZE in) - i - 1 >= 0
(SIZE in) - i' - 1 >= 0
i >= 0
i' - i - 1 >= 0
i' - 1 >= 0
j >= 0
j' >= 0
63 - j >= 0
63 - j' >= 0

Hmmm. That’s about as helpful as some Haskell type errors, where the only useful part of the error is the source file and line number. i and j are index variables of replicated PARs, and i’ (i-prime) and j’ are dummy variables. We effectively check two instantiations of the replicated PAR, one with (say) i and one with i’ (where i is not equal to i’) to check for possible problems. Thankfully, the code already does some simple (syntactic, rather than semantic) rearrangement into this state:

tock: Error: basic.occ:60:11 Indexes of array "sum" ("j" and "j")
  could overlap when:
(1 + i,1 + i') <= (SIZE in)
0 <= i <= -1 + i'
1 <= i'
0 <= j <= 63
0 <= j' <= 63

That’s a bit better. Effectively the code collects lower and upper bounds for each variable, does some cross-multiplication not relevant to this example and lists them with one variable per line. Leaving aside any further extensive numerical processing on the inequalities, perhaps we could rearrange them to be even more helpful. This could actually make a small undergraduate assessment (we set our first year undergrads similar problems).

Something to spot would be that the upper-bound x <= y – 1 could be changed into x < y (all our problems are on integers). Similarly, the lower-bound y + 1 <= x would become y < x. So this could simplify our output to:

(i, i') < (SIZE in)
0 <= i < i'
1 <= i'
0 <= j <= 63
0 <= j' <= 63

This would make it a little clearer, but perhaps the more important issue here is how we could provide the output that would best lead the programmer to the cause of the problem. In this case, the brief summary of the constraints is: “whenever (SIZE in) is 2 or larger, your code is unsafe for all values of j”, but whether a program can reasonably approach that level of summary is another matter.

Neil.

Report post

CPA 2009

March 26, 2009 – 6:19 pm

We are pleased to announce the Communicating Process Architectures (CPA) 2009 conference, which our group is involved in organising.  This year the conference will be held in Eindhoven (The Netherlands) as part of Formal Methods Week 2009.  All submissions related to concurrency are welcomed. All the details are on the webpage; most importantly, the CFP deadline is 29th June 2009 (slightly later than usual).

Report post

Protected by Akismet. Blog with WordPress.