LINUX.ORG.RU

[C++/OpenMP] Распараллеливание поиска значения в векторе.


0

1

Задача состоит в поиске в очень большом векторе элемента, удовлетворяющего некоторым условиям (проверка достаточно затратна по времени). C OpenMP раньше дела не имел. Реализовал для примера поиск минимального элемента в массиве. Каждый из потоков ищет минимальный элемент в выделенной ему части массива, затем выбирается минимальный элемент из минимальных элементов для каждой части массива.

Компилирую и запускаю:

$ g++ -fopenmp main.cpp

$ ./a.out 1

Time: 1.92

$ ./a.out 2

Time: 2.02

$ ./a.out 3

Time: 2

Почему время поиска не меняется в зависимости от числа потоков? (в системе 2 ядра, top показывает правильное число потоков).

main.cpp:

#include <omp.h>
#include <vector>
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <limits>

typedef unsigned int Element;
typedef std::vector<Element> Array;

unsigned int getMinElement(const Array& array, int threadsCount) {
	omp_set_num_threads(threadsCount);
	Array minElements(
		threadsCount,
		std::numeric_limits<Element>::max()
	);
	int size(array.size());
	#pragma omp parallel for schedule(static)
	for (int i = 0; i < size; ++i) {
		int threadNum(omp_get_thread_num());
		if (array[i] <= minElements[threadNum])
			minElements[threadNum] = array[i];
	}
	Element minElement(minElements[0]);
	for (int i = 1; i < minElements.size(); ++i)
		if (minElements[i] < minElement)
			minElement = minElements[i];
	return minElement;
}

int main(int argc, char** argv) {
	Array a;

	for (unsigned int i = 0; i < 100000000; ++i)
		a.push_back(rand());
	
	if (argc < 2)
		exit(1);

	clock_t startTime(clock());
	unsigned int minElement(getMinElement(a, atoi(argv[1])));
	clock_t arrayProcessTime(clock() - startTime);

	std::cout << " Time: "
		<< double(arrayProcessTime) / CLOCKS_PER_SEC << std::endl;

	return 0;
}


> for (int i = 0; i < size; ++i)

You did it wrong. Те каждый поток бегает по _всему_ массиву, сделайте так шоб бегал по кусочкам.

nikitos ★★ ()
Ответ на: комментарий от nikitos

You did it wrong. Те каждый поток бегает по _всему_ массиву, сделайте так шоб бегал по кусочкам.

Создаётся впечатление, что вы не правы:

20a21,22
>               #pragma omp critical
>               std::cout << i << " " << threadNum << std::endl;
34c36
<       for (unsigned int i = 0; i < 100000000; ++i)
---
>       for (unsigned int i = 0; i < 10; ++i)
5 1
6 1
7 1
8 1
9 1
0 0
1 0
2 0
3 0
4 0
 Time: 0
SSN ()
Ответ на: комментарий от SSN

Ну и по мелочам:

1) if (array[i] < minElements[threadNum]), 2) size_t std::vector<T>::size();

nikitos ★★ ()
Ответ на: комментарий от nikitos

Насколько мне помнится, OpenMP как раз и делалось что не РУБИТЬ ЦИКЛ НА КУСОЧКИ РУКАМИ. Каждый тред берет тока то что ему нужно, так что Вы тут не правы однозначно.

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

Ну и да, погуглите, там наверное моно как то заюзать reduction вместо того что бы связываться с номером треда - но тут я не уверен, OpenMP не копал;-)

AIv ★★★★★ ()

угу, выделение памяти съедает 90% времени.

попробуй увеличит количество итераций раз в 1000, и в цикле просто числа сравнивать (складывать/делить), и понаблюдать за скоростью обработки при одном и двух тредах.

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

mrs ()
Ответ на: комментарий от mrs

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

Уменьшается эффективный объем кэша в пересчете на активное ядро

unanimous ★★★★★ ()
Ответ на: комментарий от unanimous

возможно... я просто гонял тесты на гостевой операционке, которая юзает все ядра CPU, разделяя его с основной ОС.

mrs ()
Ответ на: комментарий от mrs

ВРемя выпонения это max(t_calc,t_load) где t_calc - время выолнеия операций вычислителем, t_load - время загрузки/выгрузки данных. Как только в t_load уперся - никакого ускорения получить уже нельзя, можно только замедлится за счет синхронизации между потоками и пр.

AIv ★★★★★ ()
Ответ на: комментарий от AIv

ну эт понятно, у меня просто был довольно ощутимый регресс при 4х потоках, по сравнению с тремя.

а вот на счет разделения цикла по потокам, в исходнике выше вроде всё верно: [code=c]#pragma omp parallel for schedule(static)[/code]

должен разделить весь цикл на threadsCount серий, и каждую серию сопоставить одному потоку.

mrs ()

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

Reset ★★★★★ ()
Ответ на: комментарий от PayableOnDeath

Что за бред? Как оно написано так и будет работать, в данном случае выполняться будет на всех ядрах. Но задача слишком простая да еще и данные в кеш не влазят, поэтому ускорения никакого не будет. По этим причинам не параллелится blas level 1, практически не параллелится blas level 2, но отлично параллелилтся blas level 3 (в блочном варианте, ессесно).

Reset ★★★★★ ()

1) Номер нити лучше получать вне цикла:

#pragma omp parallel
{
int threadNum(omp_get_thread_num());
#pragma omp for schedule(static)
for (int i = 0; i < size; ++i) {
if (array[i] <= minElements[threadNum])
minElements[threadNum] = array[i];
}
}

2) Функция clock получает CPU-time, т.е. время работы всех нитей.

double startTime(omp_get_wtime());

Итого:


this@this-desktop:/tmp$ ./a.out 1
Time: 0.994852
this@this-desktop:/tmp$ ./a.out 2
Time: 0.504674
this@this-desktop:/tmp$ ./a.out 4
Time: 0.255984

YesSSS ★★★ ()
Ответ на: комментарий от YesSSS

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

g++ -fopenmp -O2 abc.cpp
./a.out 1
Time: 0.15357
./a.out 2
Time: 0.110774

YesSSS ★★★ ()
Ответ на: комментарий от YesSSS

> int threadNum(omp_get_thread_num());

#pragma omp for schedule(static)
for (int i = 0; i < size; ++i) {

как это понимать?

потоки ведь по идее запускаются начиная с цикла, и после прагмы.

mrs ()
Ответ на: комментарий от YesSSS

omp_get_thread_num() в цикле вызывать конечно слишком жирно, но перед циклом - бессмысленно, по-моему.

mrs ()
Ответ на: комментарий от mrs

В моем коде 2 прагмы, первая «omp parallel» порождает нити(после нее весь код исполняется всеми нитями), вторая «omp for» загоняет эти нити в параллельный цикл, afaik так вполне можно. ТС использовал прагму, которая делает оба действия сразу.

#pragma omp parallel
{
int threadNum(omp_get_thread_num());
std::cout << threadNum << std::endl;
#pragma omp for schedule(static)
for (int i = 0; i < size; ++i) {
if (array[i] <= minElements[threadNum])
minElements[threadNum] = array[i];
}
}

итого:

./a.out 4
20
1
3

Time: 0.128393

YesSSS ★★★ ()
Ответ на: комментарий от nikitos

Опубликуйте пожалуйста исходник на какой-нибудь pastebin (если вы его меняли).

В сообщении выше есть вывод diff относительно исходника в первом сообщении

SSN ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.