Форум на Исходниках.RU

Ускорить процесс подготовки "Карты смещений"

JoeUser — Thu, 28 May 2020 10:27:04 +0000

JoeUser:

Цитата Black_Dragon @ 28.05.20, 09:08

JoeUser
Те же цифры.

Просто код поскромнее :lol:

Ускорить процесс подготовки "Карты смещений"

Black_Dragon — Thu, 28 May 2020 09:08:37 +0000

Black_Dragon: JoeUser
Те же цифры. :)

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

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

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

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

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

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

Использование хеша + 12 потоков
00:00:03.4497785

Ускорить процесс подготовки "Карты смещений"

JoeUser — Thu, 28 May 2020 08:16:42 +0000

JoeUser: Black_Dragon, для замеров времени лучше пользовать стандартную либу, вместо привязки к оси:

#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;

Ускорить процесс подготовки "Карты смещений"

Black_Dragon — Thu, 28 May 2020 06:05:17 +0000

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 — Thu, 28 May 2020 04:46:05 +0000

Black_Dragon:

#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 может увеличить итоговое время расчета (особенно, если это где-то еще в выше стоящих циклах используется), так как накладные расходы высокие.

Добавлено 28.05.20, 04:59
+

void genarr()

{

#pragma omp parallel for

for (int i = 0; i < numberOfObjects; i++)

{

object[i] = 1 + (i % 10);

}

Время этого кода в тех же пределах.

Ускорить процесс подготовки "Карты смещений"

Славян — Sun, 15 Mar 2020 04:14:21 +0000

Славян: 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 тактов!!

Ускорить процесс подготовки "Карты смещений"

JoeUser — Sat, 14 Mar 2020 22:28:07 +0000

JoeUser: amk, что-то я запутался в твоей методике :-? Посмотри, так ли я понял... я взял 16 цифр от 0 до 15 и разбил их на 4 "процессора":

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 такта.
Где чего я не понимаю?

Ускорить процесс подготовки "Карты смещений"

gordey — Sat, 14 Mar 2020 13:22:00 +0000

gordey: Спасибо всем большое за идею распараллеливания.

Ускорить процесс подготовки "Карты смещений"

amk — Sat, 14 Mar 2020 11:19:51 +0000

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

Добавлено 14.03.20, 11:46
Насчёт разбивки данных ошибся, время не меняется но организовав процесс вычисления поправок можно свести время до 2*N/s + log(s), что, впрочем, при s< Кстати, при наличии 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
Можно суммировать и в другом порядке, но думаю, идея понятна.

Ускорить процесс подготовки "Карты смещений"

Славян — Sat, 14 Mar 2020 09:27:39 +0000

Славян: 2. Итак, мы хотим параллельно посчитать что-то вроде: a[i] = сумма всех предыдущих + сам_я.

for( int i=1; i<n; i++) a[i] += a[i-1]; // так делается

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

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

Добавлено 14.03.20, 09:30

Цитата MBo @ 14.03.20, 09:09

неужели затраты времени на примитивную операцию сложения существеннее доступа к памяти по куче адресов?

Тьфу, это я там немного не оттуда выдрал пример. Просто было:

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];

}

Виноват, малёх.

Добавлено 14.03.20, 09:35

Цитата я

Их будет n/потоков.

Тьфу, снова немного попутал! :wall:
Их (элементов в массиве b) будет как раз равно количеству потоков s. А вот количество суммирований в каждом потоке будет именно равно n/s. Таким образом, мы посчитаем хвосты за время n/s. Т.е. во столько раз выиграем!

Ускорить процесс подготовки "Карты смещений"

MBo — Sat, 14 Mar 2020 09:09:00 +0000

MBo: Хм, действительно есть параллельные алгоритмы: https://en.wikipedia.org/wiki/Prefix_sum#Parallel_algorithms

Но неужели затраты времени на примитивную операцию сложения существеннее доступа к памяти по куче адресов? (хотя этот доступ тоже, видимо, многоканальный)

Ускорить процесс подготовки "Карты смещений"

Славян — Sat, 14 Mar 2020 08:43:21 +0000

Славян:

Цитата MBo

Распараллелить вряд ли получится из-за зависимости по данным - для вычисления каждого элемента нужно знать предыдущий.

И, тем не менее, таковое всё же возможно. И даже вполне несложно. Сейчас нарисую/напишу схему. :blush:

Добавлено 14.03.20, 09:02
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. Сейчас=далее будет схема.

Ускорить процесс подготовки "Карты смещений"

MBo — Sat, 14 Mar 2020 07:31:48 +0000

MBo: Распараллелить вряд ли получится из-за зависимости по данным - для вычисления каждого элемента нужно знать предыдущий. Однако для 10 миллионов целых чисел выполнение должно быть порядка 10 мс.
Это время выглядит вполне приемлемым для разовой операции.

Другое дело - если исходный массив постоянно меняется - в этом случае нужно думать о смене структуры данных - например, дерево Фенвика может подойти, если логарифмическое время доступа устроит (модификация будет тоже за логарифм)

Ускорить процесс подготовки "Карты смещений"

ЫукпШ — Fri, 13 Mar 2020 20:41:14 +0000

ЫукпШ:

Цитата gordey @ 13.03.20, 19:49

Да, это сравнение было лишним. Понятно, что без сравнения цикл отработает быстрее.

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

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

Ускорить процесс подготовки "Карты смещений"

gordey — Fri, 13 Mar 2020 19:49:04 +0000

gordey: Да, это сравнение было лишним. Понятно, что без сравнения цикл отработает быстрее.

Есть варианты распараллеливания этого цикла?
И 10 млн. это не предел, на самом деле у меня там объектов под млрд. :)

Ускорить процесс подготовки "Карты смещений"

ЫукпШ — Fri, 13 Mar 2020 19:43:10 +0000

ЫукпШ:

Цитата Славян @ 13.03.20, 19:03

Это ну совершенно несущественный шаг, ЫукпШ.

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

Ускорить процесс подготовки "Карты смещений"

gordey — Fri, 13 Mar 2020 19:06:34 +0000

gordey: Тем более, что в оригинале у меня именно так и написано ;)

Ускорить процесс подготовки "Карты смещений"

Славян — Fri, 13 Mar 2020 19:03:40 +0000

Славян: Это ну совершенно несущественный шаг, ЫукпШ.

Ускорить процесс подготовки "Карты смещений"

ЫукпШ — Fri, 13 Mar 2020 18:02:45 +0000

ЫукпШ:

Цитата gordey @ 13.03.20, 17:29

Помогите, пожалуйста, ускорить процесс заполнения массива

Попробуй для начала так:

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;

Ускорить процесс подготовки "Карты смещений"

gordey — Fri, 13 Mar 2020 17:29:05 +0000

gordey: Привет.
Есть, например, 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;

Спасибо!