The future of programming.

[Julian]

It's post like this that makes me proud of this community.

Anyway, I too thought of the problem like Graf Zahl did and I'm afraid a language will not be enough.

You'd need an OS that actually acts as the intermediate to assembly code translater of today's compilers. All apps on this OS would have to be written in a very high-level language with a degree of abstraction much more important than what we have today (don't ask me in which form, I have no clue, but probably exhibiting properties similar to Haskel) and an equally high-level standard library.

The idea is that the more high-level your program concerns are, the more opportunities for optimizations there is (somehow counter-intuitive but I think we, coders, tend to confuse having control and writing efficient code).

Oh well, anyway, just wanted to contribute to this fine discussion :)

[Maes]

Hey who knows maybe Befunge is the programming language of the future. Compared to that, even the most abstract and layered enterprisey factory of factories of factories seems like child's play.

Now, take Befunge, throw some lambda calculus in it and make it functional.

It will be so hard to write anything remotely sane and optimized in it, that the slightest improvement the compiler might provide will seem like heaven. ;-)

But TBQH, I can only imagine sad larval stage hackers tinkering with such a Turing tarpit for more than 10 minutes in their whole life ;-)

If anything, because it's preposterous to ask of a novice programmer to think in terms of functions before he has even ran his first hello world.

[grubber]

I find your attitude of "I don't know anything about Haskell or functional programming, but it surely must suck" quite silly. But that's just me.

[Maes]

I find your attitude of "I don't know anything about Maes or his actual knowledge of Haskell or functional programming, but they surely must suck" quite silly. But that's just me.

P.S.: I hate this provincial "WE DON'T LIKE THIS KIND OF ATTITUDE IN OUR NECK OF THE WOODS!!!" attitude as well. But that's just me.

[grubber]

I wasn't talking specifically to you.

[Maes]

Aha. Exploiting the singular/plural form ambiguity of the "your" adjective in the English language, are we?

[grubber]

Yes, we are. My apologies.

[Maes]

Awwww

[DuckReconMajor]

Once when I did that I accidentally called my Spanish teacher fat.

[Gez]

English is a silly language. It had a perfectly serviceable second person singular pronoun, and decided to drop it altogether to make things more confusing.

[Maes]

And then there's still the your/you're debate to settle. Even the greatest Internet Grammarian Elders haven't been able to definitively solve this one.

[Aliotroph?]

What debate? Did I miss something. All I see is a huge number of people who confuse those for no reason.

Also, I decided I have to think a lot more about the whole parallelism thing before I can say very much that's constructive -- and then it still won't be that good, because I never solve those sorts of problems.

[Ladna]

I think the biggest obstacle between us and parallel programs is memory management and access. The definition of "embarrassingly parallel" usually means "these different routines don't access or modify the same things in memory". The problem is creating a general solution for computation that doesn't fit this definition. As soon as you create locks/mutexes/semaphores you're introducing overhead, deadlocks, and starvation. You can build seriously sophisticated schemes for dealing with those things (Linux's I/O scheduler for instance), but not only will you create more bugs, you'll spend the rest of your days tuning the thing for different workloads. And really, threads and locks are high-level instruments; past a certain point the overhead of lock acquisition and context switching will curb your scaling.

So I think the solution will fundamentally involve read-only memory of some kind. Really you can label a lot of parallelization problems as memory access & modification problems (side-effects, simultaneous modification, data structure mutation, etc.) and quite a few of them go away when you can mark your data structures as immutable... but not all of them of course.

Programming language semantics are a different issue, and I think the language that comes closest to explicitly handling parallelization is Erlang. The Wikipedia page has the requisite examples of factorial and quicksort, but the best example is under Concurrency and Distribution Orientation where the use of channels is pretty explicit. I like this because it can function at whatever level you want; you can parallelize at the function level or you can parallelize specific processes (like rendering columns in a software renderer ;) ). I'm a little wary of the fact that the only thing Erlang seems to be used for is network applications, but hopefully that will change at some point.

