Monthly Archives: Февраль 2012

ParallelSort: Tier-0 VirtualBox

Довольно интересно посмотреть на эффективность виртуальной машины в самом, пожалуй, неудачном для неё случае: когда «бутылочным горлышком» оказывается производительность подсистемы памяти (что как раз характерно для сортировок). Я провёл тестирование tier-0 на Oracle VM VirtualBox 4.1.6 r74713 с установленной на ней Windows XP SP3 (32-битная), использующей 2Гб RAM и 2 ядра ЦП хост-машины «Deneb». Результаты тестирования показывают относительно неплохую производительность порядка 60% — 95% от скорости на хост-машине. Тем не менее, не следует проявлять излишний оптимизм касательно производительности виртуальных машин и доверять заверениям вроде «почти без потерь» или «95% от ОС хоста».

Далее: tier-1 VirtualBox.

Реклама

ParallelSort: Tier-1a Bitonic

Битоническая сортировка является самой популярной сортировкой на основе сортирующих сетей. Исходный код однопоточного нерекурсивного варианта. Тип Index является синонимом библиотечного типа std::ptrdiff_t и используется для представления индексов и размеров массивов. Если присмотреться к коду, то можно заметить, что а) всего производится O(N (log N)2) сравнений и их количество зависит только от N, а не от содержимого (от него уже зависит количество обменов); б) итерации внутренних циклов (по k и p) независимы друг от друга и могут выполняться параллельно. Благодаря указанным свойствам битоническая сортировка может быть реализована аппаратно (для фиксированного N) в виде сети компараторов, может эффективно выполняться параллельно на устройствах с высокой степенью параллелизма, например, графических процессорах.

Для распараллеливания битонической сортировки на ЦП было применено расширение языка C OpenMP. MSVC поддерживает OpenMP 2.0. При использовании OpenMP низкоуровневым управлением потоками исполнения занимается компилятор, программист же размечает исходный код директивами OpenMP, основанными на директиве препроцессора pragma. Это весьма удобно, пока код укладывается в ограничения OpenMP, например, если достаточно параллельного исполнения итераций цикла for. Последнее делается следующим образом:

#pragma omp parallel for
for (SignedIntegerType i = i0; i < i1; i += di)
  // code

Ограничения, накладываемые директивой parallel for:

  • тип переменной-счётчика должен быть целым со знаком;
  • количество итераций должно быть известно и фиксировано на момент входа в цикл;
  • инкремент счётчика должен выполняться простой формулой (удалить или добавить константу);
  • тело цикла не должно содержать break или выход из цикла по goto.

Так как ядер в современных массовых ЦП относительно немного, то решено сделать ветвление, которое распараллеливает либо цикл по k, либо цикл по p: исходный код и результаты тестирования. К сожалению, реальная эффективность распараллеливания оказалась довольно низкой, видимо, из-за большого количества промахов кэшей (в пользу этого говорит и то, что оценка parallelism на основе congestion довольно хорошо описывает реальную эффективность параллельной версии). В случае использования битонической сортировки на ГП указанный фактор уже не должен оказывать заметного влияния.

Далее: tier-1b bucket.

ParallelSort: Tier-0

Итак, результаты стандартных алгоритмов. Heap sort реализован как

template <class RanIt>  // RanIt == Random Iterator
void heapSort (RanIt begin, RanIt end)
{
  std::make_heap (begin, end);
  std::sort_heap (begin, end);
}

В среднем/худшем случае std::stable_sort оказалась лишь немного хуже std::sort. Последняя обычно является «прокаченным» вариантом introsort с выборкой (вероятной) медианы в качестве опорного элемента и переключением на сортировку вставками при обработке небольших диапазонов, и с ней действительно сложно соревноваться. Высокое качество работы std::sort демонстрируют низкие показатели congestion (соответственно, высокий parallelism). У std::stable_sort они существенно хуже и ещё хуже у пирамидальной сортировки, которая из-за частых промахов кэшей упирается в латентность случайного доступа контроллера DRAM.

Далее: tier-1a bitonic, tier-0 VirtualBox.

ParallelSort: Testing method

Тестируемые сортировки выполняются по возрастанию над массивами чисел с плавающей запятой двойной точности (double, 64-bit). Размер массива составляет 225 элементов или 256Мб. Размер, равный степени двойки, выбран для того, чтобы не усложнять реализацию битонической сортировки, простой вариант которой требует равный степени двойки размер сортируемой коллекции. Остальные алгоритмы этого не требуют. Размер массива в 256Мб достаточно велик, чтобы даже одна восьмая его не помещалась в L3 кэш распространённых x86 процессоров, при этом он достаточно мал, чтобы позволить себе хранить несколько таких массивов в RAM, и при этом система с 2+ Гб RAM «не уходила в своп«, а под 32-битной ОС процессу хватало адресного пространства (Windows address space limits).

