algorithms that benifit from highly parallel implementations?

[buleyb]

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]

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...

 

[buleyb]

I like the idea, especially one run in real-time.


Any more ideas?

 

[Armitage]

IIRC, there is a PVM based version POVRAY for clusters.
Also, genetic algorithms are sometimes referred to as "embarrisingly parallel"

 

[Peter]

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]

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]

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]

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]

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]

because i'm developing for a dense multi-computer that handles MPI or a faster proprietary API. No typical cluster here guys

 

[Armitage]

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]

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.