Ужасно параллельный

Параллельные вычисления, парадигма вычислений, при которой одновременно выполняется несколько задач, может содержать так называемый досадно параллельная рабочая нагрузка или проблема (также называемая совершенно параллельная, восхитительно параллельная или приятно параллельная ). Ужасно параллельную задачу можно считать тривиальным случаем - для разделения проблемы на несколько параллельных задач не требуется никаких манипуляций. Это часто случается, когда между этими параллельными задачами или в результатах между ними существует небольшая зависимость или нет необходимости.

Таким образом, они отличаются от задач распределенных вычислений, требующих коммуникация между задачами, особенно передача промежуточных результатов. Их легко выполнить на фермах серверов, в которых отсутствует специальная инфраструктура, используемая в настоящем кластере суперкомпьютер. Таким образом, они хорошо подходят для крупных распределенных Интернет-платформ, таких как BOINC, и не страдают от параллельного замедления. Противоположностью досадно параллельным задачам являются изначально последовательные задачи, которые вообще невозможно распараллелить.

Типичным примером неловко параллельной проблемы является рендеринг 3D-видео, обрабатываемый блоком обработки графики, где каждый кадр (прямой метод) или пиксель (метод трассировки лучей ) можно обрабатывать без взаимозависимостей. Некоторые формы взлома паролей - это еще одна неприятно параллельная задача, которая легко распределяется на центральные процессоры, ядра ЦП или кластеры.

Содержание

• 1 Этимология
• 2 Примеры
• 3 Реализации
• 4 См. Также
• 5 Ссылки
• 6 Внешние ссылки

Этимология

«Неловко» - это используется здесь в том же смысле, что и во фразе «позор богатства », означающем переизбыток - здесь имеется в виду проблемы распараллеливания, которые «до неприличия просты». Этот термин может также означать затруднение со стороны разработчиков или компиляторов: «Поскольку так много важных проблем остаются нерешенными, главным образом из-за присущей им вычислительной сложности, было бы неловко не разрабатывать параллельные реализации полиномиальных гомотопических методов продолжения. " Этот термин впервые встречается в литературе в 1986 году в книге о мультипроцессорах создателем MATLAB Кливом Молером, который утверждает, что он изобрел этот термин.

Альтернатива Термин, приятно параллельный, получил некоторое применение, возможно, чтобы избежать негативных коннотаций затруднений в пользу позитивного размышления о параллелизуемости проблем: «Конечно, в этих программах нет ничего смущающего».

Примеры

К некоторым примерам досадно параллельных проблем относятся:

• Анализ Монте-Карло
• Запросы распределенных реляционных баз данных с использованием обработки распределенного набора.
• Числовая интеграция
• Обслуживание статических файлов веб-сервер для нескольких пользователей одновременно.
• Набор Мандельброта, шум Перлина и подобные изображения, где каждая точка рассчитывается независимо.
• Визуализация из компьютерная графика. В компьютерной анимации каждый кадр или пиксель может быть визуализирован независимо (см. параллельный рендеринг ).
• поиск грубой силы в криптографии. Известные примеры из реальной жизни включают системы distribution.net и proof-of-work, используемые в поиске криптовалюты.
• BLAST в биоинформатике для нескольких запросов (но не для отдельных больших запросов).
• Крупномасштабные системы распознавания лиц, которые сравнивают тысячи произвольно полученных лиц (например, видео системы безопасности или наблюдения через закрытые- системное телевидение ) с таким же большим количеством ранее сохраненных лиц (например, галерея жуликов или аналогичный список наблюдения ).
• Компьютерное моделирование, сравнивающее множество независимых сценариев.
• Генетические алгоритмы.
• Ансамблевые вычисления из численного прогноза погоды.
• Моделирование и реконструкция событий в физике элементарных частиц.
• Алгоритм маршевых квадратов.
• Шаг просеивания квадратное решето и решето числового поля.
• Шаг роста дерева метода машинного обучения случайный лес.
• Дискретное преобразование Фурье, где каждая гармоника вычисляется независимо.
• Сверточные нейронные сети, работающие на графических процессорах.
• Поиск по гиперпараметрической сетке в машинном обучении.
• Параллельный поиск в программировании ограничений

Реализации

• В R (язык программирования) - Пакет Simple Network of Workstations (SNOW) реализует простой механизм использования набора рабочих станций или кластера Беовульфа для затруднительно параллельных вычислений.

См. Также

• Закон Амдала определяет значение P, которое будет почти или точно равно 1 для затруднительно параллельных задач.
• Карта (параллельный шаблон)
• Многопроцессорность
• Массивно-параллельные
• Параллельные вычисления
• Процессно-ориентированное программирование
• Архитектура без совместного использования (SN)
• Симметричная многопроцессорная обработка (SMP)
• Connec Машина
• Сотовый автомат
• Фреймворк CUDA
• Многоядерный процессор
• Векторный процессор

Ссылки

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

Внешние ссылки

• Невероятно параллельные вычисления, разработка в стиле Беовульфа Вычислительный кластер
• "Star-P: высокопроизводительные параллельные вычисления "