Лучший способ вычислить результат по формуле?

Question

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

Вычисления выполняются с массивами чисел, так что, например, простое A + B на самом деле может означать 100 сложений.В настоящее время я использую Delphi, но в дальнейшем это не является обязательным требованием.Я буду использовать инструмент, наиболее подходящий для этой работы.Формулы также могут зависеть друг от друга, так что у нас может быть одна формула C = A + B и вторая, например, D = C + A.

Answer 1

Давайте предположим, что ваши формулы (уравнения) не являются циклическими, так как в противном случае вы не можете "просто" оценить их.Если у вас есть векторизованные уравнения типа A = B + C, где A, B и C являются массивами, давайте концептуально разделим их на уравнения по компонентам, так что, если размер массива равен 5, это уравнение разбивается на

a1 = b1 + c1
a2 = b2 + c2
...
a5 = b5 + c5

Теперь, предполагая это, у вас есть большой набор уравнений для простых величин (будь то целочисленные, рациональные или что-то еще).

Если у вас есть два уравнения E и F, допустим, что F зависит от E, если правая часть F упоминает левую часть E, например

E: a = b + c
F: q = 2*a + y

Теперь, чтобы узнать, как это вычислить, вы всегда можете использовать рандомизированную итерацию для решения этой проблемы (это всего лишь промежуточный шаг в объяснении), следуя этому алгоритму:

1 while (there is at least one equation which has not been computed yet)
2   select one such pending equation E so that:
3     for every equation D such that E depends_on D:
4       D has been already computed
5   calculate the left-hand side of E

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

Answer 2

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

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

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