Параллельные вычисления - проблема, которую можно тривиально разделить на параллельные задачи.
В параллельных вычислениях смущающе параллельная рабочая нагрузка или проблема (также называемая смущающе распараллеливаемой , идеально параллельной , восхитительно параллельной или приятно параллельной ) — это такая задача, при которой для разделения проблемы на ряд параллельных задач требуется мало или совсем не требуется усилий. [1] Часто это тот случай, когда зависимость или потребность в связи между этими параллельными задачами или в результатах между ними незначительна или отсутствует. [2]
Таким образом, они отличаются от задач распределенных вычислений , которые требуют связи между задачами, особенно передачи промежуточных результатов. Их легко реализовать на фермах серверов , в которых отсутствует специальная инфраструктура, используемая в настоящем кластере суперкомпьютеров . Таким образом, они хорошо подходят для крупных интернет- платформ добровольных вычислений , таких как BOINC , и не страдают от замедления параллельного выполнения . Противоположностью до невозможности параллельных задач являются по своей сути серийные проблемы , которые вообще невозможно распараллелить.
Типичным примером досадно параллельной проблемы является рендеринг 3D-видео, выполняемый графическим процессором , где каждый кадр (метод прямого перемещения) или пиксель ( метод трассировки лучей ) могут обрабатываться без какой-либо взаимозависимости. [3] Некоторые формы взлома паролей — еще одна до неприличия параллельная задача, которую легко распределять по центральным процессорам , ядрам ЦП или кластерам.
Этимология
Слово «смущающе» здесь используется для обозначения проблем распараллеливания, которые «до неловкости просты». [4] Этот термин может означать замешательство со стороны разработчиков или компиляторов: «Поскольку так много важных проблем остаются нерешенными, главным образом из-за их внутренней вычислительной сложности, было бы стыдно не разработать параллельные реализации методов продолжения полиномиальной гомотопии ». [5] Этот термин впервые встречается в литературе в книге 1986 года о мультипроцессорах создателя MATLAB Клива Молера , [6] который утверждает, что изобрел этот термин. [7]
Альтернативный термин, « приятно параллельный» , получил некоторое распространение, возможно, чтобы избежать негативных коннотаций смущения в пользу позитивного размышления о распараллеливаемости задач: «Конечно, в этих программах вообще нет ничего смущающего». [8]
Примеры
Вот некоторые примеры досадно параллельных задач:
- Анализ Монте-Карло [9]
- Запросы к распределенным реляционным базам данных с использованием обработки распределенных наборов.
- Численное интегрирование [10]
- Массовая обработка несвязанных файлов схожего характера в целом, например изменение размера и преобразование фотогалереи.
- Множество Мандельброта , шум Перлина и подобные изображения, где каждая точка рассчитывается независимо.
- Рендеринг компьютерной графики . В компьютерной анимации каждый кадр или пиксель может отображаться независимо (см. параллельный рендеринг ).
- Некоторые грубые поиски в криптографии . [11] Яркие примеры из реальной жизни включают в себя распределенную сеть и системы доказательства работы, используемые в криптовалюте .
- BLAST осуществляет поиск в биоинформатике с разделенными базами данных. [12]
- Крупномасштабные системы распознавания лиц , которые сравнивают тысячи произвольных полученных лиц (например, видео с охранной системы или наблюдения через систему видеонаблюдения ) с таким же большим количеством ранее сохраненных лиц (например, галерея мошенников или аналогичный список наблюдения ). [13]
- Компьютерное моделирование, сравнивающее множество независимых сценариев.
- Генетические алгоритмы . [14]
- Ансамбльные расчеты численного прогноза погоды .
- Моделирование и реконструкция событий в физике элементарных частиц .
- Алгоритм марширующих квадратов .
- Шаг просеивания квадратичного сита и сита числового поля .
- Шаг роста дерева метода машинного обучения случайного леса .
- Дискретное преобразование Фурье , при котором каждая гармоника рассчитывается независимо.
- Сверточные нейронные сети , работающие на графических процессорах .
- Параллельный поиск в программировании в ограничениях [15]
Реализации
- На языке R (язык программирования) — пакет Simple Network of Workstations (SNOW) реализует простой механизм использования набора рабочих станций или кластера Beowulf для невероятно параллельных вычислений. [16] Подобные пакеты R включают «будущее», «параллельное» и другие.
Смотрите также
Рекомендации
- ^ Херлихи, Морис; Шавит, Нир (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 г.). «Функция получения ключа на основе пароля scrypt». 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: высокопроизводительные параллельные вычисления»