Существуют ли известные проблемы / алгоритмы в научных вычислениях, которые нельзя ускорить распараллеливанием?

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

$C$$T$$C$$T$$C$$T$$T$$N$$C \sim \log T$

Примеры

• $C = T$
• $m\times m$$T = N = \mathcal O(m^2)$$C = m = \sqrt T$
• $T = N$$C = \log T$
• $\tau$$(0,1)^d$$k = \tau / \Delta t \sim \tau N^{1/d}$$C = k$$T = k N = \tau N^{(d+1)/d}$$P = T/C = N$$N^{1/d}$

Формальная сложность

$NC = P$

$NC$$O(log^c n)$$O(n^k)$$P=NC$$P$$P$$P$$P$$NC$$P$$NC$$P=NC$

$P$$P$

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

Кроме того, ключевым вопросом часто является узкое место в пропускной способности памяти. В частности, с большинством графических процессоров ваши теоретические провалы значительно превышают количество чисел с плавающей запятой, которые вы можете получить в своих ALU, поскольку такие алгоритмы с низкой арифметической интенсивностью (провалы / ошибки кэширования) будут тратить огромное количество времени на ожидание ОЗУ.

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

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

Примером отсутствия проблемы ветвления является вычисление вектора, который является кумулятивной суммой другого вектора. ([1,2,1] -> [1,3,4])

Я не знаю, считаются ли они «известными», но, безусловно, существует большое количество проблем, с которыми параллельные вычисления вам не помогут.

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

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

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

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

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

Рассмотрим, например, процесс Грама – Шмидта и его последовательную модификацию. Алгоритм работает с векторами, поэтому вы можете использовать параллельные векторные операции, но это плохо масштабируется. Если число векторов велико, а размер вектора невелик, использование классического параллельного метода Грамса-Шмидта и реортогонализация могут быть стабильными и более быстрыми, чем у одного модифицированного Грамма-Шмидта, хотя это требует выполнения в несколько раз больше работы.