В настоящей работе рассматриваются вопросы низкоуровневого моделирования движения городского транспорта. Традиционными средствами в этой области являются клеточные автоматы [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. 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