Concurrent programming that executes the multiple threads' cycles simultaneously?

Question

I was wondering if anyone knew of a concurrent (i.e. multithreaded, parallel, etc.) programming language that was set up such that the individual threads would not fall behind each other simply because the OS failed to provide them the CPU time. I'm not even sure if assembly can avoid this. :P But I am, obviously, unsure, hence the question.

I'm not saying the program needs realtime access to CPU cycles, I'm saying that the threads shouldn't fall out of sync. Also, it would be really nice if the language compiled to a binary executable rather than bytecode, or simply to be run by an interpreter.

Answer 1

With modern processors, it is extremely hard to make sure that any specific computation proceeds at an absolutely known rate.

For instance: a thread that takes a cache miss may need several hundred more cycles, than that same thread with a cache hit. So now speed depends on what is in the cache. What is in the cached depends on the complex control and data flows executed by the thread in the past. There are lots of sources of uncontrolled delays (pipeline breaks, variable length instruction execution depending on operands, internal resource contention in OOO CPUs, memory delays through various memory hierarchies and across buses to other CPUs, message transmit/receive time, ...)

So, to make threads proceed at exactly the same rate requires vast amounts of control or prescience that you pretty much can't get. (Supercomputing guys pretty much turn off the OS to minimize the background noise, e.g., from interrupts occurring at random times. Even this doesn't help enormously).

A better approach is to have threads signal that the work they have done, is available to another that needs its. If the signaling/waiting occurs only rarely, then it is swamped by the computational work of the threads and the processors are used efficiently.

It is still difficult to achieve the above. If you do the same computation on all CPUs [e.g., big data parallel computations], and it is very regular, the overall rate may be pretty similar; you'll still need some (barrier) synchronization at the end to make sure they are all back in lock-step.

Its pretty hard to organize all computations as "the same" on every CPU. It is more likely that you have lots of irregular (varying size) computation "grains". If you can track those, then you can distribute those across many threads/CPUs, count on explicit synchronization between individual grains to make them work correctly overall, and handing new grains to a suddenly idle CPU so they stay busy. This is accomplished nicely by the concept of "work stealing": each CPU has a pool of unexecuted grains it can run and it processes them as fast as it can. Grains may manufacture more grains (if you run out, you're done computing!). If a CPU's pool of grains gets empty, it steals work from the pools for other CPUs. A work stealing scheduler is pretty hard to build; they have to be right, and avoid CPUs continually interfering with each other, because that's just wasted cycles.

Our PARLANSE parallel programming language is designed to handle exactly such problems. We run it on very large graphs representing programs; it tends to generate a bit of work for each patch of modest radius in the graph. With a million nodes in such a graph, we get lots of bits of work to do.

Answer 2

I do believe there is no such thing.

The reason why is that multiple threads can only truely be executed in paralele if they are executed on different core. In fact, until the apparition on multi-core processor, it was technically impossible to run (compute) different threads at the exact same time.

Modern OS use an extensive amount of process and therefore of threads (at least on thread by process, the threads being the "working" part of processes). Despite multicore processors, in all common usage you still have more thread active on you system then available cores.

As I write those lines, I have 357 threads actives for "only" 8 availables cores.

Thats what schedulers are used for. They share the avalable compute time among the different threads to avoid starvation and give the illusion of simultaneous execution.

For garanting that differents threads run at the same time and are not being put over form time to time you should modify the OS's Scheduler wich, if possible, is at least a bad idea.

The use of an interpreter won't help as the only for it to run multithreaded application is to create interpreting threads wich will have the same issues

For making sure differents threads are synchronised you should use barriere or semaphores as you'll never be able to modify the OS's Scheduler of user's computer

---

Note: In HPC application, researcher try to avoid losing time in context switchs (the operation that save the environment in which a thread is running to restore it later). Therefore they allocate thread according to the available cores (usualy they juste left one core for the OS and I/Os) and pin the other threads to specific cores. That helps them enshure computation is done as efficientrly as possible.

That doesn't however garanty synchronisation, and the use of specific mecanisme like barriers may still be required.