Входные последовательности

Сортируемый массив заполняется 12-ю способами. Псевдослучайные величины генерируются с помощью вихря Мерсенна и инициализируются текущим системным временем.

  1. «uniform 1» равномерное на [-1, 1] распределение.
  2. «uniform 2» равномерное на [0, 1e150] распределение.
  3. «normal 1» нормальное распределение с μ = 0, σ = 1.
  4. «normal 2» нормальное распределение с μ = 1e150, σ = 1e150.
  5. «lognormal» логнормальное распределение с μ = 0, σ = 0,5.
  6. «Cauchy» распределение Коши.
  7. «Weibull» распределение Вейбулла с k = 0,5, λ = 1.
  8. «sorted» заранее отсортированная последовательность (изначально uniform 1).
  9. «sorted/desc» заранее отсортированная по убыванию последовательность (изначально uniform 1).
  10. «sorted/blocks» последовательность из отсортированных последовательностей-«блоков» (размера порядка sqrt (N), где N – размер исходной последовательности, сгенерированной как uniform 1).
  11. «sine» синусоида (полученная копированием sqrt (N) выборок).
  12. «chaotic» «хаотическая» постепенно возрастающая последовательность, полученная по формуле a[n] = sqrt (sqrt (n)) * modf (13 * sqrt (modf (51 * sqrt (modf (107 * sqrt (n)))))).

Каждый замер (комбинация алгоритма и вида входной последовательности) производится 10 раз, в качестве результата приводится арифметическое среднее. Замер производится таймером микросекундной точности. Для упрощения сравнения приводятся минимальный, максимальный результат и геометрическое среднее («gmean») результатов по всем входным последовательностям.

Перед собственно замерами производится «прогрев»: один прогон std::sort для каждого варианта входной последовательности. После каждой сортировки производится автоматическая проверка корректности.

Congestion

Кроме собственно сортировки заданного набора выполняется оценка того, насколько сам принцип работы алгоритма (в первую очередь, характер обращений к RAM) может помешать эффективному распараллеливанию. Для этого исходный массив разбивается на равные части по числу логических ядер ЦП, замеряется максимальное время сортировки одной части в однопоточном режиме Tmax, затем замеряется время одновременной сортировки всех частей (каждому логическому ядру назначается своя часть) Tpar. Конечный результат получается по формуле congestion = (TparTmax) / Tmax.

Таким образом, если congestion равно 0, распараллеливание идеальное, если равно 1 на 4-ядернике, то получается эффективность до 50% (ускорение вдвое при загрузке всех четырёх ядер против одного). Естественно, эта метрика вычисляется только для однопоточных алгоритмов. Её результаты несравнимы между ЦП с разным числом ядер.

Компиляция и тестовые системы

Компилятор Microsoft Visual C++ 2010 SP1 x64 (в 64-битный код), опции: /O2 /Oi /GL /Gm- /EHsc /GS- /Gy /fp:fast /openmp /Gd /MD. Тесты прогонялись на двух системах с ОС Windows 7 x64:

  1. «Deneb» AMD Phenom II x4 955 3.2GHz / 2GHz uncore, 2x 2Gb DDR3-1333 (4 ядра).
  2. «Arrandale» Intel Celeron U3400 1.07GHz, 4Gb DDR3-800 (2 ядра).

Далее: tier-0.

ParallelSort: Intro

Этим постом я открываю серию постов, посвящённых исследованию возможностей распараллеливания ряда алгоритмов сортировки. Одновременно планируется исследовать применимость некоторых средств SMT распараллеливания, доступных для языка C++, в связи с чем (механизм задействования параллелизма) алгоритмы сортировки разделены на три группы («tiers») плюс эталонная однопоточная группа «стандартных сортировок»:

  1. Алгоритмы стандартной библиотеки C++: std::sort, std::stable_sort, пирамидальная heap sort (std::make_heap + std::sort_heap).
  2. Алгоритмы, распараллеливание которых может быть эффективно осуществлено путём параллельного исполнения независимых итераций циклов for: битоническая bitonic sort (нерекурсивный вариант), блочная bucket sort (базовый размер блока, соизмеримый с L2 кэшем ядра), поразрядная radix sort (базовый вариант использует 4-битные разряды).
  3. Рекурсивные алгоритмы с параллельным исполнением ветвей рекурсии: слияниями merge sort, быстрая quick sort, рекурсивный вариант битонической сортировки rbitonic sort.
  4. Алгоритмы, разные стадии которых могут исполняться параллельно, т.е. удобно выполнить конвейеризацию: расчёской comb sort.

Далее: методика тестирования.