Multi-processor concurrency

#1

I had an interesting idea last night: what if you had multiple processors running the same uLisp program? How would they communicate?

This isn’t the same as multi-threading, since all the threads running in the same cpu (regardless of how many cores) can access the same shared uLisp workspace, so a simple mutex is enough to prevent corruption.

If there are physically two separate processors, just hooked into each other so that they can communicate, a garbage collection on one won’t corrupt the other.

My idea is as follows: an extension for uLisp that would allow two processors with the extension installed to both run the same program and the code can communicate between threads via global variables without concerning itself with exactly how the processors communicate.

Whenever a global variable is changed, a message is blasted out to all of the other processors telling them what it was changed to, and this is caught in an interrupt, decoded, and updated locally.

When a thread running on one processor wants to spawn a new thread, it sends out a message querying the others for how many open thread slots and how much free memory they have. The sending processor then chooses one, serializes the code to be run, and sends it to the chosen target processor, and then both continue on with their respective threads.

The implementation would be designed in such a way that you could conceivably hook a Teensy up with a ATmega328 and neither would care.

How does this sound? Implementable? Impossible? I’m hoping this would enable uLisp users to increase their processing power by simply adding more processing power and then employing a divide-and-conquer strategy with data processing.

#2

Interesting idea!

Your idea could also work on processors with two cores, such as the STM32H747XI used on the Arduino GIGA R1. This has an ARM M4 core and an ARM M7 core, and it uses a Remote Procedure Call (RPC) to allow you to communicate between the two cores:

Guide to GIGA R1 Dual Cores

I was able to get uLisp running on both cores, but communicating between them using RPCs is not straightforward. Your idea sounds more intuitive.

Another chip with two cores is the RP2040, and it would be nice to be able to make use of both of them.

#3

As far as I know, the RP2040 has two identical cores and shared RAM, so a RPC type situation would not be necessary, only a mutex around shared memory writes.

I don’t have any experience with the Arduino Giga, but this might work to some degree. I was originally intending it to be a framework for running uLisp across physically separate processors that are hooked up to use the peripherals that they are best suited for, for example, having a STM32 run the main user interface, while a Teensy handles all audio related tasks, an ESP32 handles Bluetooth and WiFi, an ATmega32u4 (Leonardo) handles a USB interface, etc. etc.

And anyway, without any processor such as the ESP32 that natively supports multitasking, adding more physical processors is the simplest way to run multiple threads at once.

#4

The paper " Communicating sequential processes" by Tony Hoare, goes into some detail on how to manage coordinating multiple cores/processes. It lays out quite a good asyncronous event message passing style over channels which has been picked up by Clojure and a few other programming languages.

I think for uLisp’s case the easiest method would be to pin a REPL to each core and allow them to have a dedicated prompt stream to transmit uLisp back and forth. Micros with cores that share data, like the ESP32, usually have an existing SMP memory, thus updates to the shared memory is already managed with mutexes and is atomic.

#5

If some processor nodes have some features, and others don’t, then the algorithm to choose which processor to send a thread to will have to predict what features the thread will use. What if the code uses some features only available on one processor, and some other features that are only available on a different processor?

I think the best solution in this case is to force the user to be explicit when starting a new thread, as to which node they want it to run on.

For a full-automatic node-swapper program that always sends the program to the node that has features the program needs, it will need to have first-class continuations, so if it hits a point where the code must now be run on another processor, it can capture a continuation and send the serialized continuation to the other processor. Also if continuations are possible anyway, then threading is relatively easy.

The only problem is that currently uLisp isn’t written in a way that allows continuations to just be added as an extension, and would probably involve a substantial, if not complete re-write of uLisp’s internals. I’ll hold off with trying to do continuations until I see the next version of uLisp, but until then I don’t think anything in this regard would work.

#6

This has to be a solved problem without continuations, https://www.cliki.net/thread

#7

I was intending for something totally invisible to the end-user, i.e. it doesn’t require any special functions, macros, or syntax limitations. Without continuations, one of those would have to be used, and then that means if the user doesn’t write the code to use those, it won’t work.