Programming parallel computing

http://www.physorg.com/news99067728.html

QUOTE

Despite the promise of almost unimagined computing power, however, even computing experts wonder whether this time the hardware developers have raced too far ahead of many programmers' ability to create software.

Click to expand...

Clearly we're going to have to invent a new type of programming educational system if processors are moving towards 3D architecture. Program designers will have to think differently than program designers do nowadays.

I wonder what math subjects would be useful to know when trying to learn (or design) a way of programming for multiple cores? What new things should computer scientists and innovators be teaching themselves, in order for this field to progress?

It looks like 3D computing will be the future of computers. How will we make best use of them?

Imagine I know a teenager who's thinking about being a programmer as a career (and is bright enough to realise that parallel programming is the future) then he's going to want to start exposing himself to certain flavours of mathematics. This would be to start encouraging a certain type of mathematical thinking which would be conducive to being able to design parallel programs. What should I recommend?

I'm wonder what mathematical flavours would be helpful seeds in getting the most useful style of thinking? What fields of mathematical studies would it be useful to get exposure to, even before starting university?

If I knew that, it would help me, soon to be a student at University studying Computer Science.

As the interesting article mentioned, the most difficult part of future programs will be determining how break an algorithm into parts that can be processed simultaneously by multiple cores. Program design will be made harder as more insight is required to decide the order in which instructions are run, and the most optimum way to execute them.

This kind of computing will be of the greatest use to instructions that affect a large array of data at once. I guess video editing, where one must make a change (like cropping or brightening) to several frames of a video will benefit from this.

Oooo! This is my specialty! I was helping programmers develop code for BlueGene and other compute clusters, and initial versions of the Cell SDK!

YAY!

Multi-threaded programming is easy once you get out of the lazy, single-threaded mindset. Concurrency is the #1 problem. Easiest way is to compartmentalize your design, which shouldn't be a big leap if you do proper OO design in the first place.

For instance, take a first-person shooter game. You can have one thread handling I/O (level/model loading, etc). You can have one thread handling physics. You can have one thread handling graphics (it directs the GPU what to draw). One thread can handle audio. One thread can handle networking. That sort of thing. The problem that arises here is these threads, while nice in theory, don't exist in isolation. All are heavily interacting with eachother. And any stall in such an interaction is a huge performance hit.

There are lots of technical solutions to solving this kind of problem. In systems with many cores, like on Cell on the PS3 or a compute note on BlueGene, a common solution is to implement a tiny kernel on one of the chips to essentially swap out stalled threads with active threads. This relies on brute force count of threads to offset thread stalls. Other implementations depend on pre-defined "sync points" in time (eg, in Forza 2 on the Xbox 360, 360 times per second the threads all talk to eachother to pass relevant information). The components are designed to work with data bursts they retrieve every 1/360th of a second.

