algorithms that benifit from highly parallel implementations?

buleyb

Golden Member
Aug 12, 2002
1,301
0
0
I've got my project hat on...

I'm looking for algorithms that would work well in parallel, and need a lot of horsepower too. Nothing distributed intended (but those algorithms might apply nicely).

Anyone have any ideas?
 

Matthias99

Diamond Member
Oct 7, 2003
8,808
0
0
Raytracing's a good one. I don't know if POV-RAY (or even any of the commercial raytracing packages available, like 3dsMAX or Maya) run in parallel/multithreaded configurations, though. It's not impossible to write a simple one, however...
 

Armitage

Banned
Feb 23, 2001
8,086
0
0
IIRC, there is a PVM based version POVRAY for clusters.
Also, genetic algorithms are sometimes referred to as "embarrisingly parallel"
 

Peter

Elite Member
Oct 15, 1999
9,640
1
0
In general, anything that involves lots of data and very little interdependancy between those data. Raytracing is the perfect example - every individual screen surface pixel can be computed independently from any other individual screen pixel.
 

buleyb

Golden Member
Aug 12, 2002
1,301
0
0
Thats all well and good guys, but anything more specific? I know lots of theory to this, but I have nothing of use to implement. Raytracing is good, but there must be more practical stuff out there to parallelize...
 

buleyb

Golden Member
Aug 12, 2002
1,301
0
0
Originally posted by: ergeorge
IIRC, there is a PVM based version POVRAY for clusters.
Also, genetic algorithms are sometimes referred to as "embarrisingly parallel"

I found PVMPOV, i'll give its source a look-through...too bad PVM won't work for me directly...I'll just have to port the ideas
 

eigen

Diamond Member
Nov 19, 2003
4,000
1
0


These are some of the projects going on at one of the supercompting centers on my campus. Most all of these are run on some sort of linux or open mosix cluster,

Fast Heuristics for Very-Large-Scale Maximum Independent Set &Related Problems Using Neural Networks Approach

An Efficient Approach for Solving the Assignment Problem with Side Constraints

Greedy Solutions of Selection and Ordering Problems

Insights Into Two Solution Procedures for the Single Machine Tardiness Problem

Geometric structures and stabilities of CuSin clusters (n=8,10, 12)

Computational Studies on Si7 Clusters Deposited on a Graphite Substrate


etc............
 

Armitage

Banned
Feb 23, 2001
8,086
0
0
Originally posted by: buleyb
Originally posted by: ergeorge
IIRC, there is a PVM based version POVRAY for clusters.
Also, genetic algorithms are sometimes referred to as "embarrisingly parallel"

I found PVMPOV, i'll give its source a look-through...too bad PVM won't work for me directly...I'll just have to port the ideas

Why won't PVM work for you? In my experience, it works pretty much everywhere (but is a PITA on windows)
 

buleyb

Golden Member
Aug 12, 2002
1,301
0
0
because i'm developing for a dense multi-computer that handles MPI or a faster proprietary API. No typical cluster here guys :)
 

Armitage

Banned
Feb 23, 2001
8,086
0
0
Originally posted by: buleyb
because i'm developing for a dense multi-computer that handles MPI or a faster proprietary API. No typical cluster here guys :)

Still don't see why that prevents you from using PVM. IMHO, PVM is an easier to use & more robust library then MPI, and I doubt there is significant speed advantage.
 

buleyb

Golden Member
Aug 12, 2002
1,301
0
0
Originally posted by: ergeorge
Originally posted by: buleyb
because i'm developing for a dense multi-computer that handles MPI or a faster proprietary API. No typical cluster here guys :)

Still don't see why that prevents you from using PVM. IMHO, PVM is an easier to use & more robust library then MPI, and I doubt there is significant speed advantage.

Because PVM doesn't support the architecture of the system. The MPI version in use has been adapted to use the interface bus and properly suited to the architure in question. PVM is great for workstation clusters, but can't hold a flame to dedicated RTOS architectures.