Файл: Алгоритмы сортировки данных (Алгоритмы сортировки).pdf

2.4. Способы построения параллельной программы

Наиболее распространённым языком программирования в области HPC- систем являются языки Си и С++ [7]. В рамках реализации компонента будет использована модель с общей памятью. Модель передачи сообщений должна быть использована для более высокоуровневых компонент системы, разработка которых является предметом дальнейшей работы.

Существует несколько способов создания многопоточных программ, реализуемые компиляторами [18, 19]. В рамках модели с общей памятью среди них следует выделить следующие:

• ФреймворкIntel Threading Building Blocks [0]
• Расширение OpenMP [1]
• Расширение Intel Cilk Plus [2]
• Расширение OpenACC [2]
• Средства языка С++ (std: :thread) [4]
• Использование потоков операционной системы PThreads[5]

Выбор фреймворка обуславливается требованиями к реализации поставленной задачи [2].

Стандарт OpenACCиспользуется для гетерогенного программирования, то есть программирования с использованием центрального и графического процессоров. В настоящей работе не рассматривается возможность использования графических процессоров в решении задачи, поэтому предпочтение отдаётся другим расширениям и фреймворкам.

Использование встроенных средств распараллеливания, предоставляемых языком С++ или операционной системой, позволяет реализовывать специфичные низкоуровневые задачи. Реализация компараторов и процедур сортировки не относится к таким задачам.

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

IntelTBB- мощная библиотека шаблонов разработки программного обеспечения для многопроцессорных систем. Фреймворк содержит различные структуры данных и ряд алгоритмов, использование которых позволяет избежать работы с низкоуровневыми интерфейсами и синхронизацией потоков. Однако использование IntelTBBзатрудняет разработку последовательной программы, которую легче отлаживать и изменять - в отличие от расширений OpenMPи IntelCilkPlus, которые позволяют преобразовать последовательную программу в параллельную без существенных изменений в логике работы программы.

Таким образом, среди описанных способов создания параллельных программ, с учётом особенностей решаемой задачи, выбрано расширение OpenMP, поддерживаемое компиляторами GCC (GNUCompilerCollection) и ICC (IntelC++ Compiler).

Заключение

По результатам замеров производительности методов можно сделать следующие выводы:

Наиболее универсальным методом, является метод быстрой сортировки («QuickSort»), он показывает стабильно высокие результаты на любых размерах массивов. На втором месте находится метод Шелла. Его использование может быть обосновано большее простым алгоритмом с точки зрения программиста.

Метод вставки эффективен, при условии большого времени выполнения операций перестановки, так как он является абсолютным лидером по количеству перестановок, проигрывая при этом по количеству сравнений.

При использовании небольших массивов данных нет большой разницы по скорости между методами сортировки, поэтому целесообразнее применять метод Пузырька или метод вставок.

Исследование проводилось на массивах с большой степенью неупорядоченности. Для массивов, которые уже являются почти отсортированными, наиболее применим метод сортировки вставками.

Список литературы

1. Вирт Н. Алгоритмы и структуры данных; [не указано] - М., 2010. - 449 c.

2. Вирт Н. Алгоритмы+структуры данных=программы; [не указано] - М., 2016. - 678 c.

3. Дмитриева, Марина JavaScript. Быстрый старт; СПб: БХВ - М., 2014. - 328 c.

4. Дональд Э. Кнут Искусство программирования. Том 3. Сортировка и поиск; Вильямс - М., 2012. - 824 c.

5. Кишик, А. Flash 5.0 Быстро, просто, наглядно; СПб: ДиаСофт - М., 2010. - 240 c.

6. Кнут Д.Э. Искусство программирования (Том 1. Основные алгоритмы); [не указано] - М., 2013. - 303 c.

7. Кнут Д.Э. Искусство программирования (Том 2. Получисленные алгоритмы); [не указано] - М., 2009. - 383 c.

8. Лорин Г. Сортировка и системы сортировки; Главная редакция физико-математической литературы издательства "Наука" - М., 2010. - 384 c.

9. Мюллер, К. Der schnelle, gelbe Aubus/Быстрый желтый автобус; GDR - М., 2015. - 281 c.

10. Рассел Джесси Сортировка вставками; Книга по Требованию - М., 2012. - 120 c.

11. Свами М., Тхуласираман К. Графы, сети и алгоритмы; [не указано] - М., 2013. - 948 c.

12. Симмонс, Курт Mac OS X Головная боль. Типичные и нетипичные проблемы и быстрые рецепты избавления; Вершина - М., 2013. - 416 c.

Приложение

Блок схемы

Обменная сортировка