Gluk (Kazan)На 2 вообще понту нет (особенно ядрах)
Есть понт даже и на двух. Далее привожу результаты тестов.
maytonДумаю, что распараллелить всё-таки можно, но насколько будет это эффективно? Если прирост будет порядка 10-15% то не стоит связываться. В любом случае, нам нужны цифры.
Я на это тоже косвенно ответил, сославшись на свой программный пример в форуме ixbt (где я Partisan, здесь ещё добавил M потому что забыл свой пароль). Там я привёл полные исходные коды своего программного примера распараллеливания сортировки на 2 потока (потому что был 2-ядерный процессор Athlon X2 5600+, модель с кешем 2x1МБ), и ускорение получалось почти в 2 раза. Привёл варианты программы для Linux и Windows, причём ввиду переносимости библиотеки OpenMP код, нужный для распараллеливания, оказался одинаковым. Те же программы на 1-ядерном процессоре, но с hyperthreading, дали прирост в 30%. Сортировался массив равонмерно распределённых случайных чисел в несколько мегабайт. Диапазон значений чисел был большим - а то при наличии большого числа повторряющихся значений у многих алгоритмов работа ускоряется (за счёт меньшего числа перестановок элементов), что искажает результат.
Ещё сослался на закон Амдаля (Amdahl law), говорящий, что при распараллеливании рост скорости несколько меньше, чем рост числа процессоров (поскольку часть вычислений остаётся нераспараллелленной). Но для сортировки результат и должен быть хорошим.
Сейчас приведу модифицированный вариант моей тестовой программы для Linux, в котором дополнительно испытываются распараллеленные версии функций библиотеки STL (parallel mode STL), появившиеся в GCC 4.4 (который входит в дистрибутив Fedora 11). В примере использовалась такая функция __gnu::parallel::stable_sort.
Кратко:
- для массива в 100 МБ (25 миллионов целых чисел) моё распаларелливание для std::stable_sort дало прирост всего 1,5 раза. Надо разбираться, почему так мало. (Предупреждение: при подозрительно маленьком приросте надо изучить, нет ли явления "ложного распараллеливания". Но не уверен, что это оно). При уменьшении размера массива результат улучшался.
- внутренне распараллеленный вариант этой функции __gcc_parallel::stable_sort был на 1-8% быстрее, чем мой, что непринципиально (какая-то мелкая оптимизация).
- чтоб распараллеливаение в __gnu_parallel::stable_sort и подобных работало, надо добавить опеределение #define _GLIBCXX_PARALLEL 1 в программу или ключ
строки компиляции -D_GLIBCXX_PARALLEL (согласно документации. Оказалось, что при этом std::sort ускоряется в той же степени, то есть рассматривается как __gnu_parallel::stable_sort,
о чём в документации по "параллельному режиму STL" не сказано (но она скудная).
Результаты (сортировка 25 миллионов целых чисел, в секундах, среднее из 10 испытаний). Процессор Athlon X2 6000+ модель с кешем 2x1МБ:
1) c использованием -D_GLIBCXX_PARALLEL
- std::stable_sort - 2,63
- моё распараллеливание std::stable_sort на 2 потока - 2,88
- __gnu_parallel::stable_sort - 2,65
Повторяю: std::sort тут втихомолку распараллелилось, сведясь к __gnu_parallel::stable_sort,
что видно из:
2) исключаем из строки компиляции ключ -D_GLIBCXX_PARALLEL
- std::stable_sort - 4,11
- моё распараллеливание sta_stable_sort - 2,67
- __gnu_parallel::stable_sort - 2,63
Вот текст программы. Командная строка компиляции приведена в нём. Ключ -march=... требуется для параллельного режима STL, так же как библиотека OpenMP. У кого старый GCC, может исключить из примера 3-й тест (с __gnu_parallel::stable_sort) и
строку #include <parallel/algorithm>
[src]
/**
* OMP_SORT_EX
*
* версия 1.4 добавлен тест функций __gnu_parallel::*
* Компиляция:
* g++ -fopenmp -O2 omp_sort_ex.cpp -o omp_sort_ex -lgomp
*
* Выполнение:
* ./omp_sort_ex [число циклов тестирования]
*
* версия 1.3
*
* - добавлено испытание параллельной версии
* функции сортировки (требуется GCC 4.4).
* - сообщения переведены на русский язык
* - название программы изменено с omp_sort на opm_sort_ex.
* Компиляция:
* g++ -fopenmp -O2 -march=native -D_GLIBCXX_PARALLEL omp_sort_ex.cpp -o omp_sort_ex -lgomp
*
* Проверено в Fedora 11, 64-битной.
*
* версия 1.2
*
* - добавлено выполнение в цикле
*
* версия 1.1
*
* - используется std::stable_sort вместо std::sort
*
* Демонстрация многопоточной сортировки.
* Требуется компилятор с поддержкой OpenMP (http://www.openmp.org),
* например GCC версии 4.2.1 и выше (для RedHat - от 4.1.1).
* Проверено в CentOS 5.0 386 с GCC 4.1.1.
*
* Компиляция:
* g++ -fopenmp -O2 omp_sort.cpp -o omp_sort -lgomp
*
* Здесь ключ -O2 (оптимизация) не обязателен, но значительно увеличивает скорость теста.
* Добавить другие необязательные ключи по вкусу.
* Ключ -lgomp обязателен только при использовании библиотеки libgomp,
* то есть, если в программе используются функции OpenMP,
* а не только директивы OpenMP (многопоточность можно создать одними директивами).
*
* Библиотека libgomp - в RedHat имеет свой RPM пакет.
* Искать libgomp надо в /usr/lib.
*
* Вызов:
* ./opm_sort [100]
* где необязательный параметр - число повторений
* (выполнение в цикле - чтобы проверить правильность
* общего показываемого времени вручную и для устреднения результатов,
* а то они сильно колеблются).
*
*/
#include <omp.h>
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <time.h>
#include <sys/time.h>
#include <algorithm>
#include <parallel/algorithm>
#define VERSION_LABEL "v.1.4"
#define N 25000000L //размер сортируемого массива
#define RANGE 100000000 //диапазон изменения случ. чисел
#define TESTS 10 //количество циклов тестов
long values [N];//массив для сортировки
long randoms [N];//заполняем случайными числами один раз,а потом копируем в values
//Заполнить массив случайными числами от 0 до range-1.
//Не переносимо в Visual Studio, поскольку там RAND_MAX маленькое (32767),
//в то время как для GCC оно вполне приличное (2147483647):
void fillRandomArray (long* arr, int arrSize, int range)
{
srand (time (0));
for (int i = 0; i < arrSize; i ++)
{
arr [i] = (long) ((double)rand () / (double)RAND_MAX * range);
}
}
//Показать, какова упорядоченность массива. Вызывается до и после сортировки
void putOrderInfo (long* arr, int arrSize)
{ //сколько элементов:
int lesser = 0; //...меньше предыдущего
int equals = 0; //...равных предыдыдущему
int greather = 0; //...больше предыдущего
int ordered = 0; //...уже упорядоченных
long previousValue = arr [0];
for (int i = 1; i < arrSize; i ++)
{
long currentValue = arr [i];
if (currentValue > previousValue) greather ++;
else if (currentValue < previousValue) lesser ++;
else equals ++;
previousValue = currentValue;
}
ordered = arrSize - lesser;
printf ("меньше предыдущего элемента: %d равных предыдущему: %d больше предыдущего: %d\n",
lesser, equals, greather);
printf ("...всего упорядоченных элементов: %d\n", ordered);
}
//получить число секунд из структуры, содержащей секунды и микросекунды:
double getSec (struct timeval* timeVal)
{
return (double) timeVal->tv_sec + 0.000001 * timeVal->tv_usec;
}
//Вычесть значение времени y из x (где x > y). Результат - в result
//(заимствована из документации к библиотеке GCC, см. описание struct timeval)
int timeval_subtract (struct timeval* result, struct timeval* x, struct timeval* y)
{
/* Perform the carry for the later subtraction by updating y. */
if (x->tv_usec < y->tv_usec) {
int nsec = (y->tv_usec - x->tv_usec) / 1000000 + 1;
y->tv_usec -= 1000000 * nsec;
y->tv_sec += nsec;
}
if (x->tv_usec - y->tv_usec > 1000000) {
int nsec = (x->tv_usec - y->tv_usec) / 1000000;
y->tv_usec += 1000000 * nsec;
y->tv_sec -= nsec;
}
/* Compute the time remaining to wait.
tv_usec is certainly positive. */
result->tv_sec = x->tv_sec - y->tv_sec;
result->tv_usec = x->tv_usec - y->tv_usec;
/* Return 1 if result is negative. */
return x->tv_sec < y->tv_sec;
}
int main (int ac, char* av[])
{
printf ("Демонстрация распараллеленной сортировки, %s\n", VERSION_LABEL);
//считаем время - во-первых, общее (по часам):
struct timeval start, end, span;
//во-вторых, время CPU:
clock_t startCPU, endCPU;
double allTestsTime [3] = {0, 0, 0};
double allTestsCPUTime [3] = {0, 0, 0};
int nTests = TESTS;
if (ac > 1)
{
nTests = atoi (av [1]);
if (errno || nTests <= 0)
{
printf ("Задано неправильное число циклов выполнения теста: %s\n", av [1]);
return 1;
}
}
printf ("Формат:\nomp_sort_ex [циклов, по умолчанию=%d]\n", TESTS);
//Узнать "число процессоров". Ядро тоже считается за процессор,
//а если есть поддержка Hyperthreading,то за несколько.
printf ("Число логических процессоров OpenMP:%d\n", omp_get_num_procs());
fillRandomArray (randoms, N, RANGE);
for (int i = 0; i < nTests; i ++)
{
printf ("**** %d из %d ****\n", i + 1, nTests);
//1. Обычная сортировка
printf ("Тест 1 - простое применение std::stable_sort для %d элементов\n", N);
std::copy (randoms, randoms + N, values);
putOrderInfo (values, N);
//узнать текущее время:
int error = gettimeofday (&start, NULL);//ошибки игнорируем
startCPU = clock ();//ещё измеряем время CPU
std::stable_sort (values, values + N);//сама сортировка
endCPU = clock ();
error = gettimeofday (&end, NULL);
error = timeval_subtract (&span, &end, &start);
double totalTime = getSec (&span);
double totalCPUTime = ((double) (endCPU - startCPU)) / CLOCKS_PER_SEC;
putOrderInfo (values, N);//проверим, как отсортировалось
//время сортировки - общее и процессорное:
printf ("время сортировки, сек: всего %12.3f процессорное %12.3f\n", totalTime, totalCPUTime);
allTestsTime [0] += totalTime;
allTestsCPUTime [0] += totalCPUTime;
//2. Сортировка в 2 потоках со слиянием результатов:
printf ("Тест 2 - 2-поточное выполнение std::stable_sort с последующим слиянием функцией std::inplace_merge\n");
std::copy (randoms, randoms + N, values);
putOrderInfo (values, N);
error = gettimeofday (&start, NULL);//узнать текущее время
startCPU = clock ();
int n2 = N / 2; //индекс для делёжки массива примерно пополам
#pragma omp parallel shared (values, n2) num_threads (2)
{
#pragma omp sections
{ //сортировка половин массива в разных потоках:
#pragma omp section
{
std::stable_sort (values, values + n2);
}
#pragma omp section
{
std::stable_sort (values + n2, values + N);
}
}
}
std::inplace_merge (values, values + n2, values + N);//сливаем половины
endCPU = clock ();
error = gettimeofday (&end, NULL);
error = timeval_subtract (&span, &end, &start);
totalTime = getSec (&span);
totalCPUTime = ((double) (endCPU - startCPU)) / CLOCKS_PER_SEC;
allTestsTime [1] += totalTime;
allTestsCPUTime [1] += totalCPUTime;
putOrderInfo (values, N);
printf ("время 2-поточной сортировки, сек: всего %12.3f процессорное %12.3f\n", totalTime, totalCPUTime);
//1. Сортировка параллелизованной функцией (GCC 4.4)
printf ("Тест 3 - параллелизованная функция __gnu_parallel::stable_sort для %d элементов\n", N);
std::copy (randoms, randoms + N, values);
putOrderInfo (values, N);
//узнать текущее время:
error = gettimeofday (&start, NULL);//ошибки игнорируем
startCPU = clock ();//ещё измеряем время CPU
__gnu_parallel::stable_sort (values, values + N);//сама сортировка
endCPU = clock ();
error = gettimeofday (&end, NULL);
error = timeval_subtract (&span, &end, &start);
totalTime = getSec (&span);
totalCPUTime = ((double) (endCPU - startCPU)) / CLOCKS_PER_SEC;
putOrderInfo (values, N);//проверим, как отсортировалось
//время сортировки - общее и процессорное:
printf ("время сортировки, сек: всего %12.3f процессорное %12.3f\n", totalTime, totalCPUTime);
allTestsTime [2] += totalTime;
allTestsCPUTime [2] += totalCPUTime;
}
double sumTime = 0;
double sumCPU = 0;
printf ("------------ Результат ----------------\n");
for (int i = 1; i <= 3; i ++)
{
double testTime = allTestsTime [i-1];
double testCPU = allTestsCPUTime [i-1];
sumTime += testTime;
sumCPU += testCPU;
printf ("Время теста номер %d, сек: %g (процессорное: %g)\nСреднее время: %g (процессорное: %g)\n",
i, testTime, testCPU, testTime / nTests, testCPU /nTests);
}
printf ("Суммарное время тестов, сек: %g (процессорное: %g)\nСреднее время, сек: %g (процессорное: %g)\n",
sumTime, sumCPU, sumTime / nTests, sumCPU /nTests);
return 0;
}
/SRC]
