Оценка функции по определенному значению параллельно

Question

Вопрос может показаться расплывчатым, но позвольте мне объяснить его.

Предположим, у нас есть функция f (x, y, z ....) и нам нужно найти ее значение в точке (x1, y1, z1 .....).

Самый простой подход - просто заменить (x, y, z ...) на (x1, y1, z1 .....).

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

Поэтому мой вопрос: какие ограничения я должен искать, пока «думаю», чтобы распараллелить f (x, y, z ...)?

Если возможно, поделитесь ссылками для изучения.

Answer 1

Задание вопроса таким общим способом не позволяет дать очень конкретный совет.

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

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

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

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

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

Другая область, в которой много известно, - это многомерные полиномиальные и рациональные функции.

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

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

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

Добавлено: Некоторые ссылки и обсуждение стратегии поиска

Большинство авторов используют фразу "оценка параллельной функции" для означает оценку одной и той же функции в нескольких точках аргумента.

См. Например:

[Оценка крупнозернистых параллельных функций - Рулон и Юсеф]
http://cdsweb.cern.ch/record/401028/files/p837.pdf

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

Также эффективно сосредоточиться на определенных видах функций, например, «полиномиальная оценка», а не «оценка функции».

Вот, например, у нас есть лечение некоторых известных методов для «быстрых» оценок, применяемых для проектирования вычислений на основе графического процессора:

[Как получить эффективные ядра GPU - Круз, Лейтон и Барба]
http://arxiv.org/PS_cache/arxiv/pdf/1009/1009.3457v1.pdf

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

Другим поисковым термином, который стоит исключить, является «конвейерный». Этот термин неизменно обсуждает вид параллелизма, который может использоваться, когда необходимо выполнить множественные оценки функций. Рано Этапы вычисления могут быть выполнены параллельно с более поздними ступени, но на разных входах.

Так что это поисковый запрос, который можно исключить. Или нет.

Вот статья, в которой обсуждается n-кратное ускорение для n-variate. полиномиальная оценка над конечными полями GF (p). Это может быть прямой интерес для криптографических приложений, но подход через модифицированный метод Хорнера может быть интересен для его потенциал для обобщения:

[Сравнение алгоритмов на уровне битов и слов для оценки Неструктурированные функции над конечными кольцами - Сунар и Сигански]
http://www.iacr.org/archive/ches2005/018.pdf

"Мы представляем модификацию алгоритма Хорнера для оценки произвольные n-переменные функции, определенные над конечными кольцами и полями. ... Если область является конечным полем GF (p), то сложность многовариантная оценка полинома Хорнера улучшена с O (p ^ n) в O ((p ^ n) / (2n)). Докажем оптимальность представленного алгоритма. "

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

Тема постоянных оценок фракций позволяет нам к последней ссылке, которая связывает эту тему с некоторыми знакомыми параллелизм числовой линейной алгебры:

[LU Факторизация и параллельная оценка продолженных фракций Ömer Egecioglu]
http://www.cs.ucsb.edu/~omer/DOWNLOADABLE/lu-cf98.pdf

"Первые n сходящихся общей непрерывной дроби (CF) может быть оптимально вычислено в логарифмической параллели время с использованием O (n / log (n)) процессоров. "

Answer 2

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

Однако обычно люди, задающие ваш вопрос, на самом деле вызывают функцию много раз (скажем, N раз) для разных значений x,y, z (например, x1, y1, ... x2, y2, ... xN, yN, ... используя ваш словарный запас).Да, если вы ускорите выполнение функции, общий набор вызовов ускорится, и это то, что люди хотят.Если это так, то «технически легко» ускорить общее выполнение: сделать N вызовов функции параллельно.Тогда все точечные оценки происходят одновременно.Чтобы это работало, у вас в значительной степени есть составляющие векторов из значений, которые вы хотите обработать (поэтому этот вид трюка называется программированием "параллельной передачи данных").То, что вы действительно хотите, это что-то вроде:

    PARALLEL DO  I=1,N
          RESULT(I)=F(X[J],Y[J], ...)
    END PARALLEL DO

Как вы реализуете PARALLEL DO, зависит от языка программирования и библиотек, которые у вас есть.Обычно это работает, только если N - довольно большое число, но чем дороже выполнить f, тем меньше эффективный N.

Вы также можете воспользоваться структурой своей функции, чтобы сделать ее еще более эффективной.,Если f вычисляет некоторое внутреннее значение таким же образом для часто используемых случаев, вы можете выделить особые случаи, предварительно вычислить их, а затем использовать эти результаты для вычисления «остатка от f» для каждого отдельного вызова.

Если вы объединяете («сокращаете») результаты всех функций (например, суммируете все результаты), вы можете сделать это вне цикла PARALELL DO.Если вы попытаетесь объединить результаты внутри цикла, у вас появятся «зависимости, переносимые циклом», и вы либо получите неправильный ответ, либо он не будет идти параллельно, как вы ожидаете, в зависимости от вашего компилятора или библиотек параллелизма.Вы можете эффективно комбинировать ответы, если комбинация является некоторой ассоциативной / коммутативной операцией, такой как «сумма», путем построения того, что составляет двоичное дерево, и выполнения оценки , что параллельно.Это другая проблема, которая часто возникает в параллельных вычислениях данных, но мы не будем вдаваться в подробности.

Часто издержки параллельного цикла for довольно высоки (разветвление потоков стоит дорого).Поэтому обычно люди делят накладные расходы на несколько итераций:

   PARALLEL DO  I=1,N,M
        DO J=I,I+M
            RESULT(J)=F(X[J],Y[J], ...)
        END DO
   END PARALLEL DO

Константа M требует калибровки для эффективности;Вы должны "настроить" это.Вы также должны позаботиться о том, чтобы N не было кратным М;это требует только дополнительной чистой петли для обработки краевого состояния:

   PARALLEL DO  I=1,int(N/M)*M,M
        DO J=I,I+M
            RESULT(J)=F(X[J],Y[J], ...)
        END DO
   END PARALLEL DO
   DO J=int(N/M)*M,N,1
            RESULT(J)=F(X[J],Y[J], ...)
   END DO