Асинхронный алгоритм сортировки массива чисел с использованием ингибиторных сетей Петри
Ключевые слова:
алгоритмы сортировки, пузырьковая сортировка, сети Петри, асинхронность, параллельные вычисленияАннотация
В настоящее время задачи ускорения вычислений и/или их оптимизация является достаточно актуальной задачей. Среди направлений решения вышеприведенной задачи в статье рассматривается применение подхода распараллеливания и асинхронизации алгоритма сортировки. Предлагается метод сортировки, основанный на принципе разбиения всего массива на множество независимых пар чисел и их параллельное и асинхронное сравнение, что отличает предлагаемый алгоритм от традиционных алгоритмов сортировки (таких как быстрая сортировка, сортировка слиянием, вставками и другие). Алгоритм реализован с использованием сетей Петри как наиболее подходящего инструмента для описания асинхронных систем, а также приведен пример его работы. В статье выполнена оценка быстродействия алгоритма для наилучшего и наихудших случаев. В наилучшем случае алгоритм выполняется за 2 или 3 условных такта в зависимости от разбиения массива на пары соседних элементов. В наихудшем случае – за n или за 3n/2, где n – число элементов. Принципы распараллеливания и асинхронизации, использованные при построении алгоритма, также могут быть применены для других алгоритмов.Литература
1. Wilkinson B., Allen M. Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers (2nd Edition) // Pearson Education. 2005. 431 p.
2. Kirk D.B., Hwu W.W. Programming Massively Parallel Processors, Second Edition: A Hands-on Approach // Morgan Kaufmann. 2012. 496 p.
3. Малышкин В. Э., Корнеев В. Д. Параллельное программирование мультикомпьютеров // Издательство НГТУ. 2011. 296 с.
4. Cormen T., Leiserson C., Rivest R., Stein C. Introduction to Algorithms: 3rd Edition // The MIT Press. 2009. 1328 p.
5. Jan B., Montrucchio B., Ragusa C., Khan F. G., Khan O. Fast parallel sorting algorithms on GPUs // International Journal of Distributed and Parallel Systems (IJDPS). 2012. pp. 107‒118.
6. Inoue H., Moriyama T., Komatsu H., Nakatani T. AA-Sort: A New Parallel Sorting Algorithm for Multi-Core SIMD Processors // Proceedings on 16th International Conference on Parallel Architecture and Compilation Techniques (PACT 2007). 2007. pp. 189‒198.
7. Capannini, G., Silvestri F., Baraglia R. Sorting on GPUs for large scale datasets: A thorough comparison // Information Processing and Management. 2011. vol. 48(5). pp. 903–917.
8. Haykin S. Neural Networks and Learning Machines, 3rd Edition // Pearson Education. 2009. 938 p.
9. Graves A. Wayne G., Danihelka I. Neural Turing Machines // The Computing Research Repository 1410. 5401. 2014. pp. 1–24.
10. Воевода А.А., Полубинский В. Л., Романников Д.О. Сортировка массива целых чисел с использованием нейронной сети // Научный Вестник НГТУ. 2016. №2(63). С. 151–157.
11. Коротиков С.В., Саркенов Д.О. Применение спецификации эквивалентности в моделировании сеанса связи таксофона и центра дистанционного контроля и управления таксофонами раскрашенной сетью Петри // Сб. науч. тр. НГТУ. 2007. № 3 (49). С. 97–104.
12. Марков А.В. Автоматизация проектирования и анализа программного обеспечения с использованием языка UML и сетей Петри: дисс. канд. техн. наук // Новосибирск. 2015. 176 c.
13. Воевода А.А., Марков А.В., Романников Д.О. Разработка программного обеспечения: проектирование с использованием UML диаграмм и сетей Петри на примере АСУ ТП водонапорной станции // Труды СПИИРАН. 2014. №3(34). C. 218–232.
14. Марков А.В. Поиск манипулятором кратчайшего пути в лабиринте // Сб. науч. тр. НГТУ. 2011. №4(66). С. 75–90.
15. Марков А.В., Воевода А.А. Развитие системы “Перемещение манипулятора в пространстве с препятствиями” при помощи рекурсивных функций // Автоматика и программная инженерия. №2(4). 2013. С. 35–41.
16. Марков А.В. Свойства инверсии сетей Петри // Сб. науч. тр. НГТУ. 2014. №4(78). С. 139–152.
2. Kirk D.B., Hwu W.W. Programming Massively Parallel Processors, Second Edition: A Hands-on Approach // Morgan Kaufmann. 2012. 496 p.
3. Малышкин В. Э., Корнеев В. Д. Параллельное программирование мультикомпьютеров // Издательство НГТУ. 2011. 296 с.
4. Cormen T., Leiserson C., Rivest R., Stein C. Introduction to Algorithms: 3rd Edition // The MIT Press. 2009. 1328 p.
5. Jan B., Montrucchio B., Ragusa C., Khan F. G., Khan O. Fast parallel sorting algorithms on GPUs // International Journal of Distributed and Parallel Systems (IJDPS). 2012. pp. 107‒118.
6. Inoue H., Moriyama T., Komatsu H., Nakatani T. AA-Sort: A New Parallel Sorting Algorithm for Multi-Core SIMD Processors // Proceedings on 16th International Conference on Parallel Architecture and Compilation Techniques (PACT 2007). 2007. pp. 189‒198.
7. Capannini, G., Silvestri F., Baraglia R. Sorting on GPUs for large scale datasets: A thorough comparison // Information Processing and Management. 2011. vol. 48(5). pp. 903–917.
8. Haykin S. Neural Networks and Learning Machines, 3rd Edition // Pearson Education. 2009. 938 p.
9. Graves A. Wayne G., Danihelka I. Neural Turing Machines // The Computing Research Repository 1410. 5401. 2014. pp. 1–24.
10. Воевода А.А., Полубинский В. Л., Романников Д.О. Сортировка массива целых чисел с использованием нейронной сети // Научный Вестник НГТУ. 2016. №2(63). С. 151–157.
11. Коротиков С.В., Саркенов Д.О. Применение спецификации эквивалентности в моделировании сеанса связи таксофона и центра дистанционного контроля и управления таксофонами раскрашенной сетью Петри // Сб. науч. тр. НГТУ. 2007. № 3 (49). С. 97–104.
12. Марков А.В. Автоматизация проектирования и анализа программного обеспечения с использованием языка UML и сетей Петри: дисс. канд. техн. наук // Новосибирск. 2015. 176 c.
13. Воевода А.А., Марков А.В., Романников Д.О. Разработка программного обеспечения: проектирование с использованием UML диаграмм и сетей Петри на примере АСУ ТП водонапорной станции // Труды СПИИРАН. 2014. №3(34). C. 218–232.
14. Марков А.В. Поиск манипулятором кратчайшего пути в лабиринте // Сб. науч. тр. НГТУ. 2011. №4(66). С. 75–90.
15. Марков А.В., Воевода А.А. Развитие системы “Перемещение манипулятора в пространстве с препятствиями” при помощи рекурсивных функций // Автоматика и программная инженерия. №2(4). 2013. С. 35–41.
16. Марков А.В. Свойства инверсии сетей Петри // Сб. науч. тр. НГТУ. 2014. №4(78). С. 139–152.
Опубликован
2016-10-10
Как цитировать
Воевода, А. А., & Романников, Д. О. (2016). Асинхронный алгоритм сортировки массива чисел с использованием ингибиторных сетей Петри. Труды СПИИРАН, 5(48), 198-213. https://doi.org/10.15622/sp.48.10
Раздел
Алгоритмы и программные средства
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
