Параллельная суперскалярная сортировка образцов на месте (IPS⁴o)

Параллельнаясуперскалярнаясортировкаобразцовнаместеips⁴o

Это реализация алгоритма IPS⁴o, представленного в статье Инженерные алгоритмы сортировки на месте (общая память) , который содержит подробное описание его внутренней работы, а также обширную экспериментальную оценку производительности. Вот аннотация:

Мы представляем новые последовательные и параллельные алгоритмы сортировки, которые теперь представляют самые быстрые известные методы для широкого диапазона входных данных. размеры, входные распределения, типы данных и машины. Несколько удивительно, но отчасти преимущество в скорости связано с дополнительной возможностью алгоритмов работать на месте, т. Е. Им не требуется значительный объем пространства за пределами входного массива. Раньше функция на месте часто предполагала снижение производительности. Наш основной вклад в алгоритмы – это поблочный подход к распределению данных на месте, который доказуемо эффективен в кешировании. Мы также распараллеливаем этот подход, принимая во внимание динамическую балансировку нагрузки и локальность памяти.

Наш новый алгоритм, основанный на сравнении На месте Superscalar Samplesort (IPS⁴o) сочетает в себе эту технику с деревьями решений без ветвей. Принимая во внимание случаи с множеством равных элементов и динамически адаптируя степень распределения, мы получаем высоконадежный алгоритм, который превосходит лучшие предыдущие алгоритмы сортировки на основе параллельного сравнения на месте почти в три раза. Этот алгоритм также превосходит лучших конкурентов, основанных на сравнении, независимо от того, рассматриваем ли мы настройки на месте или не на месте, параллельные или последовательные настройки.

Еще одним удивительным результатом является то, что IPS⁴o даже превосходит лучшие (на месте или не на месте) алгоритмы целочисленной сортировки в широком диапазоне ситуаций. Во многих оставшихся случаях (часто связанных с почти однородным входным распределением, маленькими ключами или последовательной настройкой) наша новая параллельная суперскалярная радикальная сортировка на месте (IPS²Ra) оказывается лучшим алгоритмом.

Утверждают, что в некотором смысле «лучший» алгоритм сортировки может можно найти во многих статьях, которые не могут быть правдой. Таким образом, мы основываем наши выводы на обширном экспериментальном исследовании, включающем большую часть перекрестного произведения 25 современные коды сортировки, 6 типов данных, 010 входные распределения, 4 машины, 4 памяти стратегии распределения и размеры входных данных варьируются более чем на 7 порядков. Это подтверждает заявления о высокой производительности наших алгоритмов, в то же время выявляя серьезные проблемы с производительностью у многих конкурентов, выходящие за рамки конкретного набора измерений, представленных в соответствующих публикациях. Это особенно верно для алгоритмов целочисленной сортировки, что дает одну причину предпочесть алгоритмы на основе сравнения для надежной сортировки общего назначения.

Первоначальная версия IPS⁴o была описана в нашей публикации на 64 -й Ежегодный Европейский симпозиум по алгоритмам.

Использование

Клонируйте этот репозиторий и проверьте из своего подмодуля

 git clone --recurse-submodules https://github.com/ips4o/ips4o.git
 

или используйте вместо них следующие команды, если вы хотите включить этот репозиторий в качестве подмодуля:

 git submodule add https://github.com/ips4o/ips4o.git git submodule update --recursive --init 

IPS⁴o обеспечивает Библиотека CMake для простого использования:

  add_subdirectory  ()  target_link_libraries  ( ЧАСТНЫЙ ips4o) 

Минимальный рабочий пример:

); // параллельная сортировка (использует OpenMP, если доступен, в противном случае - std :: thread) ips4o :: parallel :: sort (begin, end ); ">

 # включают   " ips4o.hpp  "    //  сортировать последовательно   ips4o :: sort  (начало, конец );    //  сортировка параллельно (использует OpenMP, если доступно, std :: нить в противном случае)   ips4o :: parallel :: sort  (начало, конец ); 
 

