A Programming Language with Deterministic Multithreading | Hacker News Reader

A Programming Language with Deterministic Multithreading

tormeh.github.io

78 pointstormeh24 comments

This sort of parallelism is common for big matrix number-crunching on machines with large numbers of CPUs. There's a big computational cycle, where lots of CPUs are turned loose on an isolated chunk of the problem. No shared state changes during this phase. When they're all done, there's a state update to shared state for the next round. For that kind of work, each thread does about the same amount of work, so the threads finish at roughly the same time. This is useful for finite element analysis, hydrodynamics, weather prediction, and similar large problems that decompose into spatial cells. If everything follows the updating isolation rules, results are repeatable.

But for real-time control?

are you a markov chain?

> The language I'm speaking of is designed for real-time high-reliability scenarios where ease of programming takes the back seat to correctness and determinism.

It sounds like the opposite - the setup allows for a low priority task to block every other task, which is normally the last thing you'd want in such a system.

Yes, this is a weakness of the model, but the key strength is that it will do so every time, which makes it way easier to test than the alternatives. Real-time doesn't mean that performance is as high as possible, it means that you can guarantee a certain level of responsiveness. A language can't do that for you, but it can help, which is why people use Esterel.

"Real-time doesn't mean that performance is as high as possible"

At one time "real-time" actually meant "real-time" as in "the sensor that determines whether to deploy the air bag in your car makes its decision in less than a ten thousandth of a second."

Nowadays, people are using "real-time" to refer to things that don't come close to being real time. If you allow a single thread to block all other threads than a thread engaging in a slow I/O operation could potentially block your whole app for several seconds. If that is the new definition of "real-time" than the phrase has become meaningless.

It sounds like you think real-time just means 'fast'. I don't think it ever meant that. In my mind it's about guarantees. 0.1ms to decide to deploy an airbag is a real-time guarantee, but so is 3s to decide to do something on a whole different scale like close a fire door.

So if the slowest thread blocks you, but you know it can't block you for longer than you care about, then that's still real-time.

Real-time is about guarantee, not speed. I suggest you to read the Wikipedia article which is pretty clear https://en.wikipedia.org/wiki/Real-time_computing

I understand that one semester is short and I think you did already a great job.

I don't really understand what Fumurt brings compared to existing approaches. It seems that you are blocking all threads at one rendez-vous point and that seems too radical, though. Also, "underthreads" could result in a unbalanced system where one thread does most of the work while others are waiting. Automatic ways to distribute code among tasks exist in synchronous language (I don't think synchronous languages necessarily sacrifice performance).

It seems you did a lot of work on the parser and compiler. You also use synchronized variable which seems a little odd: you say that "[...] the programmer doesn’t have to worry about the order in which a synchronized variable is written to by the different threads.". Do different threads really want to write the same variable during one timestep?

You mention Esterel and synchronous languages. I am not sure Esterel (or Quartz[1]) is the most widely used implementation. I would bet on Scade, a child of Lustre, but I am not sure. As you say they support a way to distribute code among execution units and Signal[2] in particular is designed to make it easy and efficiently compilable.

In Signal, you define processes and map them to different execution units through a "RunOn" directives. The Signal compiler then statically compute the order by which I/O and computations are executed on each concurrent thread (posix threads and fifos or MPI). There is also a lot to say about logical clocks which allow to transmit only the necessary information to synchronize distributed code. The result is very little scheduling code: only signal/wake instructions surrounding sequential code with nested "if" blocks for clocks (activation condition).

So while you did a lot of work for this language, I fail to see where your approach is beneficial compared to older ones. I mean, existing languages surely could be improved, but what could convince a user to switch to this one? (a hard question, sorry).

[1] https://es.cs.uni-kl.de/publications/datarsg/Schn09.pdf

[2] https://en.wikipedia.org/wiki/SIGNAL_(programming_language)

>"underthreads" could result in a unbalanced system where one thread does most of the work while others are waiting

Underthreads is a mechanism I propose to speed up the slowest top thread in cases where this can be done. Like, you benchmark the program and see that one thread is holding it up. This thread has a workload that's easy to multithread, so you use underthreads to (hopefully) speed this thread up and fix the bottleneck.

>Do different threads really want to write the same variable during one timestep?

No, they are not allowed to. Every shared variable has an owner thread which is the only thread that can write to it. Hence there's no need to worry.

>what could convince a user to switch to this one?

Hopefully nothing. It's useless as it is. It's meant more as a contribution to public thought about hard real-time languages. If someone decides to use my code for anything then that's cool, but that's not important.

Every search for Scade ends up pointing to Esterel Technologies, which confused me, I guess. Didn't really know about it. Signal sounds interesting!

Why do we need a language to enforce this discipline of threading? Can't we just take away the lessons?

- explicitly label shared data and control flow - group together where the top threads are spawned

Less "deterministic multithreading," more "side-effect-free multithreading," IMHO.

If your tests depend on thread order, they are bad tests or your code or design is bad. Period.

Wait, isn't Erlang the exact language of choice for that?

I read the title and thought - Oh, nice, an article of Erlang.

It seems the perfect fit ...?! Why reinvent the wheel?

Is Erlang deterministic? If I have two processes send a message each to a third process then they could arrive in either of two orders - that's a race condition and non-deterministic isn't it?

Erlang is not deterministic

Ah, ok, I see :)

couldn't a function's inclusions be determined statically at compile time?

Often times people create a new language when all the really need is a new library.

someone should read Hoare's CSP paper and spend more time thinking, less time making graphs.

I can assure you that I did not spend a full semester making graphs. I know it's not the first deterministic concurrency model. Thank you for making me realize that the concurrency model described can be modeled using CSP. That's neat, considering all the analysis tools available for it. Determinism is not enough, however. The space of all thread state combinations need to be reined in, not least because while deadlocks & co. can be found using automated tools, subtler errors can't. Additionally, threads compete for resources, and you need to account for hidden sources of indeterminism like that one. Two logically independent threads that can be modelled and trivially shown to not interfere with each other will definitely interfere with each other on a single-core system.

I realize that this is an unusually strict approach. I'm also terribly embarrassed if there's something I haven't considered.

You should not be embarrassed. You did a thing and learned a bunch. Not knowing everything often leads to innovation, as knowledge can be a burden. I admire you!

That said, there's always more to know. I'm happy hackernews people are so critical and insightful with their comments. Good job and carry on!

Truly deterministic multithreading is really just single threading. Multithreading is by its nature undeterministic. To make it deterministic you really have to synchronize enough until just one thread at a time is making progress. It kindof defeats the purpose of multithreading. Synchronization is the enemy of scalability. You want to avoid it at all costs.

That's true if all operations and intermediate states must be determistic, but if instead you only need some things to be deterministic then the cost is a lot lower. For instance, if you spawn a bunch of threads and join in them in the same order they were created, the order of the results you gather from them can be always be the same even if they didn't complete in the same order. The computation phase didn't pay any synchronization cost, but the gathering phase did

This is debatable, SIMD instructions and GPUs are highly synchronized, yet they do help with scalability.

Fair enough. I was talking about synchronisation of threads though.

Reply on news.ycombinator.com