• Регистрация
AlexeevaNatalya
AlexeevaNatalya 0.00
н/д

Parfor для многочастичной задачи

05.10.2020
Здравствуйте. Есть проблема с работой параллельного цикла parfor. Решаю многочастичную задачу для расчета которой требуется большое количество времени. Решила воспользоваться возможность распараллелив...

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

Прикрепляю оба варианта цикла и очень надеюсь услышать от вас рекомендации относительно их усовершенствования. Заранее большое спасибо за ответ.

 

Теги

    05.10.2020

    Комментарии

    • aBoomest
      aBoomest+942.89
      5.10.2020 18:32

      1. Как происходит запус программы? Сколько ядер? Пулов?
      2. Вобще первое, что надо сделать для анализа кода - воспользоваться профайлером, хотя в вашем случае см.п.3.
      3. Время у вас и так маленькое 4-5 мс, нет? Вы еще ускорить хотите? Есть смысл в этом? понятно если гигантский расчет - и считает минут 20, тут ясно . . .  

      • AlexeevaNatalya
        AlexeevaNatalya0.00
        5.10.2020 19:15

        Спасибо за обратную связь.

        1. 12 пулов.

        2-3. В тексе программы приведен простейший пример, с небольшим количеством частиц, на самом деле хочется посмотреть эволюцию порядка 10^2-10^3 частиц, и здесь уже счет происходит неделями, поэтому нужно ускорить.

        • aBoomest
          aBoomest+942.89
          5.10.2020 20:07

          1. 12? Я конечно не профи в этом, но проц какой? Или вы соединяете несколько системников PC? Думается мне 1 пул на 1 ядро. Хотя всетаки еще раз повторюсь, что мой опыт ограничивается вариациями машин 1-4 ядра. Так что если вы собираете кластер из 3х PC c 4-ядерными камнями, то я только с интересом почитаю результаты выших трудов.)))

          2-3. Тогда profile view и  . . .

      • AlexeevaNatalya
        AlexeevaNatalya0.00
        6.10.2020 10:46

        1. Восьмиядерный процессор. Считаю с использованием локальных работников без объединения в класстреры. 

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

        2. Спасибо. Посмотрела profile view. Частей кода, нуждающихся в оптимизации нет.

        • aBoomest
          aBoomest+942.89
          6.10.2020 12:15

          Как-то тяжело поверить. Если (2) принять истной и итерации цикла независимы друг от друга, то приращение в скорости должно чувствоваться. Может есть какие-то нюансы?

          Может код для фор и парфор? Только чтоб не 4 мс выполнялся а минуту, чтобы можно было явно заметить.

          • AlexeevaNatalya
            AlexeevaNatalya0.00
            6.10.2020 12:30

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

            Как я понимаю, если итерации были бы зависимы, цикл parfor не работал бы!?

            Смотрела и для большего числа значений (макс = 125). Времменные затраты для циклов for и parfor несильно отличаются.

            • aBoomest
              aBoomest+942.89
              6.10.2020 12:39

              Как я понимаю, если итерации были бы зависимы, цикл parfor не работал бы!?

              Скорее всего да. Просто мало ли чего там гении-разрабы придумали. Может он (матлаб) в некоторых случаях сам разруливает если есть  зависимость. Сказака скорее всего, порсто недостаток знаний.

              Смотрела и для большего числа значений (макс = 125). Времменные затраты для циклов for и parfor несильно отличаются.

              А конкретнее чуть можно?

              • AlexeevaNatalya
                AlexeevaNatalya0.00
                9.10.2020 07:02

                К вопросу о конкретике. Выполнила тествый запуск (4 работника) для N = 125:

                for - 0,007 sec; parfor - 0,043 sec

                для N = 1000:

                for - 0,108 sec; parfor - 0,78 sec

                 

          • kurguz
            kurguz+270.00
            7.10.2020 17:15

            Распараллеливание кода может вам показаться хорошей идеей, но начинать оптимизацию нужно не с этого. Для начала нужно написать хорошо сам алгоритм.

            Во-первых, никогда не используйте в MATLAB циклы, если хотите получить быстрый код. Вместо циклов используйте векторизацию. Также нужно понимать, что циклы невозможно распараллелить, поэтому вы и не получаете прироста скорости.

            Во-вторых, профайлер явно намекает, что вам стоит избавиться от типа данных cell. Поскольку вы работаете с числами, это не проблема, используйте обычные массивы.

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

            Распараллеливанию не поддается всё подряд, и, если вы нацелены на использование parfor, то стоит заранее ознакомиться с возможностями и требованиями, и переписать ваш код соответственно. Также сильно сократить время вычислений можно с помощью замены системного HDD на SSD и установки большой и быстрой оперативной памяти.

            П.С. Ваш код слишком быстрый для точного замера времени выполнения одним запуском. Результаты будут точнее, если вы запустите его в цикле раз 10-20, замерите все время выполнения и найдете среднее. Первые 3-4 итерации код работет чуть медленнее, он как бы разогревается, и их можно не учитывать в замерах.

            Коллега снизу правильно заметил, что parfor призван и должен ускорять циклы. Должен, но не все, вот полезная ссылка: https://www.mathworks.com/help/releases/R2020a/parallel-computing/decide-when-to-use-parfor.html#bvnz955

            • aBoomest
              aBoomest+942.89
              7.10.2020 17:45

              Также нужно понимать, что циклы невозможно распараллелить, поэтому вы и не получаете прироста скорости.

              Как так? Я что-то не допонимаю. Если так, то логично подумать: "Зачем придуман parfor"?

              PS: Решал когда-то диф. ур-е. Надо было решить его много раз для разных частот. 10-ки тысяч раз. Простой for давал примерно 3-4 часа. Parfor на 4-ядерной машине - 10-ок минут.
              PSPS: И векторизацию тут наверно нельзя применять? Или тоже можно? "Затолкать" в дифур не число а вектор и матлаб даст сразу решения для всех значений?

              • kurguz
                kurguz+270.00
                7.10.2020 17:55

                Про параллелку вы правильно заметили. Я немного криво выразился, нужно было написать наверно так: "Также нужно понимать, что многие циклы невозможно распараллелить с приростом скорости". 

                Вот полезная ссылка: https://www.mathworks.com/help/releases/R2020a/parallel-computing/decide-when-to-use-parfor.html#bvnz955 

                Про векторизацию в дифурах несогласен, можно решать  матрицами например, также можно их преобразовать к другому виду, можно скомпилировать, можно описать их в симулинке, - много вариантов))

                • aBoomest
                  aBoomest+942.89
                  7.10.2020 18:21

                  А есть литература/ссылочка про "решать матрицами" . . . ?

                  • kurguz
                    kurguz+270.00
                    7.10.2020 19:00

                    У меня нет таких ссылочек, у меня есть векторизация.

              • AlexeevaNatalya
                AlexeevaNatalya0.00
                7.10.2020 18:17

                Спасибо за обратную связь!

                Естественно я ознакомилась с требованиями к parfor и, по моему мнению, я их не нарушила. Тип данных cell был выбран как раз таки для удовлетворения одного из них (чтобы сделать итерации по i независимыми). 

                Все что можно было векторизовать в данной задаче, векторизовано. Часть кода, вынесенная на обсуждение, как раз отвечает за расчет "вектора ускорения" для дальнейшей подстановки в дифуры.

                Если у Вас есть опыт векторизации двойной суммы (в моем случае цикл рассчитывает силы, действующие на частицу со стороны других частиц), или Вы сталкивались с таким, то поделитесь, пожалуйста источниками!) По-моему, в данном случае векторизация невозможна!

                • kurguz
                  kurguz+270.00
                  7.10.2020 19:03

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

                  dx = (X(i)-X(j)) => dx = X(i)-X(i+1:end)

                  ... и д0альше по аналогии. Почти уверен, что оба цикла можно будет свести к векторам/матрицам.

                  • kurguz
                    kurguz+270.00
                    9.10.2020 14:59

                    Наталья, вот посмотрите, я переписал ваш алгоритм через векторизацию, убрав только 1 из двух циклов:

                        N = length(X);
                        AX1 = zeros(1,N);
                        AY1 = zeros(1,N);
                        forceX = zeros(N);
                        forceY = zeros(N);
                        for i = 1:(N-1)
                            dx = X(i)-X(i+1:N);
                            dy = Y(i)-Y(i+1:N);
                            r = sqrt(dx.^2 + dy.^2);
                            forceX(i,i+1:N) = -dx./r.^3;
                            forceY(i,i+1:N) = -dy./r.^3;
                        end
                        AX1 = sum(forceX') - sum(forceX);
                        AY1 = sum(forceY') - sum(forceY);

                    На моем компьютере на выборке в 1000 точек исходный алгоритм выполняется 0.0499 секунды, а новый 0.0045 секунды, т.е. расчет ускорился примерно в 10 раз.

                    Прикрепляю файлы, попробуйте у себя.

                    • AlexeevaNatalya
                      AlexeevaNatalya0.00
                      12.10.2020 07:42

                      Да, действитьно считает быстрее, большое спасибо. Но пока самый быстрый этот:

                      N = 5;
                      X = [1 76 89 4 5];
                      Y = [12 13 14 15 11];
                      AX = zeros(1,N);
                      AY = zeros(1,N);
                      for i=1:(N-1)
                         for j=(i+1):N

                           dx = (X(i)-X(j));
                           dy = (Y(i)-Y(j));
                           r = sqrt(dx^2 + dy^2);
                           forceX = - dx/r^3;
                           forceY = - dy/r^3;

                           AX(i) = AX(i) + forceX;
                           AX(j) = AX(j) - forceX;
                           AY(i) = AY(i) + forceY;
                           AY(j) = AY(j) - forceY;

                         end
                      end

                      • kurguz
                        kurguz+270.00
                        12.10.2020 09:10

                        Примените к нему векторизацию, и он станет в разы быстрее :)