What exactly is a Parallel Algorithm ?

[Benjamin113]

What exactly is a "Parallel Algorithm"?

I understand what parallel algorithms are intended to do, but I do not know what they are used for.

 

[Benjamin113]

Would anyone care to explain?

 

[f95toli]

It is an algorithm for solving one problem that can utilize more than one processor simulataniously (and the term is usually reserved for algorithms where the execution time decreases when more than one processor is used; which is not at all obvious).

Example: A parallel algorithm for adding 1+2+3+4 would be to let one processor add the first two terms; at the same time as a SECOND processor is adding the third and fourth terms (3+4); once that is done both processors send their results to to a third processor which adds the results and comes up with a final answer.

 

[Benjamin113]

I see.

 

[Benjamin113]

Thanks!
One more question:
What are it's applications?

 

[CRGreathouse]

I dunno, maybe someone will invent a dual or quad core processor some day.

 

[FredGarvin]

Thanks!
One more question:
What are it's applications?

People work with systems of equations that involve thousands of variables/equations. It's in these situations where it is efficient to take advantage of this if possible to decrease computation time.

 

[rcgldr]

Parallel could also include stream or vector processing, essentially multiple arithmetic units in a computer, allowing simultaneous or overlapping math operations. The newer video cards in PC's include multiple floating point arithmetic units, and gpu math libraries are available to implement stream processing.

A matrix multiply can be an example for parallel math, all of the multiplies are independent, so all could be done at the same time. The products would then be summed as they became available, to form the result.

A file copy could be an example of a parallel multi-threaded algorithm. One thread would read the source file into buffers, and the other thread would write the buffers into an output file. The buffers would be used in a fifo basis. This implementation would overlap the I/O operations. It wouldn't do much on a modern system with cacheing in the OS and the peripherals, but it's a reasonable example. I created an example windows command line program that implements a file copy using multiple threads.

http://jeffareid.net/misc/mtcopy.zip

Yes it has goto's and trailing right braces, but the code is easy to read.

If there was processing to be done with with the file I/O example, then a third thread could be used to process the buffers. Normally this third thread would be set to lower priority since it's a non-I/O thread, to allow buffering to continue while processing the data in that third thread.

 

[CylonMath]

Is Windows Copy Program uses non-thread copying ?
I am shocked...

In senior project, we have designed a system that fetches satellite images to process them, we gave a coordinate of a place and took the big picture. And then divide this 1 big photo to smaller photos and image process them by using multiple processor ( each one using same algorithm on different pictures) and some processors were responsible for combining smaller pictures into first picture.

Thats what parallel algos does.

 

[rcgldr]

Is windows copy program uses non-thread copying ?

I don't know. The purpose of mtcopy.c is as an example of windows multi-threading. Mutexes, semaphores, waitformultipleobjects(), and link list fifo "messaging" between threads is demonstrated.

In senior project, we have designed a system that fetches satellite images to process them, we gave a coordinate of a place and took the big picture. And then divide this 1 big photo to smaller photos and image process them by using multiple processor ( each one using same algorithm on different pictures) and some processors were responsible for combining smaller pictures into first picture.

A more general multi-threading algorithm involves significantly different processes running at the same time, for example in the case of a cd/dvd read write drive, the processes are: maintaining or changing spindle speed, moving the read/write heads, reading or writing data to the disk surfaces, buffering of data to be read by the host or written to the hard drive, error correction encoding or decoding, accepting commands and transferring data to/from the host PC, ...

 

[ytoruno]

well, even for single cpu machines, one could get a significant increase in speed for embarresingly parallel situations (monte carlo algorithms spring to mind.) If you want to learn about parallelism and perhaps some languages that support several frameworks, google NESL, which is a functional data parallel language. Their website has tutorials on the various implementations of parallel languages and gives an overview on the von neuman model and other such things.

 

[Hurkyl]

well, even for single cpu machines, one could get a significant increase in speed for embarresingly parallel situations (monte carlo algorithms spring to mind.)

This is either wrong, or misleading.

If you have one CPU, then running a thousand tasks at once just means that each task takes 1000 times longer to complete than it would normally take, and you get no savings. Actually, it would take even longer than that, because of wastes due to context switches and other thread management.

The only reason to use a parallel program on a single CPU machine is if the tasks are easier to implement as a parallel algorithm rather than as a serial algorithm. (Or you have some odd constraint that requires multithreading) (or if you are taking advantage of true parallelism that exists even on a single CPU machine -- e.g. running a calculation in parallel with an I/O transfer)

 

[rcgldr]

parallel program on a single CPU machine

True single cpu machines are virtually non-existant. Peripherals and the interfaces to them have had some sort of crude CPU, like DMA controllers on the system itself, going back to the 1960's (classic Macs are the exception, these didn't have DMA and required programmed I/O).

Even with programmed I/O, being able to buffer data in and out of a system via interrupt handlers will improve performance on a machine. There aren't many "non-parallel" environments, although specific applications within a system may be non-multi-tasking.