The Transterpreter Project

Concurrency, everywhere.

Transterpreter Summer '09 - Day 20 - 172us

The underlying theme of the last few days has been commstime, a rather large program (in comparison to our earlier Arduino test cases) which also contains some calculations which use integers that are double the wordsize of the machine (32 bit calculations on the Arduino). While the last few days hacking has made it possible to run commstime, we have had to comment out the double word calculations in the program as the virtual machine did not support double length arithmetic on anything but 32 bit platforms.

The reason for this goes back to the compiler we initially used on Windows: the free Borland C compiler (BCC). It put some limitations on how we could implement the virtual machines long instructions, used in arithmetic on numbers large than the machines wordsize (ie long long ints). BCC only supports the C89 standard (which does not include support for long long ints). While we later moved onto MinGW which gives us a GCC compiler with C99 support, our initial implementations of the virtual machines long instructions were done in terms of single length words only. Fortunately the excellent book "Hackers Delight" by Henry S. Warren, contains algorithms for doing just this sort of thing. However, they assume 32 bit words and we have never, it seems, had a compelling reason to get these instructions working on 16 bit machines.

GCC's C compiler supports C99 as well as extensions to C89 that enables the use of long long ints. This allows us to implement the long instructions in terms of much more straightforward C compared to the algorithms from Hackers Delight. Changeset 5892 introduces C99 (long long int) versions of the long instructions, which are enabled if the compiler supports long long ints for the particular target architecture.

While implementing the long instructions were perhaps not the hardest thing in the world, there were some subtleties. Notably some casting issues where we have to be careful that signed ints did not get sign extended when promoted to unsigned long long ints, as the long instructions strictly work on unsigned values.


After fixing the long instructions we finally got to run commstime (committed as changeset 5894). The context switch time (that is the time it takes the runtime to switch between two processes) for the Transterpreter running on the Arduino, ie an ATmega328P clocked at 16 Mhz, is 172 us.

Looking forward

Our proress so far looks roughly like this: we have the ability run occam programs on the ATmegas (with parallel processes); blink lights (or more generally set the value of an output pin); put occam programs in the AVR's flash (to run large programs); do 32 bit maths (which we fixed today). In light of our achievements we spent the rest of the day pondering out next steps. Given that we have done various kinds of output, lights, printing to the serial port, it now seems natural to get some input going.

While we perhaps don't strictly need to deal with interrupts in order to do input on the AVR chips, we decided that this would be our next task to poke at. We decided on using interrupts as we almost certainly do not want to poll the input pins from within occam. It would be possible to poll the pins from the runtime itself, keeping a state of the values last time round and checking for change. For example, when the runtime goes through the scheduler to run a new process (something that usually happens fairly often in occam programs) it would poll the various input pins on which the user is currently listening. If a pin had changed, the runtime would send a message to any process which was waiting on that pin. This should be easy to implement, but has a few drawbacks: we would not be able to use any of the power saving features of the chip, as we would need to constantly spin looking for pin change events in order to generate 'soft' interrupts for the running occam program; and, since occam is co-operatively scheduled, there is a danger that a process could hog the processor for long enough that a pin change event would be missed.

Regardless of how we do implement the interception of external events, the interface we ultimately want to see most programmers that use occam on the Arduino to use is that of a channel. The channel abstraction nicely mirrors the interrupt mechanism1, where you declare that you want to wait for a particular event and are only woken when that event has actually occurred. We want our occam programmers on the Arduino to think about what they are going to do once something has happened and not have to bother with thinking about the, probably rather complex, machinery used to detect that the something has actually happened.

  1. Actually the channel communication is a rendezvous, where when the two parties that communicate are made runnable again, they both know that the other party has engaged in the communication. Ie, it is a synchronisation point in the code where we know something about the state of the two processes in relation to each other. This is not necessarily the same in interrupt driven programming as we are not necessarily able to acknowledge the interrupt (in the case of an input only device, such as a button for example). Some hardware, such as a UART, might work differently and require us to acknowledge the interrupt in order to stop it from firing again immediately after re-enabling interrupts.