Аннотация
Задача объединения двух массивов элементов с одновременной их сортировкой и удалением повторяющихся элементов является одной из фундаментальных задач в компьютерных науках и часто встречается как часть других алгоритмов. В данной работе рассматривается алгоритм ее решения для параллельного и асинхронного случая. Из-за наличия параллельности и асинхронности для решения поставленной задачи был выбран инструмент сетей Петри как наиболее подходящий. Для решения поставленной задачи используется бинарное дерево поиска (binarysearchtree), адаптированное для выполнения параллельной операции вставки элементов. Свойства построения бинарного дерева поиска, а именно то, что левый элемент должен быть меньше, чем родительский, а правый – больше родительского, позволяют ему выполнять сортировку при добавлении очередного элемента. Операция удаления повторяющихся элементов реализуется путем сравнения добавляемого элемента со сравниваемым, и в случае совпадения их значений выполняется уничтожающий элемент переход. Таким образом, решение поставленной задачи сводится к добавлению элементов в бинарное дерево поиска. Полученный алгоритм позволяет одновременно выполнять операции над любым количеством массивов любой длины. В приведенном в работе примере для краткости показана сеть Петри, реализующая бинарное дерево поиска на три элемента, но она может быть легко расширена путем увеличения повторяющейся структуры элементов до требуемого количества элементов. Для моделирования Петри использовался программный пакет моделирования CPN (ColoredPetriNets) Toolsv 4.0.1, с помощью которого была показана корректность работы полученной сети.
Ключевые слова: сети Петри, алгоритмы, параллельность, асинхронность, объединение массивов, бинарное дерево поиска, ингибиторные сети Петри, оценка алгоритмов
Список литературы
1. Wilkinson B., Allen M. Parallel programming: techniques and applications using networked workstations and parallel computers. – 2nd ed. – Upper Saddle River, NJ: Pearson/Prentice Hall, 2005. – 431 p.
2. Kirk D.B., Hwu W.W. Programming massively parallel processors: a hands-on approach. – 2nd ed. – Burlington, MA: Morgan Kaufmann, 2012. – 496 p.
3. Малышкин В.Э., Корнеев В.Д. Параллельное программирование мультикомпьютеров. – Новосибирск: Изд-во НГТУ, 2011. – 296 с.
4. Introduction to algorithms / T. Cormen, C. Leiserson, R. Rivest, C. Stein. – 3rd ed. – Cambridge: The MIT Press, 2009. – 1328 p.
5. Fast parallel sorting algorithms on GPUs / B. Jan, B. Montrucchio, C. Ragusa, F.G. Khan, O. Khan // International Journal of Distributed and Parallel Systems. – 2012. – Vol. 3 (6). – P. 107–118.
6. AA-Sort: a new parallel sorting algorithm for multi-core SIMD processors / H. Inoue, T. Moriyama, H. Komatsu, T. Nakatani // Proceedings of 16th International Conference on Parallel Architecture and Compilation Techniques (PACT 2007), Brasov, Romania, 15–19 September 2007. – Los Alamitos, CA: IEEE, 2007. – P. 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). – P. 903–917.
8. Haykin S. Neural networks and learning machines. – 3rd ed. – New York: Prentice Hall/Pearson, 2009. – 938 p.
9. Воевода А.А., Полубинский В.Л., Романников Д.О. Сортировка массива целых чисел с использованием нейронной сети // Научный Вестник НГТУ. – 2016. – № 2 (63). – С. 151–157.
10. Коротиков С.В., Саркенов Д.О. Применение спецификации эквивалентности в моделировании сеанса связи таксофона и центра дистанционного контроля и управления таксофонами раскрашенной сетью Петри // Сборник научных трудов НГТУ. – 2007. – № 3 (49). – С. 97–104.
11. Марков А.В. Автоматизация проектирования и анализа программного обеспечения с использованием языка UML и сетей Петри: дис. … канд. техн. наук. – Новосибирск, 2015. – 176 c.
12. Воевода А.А., Марков А.В., Романников Д.О. Разработка программного обеспечения: проектирование с использованием UML диаграмм и сетей Петри на примере АСУ ТП водонапорной станции // Труды СПИИРАН. – 2014. – Вып. 3 (34). – C. 218–232.
13. Марков А.В. Поиск манипулятором кратчайшего пути в лабиринте // Сборник научных трудов НГТУ. – 2011. – № 4 (66). – С. 75–90.
14. Марков А.В., Воевода А.А. Развитие системы «Перемещение манипулятора в пространстве с препятствиями» при помощи рекурсивных функций // Автоматика и программная инженерия. – 2013. – № 2 (4). – С. 35–41.
15. Марков А.В. Свойства инверсии сетей Петри // Сборник научных трудов НГТУ. – 2014. – № 4 (78). – С. 139–152.
