Распараллелить внутренние циклы с потоками при записи во внешние переменные - PullRequest
0 голосов
/ 04 июля 2018

Я застрял при распараллеливании следующего кода:

double[][] a, b, c;
double d;
double[] e;
for (int i = 1; i < x; i++) {
    double f = 0.0;
    for (int j = 0; j < y; j++) {
        double a1 = a[i-1][j];
        double a2 = a[i][j];
        double a3 = a1 * a2;
        d -= a3;
        c[i][j] = c[i - 1][j] + a3;
        f += c[i][j] * a3;
    }
    e[i] = d + f;
    for (int j = 0; j < y; j++) {
        a[i][j] = e[i] * b[i][j]
    }
}

Второй внутренний цикл зависит от первого (из-за e[i]), поэтому они должны выполняться последовательно, но внутри каждого из них вычисления могут быть распараллелены на y.

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

x имеет порядок 10000 и y 250. Обработка внутренних циклов в этом примере упрощена, но на самом деле требует больших вычислительных ресурсов.

Вопрос здесь в том, как распараллелить циклы, которые читают и пишут внешние переменные?

Следующая попытка не компилируется из-за d и f:

double[][] a, b, c;
double d;
double[] e;
for (int i = 1; i < x; i++) {
    double f = 0.0;
    IntStream.range(0, y).parallel().forEach(j -> {  
        double a1 = a[i-1][j];
        double a2 = a[i][j];
        double a3 = a1 * a2;
        d -= a3;
        c[i][j] = c[i - 1][j] + a3;
        f += c[i][j] * a3;
    });
    e[i] = d + f;
    IntStream.range(0, y).parallel().forEach(j -> {  
        a[i][j] = e[i] * b[i][j];
    });
}

1 Ответ

0 голосов
/ 04 июля 2018

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

Результат первого цикла:

  • приращение к переменной d
  • значение f
  • новый c[i] подмассив

Чтобы вычислить их, вы можете создать пользовательский тип для хранения 3 значений, а затем выполнить изменяемое сокращение для вычисления всех 3. Для отсутствия лучшего имени я буду называть пользовательский тип ResultContainer.

Аналогично, результатом второго цикла является массив a[i]. Это проще, так как легко построить массив из Stream.

Таким образом, это даст:

for (int i0 = 1; i0 < x; i0++) {
    final int i = i0; // tmp store as final for use in lambda
    ResultContainer result = IntStream.range(0, y).parallel()
            .collect(() -> new ResultContainer(y), (resultContainer, j) -> {
                double a1 = a[i - 1][j];
                double a2 = a[i][j];
                double a3 = a1 * a2;
                double cij = c[i - 1][j] + a3;
                resultContainer.add(-a3, cij * a3, j, cij);
            }, ResultContainer::add);

    d += result.d;
    e[i] = d + result.f;
    c[i] = result.ci;
    a[i] = IntStream.range(0, y).parallel().mapToDouble(j -> e[i] * b[i][j]).toArray();
}

с нашим пользовательским типом:

class ResultContainer {
    double d;
    double f;
    double[] ci;

    public ResultContainer(int y) {
        this.d = 0;
        this.f = 0;
        ci = new double[y];
    }

    public void add(double d, double f, int j, double cij) {
        this.d += d;
        this.f += f;
        ci[j] = cij;
    }

    public void add(ResultContainer resultContainer2) {
        d += resultContainer2.d;
        f += resultContainer2.f;
        for (int j = 0; j < ci.length; j++) {
            // note that one of the two is always 0 here
            ci[j] += resultContainer2.ci[j];
        }
    }
}
...