How do the threads talk? Any kind of data structure you want...set up a message-passing interface (eg, BlueGene), utilized shared L2 cache (eg, Intel's Core 2), utilize a bus to send data (eg, Cell)...a more generic solutions is to simply use a pool of RAM, but that's not very fast.

What type of math would help in this? General problem solving -- which most math helps with. Theoretical computer science is a huge help in designing such systems, but it's underrated in most CS curricula today.

I'm a little curious Asher. How do you send part of a program to a certain core? Do you write up the proceedures (modules) that make up your program and then write up another set of instructions that tell the cores what to process and when? Do you write up a process and address it to a certain core? I have read over and over about how more cores are better but I have never seen an explanation of how a programmer splits his program to run on multiple cores. Not even a simple explanation.
Thanx in advance

3 EMS said:

I'm a little curious Asher. How do you send part of a program to a certain core? Do you write up the proceedures (modules) that make up your program and then write up another set of instructions that tell the cores what to process and when? Do you write up a process and address it to a certain core? I have read over and over about how more cores are better but I have never seen an explanation of how a programmer splits his program to run on multiple cores. Not even a simple explanation.
Thanx in advance

Click to expand...

Well, to start with -- in the Windows world -- let's define "process" and "thread".

A process is, say, game.exe. When you hit CTRL-ALT-DEL in Windows, and you click the Processes tab, it'll show you the running processes on your computer. Each process has access to its own memory (and only its own memory!) and other resources. If you kill the process, everything inside of it dies.

A thread is contained inside a process. Each process can have many threads. Each thread can access the memory and other resources of all of the other threads contained within the same process. A thread is, simply, a string of instructions. The vast majority of code today is single-threaded, meaning it's a simple program with only one flow that can occur. A single-core CPU can only run one thread at a time (note: HyperThreading on some P4s is different, but irrelevant to the big picture here). To work on another thread, they need to switch contexts.

Enter multi-threading! Multi-threading is having multiple threads running under the same process. A modern operating system that supports multiple CPUs has a scheduler that is smart enough to allocate these threads to each of the CPUs. A dual-core CPU can concurrently run two threads at the same time. A quad-core CPU can concurrently run four threads at the same time.

By utilizing multiple threads in a program, developers can utilize more than one CPU on each machine.

So your question was, how does a programmer split his program into these threads to run on different CPUs? That's up to him. In some applications, a divide-and-conquer strategy works. Let's say you have 4 CPU cores and you're using Photoshop to apply some special effects to an image. Using divide and conquer, Photoshop would divide the image into quarters and assign each quarter to a core to process.

The other approach is to compartmentalize the software, as per my example in my first post. In a game using four cores, the developer may choose to have one thread that calculates all of the physics of the game. Another thread can calculate the artificial intelligence/AI of the game. Another thread can be used for misc. other code (sound, I/O, etc). Another thread can run the main game program flow (and play "conductor" to ensure the other threads are playing nice together).

Hope this helps. Let me know if something's unclear and I can explain.

Thank you for your fine answer Asher. This below is what I have most often seen described and what most excites me about the prospect of multi-threaded applications.

Asher said:

The other approach is to compartmentalize the software, as per my example in my first post. In a game using four cores, the developer may choose to have one thread that calculates all of the physics of the game. Another thread can calculate the artificial intelligence/AI of the game. Another thread can be used for misc. other code (sound, I/O, etc). Another thread can run the main game program flow (and play "conductor" to ensure the other threads are playing nice together).

Hope this helps. Let me know if something's unclear and I can explain.

Click to expand...

Does the programmer actually have to specify, in some way, sound will be processed by core number 3? Does he simply have to make a thread for video, one for AI, one for AI and another for I/O? Does the software he programs in do this for him? That's really what I was getting at. I apologize if I was too vague.

Asher said:

Multi-threaded programming is easy once you get out of the lazy, single-threaded mindset. Concurrency is the #1 problem. Easiest way is to compartmentalize your design, which shouldn't be a big leap if you do proper OO design in the first place.

Click to expand...

The article was mentioning that the programming is harder than it looks. What about as the processors move more and more 3D? It's going to have to move away from a few processors to hundreds.

If I knew that, it would help me, soon to be a student at University studying Computer Science.

Click to expand...

Good luck! We need more bright and focused computer scientists. This particular crossroads looks like it's going to be overcome with a lot of hard work, and so it should be very rewarding.

3 EMS said:

Does the programmer actually have to specify, in some way, sound will be processed by core number 3? Does he simply have to make a thread for video, one for AI, one for AI and another for I/O? Does the software he programs in do this for him? That's really what I was getting at. I apologize if I was too vague.

Click to expand...

The programmer can specify which core, specifically, does what -- but on the PC this isn't the best idea because everyone's configurations vary so much. On the Xbox 360 and PS3 this is very common, though, to manually specify which thread goes on which core. On the PC, this is usually handled automatically by the operating system.

It is much more difficult to make four threads instead of one, and there are some tools out there that try to automagically do this -- but the results are very poor, compared to doing it properly by design.

The article was mentioning that the programming is harder than it looks. What about as the processors move more and more 3D? It's going to have to move away from a few processors to hundreds.

Click to expand...

It can be very difficult, but its mainly because it's very different from what most programmers are used to. It's just a steep learning curve, more than anything. As more and more processor cores get added to the CPU, it will get more difficult to compartmentalize your software simply on the basis of "physics for one thread, AI for another, etc". More and more, these solutions must rely on divide and conquer...spread out physics over many cores, for instance.

This kind of solution is used most extensively in 3D graphics. A GeForce 8800 GTX/Ultra, for instance, has 128 processors each with its own thread. Thousands of threads can be "in flight" on a GPU at the same time. This is because 3D graphics are very easy to scale with more computing units -- physics to an extent also. This is also why there's a trend for physics on GPUs right now. Also, things like Folding@Home are also easily scalable.

As for other kinds of operations, lots of research is currently going into that. Many algorithms we use today are not scalable to multiple cores, as they've all been optimized for a single program flow. It's a strong focus of many CS researchers.

Asher said:

This kind of solution is used most extensively in 3D graphics. A GeForce 8800 GTX/Ultra, for instance, has 128 processors each with its own thread. Thousands of threads can be "in flight" on a GPU at the same time. This is because 3D graphics are very easy to scale with more computing units -- physics to an extent also. This is also why there's a trend for physics on GPUs right now. Also, things like Folding@Home are also easily scalable.

Click to expand...

Thanks Asher. I think I did read where AMD is working on a processor that contains both CPU and GPU combined.

El Machinae said:

Good luck! We need more bright and focused computer scientists. This particular crossroads looks like it's going to be overcome with a lot of hard work, and so it should be very rewarding.

Click to expand...

Thanks! It will be hard work, but I'm sure very rewarding. I hear that Computing Science graduates are "snapped up" by employers as soon as they graduate, being there is such a great demand for them. This will be a profession for life then - which is fine, because Computing is something I enjoy.

Bumped because I got pointed at this from here

El_Machinae said:

Clearly we're going to have to invent a new type of programming educational system if processors are moving towards 3D architecture. Program designers will have to think differently than program designers do nowadays.

I wonder what math subjects would be useful to know when trying to learn (or design) a way of programming for multiple cores? What new things should computer scientists and innovators be teaching themselves, in order for this field to progress?

It looks like 3D computing will be the future of computers. How will we make best use of them?

Imagine I know a teenager who's thinking about being a programmer as a career (and is bright enough to realise that parallel programming is the future) then he's going to want to start exposing himself to certain flavours of mathematics. This would be to start encouraging a certain type of mathematical thinking which would be conducive to being able to design parallel programs. What should I recommend?

I'm wonder what mathematical flavours would be helpful seeds in getting the most useful style of thinking? What fields of mathematical studies would it be useful to get exposure to, even before starting university?

Click to expand...

The following makes no pretense to correctness. It is opinion and suggestion. I do, however, believe it to contain several facets of the answer.



Mathematics. Proofs. School spends a lot of time teaching what is correct; doing proofs and learning why something is correct (sometimes called "packing" vs "mapping") will help a lot in understanding when to apply a technique, for example by knowing what requirements a necessary to use a theorem, and whether it gives the correct result if applied to another field than the one it was learnt in. This should, IMO, be learnt first in mathematics, and has application in programming for proving the correctness of a program - writing bugfree code the first time.


Mixed. Unorthodox exercises like the Abel Competition (link) and Project Euler (link) and devising quines (link) are excellent ways of developing thinking. I believe you talked once about the importance of learning to learn. This is something of the same. These problems are in mathematics and programming, so they are well-structured, can be solved with a reasoned approach, and demonstrated clearly. On the other hand, they vary a great deal, which means that solving them will be more effective (and I would hope that one learns to do that from solving these) if one not only builds proofs or reasoning chains to the answer, but also builds up the knowledge of how to create such a chain.


Programming. Object-oriented languages such as Java and C# are the ones I know of that a great deal of important code is written in (based, admittedly, on job notices on a computer site I visit - not a study), so take courses on those. I strongly advise the learning of Lisp in some dialect as well. (Haskell may be good too, but I know too little about it.) I learned Lisp before Java; when I started taking Java courses, I screamed for my Lisp functions. Learning two programming languages with different functionality is a strong tool in writing effective code, because it promotes understanding of what a language does, why, and what applications this has.


General wisdom. Learn from other people's mistakes. Check for things such as [wiki]Anti-pattern[/wiki]s. Learn about both what's working and what's not working, and try to understand why the dividing line falls where it does, in order to project it into the future. Having multiple ways of solving a problem is another good thing - both for checking it for correctness and for comparing their speed in various cases. (This, I suppose, could be very important for multi-core computing if e.g. a linear solution requires less calculating but a parallell solution can be done in shorter time.)

I'm aware that these overlap, so feel free to pick and mix when quoting, or even reply without quoting the specific paragraphs at all.