“Concurrent programming is difficult, yet many technologists predict the end of Moore’s law will be answered with increasingly parallel computer architectures – multicore or chip multiprocessors. If we hope to achieve continued performance gains, programs must be able to exploit this parallelism. Automatic exploitation of parallelism in sequential programs, through either computer architecture techniques such as dynamic dispatch or automatic parallelization of sequential programs, offers one possible technical solution. However, many researchers agree that these automatic techniques have been pushed to their limits and can exploit only modest parallelism. Thus, programs themselves must become more concurrent.”
well, that was a pretty weak paper, especially for IEEE, even given that it was in Computer. It said nothing we didn’t know about concurrency 20 years ago and missed more than a bit of what we did know.
Pity it missed the key way of avoiding concurrency problems: competing rather than cooperating.
ah well.
Pity it missed the key way of avoiding concurrency problems: competing rather than cooperating.
Competing?
Jargon from the early days of SMP based concurrency.
Parallel programming approaches tend to rely on cooperative multi[threading,tasking,your-favorite-name] to accomplish their goals. The advantage is scalability if the problem has fine grain parallelism. (We used to call such programs ’embarrassingly parallel’.) The disadvantage is complexity of synchronization and difficulty of application to all but a handful of problems.
Contrast this with opportunistic systems in which the work is divided up ‘naturally’ into tasks that are as independ as possible, usually by the logical organization of the overall problem, and then the tasks compete for the resources. The classic example is job shop scheduling. The advantage of this approach is that synchronization tends to be simple and falls out along the lines of the real-world system being modeled. The difficulty is that it takes significant insight into the actual problem to organize the solution efficiently.
Of course, the extreme case of competitive concurrency is to just throw a lot of users at the system and let each user’s individual problem compete for resources with the others.
Those are two different paradigms for programs. How do you execute a secuential program as if it were non sequential? That’s stupid. Most programs are a sequence of instructions that need to be completed in order to complete the next step. You could achieve a slight performance increase by executing in parallel some function that is independent from the state of other sequential functions. But there’s not much gain from that if the program was designed to be sequential, as most programs are given their nature.
Multiple cores bring the benefict of parallel executing multiple processes (as in unix processes).
Multimedia applications, 3D games can be veri well vectorized/parallelized to mutliple cores/CPUs/cluesters using multiple threads/processes.
http://en.wikipedia.org/wiki/Stream_processing
I think the point you’re missing (and why parallelism isn’t designed into *everything* right now) – we’ve been writing programs the way we have (sequentially) because that’s all we were capable of barring HPC stuff (out of the reach of most mortals!)
Many tasks can be optimized for parallelism, but it requires a totally different type of thinking/thought process to accomplish. It opens a lot of doors for creative design, and methods for doing things we haven’t investigated yet.
There are some tasks which *have* to be done sequentially. This is true. There are many tasks that do not, but we currently perceive them as being sequential-only because that’s what we’ve been trained to do.
Parallelism (multi-threading, or however you achieve this) requires a new way of looking at problems, and most people haven’t gotten this down yet. The capacity is there, and the proof is in the pudding. For instance, check out “Vision” for BeOS. My good friend Anevilyak wrote it, and while it is “merely” an IRC client, it is highly threaded – as is most of BeOS/programs for BeOS.
Most tasks we work with on computers are event-driven, or *could* be event-driven. These kinds of tasks lend well to threading, because you don’t have to limit yourself to handling one event at a time. Not only that, but you can request multiple things at once, and get multiple responses at one, and this information can be combined (either by us, our own information processing – or by the program) to give us aggregate results which are much better than individual results taken apart from each other.
Think about it, that’s one of the things that makes us (humans) so “intelligent”. We are extremely well adapted to handling multiple sources of information at the same time, aggregating it, and making good decisions based on this information. A computer is gazillions of times better at information input/output/processing, so it could “offload” this from the human, and all we’d be left doing would be filtering the aggregate information for “worth” or “value”, which is really what seperates us from the machines. We can act intelligently based on the information the computer provides us, all in an instant. Imagine getting a book full of information at once instead of having to go page by page.
Obviously we are limited as humans in how much we can take in at once, but computers have limits much higher than ours in this regard, and when well designed programs take advantage of this and aggregate data into sets humans can process – wow. Revolution.
Even with all that said, one of the most difficult things about parallel/threaded programming is debugging them. There are only a few tools designed to cope with multiple threads. Standard debuggers really can’t cope with it, as soon as you define a break point and it executes, your program stops, and you single step your thread, and chances are your program will run fine. Your races are gone, because your program is now searialized.
If you manage to get your multithreaded application working during the testing phase, that is good, you may still run into more problems. And you can’t just run a debugger in production, so you then have to figure a way create a simular load and workset to expose the bug in your test environment and pray you find the bug.
Luckily things are changing, thanks to DTrace you can now debug multithreaded programs as easy as other tools allow you to do non-threaded software, plus you can use it in production because it won’t slow down your application or cause your program to crash where it wouldn’t of before. Dtrace is also poliferating you will soon be able to use it in Solaris and FreeBSD and OSX.
You are absolutely correct. I really have nothing to add to what you said, but I wanted to +1 Dtrace. It REALLY does make things MUCH easier!
Parallelism (multi-threading, or however you achieve this) requires a new way of looking at problems, and most people haven’t gotten this down yet.
Why do people keep saying this? multithreading has been around since T.H.E.
The various methods of achieving concurrency were pretty well understood by the 1990, and the only thing that has really changed since then is the widespread availability of machines that can routinely take advantage of it.
If you read my comment, you would have seen I SAID THAT. It still holds true. Most people have NO clue about parallel programming, and to them, it’s a “new way” of looking at problems. Yes, the idea has been around for ages, but just as my ORIGINAL COMMENT says, it was limited to the HPC crowd, which is NOT the normal user.
In the thirty years I’ve been developing multithreaded applications, only for five did I spend any time in the “HPC crowd”.
For at least that long there have been at least four “crowds” of concurrent programmers:
OS kernel developers
“HPC crowd”
hard realtime systems developers
“threads as a programming paradigm” developers
Standardizing pthreads was painful precisely because we tried to accomodate at least three of those “crowds”.
Java, a programming language for “normal users”, by which, I assume, you mean application programmers, has been around for fifteen years, with concurrency built it.
But is making every var that could be used by different threads synchronized an efficient way to achieve parallel execution?
It can be done with the languages that we have today, but they don’t seem optimal for threading. At least I hope they aren’t the optimum.
Java, a programming language for “normal users”, by which, I assume, you mean application programmers, has been around for fifteen years, with concurrency built it.
!start nitpick
The first public implementation of Java was in 1995, so it has been “around” for only 11 years.
!end nitpick
Congratulations, you just narrowed the “concurrent programmers” down to less than 0,01% of the programming-capable population. If not less.
How many java programmers do you know, that are good “concurrent programmers”? I know one. Out of hundreds. The rest make “threads” for the sake of making “threads”, because that’s what they’ve been told to do.
The more you follow up to my posts, the more you reinforce my point. Nitpick all you want, you’ll find minor failing in my posts I’m sure, but my general view is correct and you are doing nothing but further proving them as such.
PS – Assumption is the bane of truth.
Congratulations, you just narrowed the “concurrent programmers” down to less than 0,01% of the programming-capable population. If not less.
Amusing that you ignored the main thrust of my post and concentrated on an example language listed at the end of it.
Your point is wrong on two counts. First, concurrent programming has not been merely the province of the HPC crowd in the past, and second there are no new ideas floating around.
Even if you were correct in what you had intended to say, which is that people are not familiar with the ideas, this does not make the ideas new.
I think ADA is *the* language for concurrent computing.
The more they’re like they were last time.
DTrace doesn’t magically make heisenbugs debuggable, it merely moves around the way in which they hide from you.
I agree totally. Experience has taught me that the only way to avoid heisenbugs is to be absolutely rigorous from the early design stages of development. Everyone on the team has to understand that between any two instructions, unprotected shared data can (and will) be changed. We found the most valuable debugging tool is the peer review.
I must say I am starting to be a bit tired about all these “threads are difficult, we need new paradigm” articles.
IME, this is all hogwash. Programming with threads is not that difficult, after learning some basic principles. Just because somebody somewhere was caught by racing condition or something similar does not justify introducing “new principles”.
> IME, this is all hogwash. Programming with threads is not that difficult, after learning some basic principles. Just because somebody somewhere was caught by racing condition or something similar does not justify introducing “new principles”.
When “somebody somewhere” translates to “nearly everybody, everywhere” it does.
Just like manual memory management, synchronization is NOT easy and very error-prone in non-trivial programs. And it doesn’t scale well, anyway.
Just like manual memory management, synchronization is NOT easy and very error-prone in non-trivial programs. And it doesn’t scale well, anyway.
Well put. I like the comparison to memory management. I am not a parallel programmer but I’d like to be. Memory management was hard to master in C and C++ but I’m glad I did before I learned Java with garbage collection. I feel parallel programming is the same way. I better learn it at a lower level before a new paradigm emerges making it easier.
Indeed, and what’s more, it requires a whole lot more forethought than memory management. I usually end up modelling things out on paper, with UML and – occasionally – state-diagrams before splitting up a program. The sort of gotchas that can occur with concurrent programming (especially using the current crop of popular languages) are nightmarish.
The solution is to create a completely new paradigm. One example is the use of futures (http://en.wikipedia.org/wiki/Future_%28programming%29) and “promise pipelining” currently seen in languages like E and Alice.
Of course, given that it’s taken 30 years for techniques like total OOP and lambdas to arrive in a mainstream language (C# 3), I’m not optimistic about any of these techniques gaining mainstream acceptance in the near future.
Edited 2006-09-01 15:44
Damn, actually plotting and planning a program before coding, good form there.
is to use a signal-based programming paradigm!
(just kidding)
This was a very very very good article. I cannot emphasize this enough. Unfortunately, the comments here on OSAlert prove what the article tries to say:
Programmers think in sequential code.
Programmers think that concurrency = processes/threads.
Programmers think that threads are easy to use.
Programmers think that the bugs in their multithreaded programs are a minor issue.
Programmers are unwilling to give up these fundamental misconceptions even in the face of massive counter-evidence.
I don’t know who “programmers” are. However, *I*
do program sequentially. It’s a limitation of language: language is linear, thought is not.
do not think that concurrency = “process/threads”.
do not think that threads are *always* easy to use, or *always* hard. There are plenty of thread based idioms that work well and are easy to understand. Threads should be used where they’re appropriate.
do think that whether bugs are minor or not is independent of whether or not they are in multithreaded applications.
have no idea what the ‘massive counter-evidence’ you think exists that would change my opinions.
do think that the article is lame because it doesn’t say anything new about alternative ways of achieving concurrency and doesn’t acknowledge any of the work done prior to a few years ago in that area.
Reading most of your comments to this story, I’ve come to the conclusion you are really spiteful for some reason. Did somebody in your past really tick you off concerning parallelism/concurrency in programming? Have you written a book on the topic, and it flopped? You’re obviously quite intelligent, but you nitpick at everything and you seem VERY defensive and agitated. Why such a deep-seated personal involvement in a discussion with geeks/os junkies?
“do think that the article is lame because it doesn’t say anything new about alternative ways of achieving concurrency and doesn’t acknowledge any of the work done prior to a few years ago in that area.”
^ seems to me you got burned by somebody, and you’re out for revenge, but you’re taking it out on us all. What happened?
My goodness you’ve got an overactive imagination.
I’ll make a note to *never* comment on your spelling again.
I was just noting another example of the very common myopia in cs academia: if it’s more than five years old it gets reinvented.
As far as ‘nitpicking’, I’ll leave you with Neils Bohr’s recommendation: “never express yourself more clearly than you think.”
seems very old fashioned to me. Couldn’t the compiler do it? I’m thinking of some old fashioned C code like
for(x=0; x<n; ++x){expression;}
Now all the compiler should have to do is check wether or not the runs for x=i and x=i+1 access the same variable/resource (in fact only if one of them changes it).
Say expression was like “a[x]=x”; the code could be executed in parallel while code like printf(…) should be executed in serial (unlike Fortress does).
It just feels VERY wrong to me that you should have to do that all yourself…
Edited 2006-09-01 10:06
If only…
Your example isn’t really what multithreaded applications do. That could be solved with vectorization, but it doesn’t really benefit from multithreading. Auto-vectorization is something that compiler can do, multithreading is something they can’t. It’s tricky for even experienced programmers to do, what more the compiler.
Higher level languages can do that.
For example in Haskell you can map a function into a list, and the langauge takes care of the technicalities of how to apply that function to every element in the list. Because it’s so high-level, it’s easy to do concurrently.
Likewise, compiler designers found it easier to adapt Fortran (a language that’s nearly 60yrs old) for use with MMX and SSE hardware than C or C++. The reason was that Fortran had built-in “primitive” vector and matrix types. As the technicalities of performing arithmetic on these types were hidden from the programmer, it was easy to vectorise such operations.
The solution, basically, is an extremely high-level language, that eschews simple types and low-level details, so that the compiler has sufficient latitude to do what it likes to optimise the program the programmer enters. Specifying every single little step to be performed by the CPU (what people currently do in C, C++, Java and C#) leaves the compiler with very little room to manoever, and consequently means that programmers also have to specify every little step involved in concurrent programs
Edited 2006-09-01 15:51
Multithreaded programming is just hard because the average programmer doesnt undertand how threads work and how to use them properly…
btw. parallelism can be archived in a lot of different ways; IO multiplexing / asynchronous IO, multiple processes, etc.
A simple way to make use of a multi-CPU environment i often use, is to split a single shell command into a combo of several commands using pipes. This makes use of multiple CPUs to do a task.
What about an IDE letting the programmer define many tasks and their interactions and decide to cut the modules into pieces, so that it produce something like Microsoft Project diagrams : some parallels, some sequencials ?
Does something like this exist already ?