На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
[!] Как относитесь к модерированию на этом форуме? Выскажите свое мнение здесь
Модераторы: Qraizer
  
> Ускорить процесс подготовки "Карты смещений"
    Привет.
    Есть, например, 10 миллионов объектов. Каждый объект знает количество своих потомков.
    Нужно максимально быстро подготовить "карту смещений" для объектов.

    Карта смещений — это некий массив, размер которого равен количеству объектов + 1. Этот массив нужен для того, чтобы узнавать количество потомков у любого из объектов.
    Например:
    0 объект содержит 4 потомка.
    1 объект содержит 3 потомка.
    2 объект содержит 4 потомка.
    3 объект содержит 2 потомка.

    Размерность массива получится равной 4 + 1.
    Массив смещений должен содержать следующие значения: 0,4,7,11,13.
    Количество потомков у любого из объектов определяется следующим образом: количество потомков = массив[номер объекта + 1] - массив[номер объекта].

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

    int numberOfObjects = 10000000;
    int arraySize = numberOfObjects + 1;
    int *shiftArray = new int[arraySize];
    int shiftValue = 0;

    for( int i = 0; i <= numberOfObjects; i++ )
    {
    shiftArray[i] = shiftValue;
    if ( i < numberOfObjects )
    shiftValue += object[ i ].GetNumberOfChilds();
    }


    delete []shiftArray;

    Спасибо!
      Цитата gordey @
      Помогите, пожалуйста, ускорить процесс заполнения массива

      Попробуй для начала так:
      ExpandedWrap disabled
        int numberOfObjects = 10000000;
        int arraySize = numberOfObjects + 1;
        int *shiftArray = new int[arraySize];
        int shiftValue = 0;
         
        for(int i=0; i < numberOfObjects; i++)
        {
         shiftArray[i] = shiftValue;
         shiftValue += object[ i ].GetNumberOfChilds();
        }
        shiftArray[numberOfObjects] = shiftValue;
         
        delete []shiftArray;
        Это ну совершенно несущественный шаг, ЫукпШ.
          Тем более, что в оригинале у меня именно так и написано ;)
            Цитата Славян @
            Это ну совершенно несущественный шаг, ЫукпШ.

            10 миллионов лишних операций сравнения.
            Получилось дольше или быстрее ?
              Да, это сравнение было лишним. Понятно, что без сравнения цикл отработает быстрее.

              Есть варианты распараллеливания этого цикла?
              И 10 млн. это не предел, на самом деле у меня там объектов под млрд. :)
                Цитата gordey @
                Да, это сравнение было лишним. Понятно, что без сравнения цикл отработает быстрее.

                Есть варианты распараллеливания этого цикла?

                я не знаю.
                Можно поставить эксперимент и померить время выполнения
                2-х вариантов:
                1. этого
                2. заменить массивы с инкрементом индекса на указатели с инкрементом.
                3. Вот это "GetNumberOfChilds()" - исключить.
                ---
                И вообще ассемблерный листиг посмотреть.
                Сообщение отредактировано: ЫукпШ -
                  Распараллелить вряд ли получится из-за зависимости по данным - для вычисления каждого элемента нужно знать предыдущий. Однако для 10 миллионов целых чисел выполнение должно быть порядка 10 мс.
                  Это время выглядит вполне приемлемым для разовой операции.

                  Другое дело - если исходный массив постоянно меняется - в этом случае нужно думать о смене структуры данных - например, дерево Фенвика может подойти, если логарифмическое время доступа устроит (модификация будет тоже за логарифм)
                    Цитата MBo
                    Распараллелить вряд ли получится из-за зависимости по данным - для вычисления каждого элемента нужно знать предыдущий.
                    И, тем не менее, таковое всё же возможно. И даже вполне несложно. Сейчас нарисую/напишу схему. :blush:

                    Добавлено
                    1. Первым делом, вынесем=посчитаем все нужные числа в массив a[i], i=0..n. n = те самые 10 млн.
                    Грубо говоря, как-то так:
                    ExpandedWrap disabled
                      #pragma  omp parallel shared(shiftArray) reduction (+: sum) num_threads(12) // или какое-то другое число потоков
                      #pragma omp for
                          for(long i = 0; i < n; i++) shiftArray[i] = object[ i ].GetNumberOfChilds();

                    2. Сейчас=далее будет схема.
                      Хм, действительно есть параллельные алгоритмы: https://en.wikipedia.org/wiki/Prefix_sum#Parallel_algorithms

                      Но неужели затраты времени на примитивную операцию сложения существеннее доступа к памяти по куче адресов? (хотя этот доступ тоже, видимо, многоканальный)
                      Сообщение отредактировано: MBo -
                        2. Итак, мы хотим параллельно посчитать что-то вроде: a[i] = сумма всех предыдущих + сам_я.
                        ExpandedWrap disabled
                          for( int i=1; i<n; i++) a[i] += a[i-1]; // так делается

                        Прикреплённая картинка
                        Прикреплённая картинка

                        а) Разобьём все наши миллионы на столько-то потоков.
                        б) в каждый ai надо занести ВСЕХ предыдущих, но тогда будет зависимость тяжёлая. А мы посчитаем синие хвостики (см. рис), сумму оных, в какой-то отдельный массив b. Их будет n/потоков. И суммироваться будет всё это параллельно!
                        в) ну а дальше надо будет снова пробежаться s(кол-во потоков) раз, добавляя к каждому ai-му красный блок, кой посчитан на предыдущем шаге.

                        П.С. может быть, не всё понятно, но я постарался суть схемы передать. :oops:

                        Добавлено
                        Цитата MBo @
                        неужели затраты времени на примитивную операцию сложения существеннее доступа к памяти по куче адресов?
                        Тьфу, это я там немного не оттуда выдрал пример. Просто было:
                        ExpandedWrap disabled
                          const int n = 100;
                              int a[n], sum;
                              #pragma omp parallel shared(a) reduction (+: sum) num_threads(nthread)
                            {
                              #pragma omp for
                              for(long i = 0; i < n; ++i)
                              {
                                sum += a[i];
                              }
                              }
                        Виноват, малёх.

                        Добавлено
                        Цитата я
                        Их будет n/потоков.
                        Тьфу, снова немного попутал! :wall:
                        Их (элементов в массиве b) будет как раз равно количеству потоков s. А вот количество суммирований в каждом потоке будет именно равно n/s. Таким образом, мы посчитаем хвосты за время n/s. Т.е. во столько раз выиграем!
                          Предположим у нас есть N чисел, для которых нам надо посчитать кумулятивные суммы.
                          При прямом подсчёте нам понадобится N операций сложения
                          Если мы разобьём их на s частей, то накопление сумм для каждой части займёт N/s, потом в единственном потоке мы произведём суммирование накопленных сумм для групп - это s операций, и наконец параллельно откорректируем все суммы - ещё N/s операций. Итого это займёт 2*N/s + s времени. Эта величина минимальна при s = sqrt(2*N). Немного поменяв начальную разбивку, можно общую оценку уменьшить до 2*n/s + s/2, но это мало что меняет.
                          Видно, что нет смысла бить вычисление на два потока, но уже три дают экономию в 33% времени.

                          Добавлено
                          Насчёт разбивки данных ошибся, время не меняется но организовав процесс вычисления поправок можно свести время до 2*N/s + log(s), что, впрочем, при s<<N всё равно ничего не даёт.
                          Кстати, при наличии K процессорных ядер имеет смысл бить исходный массив на K+1 отрезок
                          На первом этапе считаем кумулятивные суммы для первых K участков. Для первого они же будут и окончательными.
                          На втором этапе суммируем общие суммы, чтобы получить начальные суммы для участков со второго по K+1
                          На третьем корректируем суммы для участков со 2 по K и считаем их "с нуля" для участка K+1. Можно и для остальных посчитать "с нуля", в таком случае на первом этапе можно не накапливать кумулятивные суммы

                          Второй этап можно чуточку ускорить (но, думаю, не имеет смысла - обеспечение синхронности съест весь выигрыш)
                          Пусть K = 8, и после первого этапа мы получили суммы S1, S2, S3, S4, S5, S6, S7, S8
                          1. S2 += S1; S4 += S3; S6 += S5; S8 += S7; s1 может уже начать корректировать отрезок 2 используя S1, как начальную сумму
                          2. S3 += S2; S4 += S2; S7 += S6; S8 += S6; s2 может начать корректировать отрезок 3 на S2
                          3. S5 += S4; S6 += S4; S7 += S4; S8 += S4; s3 и s4 могут начать коррекцию отрезков 4 и 5
                          4. s5, s6 и s7 могут начинать коррекцию участков 6, 7 и 8; s8 может начать вычисление сумм для участка 9
                          Можно суммировать и в другом порядке, но думаю, идея понятна.
                            Спасибо всем большое за идею распараллеливания.
                              amk, что-то я запутался в твоей методике :-? Посмотри, так ли я понял... я взял 16 цифр от 0 до 15 и разбил их на 4 "процессора":

                              ExpandedWrap disabled
                                0   1   2   3  |  4   5   6   7  |   8   9  10  11  |  12  13  14  15
                                ---------------+-----------------+------------------+----------------
                                0   1   3   6  |  4   9  15  22  |   8  17  27  38  |  12  25  39  54
                                               | 10  15  21  28  |  14  23  33  44  |  18  31  45  60
                                               |                 |  36  45  55  66  |  40  53  67  82
                                               |                 |                  |  78  91 105 120
                                ---------------+-----------------+------------------+----------------
                                Проверка:
                                ---------------+-----------------+------------------+----------------
                                0   1   3   6  | 10  15  21  28  |  36  45  55  66  |  78  91 105 120

                              Не пойму, что в лоб на одном "проце" считать = 16 тактов, что на четырех = 4 серии по 4 такта.
                              Где чего я не понимаю?
                              Сообщение отредактировано: JoeUser -
                                1. Сначала, Джо, нужно потратить 4 такта общего времени, чтобы получить сумму тех моих синих хвостов и длину красных блоков, коя у вас и вышла в: 6; 22; 38; 54.
                                2. Далее, тратим один (!!!) такт, чтобы красный блок добавить ко второму блоку, получая: 4+6; 9+6; 15+6 и 22+6. Т.е. все ваши верные суммы: 10; 15; 21; 28.
                                3. Далее, снова тратим ОДИН такт, чтобы красный блок добавить к третьему блоку, получая: 8+28; 17+28; 27+28; 38+28. Т.е. все ваши верные суммы: 36; 45-у вас опечатка; 55; 66.
                                4. Наконец, снова тратим ОДИН такт, чтобы красный блок добавить к 4-му блоку, получая: 12+66; 25+66; 39+66; 54+66. Т.е. все ваши верные суммы: 78; 91; 105; 120.
                                Итого: 4+1+1+1 = 7 тактов!!
                                  ExpandedWrap disabled
                                    #include <iostream>
                                     
                                    int numberOfObjects = 10000000;
                                    int arraySize = numberOfObjects + 1;
                                    int *object = new int[numberOfObjects];
                                    int *shiftArray = new int[arraySize];
                                    #ifdef _MSC_VER
                                    #define NOMINMAX
                                    #include <windows.h>
                                    __forceinline double time()
                                    {
                                        LARGE_INTEGER counter, frequency;
                                        QueryPerformanceCounter(&counter);
                                        QueryPerformanceFrequency(&frequency);
                                        return double(counter.QuadPart) / double(frequency.QuadPart);
                                    }
                                    #else
                                    #include <sys/time.h>
                                    inline __attribute__((always_inline)) double time()
                                    {
                                        timeval t1;
                                        gettimeofday(&t1, NULL);
                                        return t1.tv_sec + t1.tv_usec * 0.000001;
                                    }
                                    #endif
                                     
                                    void genarr()
                                    {
                                        for (int i = 0; i < numberOfObjects; i++)
                                        {
                                            object[i] = 1 + (i % 10);
                                        }
                                    }
                                     
                                    int main()
                                    {
                                        int shiftValue = 0;
                                        double t1, t2, t3;
                                        t1 = time();
                                        genarr();
                                        t2 = time();
                                        for (int i = 0; i < numberOfObjects; i++)
                                        {
                                            shiftArray[i] = shiftValue;
                                            shiftValue += object[i];
                                        }
                                        shiftArray[numberOfObjects] = shiftValue;
                                        t3 = time();
                                        delete[] shiftArray;
                                        delete[] object;
                                        std::cout << "t2=" << (t2 - t1) << "\nt3=" << (t3 - t2);
                                    }

                                  У меня на рабочем компе время плавает от 0.015, до 0.07.
                                  Это медлено?

                                  Так же замечу, при таких малых значениях, внедрение OpenMP может увеличить итоговое время расчета (особенно, если это где-то еще в выше стоящих циклах используется), так как накладные расходы высокие.

                                  Добавлено
                                  +
                                  ExpandedWrap disabled
                                    void genarr()
                                    {
                                    #pragma omp parallel for
                                        for (int i = 0; i < numberOfObjects; i++)
                                        {
                                            object[i] = 1 + (i % 10);
                                        }
                                    }

                                  Время этого кода в тех же пределах.
                                  Сообщение отредактировано: Black_Dragon -
                                    Сделал еще один тест
                                    Добавил два нолика к количеству
                                    тип заменил на char, перевел код на 64-бита.
                                    Первая часть результатов без OpenMP, вторая с ним для генерации исходных данных.
                                    Скрытый текст
                                    D:\Project\VS\Test2\x64\Release>Test2.exe
                                    t2=1.08864
                                    t3=0.842568
                                    D:\Project\VS\Test2\x64\Release>Test2.exe
                                    t2=1.11564
                                    t3=0.837306
                                    D:\Project\VS\Test2\x64\Release>Test2.exe
                                    t2=1.08041
                                    t3=0.853024
                                    D:\Project\VS\Test2\x64\Release>Test2.exe
                                    t2=1.08604
                                    t3=0.819968
                                    D:\Project\VS\Test2\x64\Release>Test2.exe
                                    t2=0.474971
                                    t3=0.844585
                                    D:\Project\VS\Test2\x64\Release>Test2.exe
                                    t2=0.485372
                                    t3=0.928686
                                    D:\Project\VS\Test2\x64\Release>Test2.exe
                                    t2=0.441639
                                    t3=0.789672
                                    D:\Project\VS\Test2\x64\Release>Test2.exe
                                    t2=0.508216
                                    t3=0.788921

                                    Вообщем, когда время расчета уже становиться большим, появляется эффект.
                                      Black_Dragon, для замеров времени лучше пользовать стандартную либу, вместо привязки к оси:
                                      ExpandedWrap disabled
                                        #include <chrono>
                                        auto start = std::chrono::high_resolution_clock::now();
                                        // ... тут помещаем замеряемый код
                                        auto stop = std::chrono::high_resolution_clock::now();
                                        std::cout << "Прошло:" << std::chrono::duration_cast<std::chrono::milliseconds>(stop - start).count() << "ms" << std::endl;
                                        JoeUser
                                        Те же цифры. :)

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

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

                                        Добавлено
                                        +
                                        Вот время работы программы, где велись геометрические расчеты и использовались разные уловки

                                        Начальное время расчета (4 минуты)
                                        00:04:36.0053614

                                        Использование хеш-сетки для исключения не нужных отрезков (4 сек)
                                        00:00:04.8520328

                                        Использование OpenMP на 12 потоков
                                        00:00:34.4000643

                                        Использование хеша + 12 потоков
                                        00:00:03.4497785
                                          Цитата Black_Dragon @
                                          JoeUser
                                          Те же цифры.

                                          Просто код поскромнее :lol:
                                          0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                          0 пользователей:


                                          Рейтинг@Mail.ru
                                          [ Script execution time: 0,0750 ]   [ 20 queries used ]   [ Generated: 19.03.24, 03:43 GMT ]