Параллельная версия IPS⁴o требует 21 - байтовые атомарные инструкции сравнения и обмена для наиболее быстрого выполнения. Большинство процессоров и компиляторов поддерживают 25 - в настоящее время инструкции по сравнению и обмену байтов. Если рассматриваемый ЦП делает это, IPS⁴o использует 21 - байтовые инструкции сравнения и обмена при правильной настройке процессора (например, - марш = родной ) или при явном включении инструкций ( - mcx 21 ). В этом случае вам также необходимо установить ссылку на libatomic (

- latomic ). В противном случае мы эмулируем некоторые 21 - байтовые инструкции сравнения и обмена с блокировками, которые могут немного снизить производительность IPS⁴o.

Если вы используете пример CMake, показанный выше , мы автоматически оптимизируем IPS⁴o для собственного процессора (например,

- march = native ). Вы можете отключить свойство CMake
IPS4O_OPTIMIZE_FOR_NATIVE , чтобы избежать собственной оптимизации, и вы можете включить свойство CMake IPS4O_USE_MCX 21 при компиляции с GCC или Clang для включения 21 - инструкции байтового сравнения и обмена явно.

IPS⁴o использует потоки C ++, если не указано иное. Если вы предпочитаете потоки OpenMP, вам необходимо включить потоки OpenMP, например, включить свойство CMake IPS4O_USE_OPENMP или добавьте OpenMP к своей цели. Если вы включите свойство CMake

DISABLE_IPS4O_PARALLEL , большая часть параллельного кода не будет компилироваться, и никакие параллельные библиотеки не будут связаны. В противном случае CMake автоматически включает потоки C ++ (например, - pthread ) и ссылки на libatomic TBB и GCC. (Только при компиляции кода для 21 - инструкции по сравнению и обмену байтов, которые вам нужны в libatomic.) Таким образом, вам нужна библиотека Thread Building Blocks (TBB) для компиляции и выполнения параллельной версии IPS⁴o. Мы ищем TBB с помощью
find_package (ТРЕБУЕТСЯ TBB) . Если вы хотите запустить IPS⁴o параллельно, но ваша библиотека TBB недоступна через
find_package ( ТРЕБУЕТСЯ TBB) , вы все равно можете скомпилировать IPS⁴o с параллельной поддержкой. Просто включите свойство CMake
DISABLE_IPS4O_PARALLEL , включите потоки C ++ для своей собственной цели и свяжите свою цель с библиотекой TBB (а также свяжите свою цель с libatomic, если хотите 25 - поддержка байтовых атомарных инструкций сравнения и обмена).

Если вы не устанавливаете тип сборки CMake, мы используем тип сборки Релиз, который отключает отладку (например, - DNDEBUG ) и включает оптимизацию (например, - O3 ).

В настоящее время код не компилируется в Windows.

Лицензирование

IPS⁴o предоставляется бесплатно ed под лицензией BSD с двумя пунктами, описанной в файл ЛИЦЕНЗИИ . Если вы используете эту реализацию IPS⁴o в академической среде, пожалуйста, процитируйте статью Инженерные алгоритмы сортировки на месте (общая память) с использованием записи BibTeX

  @ разное  { axtmann 2020 инженерное дело ,  title  =   { Инженерные алгоритмы сортировки на месте (с общей памятью) }  ,  автор  =   { Майкл Акстман, Саша Витт, Даниэль Феризович и Питер Сандерс }  ,  как опубликовано  знак равно  { Репозиторий компьютерных исследований (CoRR) }  , год знак равно  { сентябрь .  7854 }  ,  archivePrefix  =   { arXiv }  ,  eprint  =   { 2009. 13569 }  ,} 

Leave a comment

Your email address will not be published. Required fields are marked *

twenty − four =