Разработка высокоэффективных алгоритмов для крупномасштабных задач: различия между версиями

5. Виттер и др. предоставили каноническую теоретическую базу для экспериментальных алгоритмов с большим объемом операций ввода-вывода, использующих внешние параллельные диски (см., например, [1, 19, 20]). Для демонстрации работы модели с параллельными дисками использовались такие примеры, как сортировка, быстрое преобразование Фурье, перестановка и транспонирование матриц.

6. Юрлинк и Вейсхофф [ ] выполнили одно из первых подробных экспериментальных исследований точности нескольких моделей параллельных вычислений на пяти параллельных платформах. Авторы обсуждают прогностические возможности моделей, сравнивают модели для выяснения, какая из них позволяет разрабатывать самые эффективные параллельные алгоритмы, и экспериментальным образом сравнивают производительность алгоритмов, разработанных с помощью модели, с алгоритмами, при разработке которых учитывались характеристики конкретно машины. Авторы выводят параметры модели для каждой платформы, выполняют анализ множества алгоритмов (для матричного умножения, битонной сортировки, сортировки по образцу и поиска кратчайших путей между всеми парами) и подробное сравнение их производительности.

7. Модель LogP, разработанная Каллером и коллегами [ ], является реалистичной моделью для разработки параллельных алгоритмов для платформ пересылки сообщений. Продемонстрировано ее применение для ряда задач, включая сортировку.