Удосконалення паралельного сортування масивів чисел методом злиття

Ключові слова: потоковий граф; паралельне сортування; метод злиття; алгоритми сортування; попарне порівняння; масив даних; графічний процесор

Анотація

Удосконалено метод сортування злиттям способом просторового розпаралелення процесу сортування, яке зведено до одночасного отримання елементів зростаючого та спадаючого масивів. Визначено та розглянуто такі основні етапи розроблення потокового графу для паралельного сортування масивів даних з використанням удосконаленого методу злиття, як декомпозиція алгоритму сортування масиву із m×N чисел, проектування комунікацій між функціональними операторами, укрупнення функціональних операторів, планування процесу сортування масиву із m×N чисел. Розроблено орієнтований на архітектуру графічного процесора конкретизований потоковий граф паралельного сортування масивів даних з використанням удосконаленого методу сортування злиттям. Запропоновано розробку програмних засобів паралельного сортування масивів даних з використанням удосконаленого методу злиття виконувати на основі комплексного підходу, який охоплює: дослідження, розроблення та вдосконалення алгоритмів і методів паралельного сортування масивів даних; потокові графи алгоритмів паралельного сортування; архітектуру графічного процесора GPU та програмну модель CUDA. Показано, що попри необхідність розроблення додаткових програм для внутрішніх операцій, а саме: створення тимчасових масивів для зберігання проміжних результатів, ядра програми, циклів виконання ядра програми у потоках та блоках, бінарного пошуку, присвоєння ключів записав на фінальній стадії порівняння двох масивів і формування вихідного відсортованого масиву, реалізація на графічному процесорі паралельного сортування масивів даних з використанням удосконаленого методу злиття, забезпечує значне зменшення часу сортування порівняно з використанням тільки центрального процесора.

Біографії авторів

І. Г. Цмоць, Національний університет "Львівська політехніка", м. Львів

д-р техн. наук, професор, кафедра автоматизованих систем управління

В. Я. Антонів, Національний університет "Львівська політехніка", м. Львів

аспірант, кафедри автоматизованих систем управління

Посилання

Боресков, А. В. и др. (2012). Параллельные вычисления на GPU. Архитектура и программная модель CUDA. Москва: Изд-во Московского университета, 336 с.

Воеводин, В. В., Воеводин, Вл. В. (2002). Параллельные вычисления. СПб.: Изд. дом БХВ-Петербург, 608 с.

Гергель, В. П. (2010). Высокопроизводительные вычисления для многопроцессорных многоядерных систем. Москва: Изд-во Московского университета, 544 с.

Иванов, К. К., Раздобудько, С. А., Ковалев, Р. И. (2017). Параллельные методы сортировки. Текст: непосредственный, электронный. Молодой ученый, 7(141), 15–16.

Кнут, Д. (2000). Искусство программирования, том 3: Сортировка и поиск, 2-е изд. Москва: Изд-во Наука, 832 с.

Кормен T., Лейзерсон, Ч., Ривест, Р. (2004). Алгоритмы: построение и анализ: пер. с англ., под ред. А. Шеня. Москва: Изд-во МЦНМО, БИНОМ. Лаборатория знаний, 960 c.

Левитин, Ананий. (2006). Алгоритмы: введение в разработку и анализ.: пер. с англ. Москва: Изд. дом "Вильямс", 576 с.

Лунин, Д. В., Скворцов, С. В. (2014). Организация параллельных вычислений на платформе CUDA. Вестник Рязанского государственного радиотехнического университета, 49, 77–82.

Мельничук, А. С., Луценко, С. П., Громовий, Д. С., Трофимова, К. В. (2013). Аналіз методів сортування масиву чисел. Технологический аудит и резервы производства, 4/1(12), 37–40.

Немнюгин, С. А., Стесик, О. Л. (2002). Параллельное программирование для многопроцессорных систем. СПб.: Изд. дом БХВ-Петербург, 400 с.

Седжвик, Роберт. (2002). Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: пер. с англ. СПб.: ООО "ДиаСофтЮП", 688 с.

Цмоць, І. Г, Кісь, Я. П., Антонів, В. Я. (2015). Застосування графічного процесора для підвищення швидкодії процесу сортування великих масивів даних. Scientific Bulletin of UNFU, 25(6), 328–334. Retrieved from: https://nv.nltu.edu.ua/index.php/journal/article/view/973

Gryciuk, Y., & Grytsyuk, P. (2016). Implementation details for the cipher key generation Cardano permutation. Modern Problems of Radio Engineering, Telecommunications and Computer Science. Proceedings of the 13th International Conference on TCSET 2016, pp. 498–502. https://doi.org/10.1109/TCSET.2016.7452098

Hrytsiuk, Yu., & Bilas, O. (2019). Visualization of Software Quality Expert Assessment. IEEE 2019 14th International Scientific and Technical Conference on Computer Sciences and Information Technologies (CSIT 2019), (Vol. 2, pp. 156–160), 17–20 September, 2019.

https://doi.org/10.1109/stc-csit.2019.8929778

Hrytsiuk, Yu., Grytsyuk, P., Dyak, T., & Hrynyk, H. (2019). Software Development Risk Modeling. IEEE 2019 14th International Scientific and Technical Conference on Computer Sciences and Information Technologies (CSIT 2019), (Vol. 2, pp. 134–137), 17–20 September, 2019.

https://doi.org/10.1109/stc-csit.2019.8929778

Tsmots, I., Rabyk, V., Skorokhoda, O., & Antoniv, V. (2017). FPGA Implementation of Vertically Parallel Minimum and Maximum Values Dtermination in Array of Numbers. 14th International Conference The Experience of Desingning and Application of CAD Systems in Microelectronics, (CADSM 2017). Proceedings 7916123, pp. 234–236.

Tsmots, I., Skorokhoda, O., & Rabyk, V. (2016). Structure Software Model of a Parallel-Vertical Multi-input Adder for FPGA Implementation. Computer Sciences and Information Technologies. Proceedings of 11th International Scientific and Technical Conference (CSIT). Lviv, pp. 158-160.

Tsmots, I., Skorokhoda, O., Antoniv, V., & Rabyk, V. (2018). Vertically-paraller method and VLSI-structure sorting of one-dimension alarrays. Proceedings of 13th International Scientific and Technical Conference (CSIT). Lviv, pp. 112–116.

Опубліковано
2020-09-17
Як цитувати
Цмоць, І. Г., & Антонів, В. Я. (2020). Удосконалення паралельного сортування масивів чисел методом злиття. Науковий вісник НЛТУ України, 30(4), 134-142. https://doi.org/10.36930/40300422
Розділ
Інформаційні технології

Статті цього автора (авторів), які найбільше читають