Мой вопрос о том, как лучше всего структурировать мой (C ++) код для поддержки распараллеливания трудоемких вычислений. Рассматриваемый псевдокод имеет следующую структуру:
for a_1(y_1) in A_1
for a_2(y_2) in A_2(a_1)
...
for a_n(y_n) in A_n(a_1, ..., a_{n-1})
y_n = f(a_1, ..., a_n)
y_{n-1} = g_n(Y_n)
...
y_1 = g_2(Y_2)
.
Грубо говоря, каждый цикл перебирает элементы в наборе A_i, последовательные элементы которого зависят от обратной связи y_i от предыдущих итераций. Другими словами, чтобы определить следующее a_i, мы должны были закончить все вычисления на текущем a_i. Кроме того, внутренние наборы зависят от внешних итераций. Написано в рекурсивной форме:
Iterate(A_i, a_1, ..., a_{i-1}):
for a_i(h_i) in A_i
Y_i += Iterate(A_{i+1}, a_1, ..., a_i)
return g(Y_i)
Iterate(any, a_1, ..., a_n):
return f(a_1, ..., a_n)
Iterate(A_1)
Предположим, что f (...) - это трудоемкое вычисление, и что функции обратной связи g (...) являются простыми (быстрыми). Теперь, если все множества A_i являются «большими», тогда проблема смущающе распараллеливается. В настоящее время у меня есть пул потоков, и я просто добавляю вычисления самого внутреннего цикла в пул. Проблема в том, что очень часто самый внутренний цикл - это итерация по синглтону, поэтому в пуле потоков всегда есть только один запущенный поток. Я думал об использовании фьючерсов для возврата значений во внешние циклы, но это потребовало бы фьючерсов фьючерсов и т. Д., И это становится довольно грязным (я думаю).
Я понимаю, что структура, которую я перечислил выше, довольно сложна, поэтому я также заинтересован в нескольких упрощающих случаях:
a_i(h_i) = a_i; не зависит от h_i A_i(a_1, ..., a_{i-1}) = A_i; не зависит от a_1, ... a_ {i-1} g_i = 0; не зависит от H_ {i + 1} - Все внешние петли "большие"; количество элементов в этих наборах намного больше, чем количество ядер.
Теперь на практике n <= 3, и пункт 1 выполняется для всех внешних циклов, а пункты 2-4 - все, так что конкретных решений для этого случая достаточно. Но так как я пытаюсь задать вопрос здесь, мне интересно получить идеи о том, как справиться с дополнительной сложностью для более общих проблем, если это возможно. </p>
Edit:
Очистил первый блок псевдокода, чтобы он соответствовал другому.
Поскольку люди не могут понять мою математическую запись, вот более конкретный простой пример:
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
double f(double a1, int a2, double a3){ // Very slow function
cout << a1 << ", " << a2 << ", " << a3 << endl;
return pow(a1*a3, a2) + a1 + a2 + a3; // just some contrived example
}
int g2(const vector<double> &Y3){ // average-ish
double sum = 0;
for(int i = 0; i < Y3.size(); ++i){ sum += Y3[i]; }
return int(sum / (Y3.size() + 1));
}
double g1(const vector<int> &Y2){ // return 1/(min(Y2)+1.0)
int imin = 0; int minval = 0;
for(int i = 1; i < Y2.size(); ++i){
if(Y2[i] < minval){
imin = i;
minval = Y2[imin];
}
}
return 1.0/double(minval+1.0);
}
int main(){
for(double a1 = 0.0, h1 = 10.0; a1 < 1.0; a1 += h1){ // for a1 in A1
vector<int> Y2;
for(int a2 = 2, h2 = 1; a2 <= (int)(5*a1+10); a2 += h2){ // for a2 in A2(a1)
vector<double> Y3;
for(double a3 = 6.0, h3 = 1.0; a3 >= (a1+a2); a3 -= 0.5*h3){ // for a3 in A2(a1, a2)
h3 = f(a1, a2, a3);
Y3.push_back(h3);
}
h2 = g2(Y3);
Y2.push_back(h2);
}
h1 = g1(Y2);
}
return 0;
}
Я выбрал значения случайным образом, и получается, что f оценивается только 3 раза. Обратите внимание, что приведенный выше код НЕ распараллеливается. Предположим, что можно запросить, зависит ли приращение цикла от более высоких циклов вверх.
Я должен также уточнить, что я преследую. Когда я первоначально сказал структуру, я, возможно, должен был сказать методологию распараллеливания или что-то подобное Например, моя первая попытка распараллеливания состояла в том, чтобы бросить самые внутренние вызовы f в пул потоков и присоединиться в конце самого внутреннего цикла. Как упоминалось выше, это не работает, когда самый внутренний цикл повторяется только над одним элементом. Это на самом деле не требовало существенной реструктуризации существующего кода, и я хотел бы избежать этого, если это возможно.