4430
правок
Разработка высокоэффективных алгоритмов для крупномасштабных задач: различия между версиями
Материал из WEGA
Разработка высокоэффективных алгоритмов для крупномасштабных задач (посмотреть исходный код)
Версия от 22:19, 25 февраля 2021
, 25 февраля 2021→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Применение) |
||
| Строка 27: | Строка 27: | ||
2. В процессе демонстрации возможностей технологий разработки высокоэффективных алгоритмов ускорение в миллион раз было достигнуто при помощи сочетания ускорения последовательного выполнения кода в 2 тысячи раз и ускорения в 512 раз благодаря распараллеливанию (притом вторая составляющая ускорения может быть масштабирована на любое число процессоров) [13]. (При последующей демонстрации процесса разработки алгоритма внесенные в стратегии поиска и ограничений улучшения позволили ускорить выполнение последовательной части кода еще в 1000 раз, а общее ускорение в результате превысило 2 миллиарда раз). | 2. В процессе демонстрации возможностей технологий разработки высокоэффективных алгоритмов ускорение в миллион раз было достигнуто при помощи сочетания ускорения последовательного выполнения кода в 2 тысячи раз и ускорения в 512 раз благодаря распараллеливанию (притом вторая составляющая ускорения может быть масштабирована на любое число процессоров) [13]. (При последующей демонстрации процесса разработки алгоритма внесенные в стратегии поиска и ограничений улучшения позволили ускорить выполнение последовательной части кода еще в 1000 раз, а общее ускорение в результате превысило 2 миллиарда раз). | ||
3. Джаджа и Хелман провели эмпирическое исследование операций вычисления префиксов, сортировки и ранжирования списков на симметричных мультипроцессорах. Исследование сортировки (см. [9]) расширяет модель с параллельными дисками Виттера на иерархию внутренней памяти симметричных мультипроцессоров и использует эту новую вычислительную модель для анализа алгоритма сортировки по образцу общего вида, эффективно работающего в разделяемой памяти. При оценке эффективности используются 9 точно определенных эталонных тестов. В число этих тестов входят распределения входных данных, широко используемые для эталонных тестов сортировки (например, ключи, выбираемые равномерным случайным образом), и тесты, разработанные для проверки работы алгоритма в условиях дисбаланса | 3. Джаджа и Хелман провели эмпирическое исследование операций вычисления префиксов, сортировки и ранжирования списков на симметричных мультипроцессорах. Исследование сортировки (см. [9]) расширяет модель с параллельными дисками Виттера на иерархию внутренней памяти симметричных мультипроцессоров и использует эту новую вычислительную модель для анализа алгоритма сортировки по образцу общего вида, эффективно работающего в разделяемой памяти. При оценке эффективности используются 9 точно определенных эталонных тестов. В число этих тестов входят распределения входных данных, широко используемые для эталонных тестов сортировки (например, ключи, выбираемые равномерным случайным образом), и тесты, разработанные для проверки работы алгоритма в условиях дисбаланса нагрузки и конфликтов памяти, а также для обхода определенных проектных решений, основанных на специфических свойствах входных данных (таких как распределение данных, присутствие дублирующихся ключей, предварительно отсортированные входные данные и т. п.). | ||
4. В работе [3] Блеллок и др. при помощи анализа и реализации сравнивают три алгоритма сортировки на компьютерах Thinking Machines CM-2. Несмотря на использование устаревшей (и в настоящее время уже недоступной) платформы, эта статья превосходна сама по себе и должна быть настольным документом каждого разработчика параллельных алгоритмов. В одном из первых исследований подобного рода авторы оценивают время выполнения четырех машинных примитивов, а затем анализируют этапы трех алгоритмов сортировки в терминах указанных параметров. Экспериментальные измерения эффективности нормализованы для получения четкого сравнения масштабируемости алгоритмов по мере роста размера входных данных на компьютере CM-2 с 32 тысячами процессоров. | 4. В работе [3] Блеллок и др. при помощи анализа и реализации сравнивают три алгоритма сортировки на компьютерах Thinking Machines CM-2. Несмотря на использование устаревшей (и в настоящее время уже недоступной) платформы, эта статья превосходна сама по себе и должна быть настольным документом каждого разработчика параллельных алгоритмов. В одном из первых исследований подобного рода авторы оценивают время выполнения четырех машинных примитивов, а затем анализируют этапы трех алгоритмов сортировки в терминах указанных параметров. Экспериментальные измерения эффективности нормализованы для получения четкого сравнения масштабируемости алгоритмов по мере роста размера входных данных на компьютере CM-2 с 32 тысячами процессоров. | ||
