News for hackers. Stuff that matters.
Re:A Programming Language with Deterministic Multithreading by Animats on Sunday January 31, 2016 @02:11AM (#11005594)
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?

Re:A Programming Language with Deterministic Multithreading by GuamPirate on Sunday January 31, 2016 @04:27AM (#11005833)
are you a markov chain?
Re:A Programming Language with Deterministic Multithreading by ramchip on Saturday January 30, 2016 @07:53PM (#11004668)
> 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.

Re:A Programming Language with Deterministic Multithreading by tormeh on Saturday January 30, 2016 @08:02PM (#11004703)
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.
Re:A Programming Language with Deterministic Multithreading by lkrubner on Sunday January 31, 2016 @01:26AM (#11005482)
"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.

Re:A Programming Language with Deterministic Multithreading by chrisseaton on Sunday January 31, 2016 @06:08AM (#11006023)
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.

Re:A Programming Language with Deterministic Multithreading by maattdd on Sunday January 31, 2016 @06:22AM (#11006060)
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
Re:A Programming Language with Deterministic Multithreading by junke on Sunday January 31, 2016 @03:05AM (#11005690)
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)

Re:A Programming Language with Deterministic Multithreading by tormeh on Sunday January 31, 2016 @12:28PM (#11007059)
>"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!

Re:A Programming Language with Deterministic Multithreading by quietplatypus on Saturday January 30, 2016 @06:47PM (#11004388)
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

Re:A Programming Language with Deterministic Multithreading by pmarreck on Sunday January 31, 2016 @12:46AM (#11005385)
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.

Re:A Programming Language with Deterministic Multithreading by EllipticCurve on Sunday January 31, 2016 @04:53AM (#11005880)
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?

Re:A Programming Language with Deterministic Multithreading by chrisseaton on Sunday January 31, 2016 @05:40AM (#11005970)
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?
Re:A Programming Language with Deterministic Multithreading by ketralnis on Sunday January 31, 2016 @07:22PM (#11008839)
Erlang is not deterministic
Re:A Programming Language with Deterministic Multithreading by EllipticCurve on Monday February 01, 2016 @01:20AM (#11010119)
Ah, ok, I see :)
Re:A Programming Language with Deterministic Multithreading by zem on Saturday January 30, 2016 @08:36PM (#11004822)
couldn't a function's inclusions be determined statically at compile time?
Re:A Programming Language with Deterministic Multithreading by ktRolster on Sunday January 31, 2016 @03:17AM (#11005716)
Often times people create a new language when all the really need is a new library.
Re:A Programming Language with Deterministic Multithreading by f2f on Saturday January 30, 2016 @07:46PM (#11004633)
someone should read Hoare's CSP paper and spend more time thinking, less time making graphs.
Re:A Programming Language with Deterministic Multithreading by tormeh on Saturday January 30, 2016 @08:17PM (#11004759)
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.

Re:A Programming Language with Deterministic Multithreading by rehemiau on Sunday January 31, 2016 @06:14AM (#11006045)
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!

Re:A Programming Language with Deterministic Multithreading by petke on Sunday January 31, 2016 @12:47AM (#11005389)
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.
Re:A Programming Language with Deterministic Multithreading by ketralnis on Sunday January 31, 2016 @07:40PM (#11008907)
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
Re:A Programming Language with Deterministic Multithreading by bnegreve on Sunday January 31, 2016 @04:50AM (#11005872)
This is debatable, SIMD instructions and GPUs are highly synchronized, yet they do help with scalability.
Re:A Programming Language with Deterministic Multithreading by petke on Sunday January 31, 2016 @09:29AM (#11006488)
Fair enough. I was talking about synchronisation of threads though.