Параллельные алгоритмы и структуры данных

Question

Учитывая мои интересы в алгоритмах (см. здесь ), я хотел бы знать, существуют ли (вопреки моему предыдущему вопросу) алгоритмы и структуры данных, которые являются основными в параллельное программирование. Вероятно, еще рано спрашивать о параллельных основных алгоритмах и ds, но некоторые из гуру, возможно, имели хороший или плохой опыт с некоторыми из них.

РЕДАКТИРОВАТЬ : меня больше интересует успешное практическое применение алгоритмов и чисел, чем академических работ.

Спасибо

Answer 1

Многие технические документы Google, особенно, но не исключительно, ссылки на которые этой страницы , описывают успешные практические применения параллельных распределенных вычислений и / или их DS и алгоритмические основы. Например, этот документ имеет дело с изменением структур данных СУБД для извлечения параллелизма внутри транзакций; этот (и некоторые другие) представляет популярную архитектуру mapreduce, поскольку реализована, например, в hadoop ; этот о высокопараллелизуемом приближенном матричном факторинге, подходящем для использования в «методах ядра» в машинном обучении; и т. д. ...

Answer 2

Может быть, я полностью упускаю суть, но существует масса параллельных основных алгоритмов и структур данных, например, матричное умножение , FFT , PDE и линейное уравнение решатели, интегрирование и моделирование ( Monte-Carlo / случайные числа ), поиск и сортировка и т. Д. Взгляните на Проектирование и создание параллельных программ или Шаблоны для параллельного программирования . И тогда есть CUDA и тому подобное. Что ты после?

Answer 3

Сортировка:

• Стандартная библиотека шаблонов для очень больших наборов данных
• Тест сортировки