![>](style_images/1/nav_m.gif)
![]() |
Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
|
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.135.188.58] |
![]() |
|
Страницы: (2) [1] 2 все ( Перейти к последнему сообщению ) |
Сообщ.
#1
,
|
|
|
Привет.
Есть, например, 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; Спасибо! |
Сообщ.
#2
,
|
|
|
Цитата gordey @ Помогите, пожалуйста, ускорить процесс заполнения массива Попробуй для начала так: ![]() ![]() 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; |
Сообщ.
#3
,
|
|
|
Это ну совершенно несущественный шаг, ЫукпШ.
|
Сообщ.
#4
,
|
|
|
Тем более, что в оригинале у меня именно так и написано
![]() |
Сообщ.
#5
,
|
|
|
Цитата Славян @ Это ну совершенно несущественный шаг, ЫукпШ. 10 миллионов лишних операций сравнения. Получилось дольше или быстрее ? |
Сообщ.
#6
,
|
|
|
Да, это сравнение было лишним. Понятно, что без сравнения цикл отработает быстрее.
Есть варианты распараллеливания этого цикла? И 10 млн. это не предел, на самом деле у меня там объектов под млрд. ![]() |
Сообщ.
#7
,
|
|
|
Цитата gordey @ Да, это сравнение было лишним. Понятно, что без сравнения цикл отработает быстрее. Есть варианты распараллеливания этого цикла? я не знаю. Можно поставить эксперимент и померить время выполнения 2-х вариантов: 1. этого 2. заменить массивы с инкрементом индекса на указатели с инкрементом. 3. Вот это "GetNumberOfChilds()" - исключить. --- И вообще ассемблерный листиг посмотреть. |
Сообщ.
#8
,
|
|
|
Распараллелить вряд ли получится из-за зависимости по данным - для вычисления каждого элемента нужно знать предыдущий. Однако для 10 миллионов целых чисел выполнение должно быть порядка 10 мс.
Это время выглядит вполне приемлемым для разовой операции. Другое дело - если исходный массив постоянно меняется - в этом случае нужно думать о смене структуры данных - например, дерево Фенвика может подойти, если логарифмическое время доступа устроит (модификация будет тоже за логарифм) |
Сообщ.
#9
,
|
|
|
Цитата MBo И, тем не менее, таковое всё же возможно. И даже вполне несложно. Сейчас нарисую/напишу схему. Распараллелить вряд ли получится из-за зависимости по данным - для вычисления каждого элемента нужно знать предыдущий. ![]() Добавлено 1. Первым делом, вынесем=посчитаем все нужные числа в массив a[i], i=0..n. n = те самые 10 млн. Грубо говоря, как-то так: ![]() ![]() #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. Сейчас=далее будет схема. |
Сообщ.
#10
,
|
|
|
Хм, действительно есть параллельные алгоритмы: https://en.wikipedia.org/wiki/Prefix_sum#Parallel_algorithms
Но неужели затраты времени на примитивную операцию сложения существеннее доступа к памяти по куче адресов? (хотя этот доступ тоже, видимо, многоканальный) |
Сообщ.
#11
,
|
|
|
2. Итак, мы хотим параллельно посчитать что-то вроде: a[i] = сумма всех предыдущих + сам_я.
![]() ![]() for( int i=1; i<n; i++) a[i] += a[i-1]; // так делается Прикреплённая картинка
а) Разобьём все наши миллионы на столько-то потоков. б) в каждый ai надо занести ВСЕХ предыдущих, но тогда будет зависимость тяжёлая. А мы посчитаем синие хвостики (см. рис), сумму оных, в какой-то отдельный массив b. Их будет n/потоков. И суммироваться будет всё это параллельно! в) ну а дальше надо будет снова пробежаться s(кол-во потоков) раз, добавляя к каждому ai-му красный блок, кой посчитан на предыдущем шаге. П.С. может быть, не всё понятно, но я постарался суть схемы передать. ![]() Добавлено Цитата MBo @ Тьфу, это я там немного не оттуда выдрал пример. Просто было:неужели затраты времени на примитивную операцию сложения существеннее доступа к памяти по куче адресов? ![]() ![]() 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/потоков. ![]() Их (элементов в массиве b) будет как раз равно количеству потоков s. А вот количество суммирований в каждом потоке будет именно равно n/s. Таким образом, мы посчитаем хвосты за время n/s. Т.е. во столько раз выиграем! |
Сообщ.
#12
,
|
|
|
Предположим у нас есть 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 Можно суммировать и в другом порядке, но думаю, идея понятна. |
Сообщ.
#13
,
|
|
|
Спасибо всем большое за идею распараллеливания.
|
Сообщ.
#14
,
|
|
|
amk, что-то я запутался в твоей методике
![]() ![]() ![]() 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 такта. Где чего я не понимаю? |
Сообщ.
#15
,
|
|
|
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 тактов!! |