I do have to disagree with the premise that all parallelization is just some kind of abstraction for threading. A thread is an abstraction for the program explicitly telling the OS to create another thread of execution inside its process space, and letting the OS handle scheduling: either switching between them very quickly or using a different processor. One counter-example is Erlang's "processes" (not an actual process), which are scheduled by Erlang itself and cannot access the memory of other processes. Another is Python's "multiprocessing" library, which actually spawns processes and sends them jobs. In the same vein, Apache's famous prefork model has nothing to do with threading, but achieves parallelization all the same. Concurrency, parallelization and multithreading are not the same things at all, even though it's hard to deal with one without dealing with all of them.

[Maes]

Ladna said:

One counter-example is Erlang's "processes" (not an actual process), which are scheduled by Erlang itself and cannot access the memory of other processes.

That's a pretty restrictive assumption, and only fits well for totally isolated problems with minimal inter-process communication or composite results. Also, unless Erlang allows for a shared memory model, it would be a killer for large data sets, as it would require duplicating or carefully splitting tons and tons of read-only data across different processes, or else use costly inter-process communication. Guess what, that's exactly what MPI does.

To make an example, to parallelize a sum of an elements of vectors, in serial code I need just one accumulator variable where I just keep adding stuff into that one variable and get the result in the end.

As you said, there's is "read only" data in this problem (the vector itself) but I need to get a RESULT out of all this trouble, so there's something I need to write to. And that's where the trouble starts.

If I simply execute the addition in parallel still using one variable for accumulation, I may run into operation atomicity and cache coherency problems, no matter if I use threading or raw, directly controlled parallelism with pure assembly.

So, a more sensible solution would be to isolate each "thread" from the others, not for the vector (which needs to be either shared in memory, or -worse- replicated across processes) with its own accumulator variable, and add everything in the end when ALL threads have completed their job. This way, no thread stomps on the local accumulator of other threads, and since the vector is read-only and concurrent READS generally don't pose problems, you will be fine.

But, alas, you're not done yet! You need to know when ALL threads have finished (or else you'll get incomplete results) and you need to make sure that at some point, they will "join" back with your main program and "report" their partial results.

What I described is actually pretty transparent for the programmer when using OpenMP (in shared memory systems), while with general purpose languages you have to implement these steps yourself using library functions and objects.

We really need to clarify if we're talking about some yet-to-be found, miraculous change in machine architecture (maybe quantum computing?), programming languages or just human intuition that will somehow make this approach totally obsolete, or merely throwing syntactic sugar over what is essentially a rinse-and-repeat series of actions, well understood and documented by the current state-of-the-art in CS.

As for Multiprocessing vs Threading: you can have one without the other, that is true.

But for all effects and purposes the majority of commercially interesting "parallel programming" AND "multiprocessing" takes place in desktop multi-core CPUs, on OSes whose best tool for providing the latter is Threading, so in the end any and all languages will translate code into threads, mutexes, semaphores etc., and IMHO perpetually masking this from the programmers or deluding them that There Has To Be Another Way is a Bad Thing.

There are other important practical non-threaded models of parallel computation, e.g. GPGPU programming, DSP programming, VLIW CPUs, etc. but I take we're not considering those forms in this discussion, at least so far.

I also may be a bit biased by my parallel number crunching background, so I tend to see most "parallel computing problems" in terms of "load a shitload of data, split the job between , fire up the threads, sync up where there are coherency-breaking data dependencies, and scoop up the result in the end".

[Shaviro]

To those familiar with C# and LINQ, 4.0 introduces a few easy-to-use commands with PLINQ (Parallel LINQ). Like if you have a list of stuff to search in or do whatever query it is you want, you can write something like:

var stupidResults = (from retard in retardList.AsParallel() where retard.Stupidity > 80 select retard);

AsParallel() makes it go all parallelicious.

[Ladna]

I don't know why Erlang calls these things "processes", they're really not processes at all. There's 1 Erlang VM and a process is an internal abstraction. They also use the term "IPC", but again, it's not really IPC like SYS V IPC or something like sockets. So it doesn't really suffer from IPC overhead... but then again it's not like overhead doesn't exist; the wiki page says it's 300 bytes per message... which honestly is kind of huge.

Overall I agree with you, one of the tradeoffs I think you have to make for robust, scalable parallelization is higher memory usage. The cool thing about huge data sets is that memory is cheap; and honestly if I'm working on that kind of scale I've already got a dozen machines or a cluster (like this mofo I used to use). But really I'd probably use MPI for large, one-off jobs. Erlang is more for writing robust, scalable apps, not necessarily for processing large data sets. The vector example is just another form of the "large data set" problem, which again MPI is best at I think.

And I personally think current hardware isn't a barrier against parallel programs, if anything the faster, wider busses, faster memory & cache, and of course proliferation of multi-core processors give us all the tools necessary. The issue is creating a natural language to express parallel programs in. C works wonderfully when you're working procedurally, Java is the idiomatic OOP language, I'd probably still say that Scheme is the idiomatic functional language even if it's hard to argue against Haskell at this point, but so far I'm not sure there is a language that defines a "parallel programming" style. Erlang is much more concerned with concurrency than parallelization, and functional languages are only parallel by accident - and you can't really control the level of parallelization either. All that said, I still believe we can create a software system that allows for elegant, obvious, and powerful parallel programming.

so in the end any and all languages will translate code into threads, mutexes, semaphores etc.

No. Threads are implemented by the OS, not by hardware. There's no x86 instruction for thread creation, much less a futex or a lock. Threads are not the basis for parallelization or concurrency, I can write a perfectly concurrent program using my own scheduler and never call clone().

What I think you mean is that if your goal is to execute something in parallel in a single process then you need to use OS threads. I agree. In fact this is what the SMP versions of Erlang do. I just think they should be tucked neatly behind a thread pool and an event loop. Each instance of "pthread_mutex_lock" in a program is a futile attempt at trying to fix it, unless your program is very small or it's a kernel. I just think threads are too coarse to be an elegant solution to the parallelization problem.

[Maes]

Ladna said:

I just think threads are too coarse to be an elegant solution to the parallelization problem.

Maybe they are, but they are also the only viable general-purpose construct that allows you to perform arbitrarily complex tasks with all the expressiveness and power of a standard procedural or OO language, from number crunching, to async network traffic management, I/O, garbage collection etc.

There sure are more elegant ways...only that they are more attuned to very specific problems.

E.g. a systolic array will perform a polynomial computation in constant time and in apparent parallelism with no effort other than...well, actually ASSEMBLING the damn thing in hardware.

A GPGPU or Vector processor may offer you "inherent" parallelization on certain operations (as do MMX and SSE instructions on x86) but they are only useful for singular operations, not for keeping track of e.g. a network router's innards.

And of course you can program a multi-CPU system the old-fashioned way and handle the CPUs yourself, but in the end you will too resort to creating your own version of constructs similar to the mutex, the semaphore...and *gasp* the thread. The Thread is to parallel computing what the Heap and Stack are to traditional procedural computing: an essential data structure. Try to do without it...you'll only reinvent the wheel, perhaps in a cruder or simpler form that suits your tasks better.

Under that perspective, the good old Thread is a decent compromise between low-level "Master-Slave" CPU direct control, and the generalit afforded by traditional procedural programming, while the sort of parallelism present in GPUs, DSPs etc. is admittedly alien.

Perhaps a pure mathematician doesn't want to know anything about accumulators, futures, thread barriers etc. OK, I can understand that.

The alternative is using either sugar-coated languages and compilers which will ultimately translate everything to a threaded mess (perhaps by cross-compiling to C), and may consider a systolic array a purer approach...well, let him acquire 20 MSc's in Syst.Array design before he can come up with a useful one, then :-p

And good luck PROGRAMMING it to do anything other than what it was hardcoded to do ;-)