Параллельное программирование, на какие операции разбить?

Question

[woodyJS]

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

// A = U(t)*U, далее находим U and U(t)
            double temp;
            double[,] U = new double[n, n];      
            for(int i=0;i<n;i++)
                for (int j=0;j<n;j++)
                {
                    U[i, j] = 0;
                }
            for (int i = 0; i < n; i++)
            {
                temp = 0;
                for (int k=0;k<i;k++)
                    temp = temp + Math.Pow(U[k, i], 2);
                U[i, i] =Math.Sqrt(A[i, i] - temp);
                for (int j = i; j < n; j++)
                {
                    temp = 0;
                    for (int k = 0; k < i; k++)
                        temp = temp + U[k, i] * U[k, j];
                    U[i, j] = (A[i, j] - temp) / U[i, i];
                    
                }
                
            }
            for (int i = 0; i<n;i++)
            {
                for (int j=0; j < n; j++)
                {
                    Console.Write("{0} ", U[i, j]);
                }
                Console.WriteLine();
            }


            double[] x = new double[n];
            double[] y = new double[n];
           
            for (int i=0;i<n;i++)
            {
                temp = 0;
                for(int k=0;k<i;k++)               
                    temp = temp + U[k, i] * y[k];
                y[i] = (b[i] - temp) / U[i, i];
            }
            for(int i=n-1;i>=0;i--)
            {
                temp = 0;
                for (int k = i + 1; k < n; k++)
                    temp = temp + U[i, k] * x[k];
                x[i] = (y[i] - temp) / U[i, i];
            }
            for (int i = 0; i < n; i++)
                Console.Write("{0} ", x[i]);
            Console.WriteLine();

Answer 1

[tomatho]

В первую очередь параллель это:

for (int k = 0; k < i; k++)
    temp = temp + U[k, i] * U[k, j];

Просто разбей диапазон значений j на M ядер.
Проще всего так. Если у нас есть N операций, и мы хотим разбить на M ядер то это (N+M-1)/M с округлением вниз операций на ядро.
Update: Не всё так просто как мне казалось, в общем, это не ответ.

Можно другие попробовать распараллелить, но это это самая ресурсоёмкая часть.
Вообще хорошо гуглится описание распараллеливания этого алгоритма.

Comments

[woodyJS]

т.е. в данном случае надо выносить в отдельный поток выч диагонали, выч i-го столбца и обратных ход?

[tomatho]

Ну лично я имел ввиду выносить в отдельный поток не более чем (N+M-1)/M итераций цикла по j. Где N это количество итераций будет, M количество потоков.

[tomatho]

В общем, я плохо смотрел. Посмотрите ссылку которую я дал, может она поможет.

[woodyJS]

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

[woodyJS]

я так понимаю лучше использовать таски
но ввобще не понимаю как

[tomatho]

И так, порылся. Что могу сказать. Я изначально был прав, но меня смутили индексы.
Оказалось, что это просто неточность кода.
Тот цикл по j лучше было сделать от i+1, тогда было бы ясно, что никак одна итерация не влияет на другую итерацию. Проверить это можно нарисовав для себя:

00 01 02 03 04 05 06 07 08 09
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49
50 51 52 53 54 55 56 57 58 59
60 61 62 63 64 65 66 67 68 69
70 71 72 73 74 75 76 77 78 79
80 81 82 83 84 85 86 87 88 89
90 91 92 93 94 95 96 97 98 99

Такую матрицу и повыделять то, что нужно. Так например:

• Итерация i = 5.
  
• Желтым - уже известное.
  
• Синим - то что считаем.
  
• Красным - корень который перед циклом по j.
  
• Зелёным - самое главное - ячейки цикла которые будут затрагиваться отдельной итерацией по j.
  
• Светло зелёным - то, что читается всеми итерациями цикла по j.
  

То есть, именно эти j и нужно в первую очередь параллелить.

Каким образом? Как уже говорилось, M потоков, каждый считает по некоротому числу из них. Пока все j не посчитаются, нельзя переходить к следующему i. То есть, надо грубо говоря стартовать M=10 потоков, ждать их обработки, затем переходить к следующему i, стартовать снова 10 потоков.

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

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

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

Есть ещё MPI.Net

[woodyJS]

tomatho: tomatho: tomatho: браво
я таких ответов еще не видел
это нечто
честно
я в шоке
спасибо тебе большое

матрица должна быть полностью симметричной
но благодаря тебе я понял как делать

[woodyJS]

woodyJS: спасибо!!

[tomatho]

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

Там в статье по конкретно этому алгоритму вообще расписано как распараллелить все неконфликтующие операции, но я сомневаюсь что это тебе надо. Тем более, что на обычном C# сомневаюсь что оно даст какой-либо прирост. Это надо быть джедаем.
Суть в том, что результат Uij для каждого i и каждого j мы сразу начинаем считать с первой итерации i. То есть происходит i обновлений всех строк матрицы Uij номера которых больше либо равно i.
Они как бы хранят "накопленные" результаты.
Мне лично сходу не ясно как из распределить.