автор
Стоит ли разбивать этот массив на части и сортировать по более мелким кускам (например по 16Кб - сортируем quickSort) а затем использовать сортировку слиянием? Либо особого выигрыша здесь уже не получить, т.к. данные уже в памяти.



Если сортировать в одном потоке, то не будет вообще никакого выигрыша. Однако если распараллелить сортировку частей, а потом сливать, то ускорение будет (если компьютер с многоядерным процессором или хотя бы процессор с hyperthreading). Однако думаю части должны быть крупными, иначе потребуется много слияний. Например, если процессор 2-ядерный, то разбиваем на 2 части и делаем 1 слияние. Даёт хороший прирост скорости, но с большой оговоркой - если время сортировки частей примерно одинаково, а оно зависит от распределения данных внутри части (это я проводил эксперименты). Для борьбы с этим можно поделить массив на большее число частей, но понадобится больше слияний, то есть их тоже желательно распараллелить по потокам. Порядок слияний влияет на их общую трудоёмкость.
Вообще-то уже есть функции сортировки, распараллеленные внутри себя по этому способу - в библиотеке GCC 4.4 есть распараллеленные варианты функций std::sort, std::stable_sort и др. для C++, да и не только в GCC.
Кстати, сейчас в стандартный библиотеках компиляторов обычно применяется алгоритм не QuickSort, а IntroSort, но для него справедливы те же выводы.

Gluk (Kazan)хреново он параллелится, между нами девочками

Вообще-то я уже ответил. Можно конечно уточнять. Но раз другие не уточняют, то сам это делаю.

Алоритм QuickSort распараллеливается хорошо, хотя бы потому,что его формулировка рекурсивная. Но самостоятельная эффективная реализация алгоритма нетривиальна, и нет самысла ею заниматься, можно применить функции сортировки из стандартных библиотек - причём есть как распараллеленные внутри (тогда самому ничего делать не надо), либо взять обычную не распалаллеленную версию и распараллелить самостоятельно. Для этого массив поделить на части, сортировать их параллельно и сливать. При этом возникают проблемы оптимизации, которые я уже описал.

Также, как я написал, в нынешних стандарных библиотеках вместо QuickSort обычно используется IntroSort - эта замена сделана для борьбы со "сложным случаем" сортировки в QuickSort, когда её трудоёмкость достигает O(N*N), хотя в среднем она O (N*LOG N). Таким образом, для самостоятельного программирования QuickSort надо разбираться в предмете, но особого смыла оно не имеет. (Для примера, в MS Visual Studio 2008, в библиотеке C++ функции qsort, std::sort и std::stable_sort все реализуют алгоритм IntroSort, ими и пользоваться. Сливать части - функцией std::merge - но это только в C++).

На сколько частей разбивать.
Независимо от числа частей, в среднем трудоёмкость сортировки составит O(N*LOG N). Но это не значит, что число частей не имеет значения. Потому что надо учесть факторы:
- число частей при распараллеливании должно быть не меньше числа потоков выполнения (зависит от числа процессоров, ядер и наличия hyperthreading). Наапример, 2 ядра без hyperthreading - делаем не менее 2 потоков.
- но если сделать ровно 2 (как в описанном случае), а распределение значений не случайное, то один поток может закончить работу быстрее, чем второй, и простивать. Поэтому сделать больше - скажем, десяток. Одновременно пусть работают 2 и если один отсортирует свой отрезок, пусть начинает сортировать ещё не сортированный или сливать уже отсортированные. Очень много отрезков делать ни к чему, т.к. оптимизация от равномерной загрузки ядер будет уже небольшая.
- Порядок слияния отсортированных частей влияет на трудоёмкость слияния.
- Можно попытаться сделать оптимизацию типа "суперлинейный рост скорости". А именно, обычно рост скорости от распараллеливания - медленнее роста числа процессоров (закон Амдаля), но иногда бывает и более быстрым, чем рост числа процессоров (ядер). Это происходит, когда сортируемая часть массива полностью помещается в кеш, относящийся к процееору (ядру). То есть, ориентировочно сотни килобайт. Более мелкие куски массива уже нет смысла делать. Подробнее о "суперлинейном росте скорости" можно ппочитать в документации по организации многопоточной обработки OpenMP, но он - не свойство OpenMP, а свойство архитектуры компьютера. Библиотека OpenMP вообще удобна для распараллеливания сортировки, хотя совершенно необязательна.

Вот, написал сколько хватило терпения. Напоследок привожу фрагменты моёй программы сортировки с распараллеливанием на 2 потока функции std::stable_sort (которую легко заменить на любую другую), применяется библиотека OpenMP. Полные примеры для Visual C++ и GCC я уже привёл на форуме ixbt. Пример примитивный - в явном виде задаются 2 потока, для демонстрации идеи. Библиотека OpenMP позволяет легко задавать число потоков динамически (что и следовало бы сделать в практической программе). Но демонстрация возможностей OpenMP не являлась задачей.

Пример. Определение массива (можно заменить на любое другое):

Сортирующий фрагмент кода:

На дурацкие комментарии отвечать не буду. Нет ничего настолько простого, чтобы не нашёлся кто-нибудь, неспособный это понять. В общем, я описал распараллеливание сортировки довольно подробно. Может, кому-нибудь поможет. А если кому не поможет, то пусть это будет его проблемой.

Да, по OpenMP можно найти книжки на английском языке и много статей.

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]

maytonВ этом случае бенчмарк будет иметь еще и рекомендации по применению. Это было-бы здорово.

Я ограничился сортировкой равномерно-распределённых случайных значений, потому что этот тест хорошо показывает эффект от распараллеливания. Для других распределений на результат будет влиять и поведение самого алгоритма.
Значит, сейчас быстродействие по-видимому близко к оптимальному, потому что результат мало отличается от внутренне распараллеленной функции __gnu_parallel::stable_sort. Небольшое отставание я думаю (хотя проверию) объясняется не небольшой неоптимальностью моего способа, а тем, что производится анализ возможности распараллелить std::sort в каждом из потоков (с заменой на __gnu_parallel::stable_sort), но оно не имеет смысла, т.к. есть только 2 ядра.

Однако если бы распределение было не равномерным, а одним из предлагаемых вами, то быстродействие моего способа стало бы не оптимальным, из-за отсутствия балансировки потоков.
Действительно, скорость сортировки в какой-то степени зависит от распределения. Если оно неодинаковое в половинах массива, то скорость сортировки половин будет неодинаковой, и один поток будет простаивать.
Для борьбы с этим я придумал способ - делить на большее число подмассивов. Скажем, на 10 вместо 2 итд (в зависимости от числа ядер). Тогда если поток закончит сортировать один отрезок, он может приняться за сортировку ещё одного. Кстати, OpenMP имеет простое средство создания такой очереди задач на подмассивов для потоков. Ещё надо бы добавить автоматическое определение числа потоков по числу процессоров.
То и другое сделать легко. Как найду время, то модифицирую свой пример, тогда он и станет вполне практичной программой сортировки. А пока что он демонстрирует идею распараллеливания сортировки.