Sign In

Communications of the ACM

ACM TechNews

Retooling Algorithms

View as: Print Mobile App Share:
Charles Leiserson

MIT professor Charles Leiserson


Massachusetts Institute of Technology (MIT) professor Charles Leiserson says the best method for rewriting algorithms to run on parallel processors is to use a divide-and-conquer technique, which involves splitting problems into smaller parts to make them easier to solve, allowing the computer to cater an algorithm's execution to the resources available.

However, the divide-and-conquer method does not reveal where or how to divide the problems, which must be answered on a case-by-case basis. The divide-and-conquer strategy also means continually splitting up and recombining data, as it is passed between different cores, which can cause more difficulties, such as data storage.

MIT graduate student Tao Benjamin Schardl developed a new method of organizing data, called a bag, which led to a new algorithm for searching data trees that provides linear speedup, often considered the holy grail of parallelization because it can double the efficiency of the algorithm.

From MIT News
View Full Article



No entries found

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account