Что противоположно “смущающе параллельному”?

Question

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

Очевидно, что некоторые задачи гораздо сложнее распараллелить.Некоторые из них могут быть даже невозможны.Мне интересно, какие термины используются и каковы стандартные примеры для этих более сложных случаев.

Могу ли я предложить "Раздражающе последовательный" в качестве возможного названия?

Answer 1

По своей сути последовательный.

Пример:Количество женщин не уменьшит продолжительность беременности.

Answer 2

Существует более чем одна противоположность "смущающе параллельной" проблеме.

Идеально последовательный

Одна противоположность - это непараллеливаемый проблема, то есть проблема, для которой нет ускорение может быть достигнуто за счет использования более чем одного процессора.Несколько предложений уже было опубликовано, но я бы предложил еще одно название:a идеально последовательный проблема.

Примеры: Связанный ввод-вывод задачи", вычислить f^1000000(x₀)" тип задач, вычисляющих определенные криптографические хэш - функции.

Интенсивное общение

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

Яркий пример проблемы, требующей больших затрат на коммуникацию:решение A x = b где A представляет собой большую, плотную матрицу.На самом деле, реализация задачи используется для компиляции ТОП500 Рейтинг.Это хороший бенчмарк, поскольку он подчеркивает вычислительную мощность отдельных процессоров и качество интерконнекта (из-за интенсивности связи).

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

Answer 3

Мне трудно удержаться, чтобы не опубликовать это...потому что я знаю, что это ничего не добавляет к обсуждению..но для всех поклонников саутпарка

"Суперсериал!"

Answer 4

"Упрямо последовательный"?

Answer 5

Противоположностью смущающей параллели является Закон Амдала, в котором говорится, что некоторые задачи не могут быть параллельными, и что минимальное время, которое потребуется для выполнения идеально параллельной задачи, продиктовано чисто последовательной частью этой задачи.

Answer 6

"стандартные примеры" последовательных процессов:

• зачатие ребенка:“Аварийные программы терпят неудачу, потому что они основаны на теории, согласно которой при беременности девяти женщин можно рожать по одному ребенку в месяц”. - приписывается Вернеру фон Брауну
• вычисление pi, e, sqrt (2) и других иррациональных чисел до миллионов цифр:большинство алгоритмов последовательны
• навигация:чтобы добраться из пункта А в пункт Z, вы должны сначала пройти через некоторые промежуточные точки B, C, D и т.д.
• Метод Ньютона:вам нужно каждое приближение для того, чтобы вычислить следующее, лучшее приближение
• аутентификация "запрос-ответ"
• ключевое усиление
• цепочка хэшей
• Хэш - кэш

Answer 7

P-завершено (но это пока точно неизвестно).

Answer 8

Я использую "Унизительно последовательный"

Пол

Answer 9

"Радостно Последовательный"

Answer 10

Все это связано с зависимостями данных.Смущающе параллельные задачи - это те, решение которых состоит из множества независимых частей.Проблемами, противоположными этому, были бы те, которые имеют огромные зависимости от данных, где практически ничего нельзя сделать параллельно. Дегенеративно зависимый?

Answer 11

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

Например, обработка матрицы часто включает в себя совместное использование граничных значений по краям каждого раздела массива.

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

Answer 12

Хвастливо последовательный.

Answer 13

Я всегда предпочитал "печально последовательный" ala этап разделения в quicksort.

Answer 14

Если когда-нибудь кому-то захочется порассуждать о том, каково это - иметь естественные, неисправимо последовательные проблемы, попробуйте

блаженно последовательный

противостоять 'смущающе параллельный'.

Answer 15

- Полностью серийный?

На самом деле вас не должно удивлять, что ученые больше думают о том, что можно сделать, чем о том, чего делать нельзя.Особенно в данном случае, когда альтернативой распараллеливанию является выполнение всего, как обычно.

Answer 16

Полностью непараллеливаемый?Пессимистично распараллеливаемый?

Answer 17

Противоположное - "приводящий в замешательство сериал".

Answer 18

принимая во внимание, что параллелизм - это выполнение множества заданий за один и тот же временной шаг t.противоположностью могут быть проблемы с последовательностью во времени

Answer 19

Пример по своей сути последовательной задачи.Это распространено в пакетах САПР и некоторых видах инженерного анализа.

Обход дерева с зависимостями данных между узлами.

Представьте, что вы пересекаете график и суммируете веса узлов.

Вы просто не можете распараллелить это.

Программное обеспечение САПР представляет детали в виде дерева, и для преобразования в объект вам необходимо пройти по дереву.По этой причине рабочие станции САПР используют меньше ядер и работают быстрее, чем многоядерные.

Спасибо, что прочитали.

Answer 20

Вы могли бы, конечно, однако я думаю, что оба "имени" не являются проблемой.С точки зрения функционального программирования вы могли бы сказать, что "раздражающе последовательная" часть - это наименьшая более или менее независимая часть алгоритма.

В то время как "смущающе параллельный", если на самом деле не учитывать параллельный подход, является плохой практикой кодирования.

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