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.

Реклама

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: