В параллельных вычислениях , ошеломляюще параллельная нагрузка или проблема (также называется ошеломляюще параллелизуемой , совершенно параллельно , восхищено параллельно или приятно параллельно ) один , где мало или вообще никаких усилия требуются , чтобы отделить проблему на ряд параллельных задач. [1] Это часто случается, когда между этими параллельными задачами или в результатах между ними существует небольшая зависимость или нет необходимости в обмене данными. [2]
Таким образом, они отличаются от задач распределенных вычислений, которые требуют взаимодействия между задачами, особенно передачи промежуточных результатов. Их легко выполнить на фермах серверов, в которых отсутствует специальная инфраструктура, используемая в настоящем кластере суперкомпьютеров . Таким образом, они хорошо подходят для крупных распределенных Интернет-платформ, таких как BOINC , и не страдают от параллельного замедления . Противоположность досадно параллельным задачам - это по своей сути последовательные задачи , которые вообще нельзя распараллеливать.
Типичным примером смущающе параллельной проблемы является рендеринг 3D-видео, обрабатываемый графическим процессором , где каждый кадр (метод прямой передачи) или пиксель ( метод трассировки лучей ) может обрабатываться без взаимозависимости. [3] Некоторые формы взлома паролей - еще одна неприятно параллельная задача, которая легко распределяется по центральным процессорам , ядрам ЦП или кластерам.
Этимология
«Смущающе» используется здесь в том же смысле, что и во фразе « смущение богатством », означая переизбыток - здесь имеется в виду проблемы распараллеливания, которые «до стыда легко». [4] Этот термин может также означать затруднение со стороны разработчиков или компиляторов: «Поскольку так много важных проблем остаются нерешенными в основном из-за присущей им вычислительной сложности, было бы неловко не разрабатывать параллельные реализации методов продолжения полиномиальных гомотопий ». [5] Термин впервые встречается в литературе в 1986 году книги о мультипроцессорах по MATLAB создатель «s Клив Moler , [6] , который утверждает, что изобрел этот термин. [7]
Альтернативный термин, приятно параллельный , получил некоторое применение, возможно, чтобы избежать негативных коннотаций затруднений в пользу позитивного размышления о параллелизируемости проблем: «Конечно, в этих программах нет ничего смущающего». [8]
Примеры
Вот некоторые примеры досадно параллельных проблем:
- Анализ Монте-Карло [9]
- Запросы к распределенным реляционным базам данных с использованием обработки распределенных наборов .
- Численное интегрирование [10]
- Одновременная передача статических файлов на веб-сервере нескольким пользователям. [ необходима цитата ]
- Множество Мандельброта , Перлин шум и подобные изображения, где каждая точка рассчитывается независимо друг от друга.
- Предоставление в компьютерной графике . В компьютерной анимации каждый кадр или пиксель можно визуализировать независимо (см. Параллельный рендеринг ).
- Поиски методом грубой силы в криптографии . [11] Известные примеры из реальной жизни включают в себя distribution.net и системы подтверждения работы , используемые в криптовалюте .
- BLAST выполняет поиск в биоинформатике по нескольким запросам (но не по отдельным большим запросам). [12]
- Масштабные системы распознавания лица , которые сравнивают тысячи произвольных приобретенных граней (например, безопасность или видеонаблюдение с помощью замкнутых телевизионного ) с аналогичным большим количеством ранее сохраненными граней (например, в галерее жуликов или аналогичным список часов ). [13]
- Компьютерное моделирование, сравнивающее множество независимых сценариев.
- Генетические алгоритмы . [14]
- Ensemble расчеты по численному прогнозу погоды .
- Моделирование и реконструкция событий в физике элементарных частиц .
- В марше квадратов алгоритм.
- Шаг просеивания квадратного сита и сита числового поля .
- Шаг роста дерева техники машинного обучения случайного леса .
- Дискретное преобразование Фурье, при котором каждая гармоника вычисляется независимо.
- Сверточные нейронные сети, работающие на графических процессорах .
- Поиск по сетке гиперпараметров в машинном обучении. [ необходима цитата ]
- Параллельный поиск в программировании ограничений [15]
Реализации
- В R (язык программирования) - пакет Simple Network of Workstations (SNOW) реализует простой механизм использования набора рабочих станций или кластера Беовульфа для затруднительно параллельных вычислений. [16]
Смотрите также
- Закон Амдала определяет значение P , которое было бы почти или точно равным 1 для смущающе параллельных задач.
- Карта (параллельный узор)
- Многопроцессорность
- Массивно параллельный
- Параллельные вычисления
- Процессно-ориентированное программирование
- Архитектура без общего доступа (SN)
- Симметричная многопроцессорная обработка (SMP)
- Соединительная машина
- Клеточный автомат
- Фреймворк CUDA
- Многоядерный процессор
- Векторный процессор
Рекомендации
- ^ Херлихи, Морис; Шавит, Нир (2012). Искусство многопроцессорного программирования, исправленное издание (исправленное изд.). Эльзевир. п. 14. ISBN 9780123977953. Проверено 28 февраля +2016 .
Некоторые вычислительные задачи «до неприличия параллельны»: их легко разделить на компоненты, которые могут выполняться одновременно.
- ^ Раздел 1.4.4: Фостер, Ян (1995). Проектирование и построение параллельных программ . Аддисон-Уэсли. ISBN 9780201575941. Архивировано из оригинала на 2011-03-01.
- ^ Алан Чалмерс; Эрик Рейнхард; Тим Дэвис (21 марта 2011 г.). Практический параллельный рендеринг . CRC Press. ISBN 978-1-4398-6380-0.
- ^ Matloff Норман (2011). Искусство программирования на языке R: обзор разработки статистического программного обеспечения , стр. 347. Без крахмала. ISBN 9781593274108 .
- ^ Лейкин, Антон; Вершельде, Ян; Чжуан, Ян (2006). Параллельные гомотопические алгоритмы решения полиномиальных систем . Труды ICMS . Конспект лекций по информатике. 4151 . С. 225–234. DOI : 10.1007 / 11832225_22 . ISBN 978-3-540-38084-9.
- ^ Молер, Клив (1986). Хит, Майкл Т. (ред.). Матричные вычисления на мультипроцессорах с распределенной памятью . Мультипроцессоры Hypercube . Общество промышленной и прикладной математики, Филадельфия. ISBN 978-0898712094.
- ^ Гиперкуб Intel, часть 2, репост в блоге Cleve's Corner на сайте MathWorks
- ^ Кепнер, Джереми (2009). Параллельный MATLAB для многоядерных и многоузловых компьютеров , стр.12. СИАМ. ISBN 9780898716733 .
- ^ Эррикос Джон Контогиоргес (21 декабря 2005 г.). Справочник по параллельным вычислениям и статистике . CRC Press. ISBN 978-1-4200-2868-3.
- ^ Юэфань Дэн (2013). Прикладные параллельные вычисления . World Scientific. ISBN 978-981-4307-60-4.
- ^ Саймон, Йозефссон; Колин, Персиваль (август 2016 г.). "Функция вывода ключей на основе пароля scrypt" . tools.ietf.org . Проверено 12 декабря 2016 .
- ^ Форум SeqAnswers
- ^ Как мы сделали наш распознаватель лиц в 25 раз быстрее (сообщение в блоге разработчика)
- ^ Сигэёси Цуцуи; Пьер Колле (5 декабря 2013 г.). Массивно-параллельные эволюционные вычисления на GPGPU . Springer Science & Business Media. ISBN 978-3-642-37959-8.
- ^ Юсеф Хамади; Лахдар Саис (5 апреля 2018 г.). Справочник по параллельным ограничениям . Springer. ISBN 978-3-319-63516-3.
- ^ Пакет Simple Network of Workstations (SNOW)
Внешние ссылки
- Невероятно параллельные вычисления , проектирование вычислительного кластера в стиле Беовульфа
- « Star-P: высокопроизводительные параллельные вычисления »