=Paper=
{{Paper
|id=Vol-1482/594
|storemode=property
|title=Параллельная реализация расширенных сетей Петри в задаче низкоуровневого моделирования дорожного движения
(Parallel implementation of extended Petri nets in the low-level modeling of traffic)
|pdfUrl=https://ceur-ws.org/Vol-1482/594.pdf
|volume=Vol-1482
}}
==Параллельная реализация расширенных сетей Петри в задаче низкоуровневого моделирования дорожного движения
(Parallel implementation of extended Petri nets in the low-level modeling of traffic)==
https://ceur-ws.org/Vol-1482/594.pdf
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
Параллельная реализация расширенных сетей Петри в
задаче низкоуровневого моделирования дорожного движения*
Н.М. Ершов
Московский государственный университет им. М.В. Ломоносова
В настоящей работе рассматриваются вопросы низкоуровневого моделирования движения
городского транспорта. Традиционными средствами в этой области являются клеточные авто-
маты [1] и сети Петри [2]. В данной работе в качестве инструмента моделирования были вы-
браны сети Петри, т.к. их графовая структура является более адекватным средством представ-
ления сети дорог. При этом места сети Петри представляют собой участки дорог, по которым
перемещаются метки-машины, а ее переходы отвечают за логику движения машин. Предло-
женная модель поддерживает различные типы дорожных элементов (источники и стоки, слия-
ния, разветвления, светофоры, пешеходные переходы и т.д.) и позволяет моделировать, в том
числе, и скоростные характеристики движения транспорта.
С одной стороны, низкоуровневое моделирование требует выполнения больших объемов
вычислений, с другой – такие модели, как правило, обладают высокой степенью параллелизма
и могут быть эффективно реализованы на параллельных вычислительных системах. В данной
работе рассматривается способ крупноблочного распараллеливания, основанный на простран-
ственной декомпозиции сети Петри, когда вся сеть делится на отдельные подсети, каждая из
которых обрабатывается отдельным процессором. При этом для перемещения машины из од-
ной подсети в другую требуется взаимодействие соответствующих процессоров.
Рассматривается следующая схема разделения сети: каждый переход сети оказывается
принадлежащим ровно одной подсети; если входной и выходной переходы данного места при-
надлежат одной подсети, то это место помещается в эту же подсеть, в противном случае, дан-
ное место дублируется в каждой из двух соответствующих подсетей. Каждый процессор полу-
чает только свою часть общей сети Петри и детальный план синхронизации со своими соседя-
ми. Все планы синхронизации составляются таким образом, чтобы гарантировать бескон-
фликтное взаимодействие процессоров системы. Проблемным местом в такой схеме оказывает-
ся разделение сети Петри на заданное число частей, которое сводится к задаче поиска опти-
мального разбиения графа сети на несколько подграфов одинакового размера с минимизацией
числа разрезаемых ребер. Эта оптимизационная задача решается с помощью иерархического
подхода к выравниванию нагрузки, описанного в работе [3]. Приводятся результаты численно-
го исследования предложенной схемы распараллеливания.
Литература
1. S. P. Hoogendoorn, P. H. L. Bovy "State-of-the-art of vehicular traffic flow modelling" // J. Syst.
Cont. Eng., 2001, 215(4), pp. 283-303.
2. Mariagrazia Dotoli, Maria Pia Fanti "An urban traffic network model via coloured timed Petri
nets" // Control Engineering Practice, Volume 14, Issue 10, October 2006, Pages 1213-1229.
3. Ершов Н. Задача распределения нагрузки при параллельной реализации расширенных сетей
Петри в задаче микроскопического моделирования дорожного движения // Научный сервис
в сети Интернет: Труды Международной суперкомпьютерной конференции (22-27 сентября
2014 г., г. Новороссийск). — Изд-во МГУ, Москва, 2014. — С. 66–70.
*
Работа выполнена при финансовой поддержке РФФИ (грант №14-07-00628 А).
594
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
Parallel implementation of extended Petri nets in the low-level
modeling of traffic
Nikolay Ershov
Keywords: Petri nets, urban traffic simulation, graph partitioning, coarse-grained parallelism
This paper is devoted the problem of the microscopic simulation of urban road traffic by
using extended Petri nets. The relevance of the microscopic approach to the modeling of road
traffic is determined by the extensive development of parallel programming systems. This
paper discusses the issues of coarse-grained parallel implementation of Petri nets on
multiprocessor computer systems using MPI technology. This work was supported by RFBR
(grant №14-07-00628 A).