Communications of the ACM
Retooling Algorithms
MIT professor Charles Leiserson
MIT
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