What exactly is a Parallel Algorithm ?

In summary, Parallel algorithms are used to speed up the execution of a task by using more than one processor. They are often used in systems where there are many variables and equations to be solved.
  • #1
Benjamin113
30
0
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.
 
Technology news on Phys.org
  • #2


Would anyone care to explain?
 
  • #3


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.
 
  • #4


I see.
 
  • #5


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


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


Benjamin113 said:
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.
 
  • #8


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.
 
Last edited:
  • #9


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.
 
  • #10


CylonMath said:
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, ...
 
Last edited:
  • #11


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.
 
  • #12


ytoruno said:
well, even for single cpu machines, one could get a significant increase in speed for embarresingly parallel situations (monte carlo algorithms spring to mind.)
:confused: 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)
 
  • #13


Hurkyl said:
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.
 

1. What is a parallel algorithm?

A parallel algorithm is a type of computer algorithm that breaks down a problem into smaller parts and solves them simultaneously using multiple processors or computer cores. This allows for faster and more efficient processing compared to sequential algorithms, which solve problems one step at a time.

2. How is a parallel algorithm different from a sequential algorithm?

A parallel algorithm differs from a sequential algorithm in that it can divide a problem into smaller parts and solve them simultaneously, whereas a sequential algorithm solves problems one step at a time. This allows parallel algorithms to be more efficient and faster, especially for complex problems.

3. What types of problems are best suited for parallel algorithms?

Problems that can be divided into smaller, independent tasks are best suited for parallel algorithms. These can include tasks like sorting, searching, data mining, and simulations. Problems that require a lot of computation and can be broken down into smaller parts are also well-suited for parallel algorithms.

4. What are the advantages of using a parallel algorithm?

The main advantage of using a parallel algorithm is its ability to solve problems more quickly and efficiently compared to sequential algorithms. This is especially beneficial for complex problems that require a lot of computation. Additionally, parallel algorithms can also utilize resources more effectively, such as using multiple processors or computer cores.

5. Are there any limitations to parallel algorithms?

While parallel algorithms offer many benefits, they also have some limitations. One limitation is the added complexity of designing and implementing parallel algorithms compared to sequential algorithms. Additionally, not all problems can be effectively solved using parallel algorithms, as they require independent tasks that can be executed simultaneously.

Similar threads

  • Programming and Computer Science
Replies
6
Views
932
  • Programming and Computer Science
Replies
1
Views
888
  • Programming and Computer Science
Replies
8
Views
973
  • Programming and Computer Science
Replies
8
Views
205
  • Programming and Computer Science
Replies
3
Views
682
  • Programming and Computer Science
Replies
22
Views
2K
  • Programming and Computer Science
Replies
14
Views
1K
  • Programming and Computer Science
Replies
9
Views
1K
  • Programming and Computer Science
Replies
7
Views
931
Replies
9
Views
945
Back
Top