Parallelism

[cerin]

I saw an article on slashdot about parallelism and the writer posed the question "Is it too hard for programmers to think about?". So naturally I started looking up what exactly parallelism is in terms of applications. My question is why is it so hard to achieve? Why not develop compilers that divide the work up (I saw this in the wikipedia article)? How can I write code that uses parallelism? Is it so hard because you have to use low level languages to do it?

[XSquared]

There are some application styles which are easily parallelizable (such as a web server, simply spawn a separate thread for each client who connects up to a point). However, there are also other situations where it isn't quite as easy to parallelize the code (things such as a compression program like gzip). A big issue with parallelizing code is sharing of data between individual threads, such as in a game. You don't want to have the display code reading data at the same time that the engine is updating the data, as you could get some data in a very wonky intermediate state. Of course, once you start adding mutex locking to your code, you can get into some very funky deadlock situations, which are quite hard to get your head around, or even detect.

[cerin]

So how can I write parallel code?

[dwks]

You'd use some sort of multithreading library, like Boost, or the POSIX functions: http://beej.us/guide/bgnet/

(For C and C++, that is.)

[cerin]

Does the boost library automatically take the threads and pass them through all available processors? I have a dual core processor.

[Mad_guy]

Parallel computation is expressed in different languages a lot of different ways.

For example, for some languages, threading can be done through libraries like C or C++. In others, such as say, Erlang, parallel computation can be done via a completely different model that the entire language itself is built on.

What this basically means is "the answer depends." Parallel applications are hard due to the fact you have deadlocking problems, shared memory issues and all sorts of other things that are just implicit in the thought of operating parallel. Therefore, abstract solutions are generally a bit more preferred than dealing with close to the metal code.


For example, if you wanted to write a highly parallel or concurrent application, I would most likely recommend a language like erlang to you. Erlang is abstract, extremely lightweight and fast. It is built on parallelism; it's not a library that was included with the language or done by a 3rd party: it's a critical component of the language itself. It solves the paralleism issue with reasonably good results and it's a very tried and true language (erlang's been used in telephone switches all over the world since the mid-late 80's.)


As for the answer to your question about the dual core: that's a job of the operating system's scheduler itself. Languages like C and C++ have basic threads, when threads are created, the OS maps them to be executed on a specific processor; this is a part of what the scheduler does. These threads are called 'kernel threads.'
Other languages like Erlang implement something called 'green threads.' Green threads are basically threads managed by the language runtime itself, rather than the kernel. Switching between kernel threads is fairly expensive, but if the threads are manged by the application, they are much faster and much more lightweight, also because of this, the kernel is not aware of these threads, so it cannot schedule them for execution on a specific processor. Erlang has solved this issue though by implementing a m:n approach: the virtual machine for the language is mapped to several kernel threads (which are mapped to seperate processors by the kernel, if available), and the erlang 'processes' are split amongst the threads, so you have your processes running on seperate processors (quick jargon info: an erlang process is essentially analogous to a process thread.)

[Cactus_Hugger]

the writer posed the question "Is it too hard for programmers to think about?"

I saw that article, and was a little miffed by the question posed. There are only a few basic concepts, and they're not all that hard to grasp. Having one to five locks is not really a problem. Having tens to hundreds of locks, or many threads, and the complexity increases. The problem comes with things like locking order, and especially when things go wrong. I know I have multithreaded code that doesn't work, and I've given up trying to find out why.

Another point is economics: is it worth your time as a coder to code multithread? Sometimes yes, sometimes no.

As for API, I've used pthreads in the past since it works with both Linux/Windows. (Although I've used Win32 API just as much, if not more...) Never tried Boost, though I probably should.

dwks: um, yes, someone mentioned webservers, but random link? It's a great guide, no doubt, but I don't see the relevance to Boost or pthreads.

some very funky deadlock situations, which are quite hard to get your head around, or even detect.

Oh, I dunno about that. Dead. lock. Everything locks up solid. When your program freezes, something is aloof. (joking, of course)

[cerin]

Cactus_Hugger....I need to point out that the link you gave in your post isn't the same as the other guy gave. He linked to a socket programming guide which has relevance to parallel processing because there are different kinds one of them being divided the processing between computers.

[zacs7]

My Rant: I have a really old 'super computer' that I used to test programs on (Solaris), it had 10 x 200MHz CPUs, however the C GNU compiler I was using only used one, so it took for ever to compile even the smallest of programs.

[abachler]

"Is it too hard for programmers to think about?"

Its not too hard, but it generally takes higher than average problem solving ability to parallelize(is that a word?) non-trivial algorithms. As someone said already, some tasks are inherently highly parallel, while others require more intuition. Some tasks simply cannot be effectively executed in parallel. Some tasks are so trivial that the overhead of breaking them into sub-units is greater than any gains achieved by executing them in parallel.

I have a really old 'super computer'

Heh, I still use my quad processor Alpha to crunch prime numbers. 4 x 800 Mhz.

[Salem]

> it had 10 x 200MHz CPUs, however the C GNU compiler I was using only used one

$ make --help
Usage: make [options] [target] ...
Options:
...
  -j [N], --jobs[=N]          Allow N jobs at once; infinite jobs with no arg.
  -l [N], --load-average[=N], --max-load[=N]
                              Don't start multiple jobs unless load is below N.

A single instance of gcc probably has very little inherent parallelism, but you should be able to run (through make) many instances at the same time.

[abachler]

Ive thought about making a parallel compiler, but that woudl involve me finding a very good serial compiler with well documented easy to read code that isnt written in MFC style or some arbitrarily irrelevant language.

The true test of a compiler is if it can compile itself. Something not possible with a C/C++ compiler written in PERL. Hey I know, lets write a C/C++ compiler in JAVA, or better yet, GW-BASIC

Since most non-trivial projects consist of multiple source files, theres no reason each source file couldnt compile in its own thread. Although I cant think of how you would parallelize the linker.

[cerin]

When I said 'parallel compiler' I meant a compiler that automatically turns all applications you compile into parallel ones not a compiler that itself is actually parallel.

[Cactus_Hugger]

Cactus_Hugger....I need to point out that the link you gave in your post isn't the same as the other guy gave.

Between random links and great guides, it was meant partially as a joke. (That, and I was posting at 12:30 AM, something I apperently shouldn't do. )

He linked to a socket programming guide which has relevance to parallel processing because there are different kinds one of them being divided the processing between computers.

First, the context:

You'd use some sort of multithreading library, like Boost, or the POSIX functions:

After which, you'd expect a link to some sort of multithreading library. (At least, I would.) Rather, we got Beej's Guide to Network Programming. Nothing to do with parallelism ("...a discussion about multithreading is beyond the scope of this document..."). Granted, parallelism can be used in conjunction with sockets as a means to an ends when dealing with multiple connections, but the two are separate things.

I would've expected a link along the lines of Boost Threads, POSIX Threads for Win32, etc.

[zacs7]

> it had 10 x 200MHz CPUs, however the C GNU compiler I was using only used one

$ make --help
Usage: make [options] [target] ...
Options:
...
  -j [N], --jobs[=N]          Allow N jobs at once; infinite jobs with no arg.
  -l [N], --load-average[=N], --max-load[=N]
                              Don't start multiple jobs unless load is below N.

A single instance of gcc probably has very little inherent parallelism, but you should be able to run (through make) many instances at the same time.

:O thanks, never thought of doing it that way... I no longer have to years days for things to compile