Sunday, November 04, 2007

Parallel Algorithms

Some of us worked on parallel algorithms theory a long time ago, and many others on parallel systems. Parallel computing theory continues to remain in the backdrop, providing a hum to the motor ride that Theory of Computing is on; the (mesh, hypercube, connection) machines have disappeared, occupying real estate somewhere; people reinvented themselves, some went on to wireless networking, others to internet algorithms and beyond; wonder what happened to the software (BSP-based or otherwise).

The word on the street is that there is a revival, with the trend of multi-core processors. I hear that compilers for these systems are a rave. Will we see beautiful parallel algorithmics again, with list ranking, Euler Tour techniques and randomized matching?

2 Comments:

Blogger Francesco said...

Another question could be: will network oblivious algorithms have the same impact as cache-oblivious algorithms? CMPs are so different (topology, processor number, ...), that it could be nice having an oblivious parallel algorithm!

8:22 PM  
Anonymous Anonymous said...

I never gave up teaching PRAM algorithms to my undergraduate algorithms students. I like parallel algorithms because it forces students to think in a manner than that they are not accustomed to, but doesn't require a lot of mathematical background (like say randomized algorithms).

Kirk Pruhs

11:50 AM  

Post a Comment

<< Home