Асинхронный алгоритм сортировки массива чисел с использованием ингибиторных сетей Петри
Ключевые слова:
алгоритмы сортировки, пузырьковая сортировка, сети Петри, асинхронность, параллельные вычисленияАннотация
В настоящее время задачи ускорения вычислений и/или их оптимизация является достаточно актуальной задачей. Среди направлений решения вышеприведенной задачи в статье рассматривается применение подхода распараллеливания и асинхронизации алгоритма сортировки. Предлагается метод сортировки, основанный на принципе разбиения всего массива на множество независимых пар чисел и их параллельное и асинхронное сравнение, что отличает предлагаемый алгоритм от традиционных алгоритмов сортировки (таких как быстрая сортировка, сортировка слиянием, вставками и другие). Алгоритм реализован с использованием сетей Петри как наиболее подходящего инструмента для описания асинхронных систем, а также приведен пример его работы. В статье выполнена оценка быстродействия алгоритма для наилучшего и наихудших случаев. В наилучшем случае алгоритм выполняется за 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.
Asynchronous Sorting Algorithm for Array of Numbers With the use of Inhibitory Petri Nets
Abstract
Currently the tasks of computations speed-up and/or their optimization are actual ones. Among the ways to solve these tasks is a method of parallelization and asynchroniza-tion of a sorting algorithm, which is considered in the article. We offer a sorting method that is based on the principle of dividing an array into a set of independent pairs of numbers and their parallel and asynchronous comparison, which distinguishes the offered method from the traditional sorting algorithms (like quick sorting, merge sorting, insertion sorting and others). The algorithm is realized with the use of Petri nets as the most suitable tool for describing asynchronous systems. Examples of its work are given. The performance of the algorithm is evaluated for the best and the worst cases. In the best case the algorithm is executed for 2 or 3 conditional tacks depending on an array partition into the pairs of adjacent elements. In the worst case –for n or 3n/2, where n is the number of elements. Parallelization and asynchronization principles, used during the algorithm construction, can also be used for different algorithms.
Опубликован
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).
