Thinking Parallel

In about a decade ago, parallelization was restricted only to governments, big companies and universities with big budgets for only them could spend millions of dollars in massive machines or big clusters to process their data, but after projects like Beowulf appeared and commodity clusters (aka. cheap PC clusters) could be built everywhere it became more and more important to understand the good of parallelization and the basic technics to understand how parallel can be your algorithm.

Nowadays it's even more important as any desktop now is dual-core or hyper-threading, also benefiting from multi-threaded software. The future is also in that line with big desktop companies releasing machines with 8 cores, it's extremely naive to ignore the benefits of multi-processing techniques.

1. Can you describe more than one way of executing 10 programs at the same time? Which one would you use if you had to do it every day?
2. When you have multiple machines in cluster, what's the easiest way of running programs on all machines at the same time?
3. There are basically two types of remote execution, using a grid process manager (such as LSF, SGE) or using an automatic process migration (such as Mosix). Can you describe the pros and cons of each implementation?
4. How can you control resource access (such as filesystems) using process managers?

1. Simple data can be split into smaller chunks to ease parallel execution. Imagine a file on each line (or group of lines) can be regarded as one register. How would you split and analyse this data?
2. Suppose you just need to syntax check the data, would you have the same solution?
3. Now you have a matrix to do a Gaussian elimination, how would you split it?
4. And what about an image to compress using Fourier transformations?

1. What are the pros and cons of using threads instead of processes?
2. How to assure a method is thread safe?
3. If a container is thread-safe, can you use it as a global variable?
4. Is it always desirable to thread-safe all methods in a multi-threaded program?
5. Discuss about the types of communication between threads? How would you do to transfer large amounts of data between threads?

1. What are the pros and cons of using messages instead of threads? Which kind of problems can be resolved easier on each?
2. What are the pros and cons of using asynchronous messages?
3. What is the difference between broadcast and scatter?
4. What is the difference between gather and reduce?