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