переменная предварительная оценка в диапазоне целых чисел

Question

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

Вот Exemple:

double mu1 = 0, q1 = 0; 
    double max_sigma = 0, max_val = 0; 
    for(i = 0; i < N; i++) 
    { 
     double p_i, q2, mu2, sigma; 
     p_i = h[i]*scale; 
     mu1 *= q1; 
     q1 += p_i; 
     q2 = 1. - q1; 

     if(std::min(q1,q2) < FLT_EPSILON || std::max(q1,q2) > 1. -FLT_EPSILON) 
      continue; 

     mu1 = (mu1 + i*p_i)/q1; 
     mu2 = (mu - q1*mu1)/q2; 
     sigma = q1*q2*(mu1 - mu2)*(mu1 - mu2); 
     if(sigma > max_sigma) 
     { 
      max_sigma = sigma; 
      max_val = i; 
     } 
    } 

scale является значением double скаляр.

h является std::vector<std::uint64_t>

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

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

Итак, мой вопрос: есть ли способ определить mu1 в начале потока для диапазона B без предварительного результата mu1, что было обработано в потоке для диапазона A? Если да, то как?

Answer 1

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

Если код был больше похож:

for(i = 0; i < N; i++) 
{ 
    SomeComplexAndSlowCalculation(); // Not depending on mu1 and q1 

    mu1 = mu1 * ....; 
    q1 = q1 + ....; 

    SomeOtherComplexAndSlowCalculation(); // Depending on mu1 and q1 
              // but not changing them 

} 

вы могли бы использовать std::condition_variable что-то вроде этого:

SomeComplexAndSlowCalculation(); // Not depending on mu1 and q1 

    cv_previous.wait(...); // wait for thread handling previous index to complete 

    mu1 = mu1 * ....; 
    q1 = q1 + ....; 

    cv_next.notify_one(); // tell thread handling next index to carry on 

    SomeOtherComplexAndSlowCalculation(); // Depending on mu1 and q1 
              // but not changing them 

Вы должны запустить новый поток для каждого индекса.

Для этого, чтобы сделать разницу/улучшение, две функции должны быть довольно медленными.

Answer 2

Я сомневаюсь, что параллелизм приведет к улучшению скорости, но так, как вы бы это сделали, это алгебраически уменьшить ваши вычисления, чтобы они основывались на абсолютном значении i, а не на предыдущем состоянии (i-1), т.е. заменить

p_1 = h[i]*scale; 
mu1 *= q1; 
q1 += p_1; 

mu1 = product_n(pre_scaled_h, 0, i-1); 
q1 = sum_n(pre_scaled_h, 0, i); 

где Н [] является предварительно масштабируется для упрощения операций на нем, и product_n и sum_n определены для вычисления соответствующего продукта и суммы элементов в предварительно масштабированной ч от 0 до соответствующего третьего параметра включительно (обратите внимание, что mu1 основан на i-1, а не на i, потому что он умножается на q1 до пересчета q1).

Это алгебраическое сокращение устраняет зависимость от предыдущей итерации и должно быть возможным для всех переменных, кроме max_sigma и max_val, которые, вероятно, придется вычислять по каждому отдельному потоку, а затем соответствующий набор максимальных потоков будет иметь сравниваться, чтобы найти реальный максимум. Традиционная блокировка на них, скорее всего, устранит любое возможное увеличение скорости, поэтому обработка, которая потребует тщательного управления потоками самостоятельно (поскольку, например, параллелизм :: parallel_for не гарантирует, какой блок работы будет выполняться в заданном потоке).

Обратите внимание, что вы должны иметь возможность уменьшить это до одного вычисления, а не итеративного цикла (конечно, с простыми операциями sum/product на h), так как алгебраическая редукция, по-видимому, полностью основана на h []. Если вы можете уменьшить его до одного уравнения без итеративного цикла, вы получите больше производительности, чем любой другой вариант.