The sire language and dynamic process creation

[Jamie]

I've just published a project called 'The sire language and dynamic process creation'. It's a milestone with my implementation work which I started in January 2010 for my PhD at Bristol. Here's the project description:

This project is an implementation of a simple imperative programming language called sire that allows the creation and placement of processes across a system at runtime. It includes a complete compiler and accompanying runtime targeted at XS1 devices, but in particular the XMP-64.

In essence, a sire program is compiled into a binary that is loaded only onto node 0, core 0 but when it executes, it is able to transmit descriptions of processes to remote cores in the system and invoke their execution. This is provided in the language by the 'on' statement. For example, the statement 'on 5 do process()' is exactly the same as a regular call 'process()' except that it is executed on the remote core 5, leaving the original core free to get on with other work.

For more details on all of this, a readme file is included in with the source code explaining how to get started with the source code and there are two accompanying documents:
- sire language definition
- sire language implementation notes

You don't need to own an XMP-64 to try it out; all the example programs can be run on the simulator and inspected using the trace output (There's another project you can use). It's all pretty experimental though so it won't be obvious to begin with what is or is supposed to be happening. Also the compiler hasn't been extensively tested so it might not be particularly robust but in any case, it should all be quite interesting to look through.

Please post up any comments or criticisms - I'm looking forward to hearing what people think!

[Folknology]

Wow this looks really cool, giving the docs a good read through, bound to have questions..

Regards
Al

[Folknology]

OK my 1st question Jamie:

(page 6, para 3)..The output operator can also
be used with ports.

What about port inputs?

Also I see no mention about timers, timestamps, or port buffering how does one deal with these Xmos features?

[Jamie]

What about port inputs?

Also I see no mention about timers, timestamps, or port buffering how does one deal with these Xmos features?

The language is intended to be a platform on which to demonstrate the mechanism for process creation. I included ports as it is invaluable to use the LEDs on the XMP-64 board when debugging, but I omitted everything else that wasn't strictly necessary in arriving at some results. As the project is currently focused on concurrent program structures (of which the distribute and mergesort programs are examples), features such as timers weren't necessary.

[Folknology]

Would you be open to idea of extending sire to including such functionality?

[Jamie]

Would you be open to idea of extending sire to including such functionality?

Absolutely, I've thought all along that it would be good to have a simple language and compiler targeted at XMOS hardware available for exactly that reason. I realise that C wasn't the best language to write it in - it gets a bit tricky doing all the data structure manipulations, but it's done now and it's all quite modular so it should be pretty intelligible.

[Folknology]

Well I guess some sort of 'ALT' or 'select' would also be considered for dealing with inputs/chans and or patterns in structured way, have you thought about that also?

[Jamie]

Well I guess some sort of 'ALT' or 'select' would also be considered for dealing with inputs/chans and or patterns in structured way, have you thought about that also?

I guess the kind of programs or programming that I'm looking at is more algorithmic and hence deterministic, so it hasn't been necessary to include a select to handle non-determinism.

[richard]

The protocol in your implementation document can introduce deadlocks:

Code: Select all

outct res[r11], CT BEGIN
chkct res[r11], CT BEGIN
out res[r11], r10
outct res[r11], CT END
chkct res[r11], CT END

To see the problem consider 4 threads using the following communication (using XC syntax):

Code: Select all

par {
  on stdcore[0]: {
     par {
       c <: 0; // thread 0
       c :> int; // thread 1
     }
  }
  on stdcore[1]: {
     par {
       c <: 0; // thread 2
       c :> int; // thread 3
     }
  }
}

Suppose there was just a single bidirection link between stdcore[0] and stdcore[1] (e.g. 1 XMOS link between 2 L1s). Suppose thread execution is such that the two output statement are reached slightly before the two input statements. Thread 0 will output a CT_BEGIN and wait to receive a reply. Since it has started a packet without closing it this prevents the sending of other packets over the link in the direction stdcore[0] to stdcore[1]. Similarly thread 1 will output a CT_BEGIN and wait to receive a reply. No other packets can be sent in the direction stdcore[1] to stdcore[0] until a CT_END is sent.

Because the link is taken in both directions the CT_BEGIN tokens sent by thread 1 and thread 3 won't be delivered to their destinations and all 4 threads will deadlock.

I'd advise using the standard XC protocol. For an word size output this would be:

Code: Select all

outct res[r11], CT END
chkct res[r11], CT END
out res[r11], r10
outct res[r11], CT END
chkct res[r11], CT END

[Jamie]

I'd advise using the standard XC protocol. For an word size output this would be:

Thanks for mentioning that - I hadn't thought of that